📒 C++ - sequence container

📌 sequence container란?

- 선형구조로 데이터를 저장

- 삽입된 요소의 순서가 유지

- vector, deque, list, forward_list가 있다.

 

📌 vector

- 동적 배열의 클래스 템플릿

- 인덱싱 연산이 가능하여 접근이 빠르다.

- 요소가 추가되거나 삭제될 때마다 메모리를 자동으로 재할당하여 크기를 변경한다.

- 중간 삽입 및 삭제 속도가 느리다.

- push_back 함수를 사용하여 데이터를 저장하는 것은 대체로 O(1)의 시간이 소요 되지만, 만약 할당될 때 capacity의 크기를 넘어서게 되면 재할당이 벌어지게 되어 O(n)의 시간이 소요되게 된다.

// C++
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

int main()
{
	vector<int> vec{ 1,2,3 };
	int& num = vec[0];
	cout << num << endl;

	vec.reserve(vec.capacity() + 1);
	vec[0] = 100;
	cout << num << endl;
}

Output:
1
-572662307

- 메모리를 재할당하면서 주소가 변경되기 때문에 이전에 있던 주소는 의도치 않은 값을 가리키게 된다.

- 사용할 배열의 크기를 알고 있다면 reserve 함수를 이용하여 미리 할당해 주는 것이 좋다.

 

📌 deque

- 양쪽에 끝이 있는 큐 (double-ended queue)

- 양 끝에서 빠르게 요소를 삽입 및 삭제할 수 있다.

- 동적 배열의 클래스 템플릿

- 인덱싱 연산이 가능하여 접근이 빠르다.

- 중간 삽입 및 삭제 속도가 느리다.

- 앞, 뒤로 push 해도 상수 시간이 소요된다.

// C++
#include <iostream>
#include <deque>

using std::cout;
using std::endl;
using std::deque;

int main()
{
	deque<int> nums;
	nums.push_back(1);
	cout << nums[0] << endl;
	cout << &nums[0] << endl;
    
	nums.push_front(10);
	cout << nums[1] << endl;
	cout << &nums[1] << endl;
}

Output:
1
00EAB8E8
1
00EAB8E8

- vector와는 다르게 앞으로 삽입도 가능할뿐더러, 주소가 변하지 않는다.

- 공간을 양방향으로 미리 할당해 놓기 때문에 가능하다.

 

📌 list

- 이중 연결 리스트 (doubly linked list)

- 모든 요소에서 양방향 접근, 빠른 삽입과 삭제가 가능하다.

- 임의 접근(인덱싱 연산)이 불가능하다.

- 노드마다 포인터로 자신의 앞, 뒤 노드를 가리키고 있기 때문에 리스트 요소 재배치에 유리하다. (swap, sort, merge 등)

// C++

#include <iostream>
#include <list>

using std::cout;
using std::endl;
using std::list;

bool condition(const int& value)
{
	return value % 2 == 0;
}

int main()
{
	std::list<int> list0{ 1,2,3 };
	std::list<int>::iterator iter = list0.begin();
	std::advance(iter, 2); // iter의 주소에서 2번 이동.
	cout << *iter << endl;
	//std::sort(); // 랜덤 액세스가 가능한 객체들만 사용이 가능하다. (첨자 연산이 가능한 객체)
	list0.sort(); // 내부적으로 sort가 있다.
	list0.remove_if(condition); // 특정 조건의 데이터만 remove
	std::list<int> list1{ 1,2,3 };
	list0.merge(list1);
}

- 랜덤 액세스가 불가하기 때문에 std::sort 함수를 사용할 수 없다.

- 대신, 내부적인 sort 함수를 보유하고 있다.

- 요소에 관한 컨트롤에 유리하기 때문에 관련 함수를 다수 보유하고 있다. (sort, remove, merge, swap 등)

 

📌 forward_list

- 순방향 리스트 (singly linked list)

- 역방향 접근 불가

- 역방향 접근이 불가하기 때문에 순방향 반복자(forward iterator)만 사용이 가능

- list에 비해 더 적은 메모리를 사용

// C++

#include <iostream>
#include <forward_list>
#include <list>

using std::cout;
using std::endl;
using std::forward_list;
using std::list;

int main()
{
	list<int> list0{ 1,2,3 };
	list0.insert(list0.begin(), 10);

	forward_list<int> flist0{ 1,2,3,4 };
	flist0.insert_after(flist0.begin(), 10);

	for (int num : list0)
		cout << num << ", ";
	cout << endl;
    
	for (int num : flist0)
		cout << num << ", ";
}

Output:
10, 1, 2, 3,
1, 10, 2, 3, 4,

- 뒤에 있는 노드를 알 수 없기 때문에(단방향) 삽입할 위치의 다음 위치에 삽입이 된다.

- 메모리가 극히 제한적인 상황이 아닌 경우가 아닌 이상은 잘 사용하지 않는다.