bdfgdfg

std::unordered_map std::unordered_map은 HashTable로 구현된 자료구조로 탐색에 걸리는 시간 복잡도는 O(1) -> 상수시간복잡도. -> 기존의 std::map은 이진 탐색 트리로 탐색의 시간 복잡도는 O(logN)의 시간 복잡도. -> std::map은 자동으로 정렬되는 컨테이너. 그렇기에 요소의 삽입/삭제가 빈번할 경우 성능이 저하된다. 이름에서 알 수 있듯이. 정렬되지 않은 맵. std::map과는 달리 자동으로 정렬되지 않기 때문. std::map과 같이 중복 키를 허용하지 않으며, key와 value의 쌍(pair)으로 요소를 저장한다는 공통점이 존재. -> 다른 점은 내부 구현된 자료구조가 다르며, 요소는 key값을 통해 해시 함수가 생성하는 index기반의 ..

std::multimap std::multimap은 연관 컨테이너이며 기본적으로 map과 동일하다. 단 std::map과는 달리 중복키를 허용한다. std::map에서는 insert를 통해 중복된키에 해당하는 요소를 삽입하면 삽입되지 않으며, operator[]연산자를 이용해도 중복키에 해당하는 요소가 이미 존재한다면 값을 덮어씌운다. std::multimap은 insert를 할 때 키가 이미 존재해도 중복키를 허용하기에 데이터를 저장한다. 그 외에는 map과 동일하기에 설명할게 없다. 먼저 std::multimap을 사용하기 위해서는 헤더파일을 추가해야 한다. 기본적인 생성 방법 1 2 3 4 // 기본 생성 방식 std::multimap mMap; // 복사 생성자 지원 std::multimap mM..

std::map std::map은 연관(Associative) 컨테이너 중 하나이다. -> 모든 연관 컨테이너는 노드 기반 컨테이너이며 키(Key)를 이용해 객체를 꺼내온다. (비선형 자료구조) -> 연관 컨테이너의 종류에는 map, set, multimap, multiset 등이 존재한다. std::map은 이진 탐색 트리의 자료구조로 구현되어 있으며 그중 Red-Black트리라는 균형 이진 트리로 내부가 구현이 되어있다. -> 균형 이진 트리는 삽입/삭제/탐색의 시간 복잡도가 log(N)의 시간 복잡도를 가진다. -> 일반 이진 탐색 트리는 최악의 경우 한쪽으로 노드가 쏠려 O(N)의 시간 복잡도를 가짐. 그렇기에 균형 이진트리를 사용. (보완된 이진 탐색 트리라고도 함) -> 삽입시 데이터가 자동으..

std::priority_queue std::priority_queue는 Heap(힙) 자료구조를 기반으로 한 우선순위 큐 자료구조의 컨테이너이다. -> 우선순위 큐는 들어간 순서에 상관없이 프로그래머가 정한 우선순위의 근거에 따라 우선순위가 가장 높은 데이터가 먼저 나온다. -> 우선 순위큐의 삽입/삭제는 log(N)의 시간복잡도를 가진다. --> 삽입의 경우 완전 이진 트리의 마지막 저장 위치에서 삽입 후 부모와 우선순위를 비교해 올라가는 구조. -> log(N) --> 삭제의 경우 루트 노드 삭제 후 완전 이진 트리의 마지막 노드를 루트노드로 옮기고 자식과 우선순위 비교하면서 자기자리를 찾아가는 구조. -> log(N) 우선순위 큐는 힙 자료구조(배열)를 채택하였기에 내부 컨테이너는 default로..