A Tour of C++ : 11장 컨테이너

.

11. 컨테이너

11.1 소개

컨테이너(container) = 객체를 저장하는 것이 주 목적인 클래스

​

11.2 vector

요소들은 메모리에 연속적으로 저장.

구현 구성 요소들.

첫 요소, 마지막 요소 다음, 할당된 공간의 마지막의 다음을 가리키는 포인터

(elem, space, last)

​

요소 타입 값들로 초기화

vector<Entry> phone_book = {

{“David Hume”, 123456},

{“Karl Popper”, 234567},

{“Bertrand Arthur William Russell”, 345678}

}

​

Entry 클래스에 << 를 정의해서 다음과 같이 할 수도

void print_book(const vector<Entry>& book)

{

for ( int i =0; i != book.size(); ++i )

cout << book[i] << ‘\n’;

}

​

혹은

void print_book(const vector<Entry>& book)

{

for ( const auto& x : book )

cout << x << ‘\n’;

}

​

vector<int> v1 = {1,2,3,4}; // 크기 4

vector<string> v2;

vector<Shape*> v3(23); // 크기 23. 각 요소 초기값 nullptr

vector<double> v4(32, 9.9); // 크리 32. 각 요소 초기값 9.0

​

Entry 에 >> operator 를 정의했다면 이렇게도 쓸 수 있다.

void input()

{

for (Entry e; cin>>e; )

phone_book.push_bakc(e);

}

​

간단한 Vector 의 구조

template<typename T>

class Vector {

T* elem; // 첫 요소 포인터

T* space; // 처음으로 사용되지 않은(초기화되지 않은) 슬롯의 포인터 (새 요소가 push 될 공간)

T* last; // 마지막 슬롯의 포인터 (할당되지 않은 공간)

public:

// ...

int size(); // 요소의 개수 (space - elem)

int capacity(); // 요소를 저장할 수 있는 슬롯의 수. 사용중인 공간 포함. (last - elem)

// ...

void reserve(int newsz); capacity() 를 newsz 까지 증가시킴.

// ...

void push_back(const T& t); // Vector로 복사

void push_back(T&& t); // Vector로 이동

}

​

reserve(); 는 요소를 저장할 공간을 추가로 확보할 때. 메모리를 새로 할당하게 되면 기존 요소들을 새로 할당한 곳으로 옮긴다. 메모리 연속성을 보장.

::push_back() 할 때, capacity() 가 부족할 경우 reserve() 가 호출됨. 이 때 용량은 기존 size의 2배로 증가.

성능을 고려해서 reserve()를 쓸 정도는 아니고, 포인터를 사용하기 위해 재할당(메모리 위치 변경)을 반드기 막아야 하는 경우에만 reserve()를 명시적으로 사용한다.

​

vector<Entry> book2 = phone_book;

vector의 대입은 요소의 복사를 유발. 요소가 많다면 비용이 클 수 있다. 복사를 피하려면 참조나 포인터, 이동 연산을 사용하자.

​

​

11.2.1 요소

거의 모든 타입 한정자를 요소 타입으로 사용할 수 있다. 추가 요소는 값 자체로 복사. virtual 함수를 갖는 객체라면 컨테이너에 직접 저장하지 말고 포인터를 사용해야 함.

​

vector<Shape> vs; // 놉. Circle 이나 Smiley 저장 불가.

vector<Shape*> vps; // 좀 낫긴 하지만... 4.5.3 절 “자원 누수 피하기” 참고.

vector<unique_ptr<Shape>> vups; // 굿

​

​

11.2.2 구간 검사

vector 는 구간 검사를 보장하지 않음. 구간 밖 에러 문제는 일반적. 필자는 구간 검사를 수행하게 간단한 vector 어댑터를 사용.

at() 인덱싱 연산자, 구간을 벗어나면 out_of_range 타입 예외 throw

​

class Vec : public std::vector<T> {

...

T* operator[](int i) { return vector<T>::at(i); }

const T& operator[](int i) const { return vector<T>::at(i); }

}

​

void checked( Vec<Entry>& book )

{

try {

book[book.size()] = {“Joe”, 99999}; // 예외 Throw

}

catch (out_of_range&) {

cerr << “구간 에러\n”;

}

}

​

표준에서 구간 검사를 보장하지 않는 이유는?

성능을 중요시하는 애플리케이션에서 vector를 애용, 인덱싱 연산 검사에 10% 비용 차지. 적어도 디버그 시에 vector 를 쉽게 구간 검사, 출시버전에서는 검사 없는 검증된 vector 사용.

​

구간 for를 이용하면 [begin():end()] 안에서 반복자 이용, 추가 비용 없이 구간 에러 방지.

​

​

11.3 list

이중 연결 리스트. 다른 요소는 두고, 시퀀스에 요소 삽입/삭제. 인덱싱 접근 안 함. 대신 리스트 검색.

int get_number(const string& s)

{

for ( const auto& x : phone_book )

if ( x.name == s )

return x.number;

return 0;

}

​

반복자 begin(), end() 함수로도 시퀀스 가능

int get_number( const string& s )

{

for ( auto p = phone_book.begin(); p != phone_book.end(); ++p )

if ( p->name == s )

return p->number;

return 0;

}

컴파일러는 적은 구간 for 루프를 이런 식으로 구현. 반복자 p 의 요소 참조는 *p. ++p 는 다음요소. p->m 은 (*p).m 과 같다.

p, q 는 iterator.

​

phone_book.insert(p, ee); // p 위치 요소 앞에 ee 추가.

