데브코스 자율주행_TIL_23.09.21

오늘 배운 내용

1. C++     - Template 2. STL     - 비교 알고리즘     - 변경 알고리즘     - 집합 알고리즘     - 연관 컨테이너     - 비순차 연관 컨테이너 3. Linux     - vim editor

1. C++

- Template

템플릿은 C++의 일반화된 코드를 남기는 강력한 도구.

대상에 대한 타입만 다르고 로직이 다르지 않다면 템플릿으로 단순한 반복 작업으로 함수나 클래스를 만들 수 있다.

기본적인 구조는 다음과 같다. T는 아직 정해지지 않은 타입이며 컴파일시 타입을 추론한다.

template<typename T>
class Samlple {
	Sample(const Sample<T>& src) = default; //const Sample<T>&는 파라미터 타입의 예시
	//...
};

//함수 템플릿
template<typename T>
void f(const T& param); //const T&는 파라미터 타입의 예시

템플릿의 예시

#include <iostream>

using namespace std;

template <typename T>
T sum(T a, T b){ // T는 아직 정해지지 않은 type
    return a + b;
}

int main(){
    int a = 3, b = 5;
    cout << a + b << "\n"; // 8

    double c = 3.2, d = 5.1;
    cout << c + d << "\n"; // 8.3
    return 0;
}

템플릿 클래스나 템플릿 함수가 인스턴스화 되는 시점에 컴파일러는 그 구현부를 볼 수 있어야 하므로 템플릿의 정의는 헤더 파일에 들어가야한다. 관례적으로 이렇게 템플릿 정의가 포함된 헤더파일의 확장자를 hpp로 사용한다.

_C++_Template

 

2. STL(Standard Template Library)

- 비교 알고리즘

항목열 간 비교를 하기 위해 사용되는 알고리즘으로 equal, mismatch, lexicographical_compare이 있다.

equal, mismatch

- 첫 컨테이너에 대해 두 개의 반복자를 필요로하며 두 번째 컨테이너에 대해서는 끝 반복자를 선택적으로 받는다.

- 두 번째 컨테이너의 시작 반복자만 제공한 경우에는 첫 번째 항목열의 크기만큼만 비교 (비교 알고리즘을 커스텀 할 수 있으며 비교 알고리즘 대신 operator를 사용할 수 있음.)

- equal()

두 항목열이 완전히 같으면 true를 리턴한다.

 

- mismatch()

항목열을 서로 비교하다가 불일치가 처음 발생하는 위치의 반복자를 리턴한다.

이 때, pair로 리턴된다.

- first: 첫 번째 항복열에 대한 반복자

- second: 두 번째 항목열에 대한 반복자.

 

- lexicographical_compare()

두 항목열을 사전순으로 비교한다.

- 첫 번째 항목열이 사전순으로 앞서는 경우: true

- 그렇지 않는 경우: false

이때 기본적으로 대소문자를 구분하고 대문자가 소문자보다 사전순으로 앞서는 것으로 취급한다.

 

---

- 변경 알고리즘

- copy(), copy_n()

copy함수는 특정 범위의 항목들을 다른 범위로 차례로 복제한다.

copy_n함수는 원본 범위를 반복자 쌍이 아닌, 시작반복자와 개수를 인자로 넘겨서 복제한다.

만약 원본 범위에서 특정 조건에 해당하는 항목만 사용하고 싶다면, copy_if함수를 사용하면 된다.

 

- move()

move함수는 두가지 버전이 있다.

1. 입력: 하나의 임의의 타입을 갖는 인자를 받음, 출력: 우측값으로 캐스팅해줌.
2. 입력: 세개의 반복자를 받음. 출력: 항목열 전체 또는 항목열 일부를 다른 컨테이너로 옮김.

 

- remove(), remove_if()

remove와 remove_if는 함수를 삭제하는 것이 아닌 주어진 범위에 대해 삭제할 항목과 남겨둘 항목끼리 옮겨서 나누는 역할을 한다.

vector와 배열과 같이 연속한 메모리 구조를 유지해야하는 경우 바로 삭제하는 것이 비효율적이기 때문이다.

