コンテナ

ANSI/ISO標準C++(ANSI/ISO　Standard C++)

C++の標準化は1989年ANSI(American National Standards Institute)とISO(International Standards Organization)によって始まった．最終バージョンは1998年に両組織によって認可された．これが標準C++である．

標準C++の完全版は次のウェブサイトから手に入れることができる．

http://www.ansi.org/

標準テンプレートライブラリ(The Standard Template Library)

標準C++は名前空間(namespace)やブール型(bool type)など多くの改良を行った．その中でも特に大きな改良は，標準テンプレートライブラリ(STL)の追加である．これはクラステンプレートとコンテナオブジェクトである文字列(string), ベクタ(vector),リスト(list),キュー(queue),セット(set),マップ(map)などの使用を簡単にする関数の集まりである．STLはHwelett-PackardのAlexander Stepanovのチームによって開発され，今や標準C++ライブラリの一部である．これらのテンプレートから定義されるクラスをコンテナクラス(container class)という．

標準C++コンテナテンプレート(Standard C++ Container Class Templates)

10個の標準C++コンテナテンプレートは次の図のように構成されている．

コンテナ(container)は他のオブジェクトを含んでいるデータ構造である．コンテナに含まれているオブジェクトをコンテナの要素という．また，コンテナの要素は同じ型でなければならない．

シーケンスコンテナ(sequence container)は配列のようにその要素を順序列として含んでいるコンテナのことである．お互いの要素の位置はその値から独立である．しかし，その相対位置関係は無理に動かさないかぎり変化しない．また，シーケンスコンテナには３つの汎用シーケンスvector,deque,listがある．

連想コンテナ(associative container)は要素が整列されて格納されているコンテナのことである．したがって，ユーザはどこに要素が格納されているか知ることができない．よって，どのように要素を挿入するか考える必要がない．

標準C++ライブラリはこの他にも3つの特殊なコンテナテンプレートを定義している．

vector$<>$テンプレートはコンテナのプロトタイプで，配列への直接アクセスを一般化する．

deque$<>$テンプレートはスタックとキューコンテナを一般化する．つまり，両頭待ち行列．

list$<>$テンプレートは，指標化アクセスの代わりにもっと高速な挿入と削除演算子を持つ連係リスト構造を一般化する．

set$<>$テンプレートは和集合と積集合を用いて数学的な集合を表現するコンテナを提供する．

multiset$<>$テンプレートは，そのコンテナが複数のコピー要素を許可する以外set$<>$と同じである．

map$<>$テンプレートは連想配列を可能にする．ハッシュデータ構造はmapの特別な場合である．

multimap$<>$テンプレートは，そのコンテナが複数のコピー要素を許可する以外map$<>$と同じである．

basic_string$<>$テンプレートは添え字演算子，ランダムアクセス反復子のほか，コンテナが持つ便利な記述形式の大半を提供する．

valarray$<>$テンプレートは数値演算に合わせて最適化されたベクタである．

bitset$<>$テンプレートはビット列の処理に用いられる．つまり，論理演算子|,&, $<<$,$>>$を用いて処理を行う．

標準C++汎用アルゴリズム(Standard C++ Generic Algorithms)

標準C++汎用アルゴリズムは非メンバ関数でC++コンテナで用いられる．これらは，コンテナなの応用に必要なほぼ全ての道具を揃えている．また，これらはあるコンテナ型の要素を別のコンテナ型への変換を容易にする．

ヘッダファイル(Header Files)

標準C++コンテナテンプレートと汎用アルゴリズムは以下のヘッダファイルに定義されている．

