set은 대표적인 연관 컨테이너이자 노드 기반 컨테이너이다. 연관 컨테이너는 특정 정렬 기준에 의해 원소가 자동 정렬되는 컨테이너이다. 또한, 원소 찾기(검색)를 로그 시간 복잡도에 수행할 수 있도록 균형 이진 트리로 구현되며 여러 찾기 관련 함수를 제공하는 것이 특징이다.
연관 컨테이너(set, multiset, map, multimap)는 모두 같은 인터페이스의 멤버 함수를 제공한다.
insert(),erase() - 삽입, 제거
count() - 원소 개수
find() - 원소 찾기
lower_bound() - 원소의 시작 구간
upper_bound() - 원소의 끝 구간
equal_range() - 원소의 구간
set은 연관 컨테이너이므로 컨테이너 앞, 뒤에 추가하거나 제거하는 멤버함수로 push_front & back(), pop_front & back() 멤버 함수를 제공하지 않는다. 또한, 첫 원소와 마지막 원소의 참조를 반환하는 front()와 back() 멤버 함수도 제공하지 않는다.
연관 컨테이너의 핵심은 빠른 원소 찾기이며 균형 이진 트리를 이용한 로그 시간 검색 복잡도를 보장한다. 찾기 관련 멤버 함수는 count(), find(), lower_bound(), upper_bound(), equal_range()가 있으며 원소를 저장하기 위해 사용되는 멤버 함수는 insert()가 유일하다
set은 key라 불리는 원소를 정렬 기준에 맞춰 균현 이진 트리에 저장하며, 이 key(원소)가 연관 컨테이너 set을 구성하는 핵심 요소로 삽입, 검색, 제거 등에 모두 이용된다. 그래서 set뿐만 아니라 모든 연관 컨테이너의 key는 변경할 수 없다.
마지막으로 연관 컨테이너는 양방향 반복자를 지원하며 멤버 함수 begin(), end(),rbegin(), rend()는 순차열의 시작과 끝을 가리키는 반복자를 반환한다.
multiset
multiset은 중복 원소를 컨테이너에 저장할 수 있다는 것 외에는 set과 다른 것이 없다.
multiset의 insert는 key가 중복 저장될수 있기 때문에 set처럼 저장 위치와 삽입 성공 여부의 bool값을 반환하는 pair 객체가 아닌 저장된 위치만을 가리키는 반복자를 반환한다.
