[C++ 프로그래밍 / STL] Chapter1. 순차 컨테이너

Chapter1. 순차 컨테이너

순차 컨테이너는 항목들이 순서를 갖는 컨테이너이다. vector는 동적 배열을, list는 양방향 연결 리스트를, deque은 양방향 큐를 구현한다.

1. vector

vector는 헤더에 정의되어 있는 동적배열 자료 구조이며 다음과 같이 정의되어 있다.

template <typename _Ty, typename _Alloc = allocator<_Ty>> class vector;
template <typename _Alloc> class vector<bool, _Alloc>; //템플릿 특수화

템플릿 인자로는 항목 타입과 할당자 타입을 받는데 할당자는 디폴트로 제공되는 버전이 있으므로 일반적으로 하나의 템플릿 인자만 사용한다. 특히 vector에 대해서는 특수화되어 다르게 구현되어 있으며 bool 타입의 대리자를 통해 인터페이스가 제공되지만 실제로는 비트 단위로 항목을 다룸으로써 메모리 소모량을 줄여준다.

• 구조와 성능

동적 배열이란 런타임에 크기가 변할 수 있는 배열을 의미하며, 크기를 컴파일 타임에 특정할 수 없기 때문에 스택 메모리를 사용하지 못하고 힙 메모리를 사용한다. vector 인스턴스 자체는 스택, 힙, 데이터 메모리에 모두 할당될 수 있지만 vector 인스턴스가 관리하는 배열은 힙 메모리에 할당된다.
그리고 배열이기 때문에 모든 항목들은 메모리 상에 연속해 있다. 따라서 랜덤 액세스가 가능하므로 랜덤 액세스 반복자를 지원한다. 반복자 대신 size_t 타입의 인덱스를 통한 룩업도 가능하다. 따라서 개별 항목에 대한 룩업은 상수 시간 성능을 가진다.
삽입/삭제는 어느 위치에서든 가능하지만 마지막 항목 아니라면 선형 시간 성능을 갖는다. 그 이유는 메모리 상에서 각 항목이 연속이 되도록 하기 위해서 삽입하거나 삭제한 위치 뒤의 모든 항목들을 이동시켜주어야 하기 때문이다.
반면 마지막 항목의 삽입/삭제는 분할 상수 시간 성능을 갖는다. 상수 시간이 아니라 분할 상수 시간인 이유는 vector의 메모리 할당 방식 때문이다. vector는 그 자체로 최대 항목 수를 제한하지 않고 있고 필요에 따라 자동으로 확장된다. 그러나 모든 항목들이 메모리 상에서 연속인 성질을 유지하면서 확장하기 위해서는 배열이 통째로 자리를 옮겨야 할 수 있다.
vector가 가지고 있는 항목의 개수를 vector의 size라고 하며 size() 메서드로 확인할 수 있다.
vector의 항목들을 이사시키지 않고 확장할 수 있는 크기를 capacity라고 하며 capacity() 메서드로 확인할 수 있다.
이사를 하게 될때 capacity가 확장되는 양은 컴파일러에 따라, vector의 size에 따라 구체적으로 다를 수 있지만 size가 클수록 한번에 확장되는 capacity도 커진다.
reserve(size_t) 메서드를 이용하면 size의 변화 없이 capacity를 늘릴 수 있다. 최대 size를 알 수 있거나 예상할 수 있다면 미리 capacity를 확보해 놓음으로써 이후의 불필요한 메모리 할당 및 복사 관련 오버헤드를 피할 수 있다.

• 생성자

벡터가 제공하는 생성자는 대표적으로 세 가지가 있다.

vector<int> v1; //디폴트 생성자
vector<int> v2(10, -1); //첫번째 파라미터는 size_t, 두번째 파라미터는 const int& T
vector<int> v3 {1,2,3,4,5}; //initializer_list<T>

v1는 디폴트 생성자로 생성한 객체이다. 이 경우 벡터의 size와 capacity는 모두 0인 채로 생성된다.
v2는 size와 각 항목에 대한 초기화 값을 인자로 받아 생성된다. size를 설정한다는 것은 그 만큼의 항목을 생성한다는 의미와 같다. size 뿐만 아니라 capacity도 첫번째 인자와 같게 생성되기 때문에 그 크기 이상으로 확장하려고 하면 이사가 발생한다. 한편 두 번째 인자인 초기화 값은 항목이 디폴트 생성자를 지원하거나 빌트인 타입인 경우 생략 가능하다. 디폴트 생성자를 지원하지 않는 타입이라면 항목의 생성이 불가능하기 때문이다.
v3는 initializer_list를 인자로 받는데 이 때 나열되는 각 항목은 모두 같은 T와 같은 타입이어야 한다. 이 버전의 생성자를 호출하기 위해서는 중괄호를 이용해 초기화하는 유니폼 초기화 구문을 사용하거나 괄호 내에 중괄호를 중첩하여 나열해야 한다.
일반적으로 생성자를 호출하거나 모든 종료의 초기화에 있어서 중괄호를 이용한 유니폼 초기화 구문을 사용하는 것은 바람직하다고 여겨지지만 주의해야 하는 상황이 있다.