accumulate()	<numeric>
adjacent_difference()	<numeric>" >
adjacent_find()	<algorithm>
basic_string()	<string>
binary_search()	<algorithm>
bitset()	<bitset>
copy()	<algorithm>
copy_backward()	<algorithm>
count()	<algorithm>
count_if()	<algorithm>
deque()	<deque>
equal()	<algorithm>
equal_find()	<algorithm>
fill()	<algorithm>
fill_n()	<algorithm>
find_first_of()	<algorithm>
find_if()	<algorithm>
for_each()	<algorithm>
generate()	<algorithm>
generate_n()	<algorithm>
includes()	<algorithm>
inner_product()	<<numeric>
inplace_merge()	<algorithm>
iter_swap()	<algorithm>
lexicographic_compare()	<algorithm>
list<>	<list>
lower_bound	<algorithm>
make_heap	<algorithm>
map<>	<map>
max()	<algorithm>
max_element()	<algorithm>
merge()	<algorithm>
min()	<algorithm>>
min_element()	<algorithm>
mismatch()	<algorithm>
multimap	<map>
multiset	<set>
next_permutation()	<algorithm>
nth_element()	<algorithm>
partial_sort()	<algorithm>
partial_sum()	<algorithm>
partition()	<algorithm>
partition_sort_copy()	<algorithm>
pop_heap()	<algorithm>
prev_permutation()	<algorithm>
priority_queue<>	<queue>
push_heap()	<algorithm>
queue<>	<queue>
random_shuffle()	<algorithm>
remove_copy()	<algorithm>
remove_copy_if()	<algorithm>
remove_if()	<algorithm>
replace()	<algorithm>
replace_copy()	<algorithm>
replace_copy_if()	<algorithm>
replace_if()	<algorithm>
reverse()	<algorithm>
reverse_copy()	<algorithm>
rotate()	<algorithm>
rotate_copy()	<algorithm>
search_n()	<algorithm>
set <>	<set>
set_difference()	<algorithm>
set_intersection()	<algorithm>
set_symmetric_difference()	<algorithm >
set_union()	<algorithm >
sort()	<algorithm >
sort_heap()	<algorithm >
stack <>	<stack >
string <>	<vector >
swap()	<algorithm >
transform()	<algorithm >
unique()	<algorithm >
unique_copy()	<algorithm >
upper_bound()	<algorithm >
valarray <>	<valarray >
vector <>	<vector>

標準C++コンテナクラス(Standard C++ Container Classes)

ベクタクラステンプレート(The vector Class Template)

ベクタオブジェクトは配列に添え字が範囲をチェックする機能が付いているようなものである．しかし，ベクタはオブジェクトとして配列では不可能な代入が可能である．ベクタクラステンプレートは$<$vector$>$ヘッダファイルで定義されている．

vector();	空のベクタを作る
vector(const vector& v);	ベクタvのコピーを作成．
	事後条件： *this == v;
vector(unsigned n, const T& x=T());	xのコピーを含んだベクタを作成．
	前提条件： n $>=$ 0;
	事後条件： size() == v;
${}^{\sim}$vector();	このベクタを壊す
vector& operator=(cosnt vector& v);	vにこのベクタを代入することにより
	複写を行なう．
	事後条件: *this == v;
unsigned size() const	このベクタの要素の数を返す
unsigned capacity() const	このベクタが持つことができる要素の
	最大数を再配置なしで返す
void reserve(unsigned n)	このベクタを要素数nの容量のベクタに
	再配置
	前提条件：capacity() $<=$ n;
	事後条件：capacity() == n;
bool empty() const	size() == 0はtrueを返す必要十分条件
void assign(unsigned n, const T& x = T())	このベクタをクリアし，要素xの
	n個のコピーを挿入する．
	前提条件：n $>=$ 0;
	事後条件：size() == 0;

T& operator[](unsigned i);	要素番号iを返す
	前提条件：0 $<=$ i $<$ size();
	前提条件が正しくない場合結果は分からない．
T& at(unsigned i);	要素番号iを返す
	前提条件：0 $<=$ i $<$ size();
	前提条件が正しくない場合結果は分からない．
T& front();	このベクタの最初の要素を返す
T& back();	このベクタの最後の要素を返す
iterator begin();	このベクタの最初の要素を指している反復子
	を返す
irerator end();	このベクタの最後の要素の後のダミー要素を
	指している反復子を返す
reverse_iterator rbegin();	このベクタの最初の要素を指している逆反復子
	を返す
reverse_iterator rend();	このベクタの最後の要素の後のダミー要素を
	指している逆反復子を返す
void push_back()(cosnt T& x);	要素xのコピーをこのベクタの後に付け足す
	前提条件：back == x;
	事後条件：size() は増やされた;
void pop_back();	このベクタの最後の要素を取り除く
	前提条件：size() $>=$ 0;
	事後条件：size()は減らされた;
iterator insert(iterator p, const T& x);	位置pで要素xのコピーを挿入しpを返す
	前提条件：begin() $<=$ p $<=$ end();
	事後条件：size() は増やされた;
