ATLAS日本基礎ネットワーク C++トレーニングコース
ここでの目標
目次
C++の規格として標準ライブラリが与えられています。
名前空間としてはstdの中に定義されています。
これまでC言語で使われてきたものはstd名前空間に移され、頭に小文字cをつけたパッケージとしてまとめられています。例えばC言語で<math.h>としていたものは<cmath>となります。
標準ライブラリはいろいろなカテゴリーをカバーしています。大別すると
vectorやlist、mapなど
などとなります。このうち、コンテナ、反復子、アルゴリズムについて今回、文字列、入出力、数値計算については次回解説します。
前回見たように、コンテナ(容器)クラスはクラステンプレートとして実装されるのが望ましいように思えます。任意の基底クラスでインスタンシエートすることで様々な用途に使えるコンテナクラスを用意することが出来ます。
汎用ライブラリとしては、様々な用途に対してすべて最高の性能を発揮するクラスを設計することは難しく、そのため、いくつかの標準コンテナが用意されています。ATLASでよく使われているのはそのうちvector、list、mapです。設計に多少違いがあります。使い方は基本的に同じなので、ここではvectorについて見てみましょう。
実際に使ってみましょう。いつものように作業場所を用意しましょう。
cd ~/tutorial/cplusplus
mkdir l8
cd l8
文字列へのポインターを要素に持つvectorを定義します。vector.cxxとして
#include <iostream>
#include <vector>
main( ) {
std::vector<const char *> names(4); //char*で即値化したvector
names[0] = "sakamoto"; //配列のように扱える。
names[1] = "kawagoe";
names[2] = "ohmachi";
names[3] = "fukunaga";
for( int i = 0; i < names.size( ); i ++ )
std::cout << i << ": " << names[i] << std::endl;
std::cout << "size: " << names.size( ) << std::endl;
}
とりあえずこれだけで実行してみましょう。
g++ vector.cxx ./a.out0: sakamoto 1: kawagoe 2: ohmachi 3: fukunaga size: 4
最後のところではvectorクラステンプレートのsizeメソッドが呼ばれ、namesの現在のサイズが返されています。
C/C++の配列は寸法のチェックはしませんが、vectorではそれをさせることが可能です。
今、5番目に"takashima"を足しましょう。上記vector.cxxの最後の}の前に次を追加します。
try {
names.at(4) = "takashima";
}
catch( std::out_of_range ) {
std::cout << "out_of_range caught" << std::endl;
}
tryとchatchに関しては既に見てきました。例外を受け取る仕組みです。namesのatメソッドはstd::out_of_range例外を投げます。それを受け取るようにします。
このままコンパイルするとstd::out_of_rangeが未定義なのでシンタックスエラーになります。ファイルの先頭に
#include <stdexcept>
を追加しておきます。これを実行してみましょう。
g++ vector.cxx ./a.out ...out_of_range caught
ちゃんと例外が処理されています。names.at(4)="takashima";としたところをnames[4]="takashima"とすると、寸法のチェックをしません。通常の配列と同じ振る舞いをします。
C/C++の配列は途中でサイズを変更することは出来ませんが、標準コンテナはそれが可能です。
今の場合、"takashima"を収容するためにサイズを一つ大きくする必要があります。
names.resize( names.size( ) + 1 );
これを上記のtry節の一行上に加えます。さらに内容を確認するために出力分を追加しましょう。その結果、vector.cxxは
#include <iostream>
#include <vector>
#include <stdexcept>
main( ) {
std::vector names(4); //char*で即値化したvector
names[0] = "sakamoto"; //配列のように扱える。
names[1] = "kawagoe";
names[2] = "ohmachi";
names[3] = "fukunaga";
for( int i = 0; i < names.size( ); i ++ )
std::cout << i << ": " << names[i] << std::endl;
std::cout << "size: " << names.size( ) << std::endl;
names.resize( names.size( ) + 1 );
try {
names.at(4) = "takashima";
}
catch( std::out_of_range ) {
std::cout << "out_of_range caught" << std::endl;
}
for( int i = 0; i < names.size( ); i ++ )
std::cout << i << ": " << names[i] << std::endl;
std::cout << "size: " << names.size( ) << std::endl;
}
コンパイルして実行します。
g++ vector.cxx
./a.out
0: sakamoto
1: kawagoe
2: ohmachi
3: fukunaga
size: 4
0: sakamoto
1: kawagoe
2: ohmachi
3: fukunaga
4: takashima
size: 5
そうすると今度は例外が発生しませんでした。
ここまでの例ではvectorオブジェクトを生成した後、一つ一つの要素を設定していました。vectorのコンストラクタはその第二引数で初期化を指定することが出来ます。
std::vector<char *> names( 4, "hoge" );
これで、すべての要素を"hoge"を指すように初期化します。
標準コンテナでは、オブジェクトを生成するときにそれぞれの要素をデフォルトコンストラクタ、もしくはここで示したような初期化リストで初期化します。クラスオブジェクトのvectorを作る場合、引数無しコンストラクタが要素の数だけ呼び出されていることに注意してください。
これまで見てきただけでは大して配列と変わらないようにも見えます。コンテナの内容物にアクセスするために、反復子(イテレータ)というものが用意されており、それを用いることでコンテナのより便利な使い方が出来るようになります。
反復子は、コンテナの位置を示すポインターのような役割をします。反復子が指すものを表すのに、ポインターと同じ*(内容取り出し演算子)を使うことが出来ます。ポインターが境界のチェックをしないのに対し、反復子は境界をチェックします。
反復子にはコンテナの先頭から順番に最後までたどっていくiteratorと、逆にコンテナの最後からたどり、先頭にたどり着くreverse_iteratorがあります。また、それぞれのタイプに、対象とするコンテナの内容を書き換えないコンスタントな反復子、const_iteratorとconst_reverse_iteratorがあります。これらはすべて、それが対象とするコンテナクラスの中で定義されています。例えば先ほどの例のvector.cxxで反復子を使ってみましょう。同様に最後の}の前に次を追加します。
std::vector<char *>::iterator p = names.begin( );
std名前空間で定義された、char *で即値化されたvectorクラステンプレートの中で定義されたiteratorのオブジェクトという意味でpを定義しています。その初期値は対象とするクラスのbeginメソッドで得ています。
反復子はポインターの概念を引き継いでいます。そのため、*の他にも++や--演算も持っています。配列の引数として加減算を施すことも出来ます。上述の追加の後に、
while( p != names.end( ) )
std::cout << * p ++ << std::endl;
pはポインターでなく反復子なのですが見かけ上はほとんどポインターのように使うことが出来ます。
標準コンテナは反復子を使っていろいろな操作をするように設計されています。例えばvectorから要素を一つ消去をします。
names.erase( names.begin( ) + 3 );
この例では先頭から3つ先(つまり4番目)の要素が削除されます。この行の次に
std::cout << names.size( ) << std::endl;
を追加して実行してみましょう。サイズが一つ減っています。逆に挿入することも可能です。
names.insert( names.end( ) );
後からたどるreverse_iteratorについても
std::vector<char *>::reverse_iterator p = names.rbegin( );
while( p != names.rend( ) )
std::cout << * -- p << std::endl;
などとやることが出来ます。
実際に使ってみましょう。反復子を加えたものは次のようになります。iterator.cxxとします。
#include <iostream>
#include <vector>
#include <stdexcept>
main( ) {
std::vector names(4); //char*で即値化したvector
names[0] = "sakamoto"; //配列のように扱える。
names[1] = "kawagoe";
names[2] = "ohmachi";
names[3] = "fukunaga";
std::vector::iterator p = names.begin( );
// for( int i = 0; i < names.size( ); i ++ )
// std::cout << i << ": " << names[i] << std::endl;
int i = 0;
while( p != names.end( ) )
std::cout << i++ << ": " << * p ++ << std::endl;
std::cout << "size: " << names.size( ) << std::endl;
names.resize( names.size( ) + 1 );
try {
names.at(4) = "takashima";
}
catch( std::out_of_range ) {
std::cout << "out_of_range caught" << std::endl;
}
// for( int i = 0; i < names.size( ); i ++ )
// std::cout << i << ": " << names[i] << std::endl;
i = 0;
p = names.begin( );
while( p != names.end( ) )
std::cout << i++ << ": " << * p ++ << std::endl;
std::cout << "size: " << names.size( ) << std::endl;
}
実行してみます。
g++ iterator.cxx
bash-4.1$ ./a.out
0: sakamoto
1: kawagoe
2: ohmachi
3: fukunaga
size: 4
0: sakamoto
1: kawagoe
2: ohmachi
3: fukunaga
4: takashima
size: 5
期待通りに動いています。
標準コンテナと反復子をインターフェースとして用いることで様々なアルゴリズムを利用することが出来ます。アルゴリズムは関数テンプレートとして実装されています。
アルゴリズムはヘッダーファイルalgorithmで定義されています。vector.cxxの先頭に
#include <algorithm>
を追加しましょう。
アルゴリズムの例としてfindを見てみましょう。
先ほどのvector.cxxの最後の}の前に、
std::vector<char *>::iterator q = std::find( names.begin( ), names.end( ), "fukunaga" );
if( q != names.end( ) ) //"fukunaga"が見つかった。qはその要素を指している。
std::cout << "Found: " << *q << std::endl;
findの最初の二つの引数は反復子で、始点と終点を表しています。その次の値が比較すべき対象で、==演算を施して真であればその要素を指す反復子を返します。見つからなければ最終要素の次すなわちこの例ではnames.end( )の返すものと同じ値を返します。
同様のアルゴリズムにcountがあります。値が出現した頻度を数えます。
std::cout << "Count: " << std::count( names.begin( ), names.end( ), "fukunaga" ) << std::endl;
順番の並び替えを行うsortや、内容物をコピーするcopy、要素一つずつに操作を加えるfor_each、translateなど、数十に及ぶアルゴリズムがalgorithmに関数テンプレートとして定義されています。
g++では実際の定義は
algorithmがさらにincludeしているbits/stl_algo.hの中で与えられています。それぞれがどういうことをしているのか比較的わかりやすく記述されています。眺めておいてください。
ここまでのところでは、標準コンテナの例としてvectorのみを取り上げてきました。しかし、他にも実装方法が異なるいろいろなコンテナがあります。
vectorは名前の通り線形に要素が並べられたものと考えられます。そのため、n番目の要素を取り出すのも、2n番目の要素を取り出すのも、アドレス計算は同じ回数ですむので同じ時間で出来ます。一方、このように線形に要素が並べられている場合、間の要素を除去したり挿入するためにはそれ以降すべての要素を移動する必要があり、要素数に比例して多くの処理時間を要することになります。eraseやinsertは用意されていますが、得意ではないということです。
listと呼ばれるコンテナは要素を双方向のリンクで繋いだものです。芋づる式に次の要素をたどっていきます。そのためにn番目の要素のアドレスを計算式で得ることが出来ません。そのため、[]演算子(要素取りだし演算子)やatメソッドは実装されていません。一方、芋づる構造をしているため、途中の要素を除去したり、途中に要素を挿入することはその前後のリンクだけを修正すればよいので時間はかかりません。
使用するには
#include <list>
とします。
mapはvectorとlistの中間的な性能を与えるコンテナで、要素がキーと一緒に記憶される連想記憶方式を採用しています。平衡二分検索木と呼ばれる技法が用いられ、記憶場所は節と呼ばれる位置から参照されます。節はある値を持ち、その値はキーにより計算できます。一つの節は二つの節への枝分かれを持っており、片方のリンクはより値の少ない節を、他方はより値の大きな節を持っています。大小比較をしながら節をたどり、一致した節が見つかればその要素を取り出します。要素数をnとした場合、構造的にlog(n)の時間コストで要素を取り出せ、要素の削除や挿入も同じオーダーで可能です。それゆえ[]演算子やatメソッドも装備されています。
使用するには
#inlude <map>
です。
このように、それぞれのコンテナの性質を理解した上で使うべきコンテナの種類を選択することが、性能の良いプログラムを書くためには重要です。
クラスオブジェクトを保持するコンテナを作るときには、そのクラスが持たなければいけない機能(実際にはメソッド)が仮定されていることを理解しなければなりません。
前回、テンプレートのところでも説明しましたが、テンプレートはクラスなどの型をパラメータとして与えることが出来ます。テンプレートの実装では、パラメータとされたクラスのオブジェクトに演算を施すことが普通です。比較演算や代入演算などがオブジェクトになされます。例えば、findでは==演算子が一致する要素を見つけるために用いられています。ということは、そのアルゴリズムを使うためにはコンテナに入れたいクラスはその演算が出来なければならないということを表しています。その型の要素とfindの第三引数で与える値の型Tとの間で、==演算が出来るように、operator ==(T & rhs)が定義されていないといけないと言うことです。
標準コンテナではコンテナの初期化時に個別の要素を生成します。そのときに通常は引数を取らないコンストラクタを使用します。標準コンテナのコンストラクタの第二引数に定数オブジェクトを与えることにより、コピーコンストラクタを使用することも可能ですが、すべての要素に同じ値が与えられることになります。
デストラクタも用意されています。デストラクタはコンテナとすべての要素オブジェクトを破棄します。
クラスオブジェクトへのポインターを標準コンテナの要素とする場合、ポインターのデフォルト初期化子としてヌルポインターが使われます。当然、オブジェクトのライフタイムの管理はプログラマーにゆだねられることになります。
次回は入出力、文字列、数値計算ライブラリについて解説します。