다양한 연관 컨테이너에 대해 알아보자.
multiset, multimap 컨테이너
- 헤더 < set > 과 < map > 에 각각 저장되어 있다.
- 노드 기반으로 이루어져 균형 이진 트리 구조 로써 set 과 map과 멤버 함수가 동일합니다.
- 기존 set과 map과의 다른점은 key값의 중복을 허용한다는 점입니다.
multiset 예제
- 값의 중복을 허용 하는 것을 볼 수 있다.
#include <iostream>
#include <set>
typedef std::multiset<int>::iterator It; // aliasing the iterator type used
int main ()
{
int myints[]= {77,30,16,2,30,30};
std::multiset<int> mymultiset (myints, myints+6); // 2 16 30 30 30 77
std::pair<It,It> ret = mymultiset.equal_range(30); // ^ ^
mymultiset.erase(ret.first,ret.second);
std::cout << "mymultiset contains:";
for (It it=mymultiset.begin(); it!=mymultiset.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
Outputs
multiset contains: 2 16 77
multimap 예제
- key 값의 중복을 허용 하며 모든 값을 출력하는 것을 볼 수 있다.
// multimap::equal_range
#include <iostream>
#include <map>
int main ()
{
std::multimap<char,int> mymm;
mymm.insert(std::pair<char,int>('a',10));
mymm.insert(std::pair<char,int>('b',20));
mymm.insert(std::pair<char,int>('b',30));
mymm.insert(std::pair<char,int>('b',40));
mymm.insert(std::pair<char,int>('c',50));
mymm.insert(std::pair<char,int>('c',60));
mymm.insert(std::pair<char,int>('d',60));
std::cout << "mymm contains:\n";
for (char ch='a'; ch<='d'; ch++)
{
std::pair <std::multimap<char,int>::iterator, std::multimap<char,int>::iterator> ret;
ret = mymm.equal_range(ch);
std::cout << ch << " =>";
for (std::multimap<char,int>::iterator it=ret.first; it!=ret.second; ++it)
std::cout << ' ' << it->second;
std::cout << '\n';
}
return 0;
}
Outputs
mymm contains:
a => 10
b => 20 30 40
c => 50 60
d => 60
unordered_set, unordered_map 컨테이너
- 컨테이너 이름에서 알 수 있듯이 원소들이 정렬되어 있지 않다.
- set이나 map의 경우 순서대로 정렬되어 내부에 저장되어 지지만 unordered 경우는 그렇지 않다.
unordered_set 예제
- 다음코드에서 보는 것 처럼 특정 순서없이 출력된다.
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
int main() {
unordered_set<string> s;
s.insert("inhyeok");
s.insert("korea");
s.insert("tiger");
s.insert("hello");
s.insert("yundu");
s.insert("test");
s.insert("test");
for (const auto& elem : s) {
std::cout << elem << std::endl;
}
}
Outputs:
hello
tiger
yundu
korea
test
inhyeok
해시 함수(Hash Function)
- 사실 unordered set과 map은 해시 함수를 사용한다.
- 해시 함수를 사용하기 때문에 insert, erase, find 모두 O(1)로 수행 가능하다. (set과 map 은 O(logN) 임)
내가 만든 클래스를 unordered_set, unordered_map 의 원소로 넣고 싶을때
- 객체를 위한 해시함수 를 직접 만들어 줘야함으로 상당히 까다롭다.
- 진짜 필요한게 아니면 그냥 set과 map을 사용하는 걸 권장함.
반복자
- 기존 set과 map과는 다르게 reverse 를 사용할 수 없다. (ex rbegin, rend)
Buckets, Hash policy
- 위에서 말한 해시 함수를 사용하기 때문에 버켓값들과 해시에 대한 함수로 다음과 같은 기능을 제공.
- bucket의 수를 리턴하는 bucket_count
- 컨테이너가 보유할 수 있는 최대 버킷의 수를 리턴하는 max_bucket_count
- bucket의 사이즈를 리턴하는 bucket_size
- 값이 어느 버킷에 위치하는지 리턴해주는 bucket
- size / bucket_count 로 컨테이너 요수의 수의 비율을 나타내는 load_factor()
- load factor의 값을 변경하는 max_load_factor(float z) -> default 는 1.0
- rehash(size) -> 해시 테이블의 재구성 size > 현재 버킷 수 이면 강제로 rehash 하며 새 버킷 수는 n보다 크거나 같을 수 있다. size < 현재 버킷 수 이면 영향을 미치지 않음. 컨테이너의 모든 요소는 해시 값에따라 새로운 버킷 세트로 재배열 된다. O(N) 소요
결론 (어떤 상황에서 쓰면 좋을지)
- 데이터의 존재 유무 만 궁금할 거면 set을 사용하자.
- 중복 데이터를 허락 할 경우 multiset을 사용하자.
- 데이터에 대응되는 데이터를 저장하고 싶은 경우 map을 사용하자.
- 중복 키를 허락할 경우 multimap을 사용하자.
- 속도가 매우 중요해서 최적화를 해야 하는 경우 unordered_set , unordered_map 을 사용하자.
자세한 내용은 아래의 레퍼런스 참조 하세용
click reference site
Comments