[C++] STL 컨테이너

array

고정된 크기를 가지는 배열이다.

C의 배열과 같다.

C의 배열처럼 이름이 첫번째 원소의 포인터로 변환되지는 않는다.

 

1. #include <iostream>
2. #include <array>
3.  
4. using namespace std;
5.  
6. int main() {
7. array<int, 4> arr
8. {
9. {1, 3, 5}
10. };
11. array<int, 4>::iterator it;
12.  
13.  
14. arr[3] = 7;
15.  
16. cout << "---- Array ----" << endl;
17. cout << "Size:\t" << arr.size() << endl;
18. cout << "Content:" << endl;
19. for (it = arr.begin(); it != arr.end(); it++) {
20. cout << *it << endl;
21. }
22.  
23. }

 

vector

크기가 상황에 맞게 자동으로 늘어나고 줄어드는 배열이다.

배열처럼 데이터들이 메모리에 연속적으로 저장된다.

 

탐색시 O(1)의 시간복잡도를 가진다.

삽입시 O(n)의 시간복잡도를 가진다.

제거시 O(n)의 시간복잡도를 가진다.

1. #include <iostream>
2. #include <vector>
3.  
4. using namespace std;
5.  
6. int main() {
7. vector<int> arr;
8. arr.push_back(1);
9. arr.push_back(3);
10. arr.push_back(5);
11. arr.push_back(7);
12.  
13. arr[1] = 4;
14.  
15. arr.pop_back();
16.  
17. cout << "---- VECTOR ----" << endl;
18. vector<int>::iterator it;
19. for (it = arr.begin(); it != arr.end(); it++) {
20. cout << *it << endl;
21. }
22. }

 

 

list

이중 연결 리스트의 컨테이너이다.

이중 연결 리스트는 노드 하나가 이전 노드와 다음 노드의 위치 정보를 가지는 형태로써 중간 삽입, 삭제에 특화되어 있다. 

탐색시 O(n)의 시간복잡도를 가진다.

삽입시 O(1)의 시간복잡도를 가진다.

제거시 O(1)의 시간복잡도를 가진다.

1. #include <iostream>
2. #include <iterator>
3. #include <list>
4.  
5. using namespace std;
6.  
7. int main() {
8. list<int> lst;
9. lst.push_back(3);
10. lst.push_back(5);
11. lst.push_front(1);
12. lst.push_front(-1);
13.  
14. list<int>::iterator it;
15.  
16. it = next(lst.begin(), 2);
17.  
18. lst.insert(it, 11);
19.  
20. it = next(it, -1);
21. lst.erase(it);
22.  
23. cout << "---- list ----" << endl;
24. for (it = lst.begin(); it != lst.end(); it++) {
25. cout << *it << endl;
26. }
27.  
28. }

 

 

forward_list

단방향 연결 리스트의 컨테이너이다.

뒤쪽 방향으로의 위치 정보를 기록하지 않기 때문에 list 보다 적은 양의 메모리를 사용한다.

찾는 노드가 리스트의 뒤쪽에 있을경우 무조건 앞에서부터 탐색해야 하기 때문에 이중 연결 리스트보다 탐색 시간이 더 오래 걸릴 수 있다.

 

 

탐색시 O(n)의 시간복잡도를 가진다.

삽입시 O(1)의 시간복잡도를 가진다.

제거시 O(1)의 시간복잡도를 가진다.

 

1. #include <iostream>
2. #include <iterator>
3. #include <forward_list>
4.  
5. using namespace std;
6.  
7. int main() {
8. forward_list<int> lst;
9. lst.push_front(3);
10. lst.push_front(1);
11. lst.push_front(-1);
12. lst.push_front(-3);
13.  
14. forward_list<int>::iterator it;
15.  
16. it = next(lst.begin(), 2);
17.  
18. lst.insert_after(it, 11);
19. it = next(it, 1);
20. lst.erase_after(it);
21.  
22. cout << "---- list ----" << endl;
23. for (it = lst.begin(); it != lst.end(); it++) {
24. cout << *it << endl;
25. }
26.  
27. }

 

deque

크기가 상황에 맞게 자동으로 늘어나고 줄어든다.

데이터들의 앞쪽 끝이나 뒤쪽 끝에서 빠르게 추가/삭제가 가능하다.

배열이나 벡터와 다르게 데이터들이 메모리에 연속적으로 저장됨이 보장되지 않는다.

 

 

 

탐색시 O(1)의 시간복잡도를 가진다.

