C++ STL sequence container(vector, deque, list)

intro

자료를 linear 하게 보관하고자 할 때, array나 linked list를 사용한다.

직접 구현해도 되지만, C++ STL에서는 이를 제공하고 있다. 이를 sequence container라고 한다.

이번 포스팅에서는 sequence container에는 무엇이 있고, 각 container의 함수의 시간복잡도를 알고자 한다.

 

vector

vector container는 동적 배열로, 메모리가 연속적으로 할당된다.

주의할 것은, vector의 back 이외에 insert 하거나 delete 하는 경우, O(n)의 시간복잡도가 소요된다.

위와 같은 경우는, list container가 효율적이다. (list는 어느 위치에 insert나 delete를 하던 상수시간이 소요된다.)

 

	시간복잡도
insert	O (n)
erase	O (n)
push_back	O (1)
pop_back	O (1)

그렇다면, push_back과 pop_back으로 뭘 하면 좋을까? 이는 stack 자료구조를 대신할 수 있다. (First In Last Out)

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<char> alphaVector;
	for (int i = 0; i < 10; i++)
	{
		alphaVector.push_back(i + 'A');
	}

	int size = alphaVector.size();
	for (int i = 0; i < size; i++)
	{
		cout << alphaVector.back();
		alphaVector.pop_back();
	}
	return 0;
}

---

Deque

deque는 vector의 확장판인데, back 뿐만 아니라 front에도 push와 pop이 가능하다. 이는 queue 자료구조를 대신할 수 있다. (First In First Out)

다만, 주의할 것은 vector와 다르게 메모리가 연속적으로 할당되지는 않기 때문에, 비효율적이다.

그러므로, vector로 표현이 가능한 경우는 굳이 deque를 쓸 필요는 없다.

 

	시간복잡도
insert	O (n)
erase	O (n)
push_back	O (1)
pop_back	O (1)
push_front	O (1)
pop_front	O (1)

---

list

double linked list로 어느 위치든 삽입, 삭제가 상수 시간으로 가능하다.

#include <iostream>
#include <vector>
#include <list>
using namespace std;

int main()
{
	list<int> li;
	for (int i = 1; i <= 5; i++)
	{
		li.push_back(i);                     // 1 2 3 4 5
	}

	li.insert(next(li.begin(), 2), 6);       // 1 2 6 3 4 5
	auto it = li.erase(next(li.begin(), 1)); // 1 6 3 4 5
	cout << *it;							 // 6
	return 0;
}

 

reference

• Cpp_STL_ReferenceManual.pdf (cppreference.com)