remove: 값을 인자로 넘겨 동일한 값을 가지는 항목을 삭제할 항목으로 분류.

remove_if:  bool을 리턴하는 함수 객체 등을 인자로 받아 삭제할 항목의 조건을 커스텀할 수 있게 해줌.

 

- replace(), replace_if()

replace: 특정 값을 새로운 값으로 교체.

replace_if: 특정 조건에 맞는 항목을 새로운 값으로 교체.

find와 다르게 모든 항목을 찾아주기 때문에 찾아 바꾸기를 한다면 해당 함수를 사용하는게 좋다.

 

- unique()

주어진 항목내에서 연속적으로 중복되는 값을 제거.

remove처럼 중복되는 값을 뒤쪽으로 모아서 따로 분리하고 중복 항목이 시작하는 위치를 가르키는 반복자를 리턴한다.

연속적으로 중복된 값만 처리하므로, 이산적인 컨테이너를 sort로 정렬하고 사용해야한다.

 

- reverse()

주어진 항목열을 반전시켜주는 함수, 단순히 역방향의 순회를 목적으로 사용한다면, 해당 함수를 권장하지 않는다.

 

- next_permutation(), prev_permutation()

주어진 항목열을, 그 항목들로 생성 가능한 다음 순열 조합, 또는 이전 순열 조합으로 변환해준다.

bool타입 반환값이 있어서 순열 조합의 마지막에 도달하면, false를 반환, 그렇지 않다면 true를 반환한다.
주로 do - while()과 함께 사용한다.

 

---

- 집합 알고리즘

집합 알고리즘은 정렬된 상태의 항목열을 대상으로 사용한다.

비순차 연관 컨테이너에서는 올바르게 작동하지 않는다.

- includes()

부분 집합 여부를 판정한다

 

- set_union()

합집합을 구해 결과집합에 담아준다.

 

- set_intersection

교집합을 구해 결과 집합에 담아준다

 

- set_difference()

차집합을 구해 결과 집합에 담아준다.

 

- set_symmetric_difference()

대칭 차집합을 구해 결과 집합에 담아준다.

 

_C++_알고리즘_Part_2

 

---

- 연관 컨테이너

연관 컨테이너는 Key와 Value를 연관시켜 데이터를 관리한다.

데이터의 정렬상태를 항상 유지함. (삽입, 삭제, 룩업 성능이 모두 동일하게 로그 시간복잡도를 가짐.)

표준 연관 컨테이너는 다음과 같이 네 종류가 있다.

• set: Key 자체가 Value이며 중복 Key를 허용하지 않음.
• multiset: set처럼 Key가 Value이며 중복 Key를 허용.
• map: Key와 Value가 별개이며 중복 Key를 허용하지 않음.
• multimap: Key와 Value가 별개이며 중복 Key를 허용.

 

1. set()

헤더에 정의된 set

template <
	typename _Kty,
	typename _Pr = less<_Kty>,
	typename _Alloc = allocator<_Kty>
> class set;

첫 번째 파라미터: 항목의 타입

두 번째 파라미터: 정렬을 위한 비교 연산 타입. default value는 less템플릿(오름차순)

 

- insert

항목 삽입을 위한 매서드이다

 

- emplace

항목 생성을 위한 인자 목록을 받아 pair<iterator, bool>을 반환하는 한 가지 버전만 존재한다.

1번 버전의 insert와 유사하지만, 이동 생성 비용만큼 비용을 줄일 수 있다.

 

- emplace_hint

첫 번째 인자에 hint 반복자를 주고 이후에 항목 생성을 위한 인자 목록을 차례로 넘겨주면 된다.

올바른 힌트를 넘겨주면 상수시간에 처리되고, 그렇지 않으면 로그 시간에 처리된다.

 

- clear

전체 항목열을 비워내는 메서드 파라미터, 반환형은 없다.

- erase

1. 값을 받아서 해당 항목을 이분 탐색으로 찾아서 삭제해주는 버전
2. 반복자를 받아서 상수 시간에 삭제해주는 버전
   • 반복자 하나로 특정 위치의 항목을 삭제하는 버전
   • 반복자 쌍으로 특정 범위 내의 항목들을 일괄적으로 삭제하는 버전