삽입시 O(n)의 시간복잡도를 가진다.

제거시 O(n)의 시간복잡도를 가진다.

양쪽 끝에 삽입시 O(1)의 시간복잡도를 가진다.

양쪽 끝에서 제거시 O(1)의 시간복잡도를 가진다.

 

1. #include <iostream>
2. #include <deque>
3.  
4. using namespace std;
5.  
6. int main() {
7. deque<int> de;
8. de.push_back(7);
9. de.push_back(5);
10. de.push_front(1);
11. de.push_front(3);
12. de.push_back(9);
13.  
14. cout << "--- deque ---" << endl;
15. deque<int>::iterator it;
16. for (it = de.begin(); it != de.end(); it++) {
17. cout << *it << endl;
18. }
19. cout << endl;
20. cout << "de[2] = " << de[2] << endl;
21. cout << "de[front] = " << de.front() << endl;
22. cout << "de[last] = " << de.back() << endl;
23. cout << endl;
24.  
25. de.pop_back();
26. de.pop_front();
27.  
28. cout << "------------" << endl;
29. for (it = de.begin(); it != de.end(); it++) {
30. cout << *it << endl;
31. }
32.  
33. }

 

 

queue

First In First Out (FIFO) 를 구현하는 컨테이너 어댑터이다.

deque 컨테이너에서 데이터의 앞쪽 추가, 뒤쪽 삭제만 가능하게 제한한 컨테이너 어댑터이다.

 

 

 

1. #include <iostream>
2. #include <queue>
3.  
4. using namespace std;
5.  
6. int main() {
7. queue<int> qu;
8.  
9. cout << "---- queue ----" << endl;
10.  
11. qu.push(1);
12. qu.push(3);
13.  
14. cout << qu.front() << endl;
15. qu.pop();
16.  
17. qu.push(5);
18. qu.push(7);
19.  
20.  
21. while (!qu.empty()) {
22. cout << qu.front() << endl;
23. qu.pop();
24. }
25. }

 

stack

First In Last Out (FILO) 를 구현하는 컨테이너 어댑터이다.

deque 컨테이너에서 데이터의 뒤쪽 추가, 뒤쪽 삭제만 가능하게 제한한 컨테이너 어댑터이다.

 

 

 

 

1. #include <iostream>
2. #include <stack>
3.  
4. using namespace std;
5.  
6. int main() {
7. stack<int> stk;
8.  
9. cout << "---- stack ----" << endl;
10.  
11. stk.push(1);
12. stk.push(3);
13.  
14. cout << stk.top() << endl;
15. stk.pop();
16.  
17. stk.push(5);
18. stk.push(7);
19.  
20. while (!stk.empty()) {
21. cout << stk.top() << endl;
22. stk.pop();
23. }
24. }

 

 

map

정렬된 키-값 쌍 (Associative array, 연관 배열)들을 저장하는 컨테이너이다.

항상 키를 기준으로 정렬되어 있다.

키는 중복될 수 없다.

키는 대, 소를 비교할 수 있는 형식이어야 한다.

 

탐색시 O(log n)의 시간복잡도를 가진다.

삽입시 O(log n)의 시간복잡도를 가진다.

제거시 O(log n)의 시간복잡도를 가진다.

 

1. #include <iostream>
2. #include <string>
3. #include <map>
4.  
5.  
6. using namespace std;
7.  
8. int main() {
9. map<string, int> arr{
10. {"hello", 314},
11. {"world", 217}
12. };
13. map<string, int>::iterator it;
14.  
15.  
16. arr.insert(pair<string, int>("welcome", 2580));
17. arr.insert(pair<string, int>("nono", 8150));
18. arr.insert(pair<string, int>("cert", 8080));
19.  
20. cout << "---- Show All ----" << endl;
21. for (it = arr.begin(); it != arr.end(); it++) {
22. cout << it->first << '\t' << it->second << endl;
23. }
24.  
25. cout << endl;
26. cout << "---- Show value of \"world\" ----" << endl;
27. cout << arr["world"] << endl;
28. cout << endl;
29.  
30. for (int i = 0; i < 2; i++) {
31. cout << "---- Is \"hello\" there? ----" << endl;
32. it = arr.find("hello");
33. if (it != arr.end()) {
34. cout << "YES!" << endl;
35. cout << "VALUE:\t" << it->second << endl;
36. }
37. else {
38. cout << "NO!" << endl;
39. break;
40. }
41. cout << endl;
42.  
43. arr.erase("hello");
44. }
45. cout << endl;
46.  
47.  
48. arr["welcome"] = 9999999;
49. arr.insert(pair<string, int>("cart", 0));
50.  
51. cout << "---- Show All ----" << endl;
52. for (it = arr.begin(); it != arr.end(); it++) {
53. cout << it->first << '\t' << it->second << endl;
54. }
55. }

 

