STL_SequnceContainer

STL의 컨테이너 중 데이터를 배열처럼 선형 으로 저장하는 컨테이너를 이야기 한다.

 

종류는 다음과 같다.

1. Vector
2. Deque
3. List

---

Vector

데이터 저장방식 중 선형저장방식을 따르는 컨테이너이다.

 

원소의 저장공간이 연속적으로 이어져있다는 특징이 있다.

 

사용하는 경우

• 만드려는 컨테이너의 크기를 프로그래머가 예측이 가능할 때
• 컨테이너의 데이터에 대한 삽입 삭제가 별로 없을 때
• 연속적인 데이터 처리가 필요할 때

위와 같은 경우에 사용이 추천된다.

 

코드예시

#include <iostream>
#include <vector>

int main() {
	cout << "Vector" << endl;
	vector<int> vec;
	
	for (int i = 0; i < 10; i++)
		vec.push_back(i);

	for (const auto& ele : vec)
		cout << ele << ' ';
	cout << endl << endl;
}

위와 같은 vector 배열은 데이터 저장공간이 연속적이기 때문에 다음과 같은 특징을 따르게 된다.

 

Index	0	1	2
값	A	B	C

위와 같은 std::vector 배열이 있다고 하였을 때 인덱스 1 위치에 X라는 값을 삽입해본다고 가정하자.

 

그렇다면, 값의 이동은 다음과 같은 순서로 나타난다.

Index	0	1	2	3
값	A	B		C

Index	0	1	2	3
값	A		B	C

Index	0	1	2	3
값	A	X	B	C

위와 같이. 값을 한개씩 우측으로 옮기기 때문에 매우 비효율적이게 동작하게 된다.

---

Deque

Vector와 비슷하지만, 원소가 메모리공간에 연속적으로 존재하지 않는다.

만약, Vector처럼 메모리를 재할당할 경우가 생기면, 추가로 공간을 만든 다음 이어붙이게 된다.

그러나, 서로 떨어진 메모리 공간의 데이터를 보관해야 하기 때문에, vector 보다 추가적인 메모리가 필요하게 되어, 공간을 비효율적으로 낭비할 수 있다.

 

중간에 값을 넣을 시 vector 보다 훨씬 빠르게 넣게 된다.

 

코드 예시

#include <iostream>
#include <deque>

int main() {
	cout << "Deque" << endl;

	deque<int> deq;

	for (int i = 0; i < 10; i++)
	{
		deq.push_back(i);
		deq.emplace_front(i);
	}

	for (const auto& ele : deq)
		cout << ele << ' ';
	cout << endl << endl;
}

위와 같은 deque 배열은 데이터 저장공간이 연속적이지 않기 때문에 다음과 같은 특징을 따르게 된다.

청크 0	0	1	2
값	A	B	C

위와 같은 std::deque 배열이 있다고 하였을 때 인덱스 1 위치에 X라는 값을 삽입해본다고 가정하자.

 

그렇다면, 값의 이동은 다음과 같은 순서로 나타난다.

청크 0	0	청크 1	1	2
값	A	값	B	C

청크 0	0	청크 2	1	청크 1	2	3
값	A	값	X	값	B	C

위와 같이 Deque는 청크 단위로 배열을 관리하여, 값의 위치변동을 크게 하지 않고, 중간값을 추가할 수 있다.

---

List

Deque에서 더 작게 잘라놓았다고 생각하면 된다.

각 원소는 자기 앞 값과 자기 뒷값을 기억해서 서로가 자신의 앞 뒤를 가리키는 배열 형태를 나타낸다.

삽입삭제가 빈번하게 이루어지는 상황에서 사용하기 좋다. Deque나 vector처럼 분할하고 이동하는 작업을 하지 않기 때문.

 

코드예시

#include <iostream>
#include <list>

int main() {
	cout << "List" << endl;
	list<int> list;

	for (int i = 0; i < 10; i++)
		list.push_back(i);
	
    for (const auto& ele : list)
		cout << ele << ' ';
	cout << endl << endl;
}

위와같은 List 배열은, deque에서 분리된 청크가, 각각의 값에 존재한다고 생각하면 된다.

각각의 값이 앞과 뒤의 값을 가리키기 때문에, 중간에 값을 대입하는데 큰 연산이 필요하지 않다.