STLコンテナの概要覺書

コンテナ一覽
メンバ型
共通インタフェース
共通比較關數
vector, list, deque 共通インタフェース
vector 專用インタフェース
list 專用インタフェース
聯想コンテナ專用インタフェース
set, map 專用インタフェース
map 專用インタフェース
multiset, multimap 專用インタフェース
參考文獻

コンテナ一覽

以下、Vは要素の型、Aはアロケータの型、Cは比較基準の型、Kはキーの型、Tはキーに關聯附けられた値の型を表す。

std::vector<V, A>
std::list<V, A>
std::deque<V, A>
std::set<V, C, A>
std::multiset<V, C, A>
std::map<K, T, C, A>
std::multimap<K, T, C, A>

メンバ型

共通

型名	説明
value_type	要素の型。 (一覽における V)
value_type	map, multimap においては std::pair<K, T>。
allocator_type	アロケータの型。 (一覽における A)
size_type	コンテナの大きさを表す型。
difference_type	2つの iterator 間の差を表す型。
iterator	反復子或はイテレータ。コンテナの要素をポイントする型。
const_iterator	反復子。但し對象要素を const として扱ふ。
reverse_iterator	要素を逆順に參照する反復子。
const_reverse_iterator	reverse_iterator の const 版。
reference	要素型の參照型。
const_reference	要素型の const 參照型。

聯想コンテナ專用

型名	説明
key_type	map, multimap のキーの型。 (一覽における K)
key_type	set, multiset においては V。
mapped_type	map のキーに對應づけられた型。 (一覽における T)
key_compare	set, multiset, map, multimap のキーの比較基準型。 (一覽における C)
value_compare	set, multiset, map, multimap の value_type についての比較基準型。

個人的見解

結局、よく使ふのは iterator, const_iterator 位である。

共通インタフェース

コンストラクタ

container(): 空のコンテナを生成する。
template<class In> container(In first, In last): [first, last) を内容とするコンテナを生成する。; In は入力反復子型。
container(const container& x): コピーコンストラクタ。 x と同内容のコンテナを生成する。

デストラクタ

~container(): デストラクタ。

iterator 取得

コンテナを扱ふ上で最も基本的なインタフェース。

iterator begin(): 先頭要素を指す iterator を返す。
const_iterator begin() const: 先頭要素を指す const_iterator を返す。
iterator end(): 末尾要素の次の位置を指す iterator を返す。屡々、無效な iterator として用ゐられる。
const_iterator end() const: 末尾要素の次の位置を指す const_iterator を返す。屡々、無效な const_iterator として用ゐられる。
reverse_iterator begin(): シーケンスを逆順に見たときの先頭要素を指す reverse_iterator を返す。
const_reverse_iterator begin() const: シーケンスを逆順に見たときの先頭要素を指す const_reverse_iterator を返す。
reverse_iterator end(): シーケンスを逆順に見たときの末尾要素の次の位置を指す reverse_iterator を返す。
const_reverse_iterator end() const: シーケンスを逆順に見たときの末尾要素の次の位置を指す const_reverse_iterator を返す。

代入

container& operator=(const container& x): コンテナの内容を x の内容のコピーに變更する。
template<class In> void assign(In first, In last): コンテナの内容を [first, last) の内容のコピーに變更する。In は入力反復子型。

コンテナ諸特性値取得

bool empty() const: コンテナが空であれば true、さもなくば false を返す。
size_type size() const: コンテナの要素數を返す。
size_type max_size() const: コンテナの要素數上限を返す。

よく言はれることの一つとして、size() == 0 の判定をするなら empty() を使へといふのがある。

要素插入

iterator insert(iterator pos, const V& x): pos の前に x を插入し、その位置を示す iterator を返す。; 但し、聯想コンテナでは、pos は單なるヒントに過ぎない。

全要素削除

void clear(): 全要素を削除する。結果として、コンテナは空になる。

内容交換

void swap(container& x): x と内容を交換する。

アロケータ取得

allocator_type get_allocator() const: アロケータを返す。何に用ゐるのか支配人はよく分らない。

共通比較關數

bool operator==(const container& x, const container& y): x と y が内容等價であるか判定する。
bool operator!=(const container& x, const container& y): x と y が内容非等價であるか判定する。
bool operator<(const container& x, const container& y): x が辭書的に y よりも小さいか判定する。
bool operator<=(const container& x, const container& y): x が辭書的に y 以下であるか判定する。
bool operator>(const container& x, const container& y): x が辭書的に y よりも大きいか判定する。
bool operator>=(const container& x, const container& y): x が辭書的に y 以上であるか判定する。

vector, list, deque 共通インタフェース

コンストラクタ

container(size_type n): n 個の V のデフォルト値を内容とするコンテナを生成する。
container(size_type n, const V& v): n 個の v のコピーを内容とするコンテナを生成する。

要素アクセス

reference front(): 先頭要素を參照する。begin() が指す要素である。
const_reference front() const: 先頭要素を參照する。begin() const が指す要素である。
reference back(): 最後尾要素を參照する。
const_reference back() const: 最後尾要素を參照する。

list では使へない要素アクセス

vector では一番身近と言へるかも知れないインタフェース。list で實裝されてゐないのは、表記の簡易さと、計算時間にギャップがあるからである。

