6장 시퀀스 컨테이너

1. vector 컨테이너

• 백터의 주요 인터페이스와 특징

template<typename T, typename Allocator = allocator<T>> 
class Vector { ... }

백터는 원소의 저장 위치가 정해져 있는 배열(원소가 하나의 메모리) 기반의 컨테이너이다.

시퀀스 컨테이너의 특징인 push_back(), pop_back(), front(), back(), insert() 등의 함수가 있다.

push_back()시 자동으로 메모리가 할당된다.

 

• 생성자

생성자	설명
vector v	v는 빈 컨테이너다.
vector v(n)	v는 기본값으로 초기화된 n개의 원소를 갖는다.
vector v(n,x)	v는 x값으로 초기화된 n개의 원소를 갖는다.
vector v(v2)	v는 v2 컨테이너의 복사본(복사 생성자)이다.
vector v(b, e)	v는 반복자[begin, end)로 초기화된 원소다

 

• 멤버함수 (p:반복자, q:p다음 반복자, b:반복자 시작, e:반복자 끝)

추가/할당	설명
v.assign(n, x)	x값으로 n개를 할당한다
v.assign(b, e)	[begin, end)까지의 값을 할당한다
v.push_back(x)	끝에 원소 x를 추가한다.
v.insert(p, x)	p의 위치에 x를 삽입한다.
v.insert(p, n, x)	p의 위치에 n개의 x값을 삽입한다
q = v.insert(p, b, e)	p의 위치에 반복자 [b,e)를 삽입한다.

제거	설명
v.pop_back()	마지막 원소를 제거한다.
q = v.erase(p)	반복자에 해당하는 원소를 제거한다
q = v.erase(b,e)	반복자 [b,e)에 해당하는 원소들을 제거한다.
v.clear()	모든 원소를 제거한다.

참조/반복자	설명
v.at(i)	i번째 원소를 참조(const, 비 const 상관 X)한다
v.front()	첫 번째 원소를 참조한다.
v.back()	마지막 원소를 참조한다.
p = v.begin()	첫번째 원소를 가르키는 반복자.
p = v.end()	마지막 원소를 가르키는 반복자.
p = v.rbegin()	역 순차열의 첫 원소를 가르키는 반복자
p = v.rend()	역 순차열의 마지막 원소를 가르키는 반복자

특수	설명
v.reserve(n)	n개의 원소를 저장할 공간을 예약한다
x = v.capacity()	할당된 크기

기타	설명
v.resize(n)	크기를 n으로 변경하고, 기본값으로 초기화한다.
v.resize(n, x)	크기를 n으로 변경하고, x값으로 초기홯나다.
v.size()	원소의 개수
x = v.max_size()	담을 수 있는 최대 원소의 개수(메모리 크기)
v.empty()	비었는지 판단한다.
v.swap(v2)	v와 v2를 스왑한다.

 

• 연산자

연산자	설명
v1 == v2	v1과 v2의 모든 원소가 같은가?
v1 != v2	v1과 v2의 원소가 하나라도 다른가?
v1 < v2	v2가 v1보다 큰가?
v1 <= v2	v2가 v1 이상인가?
v1 > v2	v1이 v2보다 큰가?
v1 >= v2	v1이 v2 이상인가?
v[i]	v의 i번재 원소를 참조한다. 범위를 점검하지 않음.

※ at(i)과 [i]의 차이: at은 범위를 점검하고, []는 점검하지 않아 오류가 발생할 수 있다.

 

• 템플릿 멤버 형식

멤버 형식	설명
allocator_type	메모리 관리자 형식
const_iterator	const 반복자 형식
const_ reverse_iterator	const 역 반복자 형식
const_pointer	const value_type* 형식
const_reference	const value_type& 형식
difference_type	두 반복자의 형식 차이
iteartor	반복자 형식
reverse_iterator	역 반복자 형식
pointer	value_type* 형식
reference	value_type& 형식
size_type	첨자나 원소의 개수 등의 형식
value_type	원소의 형식

// v.size()는 size_type이기 때문에 컴파일러 에러가 발생한다.
for(int i=0; i<v.size(); ++)

// typedef된 멤버 형식 size_type을 사용한다.
// v.size()를 int로 변환하거나, unsigned_int i=0 로 하는 방법도 있다.
for(vector<int>::size_type i=0; i<v.size(); ++)

---

• 할당 및 변경

vector의 원소가 추가될 때 마다 메모리를 재할당 하고, 이전 원소를 모두 복사한다면 비효율적이다. 

그래서 원소가 추가될 때 마다 충분한 메모리를 미리 확보시킨다.

컴파일러에 따라 x2, 이전 크기의 1/2 방식으로 미리 할당한다.

vector<int> v; // size:0, cap:0
// v.reserve(8) // reserve를 통해 cap을 미리 8로 예약할 수 있다.

// 2배씩 할당한다.
// 메모리 재할당 -> 복사
v.push_back(1); // size:1, cap:1

// 메모리 재할당 -> 복사
v.push_back(1); // size:2, cap:2

