Associative Container

연관 컨테이너

연관 컨테이너는 시퀀스 컨테이너(예. vector, list, deque 등)과 다르게 key-value 구조를 갖는다. 연관 컨테이너의 종류는 다음과 같다. 이 중 unordered_*은 C++11부터 추가된 컨테이너이다.

Container	Definition	Sort by Key	Internal Implementation	Time Complexity (검색, 삽입, 삭제)	Header
set	고유한 키의 집합	O	R-B 트리	O(logN)	<set>
map	키-값의 집합, 고유한 키	O	R-B 트리	O(logN)	<map>
multiset	키의 집합	O	R-B 트리	O(logN)	<set>
multimap	키-값의 집합	O	R-B 트리	O(logN)	<map>
unordered_set	고유한 키의 집합	X	해시 테이블	O(1)	<unordered_set>
unordered_map	키-값의 집합, 고유한 키	X	해시 테이블	O(1)	<unordered_map>
unordered_multiset	키의 집합	X	해시 테이블	O(1)	<unordered_set>
unordered_multimap	키-값의 집합	X	해시 테이블	O(1)	<unordered_map>

 

연관 컨테이너의 원소 접근

연관 컨테이너는 임의의 원소에 바로 접근할 수 없고, 다음과 같이 순차적으로 접근해야 한다.

set<int> s;
for(int i=5; i>0; i--) s.insert(i);

// for(int i=0; i<5; i++) cout << s[i] << ' ';  (WRONG!!!)

for(auto itr=s.begin(); itr!=s.end(); itr++) cout << *itr << ' ';
cout << '\n';

for(auto& key: s) cout << key << ' ';

 

그렇지만, std::next(), std::advance()를 사용하면 원하는 위치의 iterator를 알아낼 수 있다. std::next(itr, n)은 itr에서 n만큼 떨어진 iterator를 반환한다. std::advance(itr, n)은 itr을 n만큼 떨어진 iterator로 업데이트한다.

// cout << s[3]; (WRONG!!!)

cout << *next(s.begin(), 3) << '\n';

auto itr = s.begin();
advance(itr, 3);
cout << *itr << '\n';

 

std::prev(itr, n)은 itr에서 n만큼 앞선 iterator를 반환한다.

cout << *prev(s.end(), 1) << '\n'; // 마지막 원소 출력

 

map의 원소 추가

기본적으로 연관 컨테이너에 원소를 추가할 때엔 inset() 메소드를 사용한다. map은 [] 연산자를 사용해 원소를 추가할 수도 있다. 이때 주어진 key를 갖는 원소가 이미 존재한다면, value가 새로 주어진 값으로 대체된다.

set<int> s;
s.insert(1);

map<int, float> m;
m.insert({1, 3.14});
m[2] = 1.64;
m[2] = 2.27; // update (2, 1.64) into (2, 2.27)