STL - 시퀀스 컨테이너

★ 컨테이너의 종류

→ 컨테이너는 deque, list, queue, priority_queue, stack, vector, map, multimap, set, multiset, bitset 이렇게 11가지 타입의 컨테이너형이 있다. ( 원래 추가적으로 더 존재하기는 하나 그것은 훗날 설명하고자 합니다. )
타입으로 분류하면 위와 같이 되고, 개념적으로 분류하면 기본 컨테이너, 시퀀스 컨테이너(Sequence Container), 결합 컨테이너 (Associative Container)가 있다.


★ 기본 컨테이너

→ 기본 컨테이너라는 개념에 대응하는 컨테이너 타입은 없다. 하지만 대부분의 컨테이너들은 이 기본 컨테이너의 요소를 가지고 있다. 즉 공통적 요소가 된다.

→ 기본 컨테이너는 다음과 같은 특성을 가지게 된다.

1. X::iterator (X는 컨테이너 타입)
→ X에 대한 이터레이터 타입

2. X::value_type
→ X의 데이터형 매개변수 타입

3. X u;
→ 크기가 없는 컨테이너 u 생성

4. X();
→ 크기가 없는 익명의 컨테이너 생성

5. X u( a ); 혹은 X u = a;
→ 복사생성자

6. ( &a )->~X();
→ 컨테이너의 모든 원소에 대해 소멸자를 적용

7. a.begin();
→ 컨테이너의 첫 번째 원소를 지시하는 이터레이터 리턴

8. a.end();
→ past-the-end (마지막 원소 바로 다음 지점) 지점의 이터레이터 리턴

9. a.size();
→ a 컨테이너의 원소 갯수 리턴( unsigned 정수 타입 )

10. a.swap( b );
→ a와 b의 내용을 맞바꾼다. ( 리턴값 없음 )

11. a == b
→ a와 b가 크기가 같고 a의 위치에 따른 b의 각각의 위치의 원소가 동일하면 true를 리턴, 아니면 false를 리턴 ( bool 타입 )

12. a != b
→ !(a == b) 와 동일 ( bool 타입 )


★ 시퀀스 컨테이너

→ 기본 컨테이너에서 더 추가된 개념이다.
deque, list, queue, priority_queue, stack, vector 가 여섯가지의 컨테이너들을 시퀀스 컨테이너라고 부르게 된다.

→ 시퀀스는 원소들이 직선 순서대로 배치가 되있으며 첫 원소 ~ 마지막 원소가 일직선으로 존재하며 첫 원소와 마지막 원소를 뺀 중간의 원소들은 반드시 앞 뒤로 인접한 원소를 각각 하나씩 가지고 있게 된다.
또한 시퀀스는 이터레이터가 최소한 전방 이터레이터는 되어야 한다.

* 시퀀스 컨테이너에 있어야 할 사항
→ n은 정수, X는 컨테이너 타입, p, g, i, j는 이터레이터, t는 컨테이너의 데이터형 인수 타입의 객체 혹은 값

X a( n, t ); → n개의 값 t로 이루어진 시퀀스 a 선언
X( n, t ); → n개의 값 t로 이루어진 익명 시퀀스 생성
X a( i, j ); → [ i, j ) 범위의 값으로 초기화된 a 생성
X( i, j ); → [ i, j ) 범위의 값으로 초기화된 익명의 시퀀스 생성
a.insert( p, t ); → p 지점 앞에 t 의 복사본 삽입
a.insert( p, n, t ); → p 지점 앞에 t 의 복사본을 n개 삽입
a.insert( p, i, j ); → p 지점 앞에 [ i, j ) 범위의 원소들의 복사본 삽입
a.erase( p ); → p 가 지시하는 원소 삭제
a.erase( p, q ); → [ p, q ) 범위의 원소들 삭제
a.clear(); → 컨테이너의 모든 원소 삭제

* 몇몇의 시퀀스 컨테이너에만 있는 사항

