bdfgdfg

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로..

std::queue std::queue는 FIFO구조를 가지는 Queue 자료구조의 컨테이너 -> FIFO(First In First Out) : 가장 처음에 삽입된 것이 가장 먼저 나온다. std::queue는 내부적으로 deque, list를 기반으로 내부가 구현이 되어있으며 자료구조인 Queue의 기능을 제공한다. -> 디폴트로 deque기반으로 구현. -> std::vector의 경우에는 std::stack에서는 내부 컨테이너로 구현되어있었지만, std::queue의 경우에는 앞에서 제거하는 연산이 느린 vector를 사용하지 않는다. 먼저 std::queue 컨테이너를 사용하기 위해서는 헤더파일을 추가해야 한다. 기본적인 생성방법 1 2 3 4 5 6 // 기본 생성 방식. std::queue ..

std::stack std::stack은 LIFO구조를 가지는 Stack 자료구조의 컨테이너. -> LIFO(Last In First Out) : 마지막에 삽입된 것이 가장 먼저 나온다. 컨테이너 어댑터는 다른 컨테이너 클래스들을 상속받아 특정한 인터페이스를 제공한다. -> 다른 컨테이너와 달리 top, front 등의 함수와 pop(삭제) 함수를 함께 사용하여야만 요소에 접근 가능하다. -> 위와 같은 특징으로 반복자(Iterator)를 제공하지 않고 범위기반 for문의 사용이 불가능하다. std::stack은 vector, deque, list를 기반으로 내부적으로 구현이 되어있으며 자료구조인 stack의 기능을 제공한다. -> 디폴트로 deque기반으로 구현. 먼저 std::stack 컨테이너를 사..