연관 컨테이너
- 특정 정렬 규칙에 의해 저장 원소가 컨테이너에 정렬 됨
- Set, Map, MultiSet, MultiMap 의 종류
- 균형 이진 트리 및 노드 기반으로 구현됨
Set 컨테이너
- Set 컨테이너는 연관 컨테이너 중 단순한 컨테이너로 key라 불리는 원소(value)의 집합으로 이뤄진 컨테이너
Set의 템플릿 형식
template<typename Key, typename Pred = less<Key>, typename Allocator = std::allocator<Key> >
class Set- Pred는 정렬 기준 조건자로 기본 조건자가 less(<)
Set의 인터페이스
생성자
set s : 기본 생성자, 즉 빈 컨테이너
set s(pred) : 정렬기준을 pred로 정렬한 빈 컨테이너
set s(s2) : s2를 복사한 s(복사 생성자 호출)
set s(b,e) : s는 반복자 구간 [b, e)로 초기화 된 원소를 가짐
set s(b,e,pred) : s는 반복자 구간 [b, e)로 초기화 된 원소를 가지며 pred로 정렬됨멤버 함수
p = s.begin() : p는 s의 첫 원소를 가리키는 반복자(const, 비 const버전)
s.clear() : s의 모든 원소를 제거
n = s.count(k) : 원소 k의 개수를 반환
s.empty() : s가 비었는지 조사(bool 타입)
p = s.end() : p는 s의 끝 원소를 가리키는 반복자(const, 비 const버전)
pr = s.equal_range(k) : pr은 k 원소의 반복자 구간인 pair객체(const, 비 const버전)
q = s.erase(p) : p가 가리키는 원소를 제거, q는 다음 원소를 가리킴
q = s.erase(b, e) : 반복자 구간 [b, e)를 제거, q는 다음 원소를 가리킴
n = s.erase(k) : k 원소를 모두 제거, n은 제거한 개수
p = s.find(k) : k 원소의 위치를 가리키는 반복자 p(const, 비 const버전)
pr = s.insert(k) : s컨테이너에 k를 삽입, pr은 삽입한 원소를 가리키는 반복자와 성공여부의 bool값을 가지고 있는 pair객체
q = s.insert(p, k) : s컨테이너에 p가 가리키는 위치에 k값을 삽입, q는 삽입한 원소를 가리키는 반복자
s.insert(b, e) : s컨테이너에 반복자구간 [b, e)를 삽입
pred = s.key_comp() : pred는 s의 key 정렬 기준인 조건자(key_compare타입)
p = s.lower_bound(k) : p는 k의 시작 구간을 가리키는 반복자(const, 비 const버전)
n = s.max_size() : n은 s가 담을 수 있는 최대 원소의 개수(메모리의 크기)
p = s.rbegin() : p는 역 순차열의 첫 원소를 가리키는 반복자(const, 비 const버전)
p = s.rend() : p는 역 순차열의 끝 원소를 가리키는 반복자(const, 비 const버전)
s.size() : s컨테이너의 원소의 개수
s.swap(s2) : s 와 s2를 swap
p = s.upper_bound(k) : p는 k의 끝 구간을 가리키는 반복자(const, 비 const버전)
pred = s.value_comp() : pred는 s의 value정렬 기준인 조건자(value_compare타입)연산자
전부 bool타입 반환
s1 == s2 : s1이 s2와 같은가
s1 != s2 : s1이 s2와 다른가
s1 < s2 : s1이 s2보다 작은가
s1 <= s2 : s1이 s2보다 작거나 같은가
s1 > s2 : s1이 s2보다 큰가
s1 >= s2 : s1이 s2보다 크거나 같은가Set의 템플릿 멤버 형식
allocator_type : 메모리 관리자 형식
const_iterator : const 반복자
const_pointer : const 포인터
const_reference : const 참조자
const_reverse_iterator : const 역 반복자
difference_type : 두 반복자 차이(std::ptrdiff_t)
iterator : 반복자
key_compare : 키 조건자 비교 형식(set은 key가 value이므로 value_compare과 같음)
key_type : 키의 형식(set은 key가 value이므로 value_typer과 같음)
pointer : 포인터
reference : 참조자
reverse_iterator : 역 반복자
size_type : 첨자니 원소의 개수등의 형식(size_t or difference_type)
value_compare : 원소 조건자(비교) 형식
value_type : 원소의 형식Set의 특징
-
Set의 구조는 아래의 그림과 같음
-
원소를 저장하는 유일한 멤버함수 insert를 제공, 이 때 자동으로 정렬되는데 기본은 less이므로 순차적으로 정렬이 됨
-
이로 인해 시퀸스 컨테이너에서 제공하는 insert이외에 변수를 집어넣는게 없음
-
set은 모든 원소(key)가 유일하므로 원소의 중복이 없음
-
중복을 허용하고자 한다면 Multiset을 사용해야함
-
찾기 연산시, 균형 이진트리를 사용하므로 시간복잡도가 O(logN)이다.
-
find함수에서 find(k)를 사용한다고 했을 때, 찾는 방식이 k == value를 찾는것이 아닌, comp가 less이기 때문에 다르게 찾는다. 아래가 찾는 방식이다.
s.find(k)
-> (!s.key_comp()(30, 50) && (!s.key_comp()(50,30))
*이런식으로 동작을 한다고 생각해야한다!!!!*MultiSet 컨테이너
- set과 기본적으로 동일하나, 중복을 허용한다는 것 외에는 다른 점이 없음
- 중복을 허용하기 때문에 insert함수가 저장 위치와 성공여부를 반환하는 것이 아닌, pair객체 저장된 위치를 가리키는 반복자만 반환
- 중복이 허용되었기 때문에, find에서 동일한 첫 원소의 위치를 반환
Map 컨테이너
- 원소를 key, value를 쌍(pair객체)으로 저장
Map의 템플릿 형식
template < typename Key, typename Value, typename Pred = std::less<Key>, typename Allocator = std::allocator<pair <const Key, Value>> >
class Map- key 와 value를 쌍(pair)로 가지며, pred는 정렬기준 조건자로 기본 정렬기준은 less(<)이다.
Map의 인터페이스
- 기본적으로 Set과 동일한 인터페이스를 가지고 있음
- 다른점으로 연산자[]를 가지고 있음
Map의 연산자
m[k] = v : m컨테이너에 원소 (k,v)를 추가하거나 key에 해당하는 원소의 value를 v로 갱신Map의 템플릿 멤버 형식
allocator_type : 메모리 관리자 형식
const_iterator : const 반복자
const_pointer : const 포인터
const_reference : const 참조자
const_reverse_iterator : const 역 반복자
difference_type : 두 반복자 차이의 형식(ptrdiff_t)
iterator : 반복자
key_compare : 키 조건자 형식
key_type : 키의 형식
mapped_type : 값의 형식
pointer : value_type* 형식
reference : value_type& 형식
reverse_iterator : 역 반복자 형식
size_type : 첨자나 원소의 개수 등의 형식(size_t)
value_type : 원소의 형식Map의 특징
-
Map의 구조
-
set과 동일하게 중복을 허용하지 않음, 중복을 허용하고자 한다면 Multimap을 사용해야함
-
value는 중복되어도 되나, key는 중복이 되면 안됨!!
-
기본정렬 시, key값을 기준으로 less정렬 됨
-
set과 동일하게 찾기 연산 시, O(logN)을 가짐
-
map은 set과 다르게 []연산이 가능하며, 원소를 추가하거나 변경하는 기능을 가진 연산자[]
MultiMap 컨테이너
- 기본적으로 Map과 동일하나, 중복을 허용함(key의 중복)