phone_book.erase(q); // q 요소 삭제

​

하지만, 특별한 이유가 없다면 vector를 사용하라. vector 는 순회(ex, find(), count()), 정렬, 검색(ex, sort(), equal_range())을 더 잘 제공한다.

​

forward_list 는 순방향 순위만 허용. (노드가 적으니) 공간 절약. 포인터 하나 크기와 동일. 요소의 개수도 저장하지 않아, 개수를 알려면 하나씩 카운트 해야함. (가급적 쓰지 마라)

​

​

11.4 map

(이름, 번호) 목록이 매우 짧은 경우가 아니라면 선형 탐색(linear search)은 비효율적. map 은 균형 이진 트리(balanced binary search tree). (일반적으로는 레드-블랙 트리 red-black tree)

연관 배열(associative array) 이나 딕셔너리(dictionary)라고도 함.

​

조회를 위해 최적화된 컨테이너, 값의 쌍을 담음.

키 값으로 인덱싱, 두 번째 값을 반환.

요소 삽입 시, 유효성을 위해 [] 대신 find()와 insert 를 사용하라.

​

​

11.5 unordered_map

map 의 저장된 요소가 n개일 때 map의 조회 비용은 O(log(n)). 비용이 낮은편.

하지만, 1,000,000 개 요소를 찾기 위해 20번 정도의 비교와 간접 참조만 수행해야 함.

<를 비롯한 순서 비교 함수 대신, 해시 조회(hashed lookup)을 이용하면 더 높은 성능.

표준 라이브러리 해시 컨테이너는 순서 비교 함수가 필요하지 않아 ‘순서 없는’(unordered)수식어 붙임.

​

string과 같은 내장 타입, 표준 라이브러리 타입에 대해 기본 해시 함수 제공. 직접 정의도 가능.(5.4.6절)

사용자 정의 타입(클래스나 구조체)인 경우 직접 해시 함수 작성 필요. 함수 객체로 만들 수도 있음.(6.3.2절)

​

struct Record {

string name;

int product_code;

// ...

};

​

struct Rhash {

size_t operator()(const Record& r) const

{

return hash<string>()(r.name) ^ hash<int>()(r.product_code);

}

}

​

unordered_set<Record,Rhash> my_set; // 조회할 때 Rhash를 사용하는 Records 집합

​

좋은 해시 함수 설계가 중요. 이미 존재하는 해시 함수를 배타적 논리합(^)으로 합치는 방식 간단하고 효율적.

표준 라이브러리 hash 특수화로 정의하면 hash 연산을 명시적으로 전달할 필요 없다.

​

namespace std {

template<> struct hash<Record> {

using argument_type = Record;

using result_type = std::size_t;

​

size_t operator()(const Record& r) const

{

return hash<string>()(r.name) ^ hash<int>()(r.product_code);

}

}

}

​

​

map과 unordered_map 차이.

- map은 순서 비교 함수( < )를 필요로 하며, 순서 있는 시퀀스 생성.

- unordered_map 은 해시 함수를 필요로 하며, 요소 사이 순서를 유지하지 않음.

​

좋은 해시 함수를 사용한다면, 컨테이너가 큰 경우 unordered_map 이 map 보다 훨씬 빠름.

반대로, 해시 함수를 잘못 사용하면 unordered_map 의 최악의 경우가 map보다 훨씬 느림.

​

11.6 컨테이너 개요

표준 컨테이너 개요

vector<T>

list<T>

forward_list<T>

deque<T>

set<T>

multiset<T>

map<K,V>

multimap<T>

unordered_map

unordered_multimap

unordered_set

unordered_multiset

​

기본적인 컨테이너 연산들

value_type 요소의 타입

p = c.begin() p 는 c의 첫 번째 요소,

p=c.end() 마지막 요소

k=c.size() 요소 개수

c.empty()

k=c.capacity()

c.reserve(k)

c.resize(k) 요소의 수를 k로 만듦. 추가된 요소의 값은 value_type{}

c[k]

c.at(k) k번째 요소. 구간 밖이면 out_of_range 예외.

c.push_back(x)

c.emplace_back(a) c의 끝에 value_type{a}를 추가. c의 크기는 1 증가

q=c.insert(p,x)

q=c.erase(p) 요소p를 제거

=, ==, !=, <, <=, >, >=

​

일관성 보장. 표준 컨테이너와 비슷한 컨테이너 만들게 함.Vector(3.5.2절)도 그 예. 각 컨테이너 타입과 독립적인 알고리즘. 요소의 수가 적은 짧은 시퀀스라면 vector 가 list 보다 효율적. emplace_back() 비롯 배치 연산은 요소의 생성자를 인자로 받음. 복사 대신 컨테이너 새 공간에 객체 생성.

예, vector<pair<int,string>> 활용

v.push_back(pair{1,”copy or move”)); // pair를 만든 후 v로 이동

v.emplace_back(1, “build in place”)); // v 안에 pair 생성

​

​

11.7 조언

[3] vector 를 기본 컨테이너로 사용하라. (11.2, 11.6)

[5] 요소 포인터/반복자 유효성 유지하려면 reserve()

[6] 실측 없이 reserve() 의 성능 향상 가정하지 말자

[10] 구간 검사가 필요하다면 at() 사용.

[16] 성능에 관해 직관을 믿지 말고 측정하라.

[19] 컨테이너 전달은 참조로, 컨테이너 반환은 값으로. (11.2절)

[28] 데이터 구조 직접 만들지 말고 표준 라이브러리 컨테이너 배우고 활용하라.

.

.

.