STL 컨테이너 개요 / 종류 / 복사 생성자, 대입 연산자
Reference:
- "전문가를 위한 C++" / 마크 그레고리 / 한빛 미디어
- "Optimized C++" / 커트 건서로스 / 한빛 미디어
컨테이너 개요
STL에서 제공하는 컨테이너는 array, bitset을 제외하고 모두 크기를 조절할 수 있고, 원소의 추가나 삭제에 따라 자동으로 크기가 늘어나거나 줄어든다. 경계값을 벗어나는 등의 이유로 메모리 공간을 오염시켜 프로그램을 죽게 만들 뿐 아니라 최악의 경우 보안의 위협을 노출시키는 표준 C 스타일의 배열보다 안정적이라 할 수 있다.
STL에서 제공하는 컨테이너는 크게 4가지 범주로 나눌 수 있다.
1. 순차 컨테이너
- vector(동적/가변 크기 배열)
- dequeue
- list
- forward_list
- array
- 시퀀스 컨테이너는 항목을 삽입한 순서대로 저장한다.
- 모든 순차 컨테이너에는 상수 시간에 항목을 뒤에 삽입할 수 있는 멤버 함수가 있다. push_back()
- 그러나 효율적으로 항목 앞에 삽입할 수 있는 순차 컨테이너는 deque, list, forward_list 뿐이다. push_front()
- vector, deque, array는 항목에 0 ~ size-1까지 번호를 매기며 첨자(
[])를 통해 효율적으로 접근 가능하나, list, forward_list는 항목에 번호를 매기는 방법이 달라서 첨자 연산자가 없다. - vector, deque의 내부는 배열과 같은 구조로 이루어져 있다. 따라서 중간 삽입을 하면 내부 배열이 재할당될 수 있으며 모든 반복자의 포인터가 무효화 된다. 반면 list, forward_list의 인스턴스는 반복자를 유효한 상태로 유지하면서 함께 이어 붙이고, 병합할 수 있다.
2. 연관 컨테이너
- map
- multimap
- set
- multiset
- 연관 컨테이너는 항목을 삽입한 순서대로 저장하지 않고, 항목의 순서 특성에 기반해 저장한다.
- 순서가 지정된 연관 컨테이너에서는 키(key)나 항목 자체(std::set인 경우)에 정의된
operator<()처럼 순서 관계가 필요하다. - 순서가 지정된 연관 컨테이너는 균형 이진 트리를 구현하며 정렬하지 않아도 된다.
- 항목을 삽입하거나 삭제하는 분할 상환 시간은 O(logN)이다.
3. 비정렬 연관 컨테이너(해시 테이블)
- unordered_map
- unordered_multimap
- unordered_set
- unoredered_multiset
- 순서가 지정되지 않은 비정렬 연관 컨테이너는 해시 테이블로 구현한다.
- 항목을 삽입하거나 삭제하는 시간은 평균적으로 상수 시간이며, 최악의 경우 O(N)의 시간이 걸린다.
4. 컨테이너 어뎁터
- queue
- priority_queue
- stack
컨테이너 원소에 대한 요구사항
STL 컨테이너는 원소를 값을 처리한다. 원소의 복제본을 저장하고, 대입 연산자로 대입하고, 소멸자로 원소를 삭제한다.
STL을 사용하는 클래스를 작성할 때에는 반드시 복제할 수 있게(copyable) 만들어야 한다.
반대로 STL 컨테이너에서 원소를 요청하면 저장된 복제본에 대한 참조를 리턴한다.
struct Node {
int value;
Node* next;
};
int main() {
Node node1 = { 100, nullptr };
Node node2 = { 200, &node1 };
vector<Node> nodeVec;
// Node 구조체의 기본 복사생성자가 내부적으로 호출
nodeVec.push_back(node1); // 원본의 복제본을 저장한다.
nodeVec.push_back(node2);
cout << "node1 주소: " << &node1 << endl;
// => "node1 주소: 004AF994"
cout << "node2 주소: " << &node2 << endl;
// => "node2 주소: 004AF984"
cout << "node1 주소(vec): " << &nodeVec[0] << endl;
// => "node1 주소(vec): 00AC65A8"
cout << "node2 주소(vec): " << &nodeVec[1] << endl;
// => "node2 주소(vec): 00AC65B0"
}cf) Node 구조체의 기본 복사생성자가 호출된다. 따라서 포인터 필드(next)의 값(포인터)는 그대로 복사된다.
기본 복사생성자는 클래스의 기본 자료형 필드는 그대로 복사하고, 객체라면 해당 객체의 클래스에 정의된 복사생성자를 호출한다. (만약 클래스형 필드고, 해당 클래스가 복사생성자를 정의하지 않았다면, 마찬가지로 기본 복사생성자가 호출된다.)cout << "node2의 next필드(포인터): " << node2.next << endl; // => "node2의 next필드(포인터): 006FF74C" cout << "node2(vec)의 next필드(포인터): " << nodeVec[1].next << endl; // => "node2(vec)의 next필드(포인터): 006FF74C"
컨테이너를 사용하면서 호출될 수 있는 메서드는 다음과 같다.
1. 복사 생성자
복사 생성자는 기존 원소와 똑같은 원소를 새로 생성(다른 메모리 공간에)하며 기존 원소에 아무런 영향을 미치지 않고 안전하게 제거할 수 있다.
주로 1) 객체가 함수에 인수로 전달될 때, 2) 함수가 객체를 반환값으로 반환할 때, 3) 새로운 객체를 같은 클래스 타입의 기존 객체와 똑같이 초기화 할 때, 4) STL 컨테이너에 원소를 추가할 때 호출된다.
// 3) 새로운 객체를 같은 클래스 타입의 기존 객체와 똑같이 초기화 할 때 호출
// 복사 생성자 정의
Book(const Book& origin){
title = origin.title;
totalPage = origin.totalPage;
currentPage = currentPage;
..
}
int main(){
Book originBook{"HTML", 300, ..};
Book destBook(originBook); // 복사 생성자 호출
}이 복사 생성자는 원소를 컨테이너에 추가할 때마다도 호출된다. (단, emplace 메서드에선 호출되지 않는다.)
예를 들어,
// uniform initialization
// 생성자 호출
Node node1 = { 100, nullptr };
Node node2 = { 200, &node1 };
vector<Node> nodeVec;
// Node 구조체의 기본 복사생성자가 내부적으로 호출
nodeVec.push_back(node1); // 원본의 복제본을 저장한다.
nodeVec.push_back(node2);
// node2의 next필드(포인터): 00EFF92C
// node2(vec)의 next필드(포인터): 00EFF92C
// 같은 포인터push_back에서 node2의 원본을 복사 생성자를 통해 벡터로 push 되는데 기본 복사 생성자가 호출되어 단순히 포인터 필드가 복사되었다. 복사 생성자 구현하여 next 필드가 새로 생성된 노드를 가리키도록 할 수 있다.
// 포인터 값을 가지는 필드의 얕은 복사를 막기 위해 복사 생성자 정의
Node(const Node& origin) {
value = origin.value;
if (origin.next != nullptr)
next = new Node(origin.next->value, origin.next->next);
else
next = nullptr;
}
// node2의 next필드(포인터): 001AFCD0
// .node2(vec)의 next필드(포인터): 001FF128
// 다른 포인터이를 통해 컨테이너에 원소를 추가할 때 복사 생성자가 호출됨을 알 수 있다.
2. 대입 연산자
대입 연산자를 통해 원소의 내용을 원본의 복제본으로 교체한다.
이 대입 연산자는 컨테이너의 원소를 수정할 때마다 호출된다.
// vector<Node> vec;
Node node = {100, nullptr};
vec[3] = node; // 대입 연산자 호출3. 소멸자
컨테이너의 원소를 제거할 때마다 호출된다.
4. 디폴트 생성자
인수가 하나 뿐인 vector::resize()나 map::operator[]와 같은 특정한 연산에서만 호출된다.
vector::resize()
void vector::resize(size_type count);
size < count인 경우에 기본 생성자를 호출하여 size가 count가 되도록 늘린다.
5. operator==
비순차(비정렬) 연관 컨테이너(해시 테이블)의 키를 비교할 때 호출된다.
ex) 해시 테이블 클래스의 ADD 메서드
6. operator<
순차(정렬) 연관 컨테이너의 키를 비교할 때 호출된다.
