: 키(Key) - 값(Value) 구조를 가지며, 특정 키를 넣으면 이에 대응되는 값을 돌려줌
❓ 특정 키가 연관 컨테이너에 존재하는가 ❓
=> set / multiset 사용
❔ 특정 키에 대응되는 값이 무엇인가 ❔
=> map / multimap 사용
❓ map <-> multimap / set <-> multiset ❓
: key값을 중복으로 사용할 수 있는가 아닌가의 차이
❔ map <-> unordered_map / set <-> unordered_set ❔
: unordered는 값을 정렬시키지 않는다. (중복이 허용되지 않는건 같음)
따라서 값을 더 빠르게 찾음
📌 unordered MultiMap도 있음 -> 중복 허용, 정렬X, 이걸로 Dictionary를 만들 수 있음.
Set
- 원소를 추가할 때 insert 함수 사용하며 추가/삭제에 O(logN)시간 소요
- 셋도 저장되어 있는 원소들에게 접근하기 위해서 반복자(BidirectionalIterator) 제공
(임의의 위치에 있는 원소에 접근하는건 불가능, 순차적으로 하나씩 접근한다) - find 함수로 원소개 존재하는지 아닌지 확인. 존재하지 않으면 .end()를 반환
- 원소 존재여부 확인에 O(logN)의 시간 소요 -> 이유는 내부적으로 트리 구조로 구성되어 있음
( Red-black Tree : https://en.wikipedia.org/wiki/Red%E2%80%93black_tree )
Map
- key와 함께 그에 대응 되는 값을 저장 (기본적으로 set보다 메모리가 큼)
- 맵에 insert 함수 이용해서 추가하는데 반드시 pair객체로 전달해야 함
- pair 사용시 반드시 데이터 타입을 적어줘야 하는데 make_pair 사용하면 알아서 추측해줌
- operatr[]를 이용해서 새로운 원소 추가도 가능하다 (중복X)
- 반복자를 이용해서 순차적으로 맵에 저장되어 있는 원소 탐색 가능.
Multimap
- 원소의 중복을 허용함
- find(key) 사용 못함. []연산자 자체를 제공하지 않음
- 따라서 equal_range 함수를 제공한다. 이 함수는 인자로 멀티맵의 키를 받고 이 키에 대응되는 원소들의 반복자들 중에서 시작과 끝 바로 다음을 가리키는 반복자를 pair 객체러 만들어서 리턴
즉, begin()과 end()를 pair로 만들어서 세트로 리턴. 다만 first로 시작점, second로 end()=끝점 바로 뒤를 가리키는 반복자 리턴
Unordered_set, Unordered_map
- insert, erase, find가 전부 수행시간 O(1)을 가짐
- 새로운 함수가 insert되면 해시함수를 통해서 어떤 상자에 들어갈지 결정됨 (해시 충돌 일어날 수 있음) -> (해시 관련해선 https://velog.io/@acodeam/%ED%95%B4%EC%8B%B1-Hashing 보기)
- Unordered 친구들의 해시함수는 1부터 n(=상자의 수)까지의 값을 반환하고 그 해시값(같은 원소면 같은 값 반환)을 원소를 저장할 상자의 번호로 삼음 -> 모든 상자를 고루고루 사용
- 처음부터 많은 개수의 상자를 사용할 순 없으니(메모리 낭비 때문에) 상자의 개수는 삽입되는 원소가 많아짐에 따라 점진적으로 늘어남. 상자의 개수가 늘어나면 해시 함수를 바꿔야 하기 때문에 (더 많은 값을 해시 값으로 반환하도록) 모든 원소들을 처음부터 끝까지 다시 insert -> rehash (시간: O(N))
- 직접 넣으려면 "해시 함수"를 직접 만들어줘야 함 -> 순서대로 정렬하지 않아서 operator< 는 필요하지 않지만 operator==는 필요
- 해시 함수를 직접 제작하는 일은 어렵다. 제대로 성능을 발휘하기 위해서는 해시 함수가 입력 받은 키를 잘 흝뿌려야 하기 때문. 만약 해시 함수 결과가 특정 범위 값에만 집중되어 있으면 map이나 set보다 훨씬 못함. 기본 타입들에 대한 해시 함수 (https://en.cppreference.com/w/cpp/utility/hash) 를 사용하거나 map / set 사용하자
배움기록