// 메모리 재할당 -> 복사
v.push_back(1); // size:3, cap:4
v.push_back(1); // size:4, cap:4

// 메모리 재할당 -> 복사
v.push_back(1); // size:5, cap:8
v.push_back(1); // size:6, cap:8
v.push_back(1); // size:7, cap:8

resize(), clear() 함수를 통해 size의 크기를 변경할 수도 있다.

vector<int> v(5) = {1,2,3,4,5}; 

v.resize(10); 
// v = 1, 2, 3, 4, 5, 0, 0, 0, 0, 0
// size:10, cap:10

v.resize(5); // v = 1, 2, 3, 4, 5
// size:5, cap:10

v.clear();
// size:0, cap:10

다만 size가 0이 되도 메모리에서는 제거되지 않는다. 메모리에서 제거를 굳이 하고싶다면 swap을 이용하자.

vector<int> v(5);
vector<int>().swap(v); 

// 기본 생성자로 만든 임시 객체(cap:0) v(cap:5)를 스왑!
// 임시 객체 cap:5
// v cap: 5
// 임시객체는 자동으로 제거!

---

• 참조

참조에는 front(), back(), at(), [] 연산자가 있다.

front()와 back()은 참조 및 변경이 가능하다.

vector<int> v(5) = {1,2,3,4,5};

cout << v.front() << ", " << v.back() << endl; // 1, 5
v.front() = 10;
v.back() 50;

cout << v.front() << ", " << v.back() << endl; // 10, 50

at()과 [] 연산자는 범위 점검의 유무 차이만 있다.

vector<int> v(5);

cout << v.at(6) << endl; // 에러 X
cout << v[6] << endl; // 에러: out_oif_range

---

• 반복자

vector<int> v = {1,2,3,4,5};

vector<int>::iterator iter = v.begin(); // vector<int>::iteartor 반복자 객체 생성

// iter != v.end() iter가 끝을 가리키는지?
// ++iter 반복자를 다음 원소를 가르키도록
for(iter = v.begin(); iter != v.end(); ++iter) 
{
    cout << *iter << endl; // *iter : 반복자가 가리키는 원소 참조
}

iter = v.begin();

// +=, -= 연산자 사용 가능
iter += 2;
cout << *iter << endl; // 3
iter -= 1;
cout << *iter << endl; // 2

// ++ 연산자 가능
cout << *++iter << endl; // 3

// const_iterator가 아니면 수정이 가능하다
*iter = 10; // v = {1, 2, 10, 4, 5}

 

• 상수

vector<int>::iterator iter; // 이동, 원소의 변경이 가능하다

vector<int>::const_iterator citer; // 이동은 가능하나, 변경은 불가능하다.

const vector<int>::iterator iter_const; // 이동이 불가능하고, 변경은 가능하다.

const vector<int>::const_iterator citer_const; // 이동과 변경 둘다 불가능하다.

 

• 방향 반복자

vector<int>::iterator iter; // 정방향 반복자
vector<int>::reverse_iterator riter; // 역방향 반복자

for(iter = v.begin(); iter != v.end(); ++iter) // 0 -> v.size()
{
    ...
}

for(iter = v.rbegin(); iter != v.rend(); ++iter) // v.size() -> 0
{
    ...
}

 

• insert: 중간 삽입 가능, erase: 중간 삭제 가능

vector<int>::iterator iter = v.begin() + 2;
vector<int>::iteartor iter2;

iter2 = v.insert(iter, 100); 
// v = {1, 2, 100, 3, 4, 5}
// *iter2 = 100;

iter2 = v.erase(++iter);
// v = {1, 2, 100, 4, 5}
// *iter = 4;

 

• 생성

vector<int> v(n); // 1,2,3,4,5

// 순차열 [begin, end)
vector<int> v2(v.begin(), v.end()); // 복사 생성자

// assign
vector<int> v3;
v3.assign(v.begin(), v.end());

---

• vector의 주요 특징

• 임의 접근 반복자(at, [])를 지원하는 배열(원소가 하나의 메모리 블럭에 연속해서 저장) 기반의 컨테이너
• 메모리 재할당을 줄이기 위해 reserve(), capacity를 배로 증가한다.
• insert(), erase(), push_back()이 빈번할 경우 다른 컨테이너를 쓰자.
• 시퀀스 컨테이너(원소가 순서를 유지)로 front()와 back()이 가능하다. 다만 배열 기만이니 push_front()나 pop_front()는 없다.

---

2. deque 컨테이너

vector와 같이 시퀀스 컨테이너이며 배열 기반의 컨테이너다.

• 주요 인터페이스와 특징

template<typename T, typename Allocator = allocator<T>> 
class dequeue { ... }

 

• 생성자

생성자	설명
deque dq	빈 컨테이너
deque dq(n)	기본값으로 초기화된 n개의 원소를 가진다.
deque dq(n,x)	x값으로 초기화된 n개의 원소를 가진다.
deque dq(dq2)	dq2 컨테이너 복사본(복사생성자)이다
deque dq(b,e)	반복자 구간 [b,e)의 원소를 가진다.

 