iterator erase(iterator p);	位置pで要素を取り除き，pを返す
	前提条件：begin() $<=$ p $<=$ end();
	事後条件：size() は減らされた;

iterator erase(iterator p1, iterator p2);	p1からp2までの要素を取り除き，
	p1を返す．
	前提条件：begin() $<=$ p $<=$ p2 $<=$ end();
	事後条件：size() はint(p2 - p1)だけ減らされた;
void clear();	このベクタからすべての要素を取り除く
	事後条件：size() == 0;

例題 15..1   ベクタオブジェクトに反復子を用いる
次のプログラムを実行するとどんな結果が得られるか．

#include <iostream>
#include <vector>
using namespace std;
typedef vector::iterator It;
int main()
{
vector<int> v(4);
for(int i=0; i<4; i++)
v[i] = 222*i + 333;
cout << "反復子itをforループで用いる" << endl;
for(It it=v.begin(); it!=v.end();it++)
cout << "\t *it=" << *it << endl;
cout << "反復子itをwhileループで用いる" << endl;
It p = v.begin();
while(p!=v.end())
cout << "\t *p++ =" << *p++ << endl;
}

実行結果

解答 ベクタvは333,555,777,999の4つの要素を持っている．forループは反復子itを用いて，ベクタvの先頭から最後尾までを走査し，それぞれの要素を*itでアクセスする．*pを用いてwhileループは同じ効果を生んでいる．

例題 15..2   ベクタオブジェクトに逆反復子を用いる
次のプログラムを実行するとどんな結果が得られるか．

#include <iostream>
#include <vector>
using namespace std;
typedef vector::reverse_iterator RIt;
int main()
{
vector<int> v(4);
for(int i=0; i < 4; i++)
v[i] = 222*i + 333;
cout << "反復子ritをforループで用いる" << endl;
for(RIt rit=v.rbegin(); rit!=v.rend();rit++)
cout << "\t *rit=" << *rit << endl;
cout << "反復子ritをwhileループで用いる" << endl;
RIt rp = v.rbegin();
while(rp!=v.rend())
cout << "\t *rp++ =" << *rp++ << endl;
}

実行結果

解答 ベクタvは333,555,777,999の4つの要素を持っている．forループは逆反復子ritを用いて，ベクタvの最後尾から先頭までを逆向きに走査し，それぞれの要素を*ritでアクセスする．*rpを用いてwhileループは同じ効果を生んでいる．

例題 15..3   ベクタオブジェクトにinsert()関数を用いる
次のプログラムを実行するとどんな結果が得られるか．

#include <iostream>
#include <vector>
typedef vector<int> Vector;
void print(const Vector&);
using namespace std;
typedef vector::reverse_iterator RIt;
int main()
{
vector<int> v(4);
for(int i=0; i<4; i++)
v[i] = 222*i + 333;
print(v);
It it = v.insert(v.begin()+2, 666);;
print(v);
cout "*it=" << *it << endl;;
}

void print(const Vector& v)
{
cout << "size=" << v.size() << ": (" << v[0];
for(int i=1; i < v.size(); i++)
cout << ")" << endl;
}

実行結果

解答 ベクタvは333,555,777,999の4つの要素を持っている．挿入関数insert()を用いて，先頭から2つ目，777，の前に666を挿入した．

デッククラステンプレート(deque Class Templae)

deque(デックとよむ)オブジェクトは両端から出し入れができるキューである．これにより，効率のよい挿入と削除ができる．デックはvectorクラスが持っているcapacity()およびreserve()以外のすべてのメンバ関数のほかに2つのメンバ関数を持っている．デッククラステンプレートは$<$deque$>$ヘッダに定義されている．

void push_front(const T& x);	このデックの先頭に要素xのコピーを挿入
	前提条件：front() == x;
	事後条件：size()は増やされた;
void pop_front()	このベクタの最初の要素を取り除く
	前提条件：size() $>$ 0;
	事後条件：size()は減らされた;

スタッククラステンプレート(stack Class Template)

スタックオブジェクトはtopと呼ばれる一方の端からだけ出し入れができる連続したコンテナである．標準C++ライブラリでは，スタッククラステンプレートはデッククラステンプレートを改造している．ということは，スタックメンバ関数は下に示すようにデックメンバ関数として実行される．スタッククラステンプレートは$<$stack$>$ヘッダに定義されている．

