C++4 [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++] vector와 list vector는 array 기반, list는 Linked List 기반으로 value를 저장하는 자료구조입니다. vector vector는 array이므로, 연속적인 메모리 공간에 할당합니다. capacity와 size를 기준으로 스스로 확장, 축소하는 Dynamic Array입니다. iterator 및 index로 접근이 가능하고, array 기반이므로 list에 비해 임의 접근 속도가 O(1)입니다. 삽입, 삭제 또한 O(1)이나, 컨테이너 끝이 아닌 경우 모든 요소를 밀고 삽입해야 하므로 O(N)의 시간 복잡도를 갖습니다. list list는 Linked List를 기반으로 하기 때문에, 연속된 공간이 아닌 요소가 다음 요소를 가리키는 포인터를 가지는 방식으로 구현되어 있습니다. 이로 인해 index.. 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 다음
