[C++ STL] 3-1. 컨테이너 - 시퀀스 컨테이너(sequence container)

공부 내용을 정리하는 목적 이므로 참고용으로만 읽어 주시기 바랍니다. 틀린 부분에 대한 지적은 감사합니다.

1. 시퀀스 컨테이너(sequence container) 특징

• 메모리 상에서 모든 요소가 직선 순서로 배치되어 순서가 존재해야 한다. 즉, 첫 번째 요소와 마지막 요소를 제외한 모든 요소는 앞뒤로 컨테이너의 요소가 존재해야 한다.
• 반복자가 이동할 때 요소의 순서가 변경되지 않음을 보장하기 위해 반복자는 최소 순방향 반복자를 사용해야 한다.
• 시퀀스 컨테이너는 직선 순서로 배치되어 명확한 순서가 존재하므로 특정 위치에 대한 참조가 가능해야 한다.

2. vector

벡터는 동적 배열의 클래스 템플릿으로 가장 기본이 되는 컨테이너이다.

벡터는 데이터가 들어가고 나올 수 있는 입출구가 뒤쪽 하나이며 앞쪽은 막혀있는 형태이다. 따라서 데이터를 넣을 때도 뒤에서부터 쌓이고 데이터를 꺼낼 때는 맨뒤에서부터 뺄 수 있다.

또한 시퀀스 컨테이너의 경우 요소가 메모리상에서 연속적으로 존재해야 한다고 했다. 벡터는 그 특징을 위해 메모리를 연속으로 할당받는데 문제는 요소가 추가될 때이다. 요소가 추가되면 이미 할당받은 메모리 공간의 바로 옆을 추가로 할당받아야 하는데 이미 해당 부분의 메모리를 사용 중일 경우 순서대로 저장할 수 없게 된다. 따라서 벡터는 요소가 추가되어 메모리를 추가로 할당해야 할 경우 추가된 요소를 담을 수 있을 만큼 새로 메모리를 재할당하고 기존의 원소를 전부 복사하여 가지고 간다. 따라서 요소가 하나씩 반복적으로 추가될 때 하나의 요소를 위해 계속 재할당을 수행하면 시간을 너무 잡아먹기 때문에 재할당시 메모리의 크기를 (기존 메모리 크기 + 기존 메모리 크기/2) 만큼 할당하여 일정 요소는 재할당 없이 저장할 수 있도록 동작한다.

즉, 벡터(vector) 객체는 요소가 추가되거나 삭제될 때마다 자동으로 메모리를 재할당하여 크기를 동적으로 변경합니다.

 

문법)

#include <vector> 벡터 헤더를 추가해 주어야 사용할 수 있다.

vector<타입> 벡터명(생성자 인수)

 

생성자 인수를 입력하지 않을 경우 빈 벡터가 생성된다. 생성자 인수를 입력할 경우를 정리하면 다음과 같다.

vector v(n) : n은 원소의 개수를 의미한다.
vector v(n, x) : x값으로 초기화된 n개의 원소
vector v(v2) : 복사 생성자 형식, v2라는 컨테이너를 그대로 복사한 벡터 컨테이너
vector v(b, e) : 반복자의 구간[begin, end)로 초기화된 원소를 갖는다

 

예시와 함께 자주 쓰이는 벡터의 멤버 함수를 정리하자.

v라는 빈 벡터 객체를 생성하고 push_back() 멤버 함수를 사용하여 벡터에 요소를 추가하였다. 요소가 추가될 때 벡터의 메모리 크기를 확인해보면 요소의 개수보다 많이 할당되어있는 것을 확인할 수 있다. 원래 5개의 요소를 가지고 있을 때는 메모리의 크기가 6이다. 거기서 5개를 더 추가하기 위해 메모리를 재할당하는데 6+6/2 = 9이므로 10개를 담기에는 크기가 부족하다 따라서 해당 크기에서 한 번 더 할당했을 때의 크기인 9+9/2 = 13을 할당해 10개의 원소를 담게 되는 것이다.

 pop_back()은 벡터의 요소를 하나씩 꺼내 주는 멤버 함수이다. 따라서 5개의 원소를 꺼내게 되며 요소를 꺼내도 이미 할당된 메모리의 크기는 줄어들지 않는다.

 

 

또한 벡터는 순서가 존재하기 때문에 인덱스를 통한 접근이나 참조를 통한 접근이 가능하다. front()와 back() 함수는 벡터의 첫 번째 요소와 마지막 요소를 참조해주는 함수이다.

또한 여기서 사용한 begin과 end는 해당 컨테이너의 반복자를 반환하는 함수이다.

begin() 시작을 가리키는 반복자를 반환하는 함수이다. A~E라는 요소를 가진다면 A를 가리킨다. 
end() 끝을 가리키는 반복자를 반환하는 함수이다. end() 함수는 만약 요소가 A~E까지 있다면 E가 아니라 past-the-end라는 끝을 뜻하는 원소를 가리키고 있다. 따라서 위의 예시에서 마지막 요소를 참조할 때 end-1로 마지막 원소를 참조한 것이다.

 

