자료구조

C++ STL 컨테이너
기타
- 레드블랙트리

C++ STL 컨테이너

vector
reserve() 호출이 눈에 뜨일 정도의 성능상의 효과가 없었다는 점을 발견하고 놀랐다. (TCPPL, 2013)
list는 doubly linked list로 어느 위치에나 삽입/삭제가 O(1)이지만 검색/접근은 O(n)이다. 임의 접근이 어려우므로 제네릭 알고리즘으로는 성능이 떨어져, 자체 정렬 멤버 함수인 sort()를 제공한다. 요세푸스 문제가 유명하다.
deque가 list와 동일하게 doubly linked list라고 생각하기 쉬우나 파이썬과 달리 C++의 deque는 very much like a vector이다. https://stackoverflow.com/a/1436038/3513266
set/multiset은 red-black tree를 이용해 정렬된 상태로 저장된다. 삽입/검색/삭제 모두 \(O(\log{n})\) 이다. 배열을 미리 할당해 놓지 않아도 되기 때문에 잠재적으로 적은 공간을 사용한다는 장점이 있다. 또한 키의 집합을 특정 순서로 차례대로 접근할 수 있어 유용한 경우가 있다. multiset은 같은 값이 허용되며(다중집합), 삽입 순서가 유지된다. Java/Python은 multiset을 지원하지 않는다.
map/multimap은 set과 비슷하지만 정렬이 가능한 key와 그 key가 가리키는 객체의 pair로 저장된다. Java에서 유사한 구현은 TreeMap이다. C++에서는 역사적인 이유로 hash table이 아닌 tree 기반의 map이 디폴트가 되었다고 한다.
unordered_set/unordered_map은 hash table로 저장하며 O(1)이지만 key가 충돌할 경우 worst는 O(n)이다. Java는 HashSet/HashMap, Python은 dict로 구현되어 있다. STL에 hash_map이 있었지만 C++ Standard Library에 포함되지 못하고 C++ 11에서 unordered_map으로 추가됐다.

기본 제공 배열보다는 vector, string, array 같은 컨테이너를 선택한다. 이유는,

기본 제공 배열은 배열에서 포인터로 암시적인 변환이 일어난다.
기본 제공 배열의 경우 크기를 기억해야 하기 때문에 수많은 오류의 원인이 된다.
C 스타일 문자열의 포인터 의미 구조는 미숙한 표기법을 낳고 프로그래머의 추가적인 작업을 필요로 하기 때문에 역시 수많은 오류(메모리릭 같은)의 원인이 된다.

std::vector

Note that vector inherits from _Vector_val, which contains the following members:

pointer _Myfirst;   // pointer to beginning of array
pointer _Mylast;    // pointer to current end of sequence
pointer _Myend; // pointer to end of array
_Alty _Alval;   // allocator object for values

(TCPPL, 2013)

Java의 ArrayList가 C++의 vector와 유사하다.

LinkedList implements it with a doubly-linked list. C++에서는 list.
ArrayList implements it with a dynamically re-sizing array.

장점

촘촘하게 저장되어 메모리 오버헤드가 존재하지 않는다.
순회가 매우 빠르다. 포인터를 통해 간접하지 않아도 되며, 현대적^modern? 컴퓨터는 연속적인 접근에 최적화되어 있다.
간단하고 효율적인 임의 접근을 지원한다. 따라서 sort(), binary_search()(정렬된 시퀀스에 유효) 같이 vector에 대해 수많은 알고리즘이 효율적이다.

마지막에 삽입, 임의 참조 모두 O(1)이다. list는 vector의 순회 탐색 비용에 비해 10배 이상이 될 수 있다. (TCPPL, 2013) linked list 이므로.

std::array

std::array<int, 3> a1 = {1, 2, 3};
std::array<std::string, 4> aa = {"a", b"};
// 마지막 두 원소는 빈 문자열

array의 원소 개수는 컴파일 타임에 알 수 있기 때문에 size()는 constexptr이다.

장점

배열의 크기를 정확히 알 수 있다.
포인터가 자동으로 잘못 타입 캐스팅 되는 것을 피할 수 있다.
- 타입이 다르면 포인터로 변환되지 않는다.
기본 제공 배열은 포인터로 잘못된 오프셋을 지정할 수 있다.
STL 반복자, 알고리즘을 이용할 수 있다.

std::valarray

단일 차원 수치 배열로 수치 벡터 산술 연산 및 다양한 첨자 연산자, 분할 및 간접 액세스를 제공한다.

기타

레드블랙트리

노드에 색을 부여하여 트리의 균형을 유지하며, 탐색, 삽입, 삭제 연산의 수행시간이 각각 O(logN)을 넘지 않는 매우 효율적인 자료구조다. 일반적인 레드블랙트리는 삽입이나 삭제를 수행할 때 트리의 균형을 유지하기 위해 상당히 많은 경우를 고려해야 한다는 단점이 있으며, 이에 따라 프로그램이 복잡해지고 그 길이도 증가한다. 그러나, 좌편향 레드블랙 ^{Left-Learning Red-Black, LLRB}트리는 삽입이나 삭제 시 고려해야 하는 경우의 수가 매우 작아서 프로그램의 길이도 일반 레드블랙트리 프로그램의 1/5 정도에 불과하다는 장점을 갖는다. 또한 LLRB 트리는 실제로 AVL 트리, 2-3 트리, 2-3-4 트리, 일반 레드블랙트리보다 우수한 성능을 갖는다. (파이썬과 함께하는 자료구조의 이해, 2018)

Last Modified: 2023/06/03 02:18:41