vector<int> v {5, 1};
cout << v.size(); //output : 2

벡터의 크기와 초기값을 인자로 받는 버전의 생성자가 호출되길 기대하고 위와 같은 코드를 작성할 수 있다. 그런데 공교롭게도 유니폼 초기화 구문을 사용하였으며 넘겨준 인자가 모두 int 타입이고 T도 int 이므로 initializer_list를 인자로 받는 버전의 생성자가 더 정확하게 타입이 부합한다. 따라서 v의 크기는 2이며 첫 번째 항목이 5, 두 번째 항목이 1인 vector가 된다.
이 외에도 복사 생성자, 이동 생성자 등을 지원하며 각 항목에 대해 복사 및 이동을 수행한다.

• 복제와 대입

vector 클래스의 복제 연산자와 대입 연산자는 저장된 항목들에 대해 깊은 복제를 하도록 구현되어 있다. 때문에 vector 객체를 전달할 때는 참조형 또는 const 참조형으로 전달하여 복제 오버헤드를 피해야한다.
일반적인 복제와 대입 말고도 assign 메서드가 제공되는데 앞서 설명한 생성자의 두 번째 버전과 세 번째 버전과 같은 파라미터를 갖는다. 이 메서들는 현재 저장된 항목을 모두 삭제하고 새로운 항목을 추가하는 것으로 vector 객체를 재사용할 때 유용하다.

vector intVector(10, 0);
//...
intVector.assign(5, 100);
//...
intVector.assign({1,2,3,4});

• 항목 룩업

가장 기본적인 룩업 방법은 []연산자이다. 이 연산자를 활용하면 vector를 raw 배열과 같이 활용할 수 있다. 인덱스 연산을 통해 반환되는 것은 항목의 참조자이다.
인덱스 연산을 통한 항목 룩업시 유효한 범위를 벗어나는 인덱싱에 대해서는 표준 동작이 정의되어 있지 않다. 컴파일러에 따라 처리 방식이 다를 수 있는데 예를 들어 ms vs c++은 디버그 모드 컴파일인 경우 런타임 에러를 발생시키고 릴리즈 모드 컴파일인 경우 성능을 우선하여 경계 검사를 하지 않는다.
at() 메서드 또한 인덱스 연산과 마찬가지로 항목을 왼값으로 리턴해주지만 표준에 의해 범위를 벗어나는 인덱싱에 대하여 out_of_range 익셉션을 발생시키도록 되어 있다.
front() 메서드나 back() 메서드를 통해 첫 항목이나 마지막 항목을 룩업할 수도 있다.

vector<int> v {1,2,3,4,5};
v[2] = 0; //인덱스 연산을 통한 룩업
v.at(3) = -1; //at 메서드를 통한 룩업
v.front() = 2; //첫번째 항목의 참조자 리턴
v.bakc() = -3; //마지막 항목의 참조자 리턴

• 반복자

vector는 랜덤 액세스 반복자를 제공함으로 앞 또는 뒤로 옮기거나 임의의 위치로 점프할 수 있다. 항목 룩업시 인덱스를 이용하는 것이 일반적이나 임의의 위치에 삽입 또는 삭제가 필요한 경우에는 반복자를 써야만 한다.

vector<int> intVector(10, 0);
auto it = intVector.begin();
it += 5;
--it;
*it = 4;

반복자는 포인터 정도의 안정성 밖에 안된다. 즉, 댕글링 포인터 등의 버그에 취약하며 사용에 유의해야함을 의미한다. 반복자의 비교시 같은 객체에 대한 반복자인지 검증하지 않기 때문에 이로 인해 무한 루프를 만들어 내기도 쉽다. 따라서 vector 전체를 순회해야 한다면 범위 기반 for문을 사용하는 것을 권장한다.

vector<int> intVector;
auto it = intVector.end();
*it = 10; //댕글링 포인터 버그

vector<int> v1(10), v2(10);
for (auto it = v2.begin(); it != v1.end(); ++it) //무한 루프
{
	//...
}
for (auto& item : v1) //범위 기반 for문
{
	//...
}

또한 반복자는 쉽게 무효화 될 수 있다. 예를 들어 항목을 삽입했을 때 이사가 발생할 수 있고, 그런 경우 기존에 저장해 둔 반복자는 모두 무효이므로 사용해서는 안된다. 또 다른 경우로 중간의 항목을 하나 삭제했다면 그 이후의 반복자는 원래 가리켜야 할 항목의 다음 항목을 가리키게 된다.

