✔️ Sequence Containers
- 데이터를 순차적으로 저장하는 자료구조
- 데이터가 정렬상태를 계속 유지할 필요가 없을 경우 좋음
📌 std::vector (std::array)
1) 정의 및 특징
- 메모리상에서 데이터가 연속적으로 위치하는 배열
- vector는 런타임에서 배열 크기 조절 O -> 크기를 미리 알 수 없거나, 크기가 변하는 경우
- array는 런타임에서 배열 크기 조절 X -> 크기를 미리 알 수 있고 변하지 않는 경우
- 포인터를 통해 만드는 동적 배열은 delete를 일일이 해줘야하지만 vector는 알아서 메모리 해제
2) 시간복잡도
- 임의 접근 (Random Access) = O(1)
- 벡터의 끝에 원소를 삽입하거나 삭제 = O(1)
- 원소의 삽입과 삭제 = O(n) (마지막 원소로부터의 거리에 비례)
3) vector의 멤버 함수
| v.assign(n, m) | m으로 n개의 원소 할당 |
| v.at(index) | index번째 원소를 반환한다. 유효한 index인지 체크하기 때문에 안전하다. |
| v[index] | index번째 원소를 반환한다. 배열과 같은 방식이며 유효성을 체크하지 않는다. |
| v.front() | 첫 번째 원소를 반환한다. |
| v.back() | 마지막 원소를 반환한다. |
| v.clear() | 모든 원소를 제거한다. 메모리는 그대로 남아있게 된다. (size는 줄어들고 capacity는 유지) |
| v.begin() | 첫 번째 원소를 가리키는 반복자(iterator)를 반환한다. |
| v.end() | 마지막 원소 다음을 가리키는 반복자(iterator)를 반환한다. |
| v.push_back(m) | 마지막 원소 뒤에 원소 m을 삽입한다. |
| v.pop_back() | 마지막 원소를 제거한다. |
| v.rbegin() | 거꾸로 시작해서 첫 번째 원소를 가리키는 반복자(iterator)를 반환한다. |
| v.rend() | 거꾸로 시작해서 마지막 원소를 가리키는 반복자(iterator)를 반환한다. |
| v.reserve(n) | n개의 원소를 저장할 공간을 예약한다. |
| v.resize(n) | 크기를 n개로 변경한다. 커진 경우에는 빈 곳을 0으로 초기화한다. |
| v.resize(n, m) | 크기를 n개로 변경한다. 커진 경우에는 빈 곳을 m으로 초기화한다. |
| v.size() | 원소의 개수를 반환한다. |
| v.capacity() | 할당된 공간의 크기를 반환한다. (size()와 다름) |
| v2.swap(v1) | v1과 v2를 swap한다. |
| v.insert(iter, m) | iter가 가리키는 위치에 m의 값을 삽입한다. 그리고 해당 위치를 가리키는 반복자(iterator)를 반환 |
| v.insert(iter, k, m) | iter가 가리키는 위치부터 k개의 m 값을 삽입한다. 다음 원소들은 뒤로 밀린다. |
| v.erase(iter) | iter 반복자가 가리키는 원소를 제거한다. capacity는 그대로 유지된다. |
| v.erase(start, end) | start 반복자부터 end 반복자까지 원소를 제거한다. |
| v.empty() | vector가 비어있으면 true를 반환한다. |
| v.max_size() | v가 담을 수 있는 최대 원소의 개수(메모리 크기) 반환 |
| v.shrink_to_fit() | capacity의 크기를 vector의 실제 크기에 맞춤 |
📌 std::deque
1) 정의 및 특징
- front와 back 양쪽에서 삽입과 삭제가 모두 가능한 구조
- std::deque는 여러 개의 버퍼에 데이터를 나눠서 저장
( std::vector는 할당된 공간이 전부 차면 배열을 통째로 새로 할당하는 반면, std::deque는 버퍼 하나만 할당)
- 데이터 삽입이 언제든 O(1)입니다.
2) 시간복잡도
- random access : O(1)
- 찾기 : O(N)
- node 삽입 / 삭제 : 중간(O(N)), 앞/뒤(O(1))
3) deque의 멤버함수
| 선언 | 설명 |
| deque dq | 빈 컨테이너를 생성 |
| deque dq(n) | 컨테이너에 n개의 원소를 저장하여 생성(default 값 저장) |
| deque dq(n,x) | 컨테이너에 n개의 원소를 저장하는데, x의 값을 넣어서 생성 |
| deque dq(dq2) | dq2와 똑같은 원소를 가지는 컨테이너를 생성 |
| 호출 | 설명 |
| dq.push_back(x) | 마지막 원소 뒤에 x를 삽입한다. |
| dq.push_front(x) | 첫번째 원소 앞에 x를 삽입한다. |
| dq.pop_back() | 마지막 원소를 삭제한다. |
| dq.pop_front() | 첫번째 원소를 삭제한다. |
| dq.clear() | 모든 원소를 삭제한다. |
| dq.empty() | dq에 원소가 하나도 없으면 true, 아니면 false를 리턴한다. |
| iter = dq.begin() | dq의 첫 번째 원소를 가리키는 반복자를 리턴한다. |
| iter = dq.end() | dq의 마지막 원소 다음을 가리키는 반복자를 리턴한다. |
| dq.size() | 원소의 개수를 리턴한다. |
| n_iter = dq.erase(iter) | iter가 가리키는 원소를 삭제한다. 그리고 다음 원소를 가리키는 반복자를 리턴한다. |
| dq.back() | 마지막 원소를 리턴한다. |
| dq.front() | 첫번째 원소를 리턴한다. |
| dq[idx] | idx번째 원소를 참조한다. (범위에 대한 예외처리 X) |
| dq.at(idx) | idx번째 원소를 참조한다. (범위에 대한 예외처리 O) |
| dq.begin() | deque의 첫번째 원소를 가리키는 iterator |
| dq.end() | deque의 마지막 원소 다음을 가리키는 iterator (마지막 원소 아님!!) |
📌 std::list (std::forward_list)
1) 정의 및 특징
- std::list는 doubly-linked list이고, std::forward_list는 singly-linked list
- singly-linked list는 맨 앞에 데이터를 삽입하는 건 빠르지만 맨 뒤에 삽입하는 건 느림. 하지만 포인터를 하나 덜 가지므로 기본적인 연산이 빠르고 메모리를 적게 사용
2) 시간복잡도
- 삽입 / 삭제 : O(1)
- random access(Container의 i번째 데이터에 O(1)에 접근)은 불가
- 찾기 : O(N)
✔️ Associative Containers
- 데이터를 정렬된 상태로 유지하는 자료구조
- Red-Black Tree를 기반으로 하고 데이터의 추가/삭제/접근의 시간복잡도가 O(logN)
- 데이터를 정렬된 상태로 유지하는 것은 매우 강력한 기능이고 O(logN)은 적은 시간복잡도지만 연산에 붙는 상수가 크고 사용하는 메모리가 많으므로 주의가 필요
📌 std::set (std::map)
1) 정의 및 특징
- std::set은 데이터를 자체를 key로 사용하고, std::map은 (key, value) 쌍을 받아서 사용
- 데이터를 정렬 상태로 유지하고 싶다면 std::set을, (key, value) 데이터 쌍을 key를 기준으로 정렬하고 싶다면 std::map
2) 시간복잡도
- 찾기 : O(log(N))
- 삽입/삭제 : O(log(N))
- 랜덤 접근 : X
3) 함수
- m.begin();
- m.end();
- m.rbegin();
- m.rend();
- m.clear();
- m.count(k);
- m.empty();
- m.insert(k);
- m.insert(iter, k);
- m.erase(start, end);
- m.find(k);
- m2.swap(m1);
- m.upper_bound(k);
- m.lower_bound(k);
- m.equal_range(k);
- m.value_comp();
- m.key_comp();
- m.size();
- m.max_size();
4) std::multiset (std::multimap)
- 같은 key를 여러 개 저장하고 싶을 때 사용
- 단, std::set에서 key의 개수를 세거나, key를 지우는 함수는 모두 O(logN)이지만, std::multiset에서는 같은 key를 모두 세고, 모두 지우므로 O(logN + (같은 key를 가지는 데이터의 개수))
✔️ Unordered Associative Containers
- 해시값을 사용해 데이터를 저장하는 자료구조
- 대부분의 경우, 데이터의 추가/삭제/접근이 O(1)
- 하지만 데이터를 정렬된 상태로 유지해야 하거나 해시 충돌이 걱정되는 상황이라면 Associated Container가 좋음
📌 std::unordered_set (std::unordered_map)
1) 정의 및 특징
- Data를 중복 없이 저장하고 싶고, Data의 순서가 상관 없을 때 사용
- 자동으로 정렬되지 않는 컨테이너. 키 값 쌍들로 저장하고, 해쉬 테이블 기반이며, 탐색 시간이 O(1)로 충돌이 없을 경우 빠름
2) 시간 복잡도
- 만약 해시값이 고르지 않게 분포하면 하나의 버킷에 모든 데이터가 삽입될 수 있고, 데이터를 추가/삭제/접근하기 위해 linked list를 순회해야 하므로 최악의 경우 시간복잡도가 O(N)
3) 함수
empty( )
- 맵이 비어있는지 확인하는 함수
- if unordered_map is empty, then return 1 else 0
size( )
- 맵의 크기를 확인하는 함수
- return size_type ( unsigned int )
operator [ ]
- 맵에서 key를 통해 value를 지정하는 operator
- map_name[key] = value
find( key )
- 맵에서 key에 해당하는 원소를 찾는 함수
- if key is contained, then iterator else map_name.end()
count( key )
- 맵에서 key에 해당하는 원소의 갯수를 반환하는 함수
- if key is contained, return 1 else 0
insert( {key, value} )
- 맵에 pair<key,value> 를 추가하는 함수
- if key is contained, then not insert
erase( key )
- 맵에서 key에 해당하는 원소를 제거하는 함수
- erase 하는 방법 : 특정 position의 pair 삭제, key를 통해 삭제, 범위 삭제
clear( )
- 맵을 초기화하는 함수
operator =
- 대입연산자 가능
📌2) std::unordered_multiset (std::unordered_multimap)
- Associateve Container 때와 마찬가지로, 같은 key를 가진 데이터를 중복으로 가져야 할 때 사용
https://math-coding.tistory.com/31
https://blog.naver.com/yoochansong/221739086178
https://blockdmask.tistory.com/70
출처: https://it-earth.tistory.com/132 [어스케이 아조시의 공부방:티스토리]