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] 데이터 구조 직접 만들지 말고 표준 라이브러리 컨테이너 배우고 활용하라.
.
.
.