c++3 [C++] deque, stack, queue, priority_queue deque deque는 vector와 list의 중간 정도의 컨테이너로, 여러 개의 메모리 블록을 할당하여 하나처럼 사용합니다. 1. vector처럼 capacity를 늘이는 과정에서 전체 copy가 일어나지 않습니다. (chunk 단위로 메모리 블록을 새로 할당 후 연결함) 2. 인덱스 접근은 가능하나, 연속적인 메모리가 아니기 때문에 포인터 연산은 불가합니다. 3. vector와 같이 처음, 끝이 아닌 중간에 삽입, 삭제하는 경우 요소를 밀어내면서 오버 헤드가 발생합니다 - O(N) stack과 queue LIFO의 stack과 FIFO의 queue는 위의 deque로 구현되어 있다. (STL 기준) 1. 두 컨테이너 모두 접근, 삽입, 삭제의 시간 복잡도가 O(1)로 아주 우수합니다. (front .. 2021. 12. 2. [C++] vector의 push_back, emplace_back 비교하기 template void std::vector.push_back(T instance); template // 가변 인자 템플릿 void std::vector.emplace_back(T's Args...) class Item // push_back, emplace_back 비교를 위한 클래스입니다. { public: int healAmount; Item(int amount) : healAmount(amount) { cout 2021. 12. 1. [C++] map과 unordered_map 기본적으로 map과 unordered_map은 key, value의 한 쌍으로, pair 형태를 띄는 자료구조입니다. map map은 아래와 같은 형태의 RB Tree로 이루어져 있습니다. (이해하는 데 도움을 받은 링크를 첨부합니다.) 요약하면 RB Tree는 레드 노드를 연속으로 배치할 수 없도록 하여 느슨한 AVL Tree를 만든 것입니다. 유사 AVL Tree이므로 자료구조의 탐색, 삽입, 삭제가 얼추 O(log N)으로 보장됩니다. Key를 기준으로 정렬되어 있으며, Iterator를 통해 그 순서대로 순회가 가능합니다. https://jwdeveloper.tistory.com/280 (알고리즘) 레드블랙트리 이번 포스팅은 레드 블랙 트리를 포스팅할 예정이다. 레드 블랙트리를 포스팅하는 이유는 .. 2021. 12. 1. 이전 1 다음
