Stanley B. Lippman
Architect, Microsoft Visual C++ team
August 2004
日本語版最終更新日 2005 年 6 月 6 日
適用対象 :
Microsoft Visual C++ 2005
標準テンプレート ライブラリ (STL) および STL.NET
メモ 本論は初期の実装に基づいており、技術的な詳細は最終リリースまでに変更される可能性があります。 STL.NET は、Visual Studio 2005 Technology Preview リリースには含まれていません。
概要 : Visual C++ 2005 では、標準テンプレート ライブラリ (STL) が .NET Framework で使用できるように再設計されています。シリーズの第 1 回となる今回は、STL.NET の概要を紹介します。
目次
過剰な選択肢
STL.NET のメリット
共通点の解明
簡単なデモ
選択のアルゴリズム
謝辞
この記事は、STL.NET についての連載記事の第 1 回となります。STL.NET は標準テンプレート ライブラリ (STL) を再設計したもので、CLI のジェネリックと C++ のテンプレートの両方のメカニズムを使って実装されています。STL.NET は、Visual C++ の新機能として Visual Studio 2005 に導入されます。私見によれば、C++/CLI の動的プログラミングのサポートの強化も相まって、この新しいバージョンの Visual C++ は実に満足度の高いプログラミング言語となっています。STL.NET がライブラリに追加されたことがいかにすばらしいことか、この連載記事を通じてそれをおわかりいただければと思います。
過剰な選択肢
Visual C++ プログラマが一連の CLI 型を操作する際に使用できるコンテナ ライブラリは 3 つあります。各ライブラリは、それぞれパラメータ化の 3 つのモデルに基づいて構築されています。以下にその概要を、各モデル内で実装された一般的なコード サンプルと共に示します。
- 元の Systems::Collection ライブラリ。すべての CLI 型に共通の Object 基本クラスを通じて要素型が格納されます。たとえば、次の ArrayList は IList インターフェイスを実装しており、Object 型の配列を表します。ここでは、String 型の要素を保持するために使用されています。
void objectCollection()
{
using namespace System::Collections;
ArrayList ^as = gcnew ArrayList;
as->Add( "Pooh" ); as->Add( "Piglet" );
as->Add( "Eeyore" ); as->Add( "Rabbit" );
as->Sort();
Console::WriteLine( "ArrayList holds {0} elements: ",
as->Count );
for ( int i = 0; i < as->Count; i++ )
Console::WriteLine( as[ i ] );
int index = as->IndexOf( "Pooh" );
if ( index != -1 )
{
// 明示的なダウンキャストが必要です
String^ item = safe_cast<String^>( as[ index ]);
as->RemoveAt( index );
}
as->Remove( "Rabbit" );
Console::WriteLine( "\nArrayList holds {0} elements: ",
as->Count );
IEnumerator^ is = as->GetEnumerator();
while ( is->MoveNext() )
Console::WriteLine( is->Current );
}
-
CLI のジェネリック メカニズムに基づく新しいコンテナ ライブラリ。System::Collections::Generic 名前空間にあります。これは Visual Studio 2005 Beta1 の実装であり、最終リリースまでに変更される可能性があります。Collection<T> は具象ジェネリック基本クラスであり、ユーザーはここから特殊化されたコンテナ クラスを派生させます。以下は、先ほどと同じ一般的なコード サンプルです。
void genericCollection()
{
using namespace System::Collections::Generic;
Collection<String^> ^cols =
gcnew Collection<String^>;
cols->Add( "Pooh" ); cols->Add( "Piglet" );
cols->Add( "Eeyore" ); cols->Add( "Rabbit" );
// Collection に関連付けられている Sort メソッドはありません
Console::WriteLine( "Collection holds {0} elements: ",
cols->Count );
for ( int i = 0; i < cols->Count; i++ )
Console::WriteLine( cols[ i ] );
int index = cols->IndexOf( "Pooh" );
if ( index != -1 )
{
// ダウンキャストは必要ありません ...
String ^item = cols[ index ];
cols->RemoveAt( index );
}
cols->Remove( "Rabbit" );
Console::WriteLine( "\nCollection holds {0} elements:",
cols->Count );
IEnumerator<String^> ^is = cols->GetEnumerator();
while ( is->MoveNext() )
Console::WriteLine( is->Current );
}
- STL.NET が提供する型のパラメータ化のモデルは、これらとはまったく異なります。これについては、次のセクションで説明します。String コンテナの STL.NET の実装は次のようになります。詳細については、この連載の後の記事で説明します。
#include <cli/vector>
#include <algorithm>
void stlCollection()
{
vector<String^> ^svec = gcnew vector<String^>;
svec->push_back("Pooh"); svec->push_back("Piglet");
svec->push_back("Eeyore"); svec->push_back("Rabbit");
// 汎用アルゴリズム: sort
sort( svec->begin(), svec->end() );
Console::WriteLine( "Collection holds {0} elements: ",
svec->size() );
for ( int i = 0; i < svec->size(); i++ )
Console::WriteLine( svec[ i ] );
// 汎用アルゴリズム: find
vector<String^>::iterator iter =
find( svec->begin(), svec->end(), "Pooh" );
if ( iter != svec->end() )
{
// ダウンキャストは必要ありません ...
String ^item = *iter;
svec->erase( iter );
}
// 汎用アルゴリズム: remove ...
remove( svec->begin(), svec->end(), "Rabbit" );
Console::WriteLine( "\nCollection holds {0} elements:",
svec->size() );
IEnumerator<String^> ^is = svec->GetEnumerator();
while ( is->MoveNext() )
Console::WriteLine( is->Current );
}
STL.NET のメリット
STL.NET の詳細に入る前に、ある意味避けては通れない疑問があります。Visual C++ プログラマが、System: Collections や System::Collections::Generic などの言語に依存しないライブラリの代わりに STL.NET コンテナ ライブラリを使用するメリットはどこにあるのでしょうか。
一般に、System::Collections ライブラリはまっ先に選択肢から外れます。その理由は、Visual Studio 2005 で Generic ライブラリが用意されることになった理由と同じです。すなわち、パラメータ化のオブジェクト モデルが複雑であり、型情報が失われるため安全でないからです。単純な用途については問題ありません。これは、要素数が 16 以下のコンテナではバブル
ソートを使用しても問題にならないのと同じです。しかし、アプリケーションで現実的な問題に対処するには、より洗練されたソリューションが必要になります。
したがって、Visual C++ のようなシステム プログラミング言語にとっての選択肢は、STL.NET と System::Collections::Generic ライブラリのいずれかになります。では、Visual C++ プログラマがこの 2 つのうち STL.NET を選択する理由はどこにあるのでしょうか。また、STL.NET を選択するとして、プログラムが他の .NET 言語から孤立する心配はないのでしょうか。これらは当然の疑問であり、ここで取り上げる価値があります。
1 つ目の答えは、拡張性です。Alex Stepanov 氏によって考案された STL のオリジナル デザイン パターンでは、アルゴリズムとコンテナが別のドメイン空間に分離されています。したがって、すべてのコンテナに適用できるアルゴリズムを追加したり、アルゴリズムを適用できるコンテナを追加したりできます。これに比べると、Generic ライブラリは従来のコンテナ モデルに近いと言えます。このことは、2 つ目の答えにもつながります。
2 つ目の答えは、統一性です。現役の C++ プログラマがこれまでに築き上げてきたものは、既存のコードばかりではありません。STL ライブラリを使ったプログラミングのノウハウも大事な資産です。私たちは、既存のコードだけでなくそうしたノウハウも移行できるようにしたいと考えています。それまで STL を利用してきた C++ プログラマにとって (STL を利用していない現役の C++ プログラマはまずいないでしょう)、.NET でそれを利用できないことは大きなマイナスです。少なくとも、筆者はそう感じてきました。これについては、多くの熟練 C++ プログラマから懸念の声が上がっており、彼らが .NET への移行を見合わせる理由となっています。
3 つ目の答えは、パフォーマンスです。しかし、C++ プロラマはパフォーマンスの問題にうるさいことで有名なので、ここでこの問題に踏み込むのはやめて、後の記事で取り上げることにします。
最後に、STL.NET は確かにすばらしいが、それを使用することによって C++ プログラマや C++/CLI プログラムが .NET コミュニティから孤立するのではないか、という疑問にお答えしておきましょう。その答えはノーです。私はそう思っています。この問題については、Anson Tsao、Martyn Lovell、P.J. Plauger を始めとする STL.NET のアーキテクトが徹底的な調査を行っており、IEnumerator、IList、および ICollection のサポートを通じて他の .NET 言語との互換性を確保できるようになっています。これについては、後の記事である程度詳しく取り上げる予定です。
共通点の解明
STL.NET へのアプローチについては 2 とおりの方法が考えられます。STL と STL.NET の違いを明らかにすることから入る方法と、両者の共通点を明らかにすることから入る方法です。STL の使用経験がある方には、両者の違いを挙げていく方法の方がわかりやすいかもしれません。しかしその場合は、部外者にはよくわからないコンテナの話や、それらのコンテナと System コレクション ライブラリとの相互運用の話にすぐに入ることになるため、このライブラリについてよく知らない方が取り残されてしまうおそれがあります。方法としては効率的かもしれませんが、初心者の方が話を理解できるように最初に準備できれば、それに越したことはありません。少なくとも、この後の一連の短い導入のセクションは、そうした意図の下に書かれています。これにより、このライブラリを使用したことがない方でも、STL と STL.NET の両方が提供するパラメータ化されたコレクションの拡張可能なモデルについて、それがどのようなものかを把握できます。
では、STL と STL.NET の共通点とは何でしょうか。これらは両方とも、2 つの主要な要素で構成されています。1 つはシーケンス コンテナと連想コンテナという 2 種類のコンテナ、もう 1 つは一連の汎用アルゴリズムです (熟練の STL 開発者には退屈な話かもしれませんが、 共通のボキャブラリーと背景を確立するために、今しばらくご辛抱ください)。汎用アルゴリズムは、直接コンテナ型を操作するものではありません。汎用アルゴリズムに対しては、コンテナ型ではなく、操作する要素の範囲を示すイテレータのペア (通常は first と last と呼ばれます) を渡します。要素の範囲の表記法 (以前は left-inclusive 間隔と呼ばれていました) は次のようになります。
// これは、 first から last に至る各要素を含む、
// という意味です。ただし、last の要素は含まれません。
[ first, last )
これは、範囲が
first
で始まり
last
で終わることを意味します。ただし、
last
は範囲に含まれません。
first
と
last
が等しい場合、その範囲は空になります。
シーケンス コンテナは、1 つの型の要素が順番に並べられているコレクションを保持します。主要なシーケンス コンテナとして、vector と list の 2 つがあります (3 つ目のシーケンス コンテナの deque (「デック」と読みます) は、vector と同じ動作を提供しますが、最初の要素の挿入と削除を効率的に行えるようになっています。
たとえばキューを実装する場合などには、vector より deque の方が適しています)。
シーケンス コンテナ型を参照するには、次のいずれかの適切なヘッダー ファイルを事前にインクルードしておく必要があります。
#include <cli/vector>
#include <cli/list>
#include <cli/deque>
これらのヘッダー ファイルをインクルードすると、共有基本インターフェイスの宣言 (interface_vector など) や、ジェネリック バージョンのコンテナ (generic_vector など) もインクルードされます。
STL.NET のコンテナは参照型なので、コンテナ宣言によって提供されるのはトラッキング ハンドルです。このトラッキング ハンドルは自動的に nullptr に初期化されます。実際のコンテナは、gcnew 演算子を使用して割り当てます。これについては前のセクションで手短に紹介しましたが、ここで細かく見てみましょう。
void f()
{
// 空の vector を割り当てます。 . .
vector<String^>^ svec = gcnew vector<String^>;
// 10 の要素のリストを割り当てます
// 各要素は既定で nullptr に設定されます
list<Object^>^ olist = gcnew list<Object^>( 10 );
// トラッキング ハンドルは自動的に nullptr に設定されます
deque<int>^ ideck;
// なんらかの処理 . .
};
シーケンス コンテナの宣言と使用については、次回の記事で取り上げます。
連想コンテナを使用すると、要素の有無の確認や要素の取得を効率的に行うことができます。主要な連想コンテナとして、map と set の 2 つがあります。map はキーと値のペアです。キーは検索に使用され、値には格納や取得のためのデータが含まれます。たとえば、電話帳は map で簡単に表現できます。この場合、キーは個人の名前、値はその電話番号になります。
map は、基となる抽象ツリーを使用してエントリを値の昇順で整理します。hash_map コンテナは、より効率的な取得を行えるように整理されています。ただし、hash_map の反復処理では、ややランダムな順序で要素にアクセスします。map を主に取得のために使用する場合は、hash_map コンテナの方が適しています。
set には単一のキー値が含まれており、その有無を効率的に確認できます。たとえば、テキスト クエリ システムでテキスト内に存在する語のデータベースを構築する際に、除外する一般的な語 (the、and、but など) のセットを構築できます。プログラムでは、テキストの語を順番に読み取って、除外する語のセットに含まれていないかどうかを確認します。そしてその結果に基づいて、その語を破棄するかまたはデータベースに入力します。set に加えて hash_set コンテナもあります。その一般的な特徴は、map に対する hash_map と同じです。
map と set はどちらもキーの重複をサポートしていませんが、 multimap と multiset ではキーの重複がサポートされています。たとえば先ほどの電話帳の例では、通常、1 つの個人名に対して複数の電話番号をサポートする必要があります。そのような場合は multimap を使用します。hash_multimap と hash_multiset も用意されています。
これらのコンテナ型に対応するヘッダー ファイルを以下に示します。
// map と multimap
#include <cli/map>
// set と multiset
#include <cli/set>
// hash_map と hash_multimap
#include <cli/hash_map>
// hash_set と hash_multiset
#include <cli/hash_set>
簡単なデモ
では、例を使って具体的に見てみることにしましょう。使用する例は、テキスト ファイルの単語数をカウントする単純なプログラムです。これにより、map、hash_set、および vector の使用例を見ることができます。関数は次のように宣言されています。
map<String^,int>^
build_word_count( vector<array<String^>^>^ words,
array<String^> ^common_words )
テンプレート構文は、慣れるまではかなり複雑に見えるかもしれません。このコードは何を意味しているのでしょうか。build_word_count() の戻り値の型は、キーが文字列 (ファイル内の重複しない語) で、値がその語の出現回数を表す整数の map です。この関数の 1 つ目のパラメータは、ファイルの語を文字列要素として保持する CLI 配列の vector です。2 つ目のパラメータは、カウントから除外する語のセットを保持します。
このコードが複雑に見えるのは、右山かっこを間に挟んだ複数のカレットのせいです。これは、以下の typedef のペアを使用することによって語彙的に単純化できます。
typedef array<String^>^ words;
typedef vector<words>^ text;
上の typedef を使用すると、関数の宣言は次のようになります。
map<String^,int>^
build_word_count( text theText, words common )
map の明示的な宣言を省くこともできますが、ここでは練習の意味で残しておくことにしました。次の作業は実装です。この作業は 2 つの部分に分けることができます。(1) 以下に示す map と hash_set の初期化と、(2) テキスト自体の実際の処理です。
// #1: コンテナの初期化
// 空の map を割り当てます ... サイズはわかりません ...
map<String^,int> ^wordOccur = gcnew map<String^,int>;
// hash_set に配列の要素を設定します
hash_set<String^> ^comWords =
gcnew hash_set<String^>(
&common[0],
&common[common->Length]);
STL をよく知らない方にとっては、この hash_set の初期化は常軌を逸したものに見えるかもしれません。しかし、構文を別にすれば、この宣言は直接的で、実に強力なものとなっています。
ここでの目的は、hash_set を配列の要素で初期化することです。これはもちろん、for each ステートメントを使用して要素を反復処理することによって、明示的に行うこともできます。以下に例を示します。
// hash_set の宣言をわかりやすくします
// パート #1: 空の hash_set を割り当てます
hash_set<String^> ^comWords = gcnew hash_set<String^>;
// パート #2: hash_set に配列の要素を設定します
for each ( String^ wd in common )
comWords->insert( wd );
hash_set のコンストラクタに最初の配列要素のアドレスと最後の有効な配列要素の 1 つ
後のアドレスを渡すと、これと同じように hash_set に値を設定できます。この 2 つのアドレスは、hash_set のコンストラクタが反復処理する要素の範囲を指定します。これにより、各要素が順番にコンテナに挿入されます。これは、このセクションの冒頭で触れたイテレータの範囲のイディオムです。
実装の後半部分は、テキストの実際の処理です。ここではまだイテレータを見ていないことになっているため、さしあたって、従来の for ループを使用して vector を処理していくことにします。for each ステートメントを使用して、vector の個々の配列要素を順番に処理します。このコードは次のようになります。
// 配列の各要素に順番にアクセスします
for ( int ix = 0; ix < theText->size(); ++ix )
{
for each ( String^ wd in theText[ ix ] )
if ( common->find( wd ) == common->end() )
word_map[ wd ]++;
}
// 結果を返すのを忘れないようにしましょう。 . .
return word_map;
find() は hash_set のメンバ関数で、セット内に項目が存在するかどうかを調べるために使用します。find() メンバは、すべての連想コンテナでサポートされています (シーケンス コンテナ、組み込み配列、および STL/STL.NET モデルに統合される任意のコレクションは、汎用アルゴリズムの find() を使用します。アルゴリズムとコンテナの分離は、実践においては理論におけるほど顕著ではありません。これについては、後にシーケンス コンテナの list で具体的に見ます)。このメソッドによって返されるのが、まだ説明していませんが、コンテナへのイテレータです。イテレータについては、ここではさしあたって、ポインタ型の変種と考えておいてください。find() は、項目がコンテナに存在する場合はその項目へのイテレータを返します。それ以外の場合は、コンテナに含まれている最後の項目の 1 つ
後へのイテレータを返します。これは、end() によって返されるのと同じイテレータ値です。STL で要素の検索が成功したかどうかを確認するには、検索メソッドによって返されたイテレータを end() によって返されたイテレータと比較します。2 つが等しい場合、その要素はコンテナに存在しません。
各コンテナには、begin() と end() というメンバ関数があります。begin() は、コンテナの最初の要素へのイテレータを返します。end() は、先に述べたように、コンテナの最後の要素の 1 つ後へのイテレータを返します。たとえば、2 つのイテレータを宣言して、それらをこの 2 つのメンバを使って初期化する方法は、次のようになります。
vector<words>::iterator first = theText->begin();
vector<words>::iterator last = theText->end();
通常、コンテナをトラバースするには、for ループまたは while ループ内で first をインクリメントし、first と last が一致したらループを終了します。以下に例を示します。
for ( ; first != last; ++first )
このイテレータのペアには、first から始まって、インクリメント演算子を繰り返し適用することによって last に到達できなければならないという要件があります。しかし、この要件はコンパイラによって強制されないため、この要件が満たされていないと、実行時に未定義の動作が発生します。
イテレータによって参照されている要素にアクセスするには、逆参照演算子 (*) を使用します。たとえば、vector の各 CLI 配列要素を取得するには、上の for ループの本体の中に次のコードを記述します。
array<String^> ^as = *first;
連想コンテナの宣言と使用については、今後の記事で詳しく取り上げます。
選択のアルゴリズム
汎用アルゴリズムでは、これらのコンテナ型と 2 つの組み込み配列型の両方の要素を操作できます。たとえば、検索 (find、count)、並べ替え (merge、partition、permutate、reverse、rotate、shuffle、sort)、削除/置換 (remove、replace、swap、unique)、コピー、関係 (equal、min、max、includes)、生成 (fill、for-each、generate、transform)、セット (union、intersection、difference)、ヒープ (make、sort、pop、push)、およびいくつかの特殊な数値演算 (accumulate、partial_sum、inner_product、adjacent_difference) などの操作が用意されています。
汎用アルゴリズムを使用するには、当然ながら、事前に適切なヘッダー ファイルをインクルードしておく必要があります。数値以外のすべてのアルゴリズムについては、次のように記述します。
4 つの数値アルゴリズム (accumulate、inner_product、partial_sum、および adjacent_difference) は、別のヘッダーに分けられています。これらのアルゴリズムを使用するには、次のように記述します。
#include <numeric>
(これら 4 つが別のヘッダーに分かれている理由については、いろいろ調べてみましたが、はっきりした理由はわかりませんでした (これによってアルゴリズムの使用についての議論が複雑になっているのは明らかです)。Stepanov 氏によるオリジナルの実装では、これら 4 つも他のアルゴリズムと同じヘッダーに含まれています。標準化の過程で数値のヘッダーが導入され、実際、標準には数値ライブラリのための独立したサブセクションも設けられています)。
<cli/algorithm> と書く必要があるのではないかと思われる方もいるでしょう。結局のところ、コンテナのヘッダーはそのように修飾されます。ではこれは間違いかと言うと、そうではありません。驚くべきことに、ネイティブの STL と STL.NET の両方でアルゴリズムの同じ実装が使用されているのです。これぞまさにコードの再利用です。
では、アルゴリズムの使用方法を見てみましょう。例として、String 要素の配列を、map に挿入する前に並べ替えてみます。そのためには、汎用アルゴリズムの sort() を使用します。引数は、ほぼすべての汎用アルゴリズムと同様、イテレータの範囲のペアです。
sort( &as[0], &as[ as->Length ] );
最初の一連のコードの中で、汎用アルゴリズムをあと 2 つ使用します。find() と remove() の 2 つです。
// 汎用アルゴリズム: find
vector<String^>::iterator iter =
find( svec->begin(), svec->end(), "Pooh" );
if ( iter != svec->end() ){ ... }
// 汎用アルゴリズム: remove ...
remove( svec->begin(), svec->end(), "Rabbit" );
そろそろ使用方法のパターンが見えてきたのではないでしょうか。イテレータのペアによって指定される範囲は、アルゴリズムをコンテナにバインドする役割を果たします。検索のアルゴリズムでは、コンテナ内に項目が見つかった場合はその項目へのイテレータが返され、見つからなかった場合は、範囲の最後の項目の 1 つ後を示すイテレータが返されます。
これから汎用アルゴリズムの興味深い使用例をいくつか紹介していきますが、残念ながら今回はこれで終わりです。今回の目的は、全体の大まかな概要を示し、今後のための共通のボキャブラリーと背景を確立することでした。では、また次回お会いしましょう。
謝辞
どんなに些細な記事でも、陰で多くの方々に支えられているものです。丁寧な校閲を行ってくれた Scott Currie 氏に感謝します。彼がいなければ、誤りのある原稿を最終稿にするところでした。STL.NET の作法について根気よく教えてくれた Anson Tsao 氏にも感謝します。STL.NET の配置に向けて取り組んでいる Martyn Lovell 氏には、その途中経過をのぞかせてもらいました。最後に、Brian Johnson 氏と Ronald Laeremans 氏に感謝します。彼らがいなければ、そもそもこの記事は存在しなかったことでしょう。
執筆者紹介
Stan Lippman は、マイクロソフトの Visual C++ チームのアーキテクトです。彼の C++ との出会いは、この言語を発明した Bjarne Stroustrup 氏とベル研究所で働いた 1984 年にまでさかのぼります。その後、Disney の Feature Animation や DreamWorks で働き、Fantasia 2000 のソフトウェア テクニカル ディレクターも務めています。