• 항목 삽입/삭제

push_back 메서드는 가장 보편적인 항목 삽입 방법이다. vector 끝 부분에 항목을 삽입하므로 분할 상수 시간 성능을 가지며 왼값을 받는 버전과 오른값을 받는 버전이 오버로딩 되어 있어 오른값 인자의 경우 이동 시맨틱이 적용된다.

vector<int> v;
v.reserve(5);
for (int i = 0; i < 5; ++i)
	v.push_back(10);

insert 메서드는 임의의 위치에 항목을 삽입할 수 있도록 해준다. 마지막 항목 위치가 아니라면 선형 시간 복잡도를 가지며 마찬가지로 이동 시맨틱도 지원한다. 특히 insert는 push_back과 달리 삽입할 항목의 수와 초기 값을 함께 넘기거나 initializer_list를 인자로 넘겨 여러 항목을 동시에 삽입할 수 있게 해준다.

vector<int> v;
v.reverse(10);
for (int i = 0; i < 5; ++i)
	v.push_back(1);
v.insert(v.begin(), 2); //{2,1,1,1,1,1}
v.insert(v.begin() + 2, 2, 3); //{2,1,3,3,1,1,1,1}
v.insert(v.end(), {4,5}); //{2,1,3,3,1,1,1,1,4,5}

또한 push_back과 insert에 대응되는 emplace_back과 emplace가 있다. 이들은 항목을 생성하고 나서 인자로 전달하는 대신에 항목을 생성하기 위한 인자를 직접 전달함으로써 메서드 내부에서 항목이 생성될 수 있게 해준다. push_back이나 insert가 이동 시맨틱을 지원한다고 하더라도 이들은 생성 + 이동 생성의 비용을 지불하는데 반해 emplace 버전들은 생성 비용만 지불하므로 좀 더 효율적이다.

struct point {int x, y; };
vector<point> v;
v.reverse(2);
v.emplace_back(1, 2); //v.push_back(point{1,2})와 같은 결과
v.emplace(v.begin(), 3, 4}; //v.insert(v.begin(), point{1, 2})와 같은 결과

벡터의 모든 항목을 삭제할 때는 clear() 메서드를 사용한다. 항목을 모두 삭제하지만 배열의 주소는 그대로이므로 capacity는 변하지 않는다.
마지막 항목 하나를 삭제할 때는 pop_back() 메서드를 사용한다. pop_back은 삭제하는 항목을 반환하지 않기 때문에 필요하다면 삭제하기 전에 back 메서드로 접근하여 복제해둬야 한다.
임의의 위치에서 하나 또는 여러 항목을 삭제할 때는 erase 메서드를 사용한다. erase 메서드는 하나의 반복자를 받아 한 항목을 삭제하는 버전과, 두 개의 반복자를 받아 범위 내 항목들을 삭제하는 버전이 있다. 이때 반복자 쌍이 나타나는 범위는 반개방형이다.

vector<int> v {1,2,3,4,5};
v.pop_back(); //{1,2,3,4}
v.erase(v.begin() + 1); //{1,3,4}
v.erase(v.begin(), v.end() - 1); //{4}
v.clear(); //{}

만약 특정 조건을 만족하는 항목을 삭제해야 한다면 이동 삭제 패턴(remove-erase-idiom)을 적용해야 한다. 전체 항목을 순회하는 루프를 돌려서 작업을 수행하면 이차 함수의 복잡도를 가지게 되므로 굉장히 비효율적이기 때문이다.
이동 삭제 패턴이란 삭제해야하는 항목과 남겨둘 항목끼리 모이도록 옮겨서 나눈 후 삭제해야 할 항목들을 한번에 삭제하는 패턴이다. STL 알고리즘의 remove나 remove_if 함수를 활용하면 효과적으로 수행할 수 있다. 사용 예는 아래의 STL 변경 알고리즘 파트에서 볼 수 있다.

• 비교 연산

vector는 ==, !=, <, >, <=, >= 연산자들을 오버로딩하고 있다. operator ==는 두 벡터 객체의 항목 개수가 같고 순서대로 짝지어 비교했을 때 각 항목끼리 모두 같을 때 참이 된다. 이 연산자를 사용하기 위해서는 항목 타입이 operator ==를 지원해야 한다.
operator <와 operator >는 두 벡터의 각 항목을 수선대로 짝지어 비교했을 때 처음으로 서로 같지 않은 항목 쌍에 대한 <, >연산 결과를 반환한다. 이 연산자들을 사용하기 위해서는 항목 타입이 operator <를 지원해야 한다.

---

2. list

list는 헤더에 정의되어 있는 이중 연결 리스트 자료 구조이며 다음과 같이 정의되어 있다.