template $<$class T$>$ class stack
{
public:
unsigned size() const {return _d.size();}
bool empty() const {return _d.empty();}
T& top() {return _d.back();}
void push(cosnt T& x) {_d.push_back(x);}
void pop() {_d.pop_back():}
protectd:
deque$<$T$>$ _d;
};

キュークラステンプレート(queue Class Template)

キューオブジェクトは連続したコンテナで一方の口からだけ挿入ができ，もう一方の口からだけ削除ができる．スタッククラスと同様に，キュークラスもデッククラスから改造された．ということは，キューメンバ関数は下に示すようにデックメンバ関数として実行される．デッククラステンプレートは$<$deque$>$ヘッダに定義されている．

template $<$class T$>$ class stack
{
public:
unsigned size() cosnt {return _d.size():}
bool empty() const {return _d.empty();}
T& front() {return _d.front();}
T& back() {return _d.back();}
void push(cosnt T& x) {_d.push_back(x);}
void pop() {_d.pop_back():}
protectd:
deque$<$T$>$ _d;
};

リストクラステンプレート(list Class Template)

リストは連続したコンテナで，どの位置からでも挿入と削除を効率よく行なえるオブジェクトである．リストはoperator[]()とat()を除くすべてのデッククラスが持っているメンバ関数に以下のメンバ関数を持っている．リストクラステンプレートは$<$list$>$ヘッダに定義されている．

void splice(iterator p. list& l, iterator p1)

リストlの位置p1の要素をこのリストの位置pに移動する;

前提条件：pはこのリストの有効な反復子である;

前提条件：p1はリストｌの有効な反復子である;

void splice(iterator p. list& l, iterator p1, iterator p2)

リストlの位置[p1:p2-1]の要素を位置pで始まるこのリストへ移動する;

前提条件：pはこのリストの有効な反復子である;

前提条件：p1とp2はリストｌの有効な反復子である;

前提条件：p1 $<$ p2;

remove(const T& x);

このリストからxと等しい要素をすべて取り除く;

取り除かれなかった要素の順は不変;

取り除かれなかった要素を指しているすべての反復子は不変;

void unique
このリストから重複している要素を取り除く;
取り除かれなかった要素の順は不変;
取り除かれなかった要素を指しているすべての反復子は不変;
merge(list& l);
リストlのすべての要素をこのリストに結合;
前提条件：リストlとこのリストの両方ともソートされてなければならない;
事後条件：size()はl.size()だけ増える;
事後条件：l.size() == 0;
O(n)の複雑度;
void reverse();
このリストの要素の順を反転する;
size()は不変である;
O(n)の複雑度;
void sort();
このリストの要素を並べかえる．
事後条件：このリストはソートされる;
size()は不変である;
O(n*log(n))の複雑度;

例題 15..4   リストオブジェクトのソートと反転

#include <iostream>
#include<list>
using namespace std;
typedef list<string> List;
typedef List::iterator It;
void print(List&);
int main()
{
    List l;
    l.push_back("Korea");
    l.push_back("Sweden");
    l.push_back("Egypt");
    l.push_back("Zambia");
    l.push_back("Japan");
    l.push_back("France");
    print(l);
    l.sort();
    print(l);
    l.reverse();
    print(l);
}
void print(List& l)
{
    cout << endl;
    for (It it=l.begin(); it != l.end(); it++)
    cout << *it << endl;
}

実行結果

マップクラステンプレート(The map Class Template)

マップオブジェクトまたは，辞書，表，連想配列とも呼ばれるオブジェクトは索引がどんな型でもよく関係演算子$<$を持った配列と考えることができる．マップは数学の関数のようなものである．つまり，それぞれの$x$の値に対して，唯一つの$y$の値をもつ．このときの$x$の値をキー値(key value)といい索引のことである．$y$の値はキーによって認識できる格納されたオブジェクトである．

英和辞書はマップオブジェクトの一つの例である．ここで，キー値は単語でありその単語の意味が連想オブジェクトである．

もう一つの典型的な例は，学生の成績のデータベース表である．このときキー値は学生番号であり，連想オブジェクトはその学生の成績である．

