C++ STL09 :: 연관 컨테이너

* 연관 컨테이너

연관 컨테이너가 시퀀스 컨테이너와 다른 점은 연관 컨테이너는 특정 정렬 규칙에 따라 저장 원소가 컨테이너에 정렬됩니다.

STL 의 표준 연관 컨테이너는 set, map, multiset, multimap 네가지의 컨테이너가 있으며 균형 이진 트리로 구분됩니다.

* set 컨테이너

set 컨테이너는 연관 컨테이너 중 단순한 컨테이너로 key라 불리는 원소의 집합으로 이루어진 컨테이너입니다.

set은 모든 원소(key)가 유일하다. 원소의 중복을 허용해야 한다면 multiset을 사용해야 합니다.

set은 같은 원소(key)를 중복 저장할 수 없으므로 insert() 멤버 함수 호출 시 반환값으로 실패를 확인할 수 있습니다.

반환값은 pair 객체이며 first 와 second는 각각 삽입된 원소(key)의 위치를 가리키는 반복자와 성공(true), 실패(false)를 나타내는 bool 값입니다.

set<int, greater<int> > ::iterator iter; //greater<int> 조건자를 사용한 반복자를 생성합니다.

* set의 주요 특징 정리

set은 대표적인 연관 컨테이너이자 노드 기반 컨테이너이다. 연관 컨테이너는 특정 정렬 기준에 의해 원소가 자동 정렬되는 컨테이너입니다. 또한 원소 찾기(검색)을 로그 시간 복잡도에 수행할 수 있도록 균형 이진 트리로 구현되며 여러 찾기 관련 함수를 제공하는것이 특징입니다.

연관 컨테이너(set, miltiset, map, miltimap)은 모두 같은 인터페이스의 멤버함수를 제공합니다.

* multiset 컨테이너 

multiset 컨테이너는 중복 원소를 컨테이너에 저장 할 수 있다는 것 외에는 set과 다른점이 없습니다.

set처럼 원소가 자동 정렬되는 연관 컨테이너에 노드 기반 컨테이너입니다.

* map 컨테이너

map 컨테이너는 연관 컨테이너 중 자주 사용하는 컨테이너로 원소를 key와 value 의 쌍으로 저장합니다.

set은 원소로 key하나만을 저장하지만, map은 원소로 key와 value의 쌍(pair 객체)을 저장한다. set처럼 원소의 key는 컨테이너에 중복 저장될 수 없으며 중복 key를 저장해야 한다면 multimap을 사용합니다.

특히, map은 [ ] 연산자를 제공하여 key에 해당 하는 원소의 value에 쉽게 접근하거나 변경할 수 있습니다.

* map의 주요 특징 정리

map은 대표적인 연관 컨테이너이자 노드 기반 컨테이너이다. 그래서 특정 정렬 기준으로 원소(key)가 자동 정렬되며 연관 컨테이너(set, multiset, map, multimap)은 모두 같은 인터페이스의 멤버함수를 제공한다. set의 원소는 key만으로 이뤄지지만 map의 원소는 key와 value의 쌍으로 이루어집니다.

마찬가지로, map 컨테이너에 중복 원소(key)를 허용해야 한다면 multimap 컨테이너를 사용한다. map은 key를 중복해서 컨테이너에 저장할 수 없지만 multimap은 여러 key를 중복해서 저장할 수 있다. 이것이 map과 다른 유일한 차이점입니다.

요약 (질문 과 질의)

Q : 시퀀스 컨테이너와 연관 컨테이너의 가장 큰 차이점 
A : 시퀀스 컨테이너는 원소의 상대적인 순서가 유지되며 연관 컨테이너는 특정 정렬 기준에 따라 원소가 결정된다. 

Q : 연관 컨테이너의 기본 정렬 기준은 무엇인가?
A : 연산자 함수 객체인 less<>이다.

Q : set에 같은 원소(key)를 저장하면 어떻게 될까?
A : set은 같은 key가 컨테이너에 존재할 수 없으므로 무시된다.

Q : multiset에 같은 원소(key)를 저장하면 어떻게 될까?
A : multiset은 같은 key가 컨테이너에 존재할 수 있으므로 정렬 기준에 따라 원소가 저장된다. 

Q : set과 map의 차이점을 쓰시오.
A : set은 컨테이너에 원소로 key만을 저장할 수 있으며, map은 컨테이너에 원소로 key와 value를 쌍으로 저장할 수 있다.

Q : 연관 컨테이너의 lower_bound()와 upper_bound()의 반환값은 무엇인가?
A : lower_bound()는 찾는 원소의 순차열 시작 반복자를 반환하며 upper_bound()는 찾는 원소의 순차열 끝 반복자를 반환한다. 원소를 찾지 못하면 모두 순차열 끝 표시 반복자를 반환한다. 

Q : 시퀀스 컨테이너의 insert()와 연관 컨테이너의 insert()의 차이점을 쓰시오.
A : 시퀀스 컨테이너는 insert()가 호출되면 가리키는 반복자의 위치에 삽입되지만 연관 컨테이너의 insert()는 특정 정렬기준에 따라 삽입 위치를 찾아 삽입된다.

Q : 연관 컨테이너의 찾기 관련 함수는 다음 중 어떤 검색 성능을 갖나요?
A : 로그 시간