- find

key를 가지고 항목을 찾아서 반환해준다. 만약 찾는 key와 일치하는 항목이 없으면 end 반복자를 반환

 

- count

key를 가지고 set에서 해당 key를 갖는 항목을 카운팅하여 반환

 

- lower_bound

찾는 key가 존재한다면 해당 항목을 가리키는 반복자를 반환, 존재하지 않는다면 key보다 작지 않은(less연산 기준) 첫 항목을 반환.

 

- upper_bound

key보다 큰(less연산 기준) 첫 항목을 반환합니다. key보다 큰 항목이 없으면 end 반복자를 반환합니다. 이 메서드는 중복을 허용하지 않는 set에서는 효용이 크지 않아 잘 쓰이지 않는다.

 

- equal_range

위의 두 메서드의 반환값들을 pair로 묶어서 반환합니다. upper_bound의 효용이 크지 않기 때문에 잘 쓰이지 않는다.

 

2. multiset()

중복을 허용하는 set으로 set과 같은 헤더에 정의되어잇으며, 동일한 템플릿 파라미터를 갖는다.

set을 사용할 줄 안다면, multiset도 쉽게 사용할 수 있다.

• insert 및 emplace가 항상 성공하기에 bool값 없이 iterator만 반환한다.
• find는 하나의 항목만 찾아주기 때문에 mutiset에서는 효용성이 떨어짐.
• lower_bound, upper_bound, equal_range를 통해 중복 항목들을 순회할 수 있는 반복자를 얻을 수 있으므로 find 대신에 이 룩업 함수들이 자주 쓰인다.

 

3. map()

map은 Key를 기준으로 정렬하여 연관된 Value들을 저장하는 컨테이너이다.

헤더의 정의는 다음과 같다.

template<
	typename _Kty, typename _Ty,
	typename _Pr = less<_Kty>,
	typename _Alloc = allocator<pair<const _Kty, _Ty>>
> class map;

비교는 Key에 대해서만 수행한다. 만약 서로 다른 두 타입을 저장하는데 어떤 타입을 Key로 하든지 상관이 없다면 비교 연산의 오버헤드가 적은 타입을 Key로 하는게 좋다.

인터페이스가 set과 유사하지만, 몇 가지 다른점이 있다.

• insert 값으로 넘겨줄 인자는 Key, Value의 pair 타입이다. 임시객체를 만들어 넘긴다면 중괄호 초기화 또는 make_pair 함수 등을 활용
• operator[]를 지원한다. []안에는 Key값이 들어가며, 해당 Key가 존재한다면 Value의 왼값을 반환하고 존재하지 않으면 자동으로 생성한 후 Value의 왼값을 반환한다. operator[]를 사용하기 위해서는 Value 타입이 디폴트 생성자를 가지고 있어야한다.또한, 항목을 자동으로 생성할 수도 있어서 const로 선언되지 않았는데 이것이 제약이 될 수 있다.

 

4. multimap()

중복 Key를 허용하는 map이다. map과 함께 헤더에 정의되어 있고 템플릿 파라미터도 같다.

몇 가지 다른점을 제외하고 인터페이스가 map과 같다.

• 키 하나에 복수의 항목이 존재할 수 있기 때문에 operator[]와 at 메서드를 지원하지 않음.
• 키 중복이 허용되기 때문에 삽입 메서드는 항상 성공함. bool값 없이 iterator만 반환.
• find역시 하나의 항목만 찾아주고 그것이 몇 번째 항목인지 알 수 없으므로 효용성이 떨어진다. multiset과 마찬가지로 lower_bound, upper_bound, equal_range 메서드를 통해 룩업을 수행한다.

 

---

- 비순차 연관 컨테이너

해시 테이블을 기반으로 연관 데이터를 관리하기 때문에 해시 테이블 컨테이너라고 부른다.

인터페이스나 기능은 연관 켄테이너와 거의 유사하지만, 해시 테이블은 데이터를 정렬하여 저장하는 방식이 아님 때문에 이들이 제공하는 반복자는 정렬된 순서가 아닌 임의의 순서