a.front() → 컨테이너의 첫번째 원소 값의 참조를 리턴 < vector, list, deque 에서 사용 가능 >
a.back() → 컨테이너의 마지막 원소 값의 참조를 리턴 < vector, list, deque 에서 사용 가능 >
a.push_front( t ) → 컨테이너의 가장 앞에 원소를 하나 추가 < list, deque 에서 사용 가능 >
a.push_back( t ) → 컨테이너의 맨 뒤에 원소를 하나 추가 < vector, list, deque 에서 사용 가능 >
a.pop_front() → 맨 앞에 있는 원소 하나를 제거(리턴값 없음) < list, deque 에서 사용 가능 >
a.pop_back() → 맨 뒤에 있는 원소 하나를 제거(리턴값 없음) < vector, list, deque 에서 사용 가능 >
a[n] → (배열과 비슷하게) n번째 원소의 참조 리턴 < vector, deque 에서 사용 가능 >
a.at( n ) → 위의 a[n]과 동일한 기능 < vector, deque 에서 사용 가능 >


★ vector 컨테이너

→ 컨테이너 중 배열과 가장 비슷하며 임의접근이 가능하다.
vector는 시퀀스 컨테이너이기도 하지만 가역성 컨테이너 ( reversible container )이기도 하다. 즉, 이 말은 역순서로 움직이는 reverse_iterator 를 사용할 수 있다는 것이기도 하다. reverse_iterator 는 써있는 이름 그대로 거꾸로 움직이는 이터레이터다. reverse_iterator 에서의 ++ 연산은 일반 iterator의 -- 연산과 같고, reverse_iterator 에서의 -- 연산은 일반 이터레이터의 ++ 연산과 같다. 이 때문에 두 개의 클래스 메서드가 더 추가된다.

rbegin()
→ 뒤집힌 시퀀스의 첫번째 이전원소 (실제는 마지막 원소 다음인 past-the-end 부분)의 이터레이터를 리턴 ( 리턴타입은 reverse_iterator )
rend()
→ 뒤집힌 시퀀스의 마지막 원소(실제는 첫번째 원소 부분) 지점 이터레이터를 리턴 ( 리턴타입은 reverse_iterator )

→ 이 두개의 메서드를 이용하여 이런 것이 가능하다.

for_each( dice.rbegin(), dice.rend(), Show );
→ 원래 일반 이터레이터를 썼다면 dice란 컨테이너를 순방향으로 출력하는 기능인데, 리버스 이터레이터를 사용함으로써 dice 컨테이너를 역순으로 돌아가며 원소들을 출력하게 된다.


★ deque 컨테이너

→ 여러가지로 vector와 많이 비슷한 컨테이너. 임의 접근이 가능하고 가역성 컨테이너이기 때문에 reverse_iterator 사용도 가능하다.
이것과 vector의 가장 큰 차이는 선두의 원소 삽입/삭제 부분이 비례시간을 가지는 vector에 비해 deque는 고정시간을 갖는다는 것이다. ( 즉, deque가 선두 원소 삽입/삭제가 더 빠르며, 그 때문인지 vector는 push_front(), pop_front() 메서드 자체가 없다. )
하지만 vector에 비해 deque는 임의접근이나 시퀀스 중간의 원소 삽입/삭제가 느린편이다.( 둘다 비례시간의 속도를 냄 )


★ list 컨테이너

→ 이중 링크드 리스트를 나타내는 컨테이너이다. 첫번째와 마지막 원소를 제외한 중간 원소들은 앞뒤로 하나씩 링크가 되어 있어서 전후방으로 훑을 수가 있다.
이것과 vector의 큰 차이는 원소 삽입/삭제 부분인데, vector는 최후방 부분의 원소 삽입/삭제만 고정시간이고 나머지 부분은 비례시간을 가지는 데에 비해 list는 어느곳에서도 삽입/삭제에 있어서는 고정 시간을 자랑한다.
결국 빠른 접근을 요하는 컨테이너를 vector (또는 deque)를 선택하는 것이 좋고, 빠른 삽입/삭제가 필요하다면 list를 선택하는 것이 좋다.

→ list 또한 가역성 컨테이너라 reverse_iterator의 사용이 가능하다. 하지만 임의접근이 불가능하기 때문에 배열처럼 [] 연산자 사용이 불가능하며 이터레이터에서 +, - 연산 등도 안된다.
또한 list의 이터레이터는 컨테이너에서 원소가 삽입되거나 삭제되도 같은 원소를 가리킨다는 특징을 지니고 있다.

→ list 만을 위한 몇몇개의 멤버함수들이 존재한다.

