map, set

map

• 레드-블랙 트리(Red-Black Tree)
  ㄴ 키의 순서에 따라 자동으로 정렬된다는 것을 의미
• 삽입, 삭제, 검색 등의 연산에서 시간 복잡도는 O(log n)
• 키가 유일(unique)해야 함 (중복 허용 X)
• 삽입, 삭제 연산 시 이터레이터가 무효화될 수 있음

unordered map

• 해시 테이블(Hash Table)
• 삽입, 삭제, 검색 등의 연산에서 최악의 경우 시간 복잡도는 O(n)이지만,
  보통은 상수 시간에 해당하는 O(1)
• 중복된 키를 허용
• 이터레이터가 무효화되지 않음

unordered_map은 해시 함수를 이용해 빠른 검색이 필요하거나 중복된 데이터가 허용되는 경우에 유용.
데이터의 개수가 적을 경우에는 std::map이 std::unordered_map보다 빠를 수 있음
반대로 데이터의 개수가 많을 경우에는 std::unordered_map이 더 빠를 수 있음.

set

• 레드-블랙 트리(Red-Black Tree)
• 원소를 저장할 때 자동으로 정렬됨
• 삽입, 삭제, 검색 등의 연산에서 시간 복잡도는 O(log n)
• 각 원소가 유일(unique)해야 함
• 삽입, 삭제 연산 시 이터레이터가 무효화될 수 있음
• 각 노드에 대한 포인터와 노드 데이터를 따로 저장하기 때문에 메모리 사용량이 큼

unordered set

• 해시 테이블(Hash Table)
• 삽입, 삭제, 검색 등의 연산에서 최악의 경우 시간 복잡도는 O(n)이지만
  보통은 상수 시간에 해당하는 O(1)
• 이터레이터가 무효화되지 않음
• 버킷과 버킷 내의 요소들을 저장하기 때문에 std::set보다 적은 메모리를 사용.
  그러나 해시 함수의 충돌이 많을 경우 버킷 크기를 늘려야 하므로 메모리 사용량이 커질 수 있음.

멤버 함수

begin(): 첫 번째 원소를 가리키는 반복자를 반환합니다.
end(): 마지막 원소 다음을 가리키는 반복자를 반환합니다.
size(): map 컨테이너에 저장된 키-값 쌍의 개수를 반환합니다.
empty(): map 컨테이너가 비어있는지 여부를 반환합니다.
clear(): map 컨테이너에 저장된 모든 요소를 삭제합니다.
insert(): 새로운 키-값 쌍을 map 컨테이너에 삽입합니다.
erase(): 지정한 키나 반복자에 해당하는 원소를 map 컨테이너에서 삭제합니다.
find(): 지정한 키를 가지는 원소를 찾아 해당 원소를 가리키는 반복자를 반환합니다. 만약 해당하는 원소가 없을 경우 map::end()를 반환합니다.
그 외에도 operator[], at(), count() 등

//반드시 정렬 후 사용
합집합 : merge() 중복허용 / set_union() 중복제거
차집합 : set_difference()
교집합 : set_intersection()
대칭 차집합 : set_symmetric_difference()

vector<int> diff; //vec1 - vec2 차집합
set_difference(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(),  back_inserter(diff));