버킷의 크기를 키울 수록 해시 충돌 가능성이 줄어들어 성능이 좋아지지만 메모리 크기가 한정적이기 때문에 무한정 늘릴 수 없다. 처음부터 적절한 버킷의 수를 가지도록 세팅해주는 것이 유리하다.

 

HashTable 관련 메소드

비순차 연관 컨테이너들은 연관 컨테이너에 대응하여 네 가지가 있다.

연관 컨테이너 버전의 인터페이스를 그대로 계승하며 HashTable과 관련한 인터페이스들을 추가로 제공한다.

 

- bucket_count()

파라미터가 없는 메소드. 호출하면 해시테이블의 버킷 개수를 반환.

 

- bucket()

키를 인자로 받아 해당 키의 버킷 인덱스를 반환.

메소드 그 자체로는 의미있는 작업을 할 수 없지만, bucket_size등을 위해 선행된다.

 

- bucket_size()

버킷 인덱스를 인자로 받아 해당 버킷 안에 있는 항목의 개수를 반환.

1이 반환되면 해당 버킷에는 해시 충돌이 없다는 것을 확인할 수 있음.

 

- load_factor()

파라미터가 없는 매서드이고 버킷당 항목의 평균 개수를 float type으로 반환.

size()를 bucket_count()로 나눈 값과 같다.

 

- max_load_factor()

max_load_factor는 load_factor를 어디까지 허용하는지를 나타낸 것이다.

 

- rehash()

버킷의 수를 인자로 받아 bucket_count를 바꾸면서 재해싱한다.

load_factor가 max_load_factor를 넘게되면 bucket_count는 최소 size() / max_load_factor()로 조정된다.

 

- reserve()

max_load_factor를 초과하지 않으면서 bucket_count를 최소화하도록 재해싱한다.

 

- hash_function()

인자가 없는 메소드. 사용중인 해시함수를 반환.

 

- key_eq()

인자가 없는 메소드. Key를 비교하기 위한 비교함수를 반환.

 

해시 테이블

- unordered_set()

set의 해시 테이블 버전. 헤더에 다음과 같이 정의되어있다.

template<
    typename _Kty,
    typename _Hasher = std::hash<_Kty>,
    typename _Keyeq = std::equal_to<_Kty>,
    typename _Alloc = std::allocator<_Kty>
> class unordered_set;

set의 인터페이스 + HashTable 관련 인터페이스들을 제공.

 

- unordered_multiset()

multiset의 해시 테이블 버전. <unordered_set>헤더에 정의되어 있으며 템플릿 파라미터는 <unordered_set>과 동일.

multiset의 인터페이스 + HashTable 관련 인터페이스들을 제공.

 

- unordered_map()

map의 해시 테이블 버전. <unordered_map>헤더에 다음과 같이 정의되어 있다.

template<
    typename _Kty,
		typename _Ty,
    typename _Hasher = std::hash<_Kty>,
    typename _Keyeq = std::equal_to<_Kty>,
    typename _Alloc = std::allocator<std::pair<const _Kty, _Ty>>
> class unordered_set;

map의 인터페이스 + HashTable관련 인터페이스 제공.

 

- unordered_multimap()

multimap의 해시 테이블 버전. <unordered_map>헤더에 정의되어 있으며 템플릿 파라미터는 <unordered_map>과 동일. multimap의 인터페이스 + HashTable관련 인터페이스들을 제공.

 

_C++_연관 컨테이너_비순차 연관 컨테이너

 

---

생각보다 많은 양을 배워서 모든 것을 다 기억할 수는 없지만, 필요할 때마다 찾아서 읽을 수 있도록 정리를 하였다.

특히, 비순차 연관컨테이너 관련 부분은 코딩테스트를 준비할 때 큰 도움이 될 것 같다.

 

항상 Linux에서 vscode로 코딩을 하다보니 vim이 처음에는 생소했지만, editor로써 사용해봐도 나쁘지 않을 것 같다는 생각을 했다. 이번 기회에 익숙해지도록 하자.