マップクラステンプレートは$<$map$>$ヘッダにより定義され，vectorクラステンプレートと同じメンバ関数を持っている．

例題 15..5   マップオブジェクトを用いる

#include <iostream>
#include <map>
using namespace std;
struct Country
{
    friend ostream& operator{\small $<<$}(ostream&, const Country&);
    Country();
    Country(string, string, string, int);
    string abbr, capital, language;
    int population, area;
};
typedef map<string, Country> Map;
typedef Map::iterator It;
typedef pair<const string, Country> Pair;
void load(Map&);
void print(Map&);
void find(Map&, const string&);
int main()
{
    Map map;
    load(map);
    print(map);
    find(map, "Vietnam");
    fing(map, "Japan");
    fing(map, "China");
}
ostream& operator{\small $<<$}(ostream& ostr, const Country& c)
{
    return ostr {\small $<<$} c.abbr {\small $<<$} ", " {\small $<<$} c.capital {\small $<<$} ", " {\small $<<$} c.language
    {\small $<<$} ", pop=" {\small $<<$} c.population;
}
Country::Country()
    : abbr(""), capital(""),language(""),population(0) { }
Country::Country(string ab, string c, string l, int p)
    : abbr(ab), capital(c), language(l), population(p)) { }
void load(Map& m)
{
    m["Korea"] = Country("KR", "Soeul", "Korean", 65000000);
    m["Japan"] = Country("JP", "Tokyo", "Japanese", 130000000);
    m["China"] = Country("CN", "Beijing", "Chinese", 1300000000);
    m.insert(Pair("Taiwan", Country("TW","Taipei","Chinese", 40000000)));
}
void print(Map& m)
{
    for(It it=m.begin(); it != m.end(); it++)
hspace{2cm} cout {\small $<<$} it $->$ first {\small $<<$} ":t" {\small $<<$} it $->$ second {\small $<<$} endl;
    cout {\small $<<$} "size" {\small $<<$} m.size() {\small $<<$} endl;
}
void find(Map& m, const string& s)
{
    cout {\small $<<$} s;
    It it = m.find(s);
    if (it == m.end()) cout {\small $<<$} "見つかりませんでした" {\small $<<$} endl;
    else cout {\small $<<$} ":t" {\small $<<$} it $->$ second {\small $<<$} endl;
}

実行結果

セットクラステンプレート(The set Clas Template)

セットオブジェクトはキーが格納されている以外はマップオブジェクトと同じ働きをする．セットクラステンプレートは$<$set$>$ヘッダで定義されている．

例題 15..6   セット関数を用いる
このプログラムは演算子+,*,-の多重定義を行ない，和集合，積集合，補集合が取れるようにする．これらは，insert()とerase()メンバ関数，set_intersection()とset_difference()汎用アルゴリズムを用いて実装される．

#include <iostream>
#include <set>
#include <string>
using namespace std;
typedef set<string> Set;
typedef set<string>::iterator It;
void print(Set);
Set operator+(Set&, Set&); //和集合
Set operatorast(Set&, Set&); //積集合
Set operator-(Set&, Set&); //補集合
int main()
{
    string str1[] = {"A", "B", "C", "D", "E", "F", "G"};
    string str2[] = {"A", "E", "I", "O", "U"};
    Set s1(str1, str1+7);
    Set s2(str2, str2+5);
    print(s1);
    print(s2);
    print(s1+s2);
    print(s1*s2);
    print(s2-s2);
}
Set operator+(Set& s1, Set& s2)
{
    Set s(s1);
    s.insert(s2.begin(),s2.end());
    return s;
}
Set operatorast(Set& s1, Set& s2)
{
    Set s(s1);
    It it = set_intersection(s1.begin(), s1.end(),
    s2.begin(), s2.end(), s.begin());
    s.erase(it, s.end());
    return s;
}
Set operator-(Set& s1, Set& s2)
{
    Set s(s1);
    It it = set_difference(s1.begin(),s1.end(),
    s2.begin(),s2.end(),s.begin());
    s.erase(it, s.end());
    return s;
}
void print(Set s)
{
    cout << "size" << s.size() << ": {";
    for (It it = s.begin(); it != s.end(); it++)
        it(it == s.begin()) cout << astit;
        else cout << "," << astit;
    cout << "}" << endl;
}