template <typename _Ty, typename _Alloc = allocator<_Ty>> list;

• 구조와 성능

순서가 있는 일련의 항목을 저장하지만 vector나 배열과 달리 각 항목은 메모리에서 연속으로 위치하지 않을 수 있다. 대신 각 항목이 자신의 앞 항목과 뒤 항목이 저장된 위치를 관리함으로써 전체 데이터를 순회할 수 있게 한다.
자료 구조 특성상 배열과 반대의 성능 특성을 보인다. 즉, 룩업 성능은 선형 시간 복잡도이며 삽입/삭제는 상수 시간 복잡도 이다. 따라서 룩업 성능보다 삽입/삭제 성능이 더 중요하다면 vector 대신 list를 사용하는 것이 효율적이다.

• 생성자

list의 생성자, 소멸자, 복제 생성자, 대입 연산자, 비교 연산자들은 vector의 것과 거의 같다. vector와 마찬가지로 유니폼 초기화 역시 지원된다.

list<string> lst = {"String1", "String2", "String3"};

• 항목 룩업

list가 제공하는 항목 룩업 메서드는 front()와 back() 뿐이다. 각각 첫 번째와 마지막 항목의 참조자를 반환한다. 이외의 항목에 룩업하기 위해서는 반복자를 이용해야만 한다.

• 반복자

list의 반복자는 양방향 반복자이다. vector와 다르게 랜덤 액세스가 불가능하므로 포인터 연산을 하듯 인덱스 범위를 더하거나 빼서 반복자를 이동시킬 수 없고 ++나 --연산으로 앞뒤로만 이동시킬 수 있다.

• 항목 삽입/삭제

push_front, push_back, emplace_front, emplace_back, insert, emplace, pop_front, pop_back, erase, clear, remove, remove_if 등의 메서드가 제공된다. insert, emplace, erase는 반복자를 인자로 받아 임의의 위치에 삽입/삭제를 수행해준다.
remove와 remove_if 메서드는 반복자가 아니라 값을 기준으로 삭제를 수행한다. 때문에 erase등과 다르게 선형 시간 복잡도를 갖는다. STL 알고리즘에 있는 remove, remove_if 함수보다 최적화되어 있어 조금 더 빠르게 작동한다.

• 유용한 메서드

size(): 담고 있는 항목의 개수를 반환해준다.
empty(): 비어있다면 true를 그렇지 않으면 false를 반환해준다.
resize(): size를 재설정한다. 이로 인해 새로운 항목이 생성되거나 기존 항목이 삭제된다.
splice(): 다른 list를 통째로 삽입한다. 연결될 위치의 항목만 수정하므로 상수시간에 처리된다.

list<int> list1{ 1,4,5 }, list2{ 2,3 };
auto splicePos = next(list1.begin(), 1);
list1.splice(splicePos, list2);
for (auto item : list1)
	cout << item << ' '; //1 2 3 4 5
    cout << endl << boolalpha << list2.empty(); //true

unique(): list에서 중복된 항목을 제거한다. 항목 타입이 operator ==를 제공해야 한다. STL 알고리즘에 있는 unique 함수보다 최적화되어 있어 조금 더 빠르게 작동한다.
merge(): 두 list를 정렬을 유지하며 병합한다. 각 list는 operator <를 기준으로 정렬된 상태여야 올바른 결과를 얻을 수 있다. 항목 타입이 operator <를 제공해야 한다. STL 알고리즘에 있는 merge 함수보다 최적화되어 있어 조금 더 빠르게 작동한다.
sort(): list를 stable sort한다. 항목 타입이 operator <를 제공해야 한다. STL 알고리즘에 있는 sort 함수보다 최적화되어 있어 조금 더 빠르게 작동한다.
reverse(): 항목을 역순으로 재배치한다. STL 알고리즘에 있는 revese 함수보다 최적화되어 있어 조금 더 빠르게 작동한다.

---

3. deque

double-ended queue의 약자이며 덱이라고 부른다. 다음과 같이 정의되어 있다.

template<typename _Ty, typename _Alloc = allocator<_Ty>> class deque;

이름에서 알 수 있다시피 양방향 큐 자료구조인데 항목열 중간에 대한 룩업도 제공하기 때문에 벡터와 매우 유사하다.
deque과 vector의 차이점을 정리해보면 다음과 같다.

• deque은 연속된 메모리에 항목을 저장할 필요가 없다.
• deque은 앞쪽과 뒤쪽 모두에서 상수 시간의 삽입/삭제 성능을 가진다.
• deque은 vector에 없는 push_front, pop_front 메서드가 제공된다.
• deque은 vector의 reverve, capacity 메서드처럼 내부 메모리 관리 기능을 노출하지 않는다.