listは双方向リストを構築したテンプレートクラスです。双方向リスト については、アルゴリズムとデータ構造編第１２章を参照して下さい。
まずはサンプルを見て下さい。
#include <list>
int main()
{
std::list<int> intlist; // int型の双方向リスト
int i;
// 10個の要素を追加していく
for( i = 0; i < 10; ++i )
{
intlist.push_back( i );
}
// 10個の要素を削除していく
for( i = 0; i < 10; ++i )
{
intlist.pop_back();
}
return 0;
} |
listもstdという名前空間に含まれています。listのデフォルトコンストラクタは、空の双方向リストを生成します。 また、デストラクタによって必要な終了処理を行います。
listは、push_back()、push_front()、 insert()の各メンバ関数によって要素を追加します。このとき、内部的にメモリ 確保が行われています。insert()については、前章にも登場したイテレータが必要になります。 push_back()は末尾に、push_front()は先頭に要素を追加します。
要素を削除するには、pop_back()、pop_front()、 erase()という各メンバ関数を呼び出します。pop_back()は末尾、pop_front()は先頭 から要素を取り出します。このとき、戻り値として削除した要素を返す訳ではありません。erase()はイテレータを使い ます。
上のサンプルプログラムでは、何も表示しないので結果がよく分かりません。listは、vectorのように[]演算子に より要素をアクセスすることができません。listは双方向リストなので、添字を使って要素をアクセスできないのです。 list内の要素をアクセスするには、イテレータを使います。
listの中から目的の要素をアクセスするには、イテレータを使って先頭から順番に探索していきます。 下のプログラムは、目的の要素という訳ではありませんが、listに含まれている全ての要素を順番に出力 します。
#include <list>
#include <iostream>
int main()
{
using namespace std;
list<int> intlist; // int型の双方向リスト
int i;
// 10個の要素を追加していく
for( i = 0; i < 10; ++i )
{
intlist.push_back( i );
}
list<int>::iterator it = intlist.begin(); // イテレータ
while( it != intlist.end() ) // listの末尾まで
{
cout << *it << endl; // 要素を出力
++it; // イテレータを１つ進める
}
return 0;
} |
前章で見たイテレータの使い方と何も変わりません。本当に基本的な使い方なので 覚えて下さい。今回はlistなので、list<int>::iterator になります。
イテレータを使って、目的の要素を探すなら、次のようになります。
while( it != intlist.end() )
{
if( *it == 5 )
{
cout << "発見" << endl;
}
++it;
}
if文を使って要素と、目的の値とを比較すればいいだけです。イテレータは先頭から末尾に向かって順番に 進んでいくので、結局、これは線形探索法になります。
listには要素の削除に関わるメンバ関数が複数用意されています。
pop_back() や pop_front() は、これまでと同様、引数無しで、先頭か末尾の要素を削除します。
erase() はイテレータを使い、指定された要素を削除します。ただし、list の場合は要素の削除には、 remove() の方を使うべきです。remove() は、指定した値を持つ全ての要素を削除します。remove_if() は、 削除する要素の条件を指定できるものですが、この辺りは使い方が難しいので説明を省きます。
remove() に関しては、
intList.remove( 100 );
のように使います。こうすると、intList に含まれている要素の中から、値が 100 のものを探して、 それらの要素を全て削除します。もちろん、削除した要素の前後の要素は、適切に接続されます。
clear() は全ての要素を削除します。
また、同じ名前のメンバ関数がオーバーロードされていることもあるので、更に複雑で分かりにくいですが、 慣れるまでは、一番引数の個数が少ないものだけ使うようにしていても充分だと思います。例えば、erase()は、 引数にイテレータを１つ又は２つ取ります。１つの方は、そのイテレータが指す要素だけを削除し、２つの方は、 それら２つのイテレータが指す要素間にある全ての要素をまとめて削除します（つまり範囲指定）。
まず、コンテナに含まれている要素数は、size()で取得します。例によって、 空かどうかはempty()で判断できます。size()==0より、empty()の方が効率的 です。
また、演算子もオーバーロードされています。==、!=、<、<=、>、>=演算子がそれぞれ使えます。 それぞれの動作は予想通りでしょう。
listには、要素をソートするためにsort()というメンバ関数が用意されて います。
#include <list>
#include <iostream>
#include <functional>
int main()
{
using namespace std;
list<int> intlist;
// listに要素を追加
intlist.push_back( 3 );
intlist.push_back( 6 );
intlist.push_back( 2 );
intlist.push_back( 4 );
intlist.push_back( 8 );
// リストをソート
intlist.sort( greater<int>() );
// 要素を出力
list<int>::iterator it = intlist.begin();
while( it != intlist.end() )
{
cout << *it << endl;
++it;
}
return 0;
} |
sort()は単に 「intlist.sort();」 のように呼び出してもいいのですが、その場合は必ず昇順にソートされ ます（昇順は小さい方から大きい方に並ぶ状態）。降順にソートするためには、上のように、
intlist.sort( greater<int>() );
とします。引数がとても不思議な感じがしますが、とりあえず意味は分からなくても使えます。
また、functionalというヘッダファイルをインクルードしていますが、 これはgreaterを使うために必要になります。VisualC++の場合は、ヘッダファイルlistの中でfunctionalもインク ルードしているので、上のように別個にインクルードする必要はありません。Borland C++ Compilerの場合は、 別個にインクルードする必要があります。別個にインクルードする必要がなくても、基本的にはインクルード を明示するべきです。その方が、他のコンパイラでも修正なしでコンパイルできます。
listは双方向リストなのですから、要素のつなぎ直しができるはずです。その１つの形として、２つのリスト を連結したい場合があります。これにはmerge()というメンバ関数を使います。
#include <list>
#include <iostream>
#include <functional>
int main()
{
using namespace std;
list<int> intlist1, intlist2;
// listに要素を追加
intlist1.push_back( 3 );
intlist1.push_back( 6 );
intlist1.push_back( 2 );
intlist2.push_back( 8 );
intlist2.push_back( 4 );
intlist2.push_back( 5 );
// 連結する前にリストをソートしておく
intlist1.sort();
intlist2.sort();
// リストを連結する
intlist1.merge( intlist2 );
// 要素を出力
list<int>::iterator it = intlist1.begin();
while( it != intlist1.end() )
{
cout << *it << endl;
++it;
}
return 0;
} |
merge()は、引数に指定したlistを、呼び出し元のlistに連結します。このとき、連結するlistがソートされた 状態であれば、連結結果もソートされた状態になります。ソートされていても、片方が昇順、一方が降順のような 状態では結果はソートされません。上のプログラムの場合、出力結果は、
2 3 4 5 6 8
となります。
listには他にもメンバ関数がありますが、とりあえずこの程度で止めておきます。リスト構造を表しているので、 それに沿ったメンバ関数があります。例えば、splice()というメンバ関数は、一方 のlistの要素を、もう一方のlistの途中に移動させます。