시퀀스 컨테이너

자료를 들어온 순서대로 보관하는 구조. 따로 데이터를 정렬하지 않는다.
삽입/삭제/검색 속도가 연관 컨테이너에 비해 느리다.
다루는 자료의 양이 적을 때 사용한다. (자료의 양이 적으면 연관 컨테이너가 더 손해)

vector

배열과 가장 유사한 구조임 (연결리스트로 구현되어있는데 이를 배열처럼 사용할 수 있음)
- 그래서 “[ ]” 연산자를 활용해 직접 접근이 가능함
  
  (일부러 at, front, end 함수는 정리하지 않았음)
- 즉 검색 속도가 매우 빠름. 시퀀스 컨테이너 중 가장 많이 사용함
- 단 배열과 유사하기 때문에 중간삽입, 중간삭제에는 적합하지 않음
  
  (일부러 insert, erase 함수는 정리 안하려고 함)
배열과 차이점: 배열은 사이즈 고정, vector는 동적 배열구조 클래스임!
push_back, pop_back 함수 덕에 맨끝 삽입/삭제가 잦은 경우에 사용하면 좋음

#include <vector>
#include <algorithm>
using namespace std;

public void iterator()
{
	// <algorithm> 함수 사용시 대부분 input으로 반복자를 사용하기 때문에 정리함
	// iterator 변수 선언 시 자료형을 'auto'로 선언하면 편하다.
	vector<int> b(5);
	vector<int>::iterator bb = b.begin() + 2; 
	// => auto bb = b.begin() + 2;
	printf("%d", *bb) // 벡터 b의 3번째 원소, 1번째 원소면 위 코드에서 + 2를 지우면 됨

	for (vector<int>::iterator bbb = b.begin(); bbb != b.end(); bbb++)
	// => for (auto bbb = b.begin(); ... )
	{
		printf("%d", *bbb);
		// 벡터 b의 모든 원소 접근
	}

	for (vector<int>::reverse_iterator bbb = b.rbegin(); bbb != b.rend(); bbb++)
	// => for (auto bbb = b.rbegin(); ... )
	{
		printf("%d", *bbb);
		// 벡터 b의 모든 원소 역순으로 접근
	}
}

public void intialize() 
{
	vector<자료형> 변수; // 빈 벡터 생성
	vector<자료형> 변수(사이즈); 
	/*
	 * 사이즈만큼 디폴트 값으로 채워진 벡터 생성
	 * ex) vector<int> a(3) => { 0, 0, 0 }
	 */
	vector<자료형> 변수(사이즈, 디폴트 값);
	/*
	 * ex) vector<char> a(3, 'a') => { 'a', 'a', 'a' }
	 * ex) int n = 3; vector<int> a(n, 5) => { 5, 5, 5 }
	 */
	vector<자료형> 변수 = { 데이터 배열 };
	vector<자료형> 변수(다른 vector변수);
	/*
	 * vector<char> a = { 'a', 'b' };
	 * vector<char> b(a);
	 */
	vector<자료형> 변수(자료형 배열, 자료형 배열 + 복사할 사이즈);
	/*
	 * int arr[] = { 1, 2, 3, 4, 5 };
	 * vector<int> a(arr, arr + 4); => a = { 1, 2, 3, 4 }가 됨
	 */ 
	vector<자료형> 변수 = (다른 vector변수.begin(), 다른 vector변수.end());
	/*
	 * vector<int> a = { 1, 2, 3 };
	 * vector<int> b(a.begin(), a.end());
	 */

	// vector, deque만 가능(∵직접접근)
	vector<자료형> 변수 = 
		(다른 vector변수.begin(), 다른 vector변수.begin() + 복사할 사이즈);
	/*
	 * vector<int> a = { 1, 2, 3 };
	 * vector<int> b(a.begin(), a.begin() + 1);
	 */
}

public void copy()
{
	vector<string> a = { "ab", "bc" };
	vector<string> c;
	c = a; // { "ab", "bc" }가 복사돼서 들어간다.
	// a.push_back()을 해도 c는 영향받지 않는다.
}

public void insert()
{
	vector<int> a;
	a.push_back(데이터); // 맨 뒤에 데이터 추가
}

public void erase()
{
	vector<int> a;
	a.pop_back(); // 맨 뒤의 데이터 삭제
	a.clear() // 모든 원소 삭제
}

public void size()
{
	vector<char> a;
	a.size();
	a.empty(); // a가 비었는지 여부 리턴
}