벡터는 많은 멤버 함수를 가지고 있지만 그중 자주 쓰이는 몇 가지를 정리하면 다음과 같다.

v.back() : v의 마지막 원소를 참조한다.
v.front() : v의 첫 번째 원소를 참조한다.

v.begin() : v의 시작을 가리키는 반복자를 반환한다.

v.end() : v의 끝을 가리키는 반복자를 반환한다.
v.clear() : v의 모든 원소를 제거한다.

v.earase(iterator) : 반복자가 가리키는 걸 지움

q = v.insert(p, x) : p가 가리키는 위치에 x값을 삽입한다. q는 삽입한 원소를 가리키는 반복자
v.insert(p, n, x) : p가 가리키는 위치에 n개의 x값을 삽입한다.
v.insert(p, b, e) : p가 가리키는 위치에 반복자 구간[b, e) 원소를 삽입한다.

v.push_back(x) : v의 끝에  x를 추가한다
v.pop_back() : 마지막 원소를 제거한다.

v.size() : v원소의 개수 리턴 값은 unsigned int가 나옴 (모든 컨테이너가 가진 함수)
v.resize(n) : v의 크기를 n으로 변경하고 확장되는 공간을 기본값으로 초기화
v.resize(n, x) : v의 크기를 n으로 변경하고 확장되는 공간의 값을 x로 초기화

v.capacity() : 실제 할당된 메모리 공간의 크기(vector만이 가지고 있는 함수)

3. deque

vector 컨테이너를 개선한 컨테이너이다.

deque는 double-ended queue를 의미하며 양쪽에 끝이 있는 큐(queue)라는 뜻이다. vector는 뒤쪽에서만 요소의 삽입과 삭제가 가능했지만 deque는 양 끝에서 빠르게 요소를 삽입하거나 삭제할 수 있다.

또한 메모리의 할당 정책과정에서 vector의 단점을 개선했다. vector는 하나의 메모리 블록을 사용해 배열처럼 정수 연산만으로 원소에 접근할 수 있지만 하나의 메모리 블록을 사용하기 위해 메모리를 새로 할당하고 원소를 그대로 복사하여 옮기고 기존의 원소를 삭제하기 때문에 성능의 저하가 발생한다.

deque는 이러한 단점을 개선하기 위해 원소 추가 시 메모리가 부족하다면 일정한 크기의 새로운 메모리 블록을 할당하여 추가할 원소를 그곳에 저장하고 이전 원소를 복사하고 메모리를 제거하는 연산을 수행하지 않는다. 즉, 여러 개의 메모리 블록을 하나의 메모리로 보이도록 하는 정책을 사용한다. 따라서 메모리가 연속적으로 존재하지 않아 vector에서 가능하던 원소들 간의 포인터 연산은 불가능하지만 해당 정책으로 인해 저장 원소가 많아 메모리 용량이 큰 경우에 원소를 확장할 때 vector에 비해 성능 저하가 덜 발생한다.

 

문법)

#include <deque>

deque<타입> 디큐명(생성자 인수)

 

생성자 인수에 대해 정리하면 다음과 같다.

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

 

간단한 예시를 통해 deque의 멤버 함수를 정리해 보면

deque는 맨뒤뿐만 아니라 맨 앞에도 원소를 추가하고 제거할 수 있다. 따라서 1은 push_back() 함수로 뒤에서 추가하고 0은 push_front() 함수로 앞에서 추가했기 때문에 컨테이너의 맨 앞에 있는 원소는 1이 아니라 0이 된다.

원소들 간의 포인터 연산은 불가하지만 []를 사용한 인덱스 접근이나 반복자를 참조하는 연산은 가능하다. 또한 앞과 뒤 두 가지 방향이 존재함에 따라 rend, rbegin과 같은 역방향 반복자도 존재한다.

 

deque가 가진 멤버 함수를 정리하면 다음과 같다.

dq.at(i) : dq의 i번째 원소를 참조한다. 

dq.back() : dq의 마지막 원소를 참조한다. 

dq.front() : dq의 첫 번째 원소를 참조한다.

dq.begin() : dq의 시작을 가리키는 반복자를 반환한다.

dq.end() : dq의 끝을 가리키는 반복자를 반환한다. 

dq.rbegin() : dq의 역 순차의 시작을 가리키는 반복자를 반환한다.  

dq.rend() : dq의 역 순차의 끝을 가리키는 반복자를 반환한다.

dq.pop_back() : dq의 마지막 원소를 제거한다. 

dq.pop_front() : dq의 첫 원소를 제거한다.  

dq.push_back(x) : dq의 끝에 x를 추가한다.  

dq.push_front(x) : dq의 앞쪽에 x를 추가한다. 