reference operator[](size_type i): i番目の要素を參照する。範圍チェックをしない。
const_reference operator[](size_type i) const: i番目の要素を參照する。範圍チェックをしない。
reference at(size_type i): i番目の要素を參照する。範圍チェックを行ひ、範圍外であれば例外 out_of_range を投げる。
const_reference at(size_type i) const: i番目の要素を參照する。範圍チェックを行ひ、範圍外であれば例外 out_of_range を投げる。

要素插入

void insert(iterator pos, size_type n, const V& x): pos の前に n 個の x を插入する。
template<class In> void insert(iterator pos, In first, In last): pos の前に [first, last) で示される要素列を插入する。In は入力反復子型。

要素削除

iterator erase(iterator pos): pos の示す要素を削除し、次の要素を示す iterator を返す。
iterator erase(iterator first, iterator last): [first, last) の範圍の要素を削除し、last が示していた要素に對する iterator を返す。

スタック演算

void push_back(const V& v): シーケンスの末尾に要素を追加する。
void pop_back(): シーケンスの末尾要素を削除する。

vector では使へないスタック演算

vector では、先頭要素を對象にしたスタック演算は、必ず全要素のコピーを引き起し、高コストであるため、實裝されてゐない。

list, deque を用ゐる場合でも、コンテナの互換性を考慮すると、先頭、末尾の兩方にスタック操作が必要な場合を除いては、末尾に對するスタック演算 (push_back(), pop_back()) を用ゐるのが望ましい。

void push_front(const V& v): シーケンスの先頭に要素を追加する。
void pop_front(): シーケンスの先頭要素を削除する。

サイズ變更

void resize(size_type n): コンテナの要素數を n に變更する。要素が増える場合は、末尾にデフォルト値の要素を追加し、減る場合は末尾から要素を削除する。

代入

void assign(size_type n, const V& v): コンテナの内容を、n 個の v のコピーとする。

vector 專用インタフェース

void reserve(size_type n): 要素を配置する爲のメモリ領域を豫めn個分確保する。豫めメモリ領域を確保しておくことにより、末尾に對する要素追加の際に、メモリ領域を再確保し、全要素をコピーする手間を省くことが出來る。
size_type capacity() const: 既に確保されてゐるメモリ領域の大きさを、要素數換算で返す。つまり、要素何個分かといふ數を返すのであり、バイト數を返すものではない。

list 專用インタフェース

void sort(): 要素をソートする。
template<class Cmp> void sort(Cmp cmp): 比較基準 cmp を基にソートする。
void marge(list& y): ソート濟の list をマージする。ソートされてゐない場合の要素の順番については不明。マージした後、y は空 list となる。
template<class Cmp> void marge(list& y, Cmp cmp): 比較基準 cmp に基づき、ソート濟の list をマージする。ソートされてゐない場合の要素の順番については不明。マージした後、y は空 list となる。
void splice(iterator pos, list& y): y の全要素を pos の直前に移動する。結果として y は空になる。
void splice(iterator pos, list& y, iterator p): p の示す y の要素を pos の前に移動。移動した要素は y から取り除かれる。
void splice(iterator pos, list& y, iterator first, iterator last): [first, last) の範圍にある y の要素を pos の前に移動する。移動した要素は y から取り除かれる。

聯想コンテナ專用インタフェース

要素探索

iterator find(const key_type& key): キー値が key である要素 (multimap、multiset では先頭要素) を指す iterator を返す。
const_iterator find(const key_type& key) const: キー値が key である要素 (multimap、multiset では先頭要素) を指す const_iterator を返す。
iterator lower_bound(const key_type& key): キー値が key である最初の要素を指す iterator を返す。
const_iterator lower_bound(const key_type& key) const: キー値が key である最初の要素を指す const_iterator を返す。
iterator upper_bound(const key_type& key): キー値が key である最後の要素の次を指す iterator を返す。
const_iterator upper_bound(const key_type& key) const: キー値が key である最後の要素の次を指す const_iterator を返す。
pair<iterator, iterator> equal_range(const key_type& key): lower_bound() と upper_bound() の對を返す。
pair<const_iterator, const_iterator> equal_range(const key_type& key) const: lower_bound() const と upper_bound() const の對を返す。

要素插入

template<class In> void insert(In first, In last): [first, last) で示される要素列を插入する。In は入力反復子型。

要素削除

void erase(iterator pos): pos の指す要素を削除する。
void erase(iterator first, iterator last): [first, last) の範圍の要素を削除する。
size_type erase(const key_type& key): キー値が key である要素を削除し、削除した要素數を返す。

比較基準オブジェクト取得

key_compare key_comp() const: キー比較基準オブジェクトを返す。
value_compare value_comp() const: value_type 型についての比較基準オブジェクトを返す。

set, map 專用インタフェース

pair<iterator, bool> insert(const value_type& val): val の插入を試みる。キー値が同じ要素がコンテナに含まれない場合は、插入を行ひ、插入した要素を指す iterator と true の對を返す。キー値の同じ要素が既にコンテナ中に存在する場合は、插入を行はず、val とキー値が同じコンテナ中の要素を指す iterator と false の對を返す。

map 專用インタフェース

mapped_type& operator[](const key_type& key): キー値 key に對應する値にアクセスする。對應する要素がない場合は、キー値 key、對應値がデフォルト値である要素がつくられ、其の要素の對應値へアクセスすることになる。

multiset, multimap 專用インタフェース

iterator insert(const value_type& val): val を插入し、插入された要素を指す iterator を返す。

參考文獻

B. Stroustrup, “プログラミング言語C++ 第3版,” 長尾高弘譯, Addison Wesley Publishers Japan, 1998.