public void search()
{
	vector<int> a = { 1, 2, 3, 4 };
	a.front(); // 1
	a.back();  // 4
	/* 
	 * 나머지 중간 원소는 
	 * 1. [1], [2] 인덱스로 직접 접근 
	 * 2. 반복문+iterator를 통해 선형탐색
	 */
	a[2] // 3
}

public void contains()
{
	// 연관 컨테이너처럼 find함수가 내장돼있지 않아서 
	// #include <algorithm> 의 find함수를 써야함
	vector<int> a = { 1, 2, 3, 4, 5 };
	auto i = find(a.begin(), a.end(), 2); // 결과값은 iterator로 받을 수 있음
	if (i != a.end())
	{
		// 원소를 포함하고 있음
		int index = i - a.begin() // 찾는 원소의 인덱스
	}
}

public void swap()
{
	vector<int> a = { 1 };
	vector<int> b = { 2 };
	a.swap(b); // a는 { 2 }, b는 { 1 }을 갖게 된다. 
}

list

(그림) 양방향 연결리스트

                                                (그림) 양방향 연결리스트

양방향(이중) 연결리스트와 가장 유사한 구조임
- 배열처럼 특정 인덱스 직접 접근 불가함! 매번 선형탐색을 해야 함
- 그래서 검색속도는 vector보다 느림
- 대신 vector보다 중간삽입, 중간삭제가 빠름
  
  (vector처럼 전체 데이터가 구조 조정을 위해 움직일 필요가 없으므로)
데이터는 적은데 중간삽입, 중간삭제가 잦은 경우에 사용하면 좋음

#include <list>
using namespace std;

public void iterator()
{
	list<int> b(5);
	list<int>::iterator bb = b.begin(); 
	// vector와 달리 b.begin() + 2 이렇게 특정 인덱스 할당할 수 없다! (∵직접 접근 불가)
	// 무조건 b.begin() or b.end()만 가능함
	printf("%d", *bb) // 리스트 b의 1번째 원소
	// 나머지는 vector와 동일
}

public void initialize()
{
	// vector와 동일 (vector와 달리 iterator로 특정 인덱스 접근 불가한 것만 주의)
}

public void copy()
{
	// vector와 동일
}

public void insert()
{
	list<int> a = { 5, 6 };
	a.push_front(값);
	a.push_back(값);
	a.insert(iterator, 값); // iterator가 가리키는 곳 앞에 값 삽입
	/*
	 * list<int>::iterator aa = a.end();
	 * a.insert(aa, 7); => a는 { 5, 6, 7 }이 된다.
	 */
}

public void erase()
{
	list<int> a = { 5, 6, 7 };
	a.pop_front();
	a.pop_back();
	a.erase(iterator); // iterator가 가리키는 곳 원소 삭제
	/*
	 * list<int>::iterator aa = a.begin();
	 * a.erase(aa); => a는 { 6, 7 }이 된다.
	 * 중간 원소 삭제를 원할 경우 iterator로 반복문을 돌아서 삭제해야함
	 */
	a.clear();
}

public void size()
{
	// vector와 동일
}

public void search()
{
	// vector와 동일 (단, 중간원소를 인덱스를 통해 직접접근하는 방식은 불가) 
}

public void contains()
{
	// vector와 동일
}

public void swap()
{
	// vector와 동일
}

deque

양방향으로 삽입, 삭제가 가능한 큐 ⇒ 데큐(혹은 덱)

vector와 유사한 구조임
- 그래서 “[ ]” 연산자를 활용해 직접 접근이 가능함
- vector처럼 중간삽입, 중간삭제에는 적합하지 않음
vector와 차이점: 맨앞/맨끝에서 삽입/삭제가 일어남 (push_back, push_front가 모두 존재)
- 맨 앞과 맨 끝에서 삽입/삭제 연산이 잦은 경우에 사용하면 좋음.

#include <deque>
using namespace std;

public void iterator()
{
	// vector와 동일
}

public void initialize()
{
	// vector와 동일
}

public void copy()
{
	// vector와 동일
}

public void insert()
{
	deque<int> a = { 5, 6 };
	a.push_front(값); // { 값, 5, 6 }
	a.push_back(값);  // { 5, 6, 값 }
}

public void erase()
{
	deque<int> a = { 5, 6, 7 };
	a.pop_front(); // { 6, 7 }
	a.pop_back();  // { 5, 6 }
	a.clear();
}

public void size()
{
	// vector와 동일
}

public void search()
{
	// vector와 동일
}

public void contains()
{
	// vector와 동일
}

public void swap()
{
	// vector와 동일
}