void merge( list<T, Alloc> &x ) // list< T, Alloc > 는 그냥 리스트 컨테이너 타입이라 생각하며 된다.
→ 리스트 x를 호출한 리스트와 합병한다.( 합한다. ) 두 리스트 모두 소팅이 완료 되있어야 하고 합병된 리스트는 호출한 리스트에 남게 되고 리스트 x는 비워진다. 해당 함수는 비례시간 복잡성을 가진다.

void remove( const T &val )
→ 리스트에 들어있는 모든 val을 제거한다. (val과 같은 원소들은 모두 제거) 이 함수는 비례시간 복잡성을 가진다.

void sort()
→ < 연산자를 사용하여 리스트를 소팅한다. 원소가 N개라면 복잡성은 N log N 이다. 참고로 list는 임의접근이 안되기 때문에 <algorithm>에 정의된 sort()를 쓸 수 없으며 소팅을 하려면 해당 멤버 함수를 호출해야 한다. ( 아마도 속도는 <algorithm>에 있는 것이 더 빠를 것이라고 생각됨 )

void splice( iterator pos, list<T, Alloc> x )
→ pos의 위치 앞에 리스트 x의 내용을 삽입하고 x는 비워진다. 이 함수는 고정시간 복잡성을 가진다.
( 사실상 insert()보다 이게 더 빠를 거라 생각됨 )

void unique()
→ 같은 원소들의 연속된 그룹을 하나의 원소로 만든다. 이 함수는 비례시간 복잡성을 가진다.
ex) list 원소가 2, 2, 2, 2, 2, 1, 4, 8, 6, 6, 4, 4, 6, 5 일때
unique() 이후의 결과는 2, 1, 4, 8, 6, 4, 6, 5 로 바뀌게 된다.


★ queue 컨테이너

→ queue의 특징은 FIFO( First In First Out : 첫번째로 들어가는 것이 제일 먼저 나감 ) 이다. 즉, 물이 흐르는 파이프 라인을 생각하면 된다.
queue는 deque ( deque : double-ended queue 의 줄임말 ) 에 비해 매우 제한적인데, 일단은 임의접근이 금지이며 queue 자체에 이터레이터도 없어서 컨테이너를 훑어볼 수도 없다.
이렇다 보니 큐 만이 가지고 있는 기본적인 연산만으로 이것을 사용할 수 밖에 없다. 아래는 멤버함수의 목록이다.

bool empty() const → 큐가 비어있으면 true, 아니면 false를 리턴
size_type size() const → 큐 안의 원소의 갯수를 리턴
T& front() → 큐의 가장 첫번째 원소를 리턴
T& back() → 큐의 가장 마지막 원소를 리턴
void push( const T& x ) → 큐의 마지막 부분에 x를 삽입
void pop() → 큐의 가장 앞 부분의 원소를 삭제 (리턴 없음)

→ 즉, 큐의 마지막 부분에 원소를 넣고 처음 부분에서 그 원소가 빠져나가는 형태이다. 큐에 있는 어떤 값을 쓰려면 이것이 빠져나가기 직전에 front()를 통해 원소를 받고 pop()을 통해 이 원소를 삭제하는 방식이다


★ stack 컨테이너

→ stack은 FILO ( First In Last Out : 첫번째로 들어간 것이 가장 마지막에 나감 ) 하다는 것만 빼면 queue와 비슷하게 많이 제한적이다. 임의접근이 안되며 이터레이터도 없다.
이것도 멤버함수들이 queue와 비슷하다.

bool empty() const → 큐의 그것과 동일
size_type size() const → 큐의 그것과 동일
T& top() → 스택의 꼭대기에 있는 원소의 참조를 리턴
void push( const T& x ) → 스택의 꼭대기에 원소를 삽입
void pop() → 스택의 꼭대기에 있는 원소를 삭제


★ priority_queue

→ 이 컨테이너는 <queue> 에 선언되어 있으며 queue와 지원하는 연산이 같다. 다만 queue와의 차이점은 가장 큰 항목이 큐의 선두로 나가게 된다는 것이다. 즉, 가장 큰 값이 우선적으로 나가게 된다.
하지만 위와 같은 경우는 priority_queue가 디폴트로 생성되었을때의 경우이고, 생성시에 생성자에 미리 정의된 함수 객체를 넣어서 큐의 선두로 나가는 순서를 바꿀 수 있는 듯 하다.
STL 중 하나인 함수 객체는 다음에 설명하고자 한다.