• 멤버 함수 (나머지는 백터와 같다)

할당/추가	설명
push_front(x)	첫 위치에 원소 x를 추가한다.

제거	설명
pop_front()	첫번째 원소를 제거한다.

 

• 연산자와 멤버형식

백터와 연산자, 멤버형식은 같다.

 

• 구조

• 시퀀스 컨테이너 : 순서 유지
• 배열 기반의 컨테이너 : 임의 접근 반복자(+, -, +=, -=, [])가 가능하다
• 여러개의 메모리 블록을 하나의 블록처럼 사용 : 복사가 일어나지 않는다.
• 양끝 삽입/삭제가 가능하다.

원소의 추가 위치에 따라 앞쪽으로 밀지, 뒤로 밀지 정해진다.

---

3. list 컨테이너

시퀀스 컨테이너로 순서를 유지하나, 노드 기반 컨테이너(at, [] 연산자 사용 X)로 이중 연결 리스트로 구현된다.

• 인터페이스와 특징

• 생성자

생성자	설명
list lt	빈 컨테이너
list lt(n)	기본값으로 초기화된 n개의 원소를 갖는다.
list lt(n,x)	x값으로 초기화된 n개의 원소를 갖는다.
list lt(lt2)	lt2 컨테이너의 복사본이다.
list lt(b,e)	[b,e) 값으로 초기화된 원소를 갖는다.

 

• 멤버 형식 (디큐의 기능 + 추가기능)

제거
remove(x)	원소 x들을 모두 제거한다
remove_if(pred)	pred(단항 연산자)가 참인 경우를 모두 제거한다

특수
merge(lt2)	lt2를 lt로 합병 정렬(오름차순)을 한다.
merge(lt2, pred)	pred를 참으로하는 lt2의 원소들만 lt로 합병 정렬한다.
reverse()	순차열을 뒤집는다.
sort()	오름차순(less)으로 정렬한다
sort(pred)	모든 원소를 pred(이항 연산자) 기준으로 정렬한다.
splice(p, lt2)	반복자 p가 가리키는 위치에 lt2의 모든 원소를 잘라 붙인다
splice(p, lt2, q)	반복자 p가 가리키는 위치에 lt2의 반복자 위치의 원소를 잘라붙인다.
splice(p, lt2, b, e)	반복자 p가 가리키는 위치에 lt2의 [b,e) 원소들을 잘라붙인다.
unique()	인접한 원소의 값이 같다면 중복들을 제거한다
unique(pred)	인접한 원소가 pred(이항 조건자)에 기준에 맞다면 중복을 제거한다.

 

• 연산자와 템플릿 멤버 형식

기존 시퀀스 컨테이너와 같다

---

• 구조와 특징

• 시퀀스 컨테이너 : 순서 유지
• 노드 기반의 컨테이너 : at(), [] 연산자 사용 불가능하고 양방향 반복자(++,--)로 탐색한다.
• 양끝 삽입/삭제가 가능하다
• 삭제(remove, remove_if)가 추가되었다.

list<int> lt; // 1->2->3->1->4->5->1->1 일 때
lt.remove(1); // 원소 1인 노드들을 모두 제거한다.

for(auto iter = lt.begin(); iter != lt.end(); ++iter)
	cout << *iter << endl; // 2->3->4->5

bool Predicate(int n) // 단항 조건자
{
    return n >= 10 ^^ n <= 30;
}

int main()
{
    list<int> lt; // 1->2->3->4->5->1
    
    lt.remove_if(Predicate); // 10~30 값들 제거
    
    // 4->5
}

※ 리스트의 경우 추가/삭제시 기존 원소들을 당기거나, 밀 필요가 없다.

 

• 정렬(merge,sort), 이어붙이기(splice), 인접 중복 제거(unique), 원소 뒤집기(reverse)

lt.sort(greater<int>()); // greater<int>() 조건자로 정렬, 내림차순(>)
lt.sort(less<int>()); // less<int>() 조건자로 정렬, 오름차순(<)

struct Greater
{
    bool operator () (int lt, int rt) const
    {
        return lt > rt;
    }
}

lt.sort(Greater()); // 사용자 정의 조건으로 정렬

lt.merge(lt2, less<int>()); // 오름차순으로 lt와 lt2를 합병 정렬한다.

list<int> lt; // 1->2->3->4
list<int> lt2; // 10->20->30

list<int>::iterator iter = lt.begin() + 2; // 3 위치
lt1.splice(iter, lt2); // 1->2->10->20->30->3->4

bool Predicate(int fst, int snd)
{
    return snd-fst <= 0;
}

int main()
{
    list<int> lt; // 1->1->2->3->3->4->5->1
    
    lt.unique(Predicate);
    // 1->2->3->4->5->1
    // 만약 조건이 없는 unique면? 1->2->3->4->5
}

※ 리스트 sort : 알고리즘의 경우 연속 메모리 기반이다보니, 리스트는 딸 ㅗ구현해준 것이다.