[C++] STL #2 연관 컨테이너 (associate container) [set & multiset, map & multimap]
목차
가-B. 연관 컨테이너 (associate container)
- key와 같은 특정 정렬 기준(연관)에 따라 원소를 정렬하는 컨테이너
- 정렬 기준에 따라 정렬이 되므로 특정 위치를 지정한 접근 및 참조가 불가능 하다.
- 노드 기반 컨테이너이다.
- 균형 이진트리로 구성되어 있다.
- 찾기 연산이 매우 빠르다. (균형 이진트리 때문)
1. std::set & std::mulitset
- set은 원소 자체가 key가 되어 분류된 균형 이진 트리이다.
- key는 유일해야 하며 key == 원소 이므로 데이터의 중복이 허용되지 않는다.
ㄴ mulitset에서는 키의 중복을 허용한다. (key의 중복허용을 제외한 다른 요소는 동일)
- 삽입 되며 자동으로 정렬이 된다. (기본 : 오름차순)
가. 선언 및 초기화
template<typename T> //template ≒ 자유 자료형
std::set<T> //T : 배열에 담길 자료형
// pred(predicate : 조건자)
- set<int> s1 // 빈 셋 생성
- set<double> s2(pred) // pred를 기준으로 정렬하는 빈 셋 생성
- char sample[] = { 'a', 'b', 'c' };
set<char> s3(begin(sample), end(sample)); // 다른 배열의 값을 사용해 초기화 가능
- string sample2[] = { "one", "two", "three" };
set<string> s4(begin(sample2), end(sample2), pred);
// 다른 배열의 값을 사용해 초기화, 정렬 기준은 pred 조건자를 사용한다. (pred 생략시 오름차순 정렬)
- set<char> s5(s3) // s3를 복사하여 s5 셋 생성
나. 멤버 함수 ( ※ 기준 : int sample[] = { 1, 2, 3, 4, 5 }; set<int> s(begin(sample), end(sample); )
| Iterators(반복자) | |
| s.begin() | 첫 번째 위치를 가리킨다. (예시 기준 1) |
| s.end() | 마지막 위치의 다음을 가리킨다. (예시 기준 5) |
| s.rbegin() | 역순으로 뒤집고 첫 번째 위치를 가리킨다. (예시 기준 5) |
| s.rend() | 역순으로 뒤집고 마지막 위치의 다음을 가리킨다. (예시 기준 1) |
| ※ s.cbegin(), s.cend(), s.crbegin(), s.crend()는 (앞에 c가 붙은 멤버 함수)는 위와 같은 역할을 하지만 const가 적용되어 수정이 불가능 하다. |
|
| Capacity(용량) | |
| s.empty() | set s가 비어있는지 확인하고 bool 값 반환 |
| s.size() | set s의 크기를 반환한다. |
| s.max_size() | set s가 담을 수 있는 최대 크기를 반환 (셋 컨테이너가 가질 수 있는 가장 큰 수를 반환한다) |
| Modifiers(수식어) | |
| s.clear() | set s의 모든 요소를 지운다. |
| s.insert(K) | K를 삽입한다, 삽입시 자동으로 정렬된 위치에 삽입된다. |
| s.emplace(K) s.emplace_hint(iterator, K) |
insert와 같은 역할. 결과는 같으나 생성 과정이 다름. emplace_hint 는 지정된 위치에 삽입이지만 자동 정렬이 되므로 위치 지정의 의미가 없다. |
| s.erase (iterator, iterator) |
iterator에서 iterator 전 까지의 원소를 삭제한다. (ex. auto target = s.begin(); advance(target, 2); s.erase(s.begin(), target); ) |
| s.swap(s2) | s와 s2의 인자를 교환한다. |
| Lookup(조회) |
|
| s.count(K) | key 값이 K인 요소의 수 반환. |
| s.find(K) | key 값이 K인 요소의 iterator 반환, 없을 시 s.end()를 반환한다. Lookup - find 예시 참조 |
| s.equal_range(K) | key 값이 K인 요소의 iterator 범위 반환. ( first로 시작 범위, second로 마지막 범위 다음 위치) Lookup - equal_range 예시 참조 |
| s.lower_bound(K) | 주어진 key 값 보다 작지 않은 첫번째 요소의 iterator 반환 |
| s.upper_bound(K) | 주어진 key 값 보다 큰 첫번째 요소의 iterator 반환 |
2. std::map & multimap
- 각 노드가 key와 value 쌍으로 이루어진 균형 이진 트리이다.
- first, second 두 요소로 구성된 pair 객체로 first = key, sencond = value 이다.
- key는 중복이 허용되지 않지만 value는 중복이 허용된다.
ㄴ multimap 에서는 중복 key를 허용한다. (key의 중복허용을 제외한 다른 요소는 동일)
- 삽입 되며 자동으로 정렬이 된다. (기본 : 오름차순)
가. 선언 및 초기화
template<typename T>
std::map<T(key), T(value)>
pred(predicate : 조건자)
- map<int, string> m1; // 빈 맵 생성
- map<int, double, pred> m2 // pred을 기준으로 정렬하는 맵 생성
- map<int, char> m3 = { // 생성과 동시에 초기화
{ 1, 'a' },
{ 5, 'b' },
{ 3, 'c' },
{ 8, 'd' },
};
- map<int, char> m4(m3.begin(), m3.end()); // m3를 복사하여 m4 맵 생성
나. 멤버 함수 ( ※ 기준 : map<int, string> m = { { 1,"Arial" }, { 3, "Angella" }, { 4, "Peter" }, { 2, "Beatrice" }, }; )
| Element access(요소 접근) | |
| m.at(K) | K를 key 값으로 지닌 value를 반환한다. |
| m[K] | K를 key 값으로 지닌 value를 반환한다. |
| Iterators(반복자) | |
| m.begin() | 첫 번째 위치를 가리킨다. (예시 기준 { 1,"Arial" }) |
| m.end() | 마지막 위치의 다음을 가리킨다. (예시 기준 { 4, "Peter" }) |
| m.rbegin() | 역순으로 뒤집고 첫 번째 위치를 가리킨다. (예시 기준 { 4, "Peter" }) |
| m.rend() | 역순으로 뒤집고 마지막 위치의 다음을 가리킨다. (예시 기준 { 1,"Arial" }) |
| ※ m.cbegin(), m.cend(), m.crbegin(), m.crend()는 (앞에 c가 붙은 멤버 함수)는 위와 같은 역할을 하지만 const가 적용되어 수정이 불가능 하다. |
|
| Capacity(용량) | |
| m.empty() | map m이 비어있는지 확인하고 bool 값 반환 |
| m.size() | map m의 크기를 반환한다. |
| m.max_size() | map m가 담을 수 있는 최대 크기를 반환 (맵 컨테이너가 가질 수 있는 가장 큰 수를 반환한다) |
| Modifiers(수식어) | |
| m.clear() | map m의 모든 요소를 지운다. |
| m.insert( {K, V} ) | key-value 쌍을 가진 {K,V}를 삽입한다, 삽입시 자동으로 정렬된 위치에 삽입된다. modifiers - insert, emplace, emplace_hint 예시 참조 |
| m.emplace({K, V}) m.emplace_hint(iterator, {K, V}) |
insert와 같은 역할. 결과는 같으나 생성 과정이 다름. emplace_hint 는 지정된 위치에 삽입이지만 자동 정렬이 되므로 위치 지정의 의미가 없다. |
| m.erase (iterator, iterator) |
iterator에서 iterator 전 까지의 원소를 삭제한다. (ex. auto target = m.begin(); advance(target, 2); m.erase(m.begin(), target); ) => m = { { 3, "Angella" }, { 4, "Peter" } }; |
| m.swap(m2) | m와 m2의 인자를 교환한다. |
| Lookup(조회) | |
| s.count(K) | key 값이 K인 요소의 수 반환. |
| s.find(K) | key 값이 K인 요소의 iterator 반환, 없을 시 s.end()를 반환한다. |
| s.equal_range(K) | key 값이 K인 요소의 iterator 범위 반환. ( first로 시작 범위, second로 마지막 범위 다음 위치) |
| s.lower_bound(K) | 주어진 key 값 보다 작지 않은 첫번째 요소의 iterator 반환 |
| s.upper_bound(K) | 주어진 key 값 보다 큰 첫번째 요소의 iterator 반환 |
※ 참조
c++ reference : https://en.cppreference.com/