dq.clear() : dq의 모든 원소를 제거한다. 

dq.empty() : dq가 비었는지 조사한다. 

dq.size() : dq 원소의 개수 

q=dq.erase(p) : 반복자 p가 가리키는 원소를 제거한다. q는 다음 원소를 가리키게 된다. 

q=dq.erase(b, e) : 반복자 구간 [b, e)의 모든 원소를 제거한다. q는 다음 원소다 

q=dq.insert(p, x) : p가 가리키는 위치에 x 값을 삽입한다. q는 삽입한 원소를 가리킨다. 

dq.insert(p, n, x) : p가 가리키는 위치에 n 개의 x 값을 삽입한다. 

dq.insert(p, b, e) : p가 가리키는 위치에 반복자 구간 [b, e)의 원소를 삽입한다. 

dq.resize(n) : dq의 크기를 n으로 변경하고 확장되는 공간의 값을 기본값으로 초기화한다.  

dq.resize(n, x) : dq의 크기를 n으로 변경하고 확장되는 공간의 값을 x 값으로 초기화한다. 

4. list

리스트(list) 컨테이너는 vector, deque와 같은 시퀀스 컨테이너지만 노드 기반 컨테이너로 이중 연결 리스트(doubly linked list)의 클래스 템플릿 표현이다.

노드 기반 이기 때문에 [ ] 연산자나 at() 함수를 이용한 임의 접근은 불가능하지만 컨테이너의 모든 요소에서 양방향 접근(++, --)을 통해 빠른 삽입과 삭제가 가능하다. 노드 기반이기 때문에 순차열 중간에 원소를 삽입/삭제하여도 상수 복잡도(연결 연산)의 수행성능을 보인다는 점이다. 사이에 원소를 추가할 때 원소를 밀어내고 그 자리에 추가하는 개념이 아니라 자신의 앞뒤 원소를 가리키는 링크(포인터)만 바꿔주면 되기 때문에 vector나 deque보다 훨씬 빠르다.

또한 배열 기반 컨테이너의 반복자는 원소의 삽입/제거 동작시 메모리가 재할당되거나 원소의 위치가 이동할 수 있으므로 기존의 원소를 가리키던 반복자가 제대로 된 원소를 가리키지 못하는 무효화 현상이 발생할 수 있다. 하지만 리스트는 반복자가 가리키던 원소 자체가 사라지지 않는 이상 무효화 현상이 발생하지 않는다.

 

문법)

#include <list>

list<타입> 리스트명(생성자 인수);

 

list l : 빈 list 생성 

list l(n) : l은 기본값으로 초기화된 n개의 원소를 갖는다.

list l(n, x) : l은 x 값으로 초기화된 n개의 원소를 갖는다.

list l(l2) : l은 리스트 l2의 복사본

list l(b, e) : l은 반복자 구간 [b, e)로 초기화된 원소를 갖는다. 

 

리스트의 멤버 함수는 vector, deque에서 사용하던 함수를 동일한 기능으로 사용할 수 있다.

push_back을 사용하여 리스트의 뒷부분에 원소를 추가하고 erase() 함수를 통해 반복자가 가리키는 곳의 원소를 제거할 수 있다. 이처럼 deque, vector에서 사용하던 멤버 함수를 그대로 사용할 수 있고 추가적으로 list만 사용하는 멤버 함수가 존재한다.

이처럼 sort() 함수를 이용해 리스트 요소를 오름차순으로 정렬하거나

인접한 원소에 동일한 값이 있을 경우 하나로 합치는 등 list에만 존재하는 멤버 함수가 존재한다.

 

list에서만 사용할 수 있는 멤버 함수를 정리하면 다음과 같다.

l.merge(l2) : l2를 l로 하나로 정렬하며 결합한다. 

l.merge(l2, pred) : l2를 l로 하나로 정렬하며 결합한다. pred(조건자)를 기준으로 합병한다.
l.remove(x) : l이 가진 x 원소를 모두 제거한다. 

l.remove_if(pred) : pred(단항 조건자)가 true인 모든 원소를 제거한다. 

l.sort() : l의 모든 원소를 오름차순으로 정렬한다.  

l.sort(pred) : l의 모든 원소를 pred(조건자)를 기준으로 정렬한다. 

l.splice(p, l2) : 반복자 p가 가리키는 위치에 l2의 모든 원소를 잘라 붙인다. 

l.splice(p, l2, q) : 반복자 p가 가리키는 위치에 l2의 반복자 q가 가리키는 원소를 잘라 붙인다. 

l.splice(p, l2, b, e) : p가 가리키는 위치에 l2의 순차열 [begin, end)를 잘라 붙인다. 

l.unique() : 인접한 원소의 값이 같을 경우 동일한 값의 원소를 하나로 합친다.  

l.unique(pred) : 인접한 원소가 pred(이항 조건자)의 기준에 맞다면 원소를 하나로 합친다.