hash_map (unordered_map)

map과 거의 비슷하다.

항상 정렬되어 있지는 않다. 대신에 해시 테이블을 활용해서 탐색에 특화되어 있다.

현재 hash_map은 비표준으로 obsolete 처리되어있다. 이와 같은 역할을 하는 C++ 표준 라이브러리의 컨테이너는 unordered_map이다.

 

탐색시 O(1)의 시간복잡도를 가진다.

삽입시 O(1)의 시간복잡도를 가진다.

제거시 O(1)의 시간복잡도를 가진다.

 

1. #include <iostream>
2. #include <string>
3. #include <unordered_map>
4.  
5.  
6. using namespace std;
7.  
8. int main() {
9. unordered_map<string, int> arr{
10. {"hello", 314},
11. {"world", 217}
12. };
13. unordered_map<string, int>::iterator it;
14.  
15.  
16. arr.insert(pair<string, int>("welcome", 2580));
17. arr.insert(pair<string, int>("nono", 8150));
18. arr.insert(pair<string, int>("cert", 8080));
19.  
20. cout << "---- Show All ----" << endl;
21. for (it = arr.begin(); it != arr.end(); it++) {
22. cout << it->first << '\t' << it->second << endl;
23. }
24.  
25. cout << endl;
26. cout << "---- Show value of \"world\" ----" << endl;
27. cout << arr["world"] << endl;
28. cout << endl;
29.  
30. for (int i = 0; i < 2; i++) {
31. cout << "---- Is \"hello\" there? ----" << endl;
32. it = arr.find("hello");
33. if (it != arr.end()) {
34. cout << "YES!" << endl;
35. cout << "VALUE:\t" << it->second << endl;
36. }
37. else {
38. cout << "NO!" << endl;
39. break;
40. }
41. cout << endl;
42.  
43. arr.erase("hello");
44. }
45. cout << endl;
46.  
47.  
48. arr["welcome"] = 9999999;
49. arr.insert(pair<string, int>("cart", 0));
50.  
51. cout << "---- Show All ----" << endl;
52. for (it = arr.begin(); it != arr.end(); it++) {
53. cout << it->first << '\t' << it->second << endl;
54. }
55. }

set

정렬된 키들을 저장하는 컨테이너이다.

map과 다르게 키만 저장한다.

항상 정렬되어 있다.

키는 중복될 수 없다.

키는 대, 소를 비교할 수 있는 형식이어야 한다.

한번 저장된 키는 값을 변경할 수 없다.

 

탐색시 O(log n)의 시간복잡도를 가진다.

삽입시 O(log n)의 시간복잡도를 가진다.

제거시 O(log n)의 시간복잡도를 가진다.

 

1. #include <iostream>
2. #include <string>
3. #include <set>
4.  
5.  
6. using namespace std;
7.  
8. int main() {
9. set<string> arr{
10. "hello",
11. "world",
12. "welcome"
13. };
14. set<string>::iterator it;
15.  
16.  
17. arr.insert("welcome");
18. arr.insert("nono");
19. arr.insert("cert");
20.  
21. cout << "---- Show All ----" << endl;
22. for (it = arr.begin(); it != arr.end(); it++) {
23. cout << *it << endl;
24. }
25. cout << endl;
26.  
27. for (int i = 0; i < 2; i++) {
28. cout << "---- Is \"hello\" there? ----" << endl;
29. it = arr.find("hello");
30. if (it != arr.end()) {
31. cout << "YES!" << endl;
32. }
33. else {
34. cout << "NO!" << endl;
35. break;
36. }
37. cout << endl;
38.  
39. arr.erase("hello");
40. }
41. cout << endl;
42.  
43. arr.insert("cart");
44.  
45. cout << "---- Show All ----" << endl;
46. for (it = arr.begin(); it != arr.end(); it++) {
47. cout << *it << endl;
48. }
49. }

컨테이너들의 함수별 시간 복잡도 정보는 다음 링크에서 확인할 수 있다.

http://www.cs.northwestern.edu/~riesbeck/programming/c++/stl-summary.html