ViVi Home > 技術文書
> さくさく理解する C/C++ コンソールアプリ入門 >
手を動かしてさくさく理解する 双方向リストクラス std::list 入門
std::list とは C++ で標準に使用できる便利な双方向リストクラスでござるぞ。
「双方向リスト」とは前後の要素へのポインタを持ち、どの位置への挿入・削除でも O(1) と高速に処理できるコンテナクラスだぞ。
※ 「コンテナクラス」とは、単一タイプ・データ構造の複数のデータを取り扱うためのクラスのことだぞ
std::list と対比されるのは std::vector である。
vector は末尾への挿入・削除は O(1) と高速だが、それ以外の位置への挿入・削除は O(N) で、データ数に比例した処理時間を要してしまう。
その半面、どの位置のデータへも O(1) と高速にアクセス（参照・代入）することができる。
任意の位置へのアクセスをランダム・アクセスと呼ぶので、vector はランダム・アクセスが O(1) ということ。
これに対して、std::list は、末尾に限らず、どの位置での挿入削除も O(1) と高速に処理することができる。 が、N 番目のデータ位置に移動するには先頭、または末尾、または現在位置からポインタをたどる必要があり、 ランダム・アクセスの処理速度が O(N) である。
つまり、std::list と std::vector はランダム・アクセスと任意の位置への挿入・削除処理時間が相補的ということである。
| ランダム・アクセス | 任意位置への挿入・削除 | |
| std::vector | O(1) | O(N) |
| std::list | O(N) | O(1) |
vector, list のどちらかが一方的に優れているというわけではなく、上記のような特性があるので、用途により使い分けて欲しい。
ただ、vector のページ でも書いたが、データ数が少ない場合（通常、数１０個程度）は vector の挿入削除も充分高速で、
扱い易いので、通常は vector を使用することをお薦めする。
ちなみに、初期のテキストエディタでは、内部データ構造として、文字列を双方向リストで管理することが多かった（ただし Emacs は除く）。
コードで書けば std::list<std::string> となる。テキストエディタで行をランダム・アクセスすることは稀なので、これで通常は問題が無かったわけだ。
本章では、list オブジェクトの宣言方法について説明する。
list オブジェクトを宣言するには、空listを宣言する、サイズを指定して宣言する、サイズと全てのデータを指定して宣言する、 元データを指定して宣言する、他のオブジェクトを元にして宣言する、のようにいくつもの方法がある。 本章ではそれらの方法を順次解説する。
ローカル変数またはグローバル変数として list オブジェクトを宣言すると、オブジェクトが生成され利用可能になる。
これらはスコープを外れると自動的に破棄される。
通常のクラスなので new で生成し、delete で破棄することも可能だ。
宣言方法を具体的に説明する前に、list を使うための準備について説明する。
list は C++標準ライブラリに含まれており、「#include <list>」を記述することで利用可能になる。
名前空間は「std」なので、使用の度に「std::」を前置するか、または「using namespace std;」を記述しておく。
#include <list> // ヘッダファイルインクルード
int main()
{
std::list<int> lst; // ローカル変数として、lst を生成
.....
}
#include <list> // ヘッダファイルインクルード
using namespace std; // 名前空間指定
int main()
{
list<int> lst; // ローカル変数として、lst を生成
.....
}
std::list オブジェクトを生成するには「std::list<型> オブジェクト名;」 と記述する。
オブジェクト名とは、宣言する双方向リストを識別するための名前のことだ。変数名と言ってもよい。
list はクラスなので、それを実体化したものはオブジェクトまたはインスタンスと呼ばれる。
下記は、int 型の双方向リストdata を宣言している例だ。
std::list<int> lst; // int 型の双方向リスト lst の宣言
当然、型の部分はどんな型でも構わない。char や double や、自分で定義した構造体、クラスでもOKだ。
※ ただし、初期化時にデフォルトコンストラクタ、バッファ拡張時にコピーコンストラクタが呼ばれことがあるので、
それらがちゃんと定義されている必要がある。
また、vector などのコンテナクラスや string などを指定することも出来る。
「std::list<型> オブジェクト名;」には要素数の指定が無いじゃないかと気づいた人は観察力がある。要素数の指定方法は次節で説明する。
このようにして宣言したオブジェクトの要素数は0だ。データを追加するには次の章で説明する push_back() などを使う。
< > は何だ？と思う人もいるかもしれない。これはC++のテンプレートという機能を使うための記法だ。
テンプレートを完全に理解するのは難易度が高いので、深く理解しようとすると先に進めなくなる。
深入りはせず、現在のところは取り扱うデータの型をこういう書き方で指定すると無条件で覚えてほしい。
list は後でサイズを増減させることが出来るが、あらかじめ要素数を指定してオブジェクトを作ることも出来る。
vector の場合、データ領域が連続しているために、データ領域が足りなくなった場合にメモリのアロケートとデータコピーが必要だ。
だが、list は個々のデータ領域が独立なので、予め要素数を指定してオブジェクトを作るメリットは vector ほどは無い。
構文は「std::list<型> オブジェクト名(要素数);」だ。
std::list<int> lst(123); // int 型で、初期要素数 123 の双方向リスト lst の宣言
配列では要素数を「[要素数]」で指定するが、list では「(要素数)」で指定する。実はこれ、コンストラクタの引数なのである。
要素数を指定するだけでなく、全要素の値を指定することも可能だ。
「std::list<型> オブジェクト名(要素数, 値);」と記述すると、指定された数の要素を確保し、全ての要素を指定された値で初期化する。
std::list<int> lst(10, 5); // 要素数10、全ての要素の値5 で初期化
上記の方法では、値が全て同じ場合でないと初期化できない。
「std::list<型> オブジェクト名(型* first, 型* last);」と記述すると、first から last が指す先までのデータで双方向リストを初期化する。
厳密に言うと、last は最後の元データの次を指す。[first, last) の範囲を元に、双方向リストを初期化する。
通常配列でデータを指定し、それを元に双方向リストを構築出来る。
int org_data[] = {4, 6, 5}; // 元データ
std::list<int> lst(org_data, org_data + 3); // 元データから双方向リストを生成
配列末尾へのポインタは org_data + 3 と記述しているが、データ配列サイズが変わった時に、修正しなくてはならないので、危険だ。
C++0x（VS2010以上）で std::end(配列名) という関数が追加され、配列末尾へのポインタを返してくれるようになった。
これを使えば、上記は下記のように記述することが出来る。
int org_data[] = {4, 6, 5}; // 元データ
std::list<int> lst(org_data, std::end(org_data)); // 元データから双方向リストを生成
実は上記の記述方法は古い書き方で、C++11（VS2013以上）から初期化子で初期値を直接指定可能になった。
「std::list<型> オブジェクト名{値0, 値1, 値2, ... 値N-1};」と記述できる。
std::list<int> lst{4, 6, 5}; // データ列を指定して双方向リストを生成
こちらの方法の方が直感的で分かりやすく、行数も短い。C++11 が利用可能であれば、この記法を使うことを強く薦める。
※ ちなみに、「std::list<型> オブジェクト名 = {値0, 値1, 値2, ... 値N-1};」と書いてもよい。
コピーコンストラクタとは、同じ型のオブジェクトを渡され、それと同じ内容のオブジェクトを生成するコンストラクタのことである。
「std::list<型> オブジェクト名(コピー元オブジェクト名);」と記述する。
当然ながら、コピー元オブジェクトと生成するオブジェクトは通常同じ型である。
※ 暗黙の型変換が可能な型であれば、コピー元オブジェクトとして指定可能ではある。
std::list<int> org{1, 2, 3};
std::list<int> x(org); // コピーコンストラクタ
上記のコードは org をコピーするので {1, 2, 3} という値をもつ双方向リスト x を生成する。
※ 余談：list オブジェクトの宣言方法は vector のそれと全く同一である。このように仕様に共通性があることを直交性があると言う。
直交性がある仕様は、ひとつ覚えると他にもすぐ使えて便利である。
だたし、後で出てくるが、ランダム・アクセスなど、list と vector の仕様は完全に同一ではないので、例外的な部分はしっかり抑えておく必要はある。
演習問題：解答例
落胆する人もいるかもしれないが、list には operator[](size_t) が無い。つまり lst の ix 番目の要素を lst[ix] で参照することが出来ない。
何故できないかと言うと、最初の方で書いたように、ix 番目のデータに移動するコストが O(N) と高いので、
コーダが安易にランダム・アクセスを行うコードを書いてパフォーマンスを低下させないよう、あえて operator[](size_t) が定義されていないのだ。
※ 余談：
ちなみに、筆者がテキストエディタ ViVi の開発を始めた時、テキストを行ごとに双方向リストで管理していた。
フレームワークは MFC（Microsoft Foundation Class ライブラリ） を使っていたのだが、MFC には双方向リストクラス CList があり、それには GetAt(int), SetAt(int, const T&) というメソッドがあり、
なんとランダム・アクセスが可能になっていた。で、筆者は「おおっ、これは便利だ」と思い、安易にそれらのメソッドを使っていたのだが、
行数が増えると編集処理がかなり遅くなるという問題が発生した。
後で高速化が必要になり苦労した（今となってはいい）思い出がある。本稿の読者にはこのような轍を踏まないようにしてほしい。
※ 余談終わり
では、どうやって任意の箇所のデータを参照するかと言うと、イテレータ（iterator）というものを利用する。
イテレータとは抽象化されたポインタのことである。ポインタなので、要素を指していてイテレータ経由で要素の参照・修正が出来、別の要素に移動することが出来る。
もう少し具体的に言うと、begin() で先頭, end() で末尾の次の要素へのイテレータを取得でき、++ または -- 演算子でイテレータを進める、戻すことができ、
* 演算子でイテレータが指す要素を参照することができる。
++, -- でひとつ移動でき、* で要素を参照できるという機能は通常のポインタと同じである。
が、内部的にはポインタと同じというわけではない。これが抽象化されたポインタと呼ばれる理由だ。
イテレータの型は std::list<型>::iterator と記述する。少々めんどくさい。
たとえば、std::list<int> lst の最初の要素を指すイテレータを取得したい場合は以下のように記述する。
std::list<int> lst;
std::list<int>::iterator itr = lst.begin(); // 最初の要素を指すイテレータ
イテレータ型の記述は少々長ったらしく面倒だが、C++0x（VS2010以上）からは auto で型推論が可能になったので、 上記は以下のように記述するのが普通である。
std::list<int> lst;
auto itr = lst.begin(); // 最初の要素を指すイテレータ
イテレータが指すデータを参照する場合は、ポインタと同じ用に * 演算子を使用する。右辺値として記述すれば値を参照し、左辺値として書けば値の代入となる。
std::list<int> lst{1, 2, 3};
auto itr = lst.begin(); // 最初の要素を指すイテレータ
std::cout << *itr; // itr は最初の要素を指しているので 1 を表示
*itr = 9; // 最初の要素を 9 に変更
list オブジェクトが保持する全ての要素を表示するには、以下のように記述する。
std::list<int> lst;
for(auto itr = lst.begin(); itr != lst.end(); ++itr) {
std::cout << *itr << "\n";
}
このような書き方は非常によく出てくるので、イディオムとして覚えておいて欲しい。
※ list のイテレータは大小比較できないので、itr < lst.end() とは書けない。
itr を ix 番目のデータに移動するには、「itr = lst.begin();」で先頭データを指すようにしたのち、「++itr;」を ix 回繰り返す。
list のイテレータは通常のポインタの様に「itr += ix;」で一度に移動することは出来ない。
演習問題：解答例
データを先頭に追加するには push_front(値); を使う。
std::list<int> lst; // 空の双方向リストを生成
v.push_front(987); // 先頭に 987 を追加
データを末尾に追加するには push_back(値); を使う。
std::list<int> lst; // 空の双方向リストを生成
v.push_back(123); // 末尾に 123 を追加
処理時間は、push_front(), push_back() ともに、O(1) で高速。O(式) は処理時間を表す数学的な記法。「ビッグ・オー記法」と呼ばれる。 O(1) は要素数に依らず常に一定時間で処理出来るという意味で、高速なのだ。
任意の場所にデータを挿入したい場合は insert(iterator, 値) を使う。
insert(iterator, 値) は、第1引数に挿入する場所へのイテレータを、第2引数に挿入するデータを指定する。
イテレータは先に説明したものだ。ix 番目に挿入するには begin() で先頭を取得し、++itr; を ix 回繰り返す。
そして、insert() は挿入したデータへのイテレータを返す。
注意： insert() を実行すると、コンテナクラスによっては、引数に指定したイテレータが不正になる場合がある。
特に vector では insert() で領域が足りなくなると、メモリをアロケートし直すので、引数に使用したイテレータをその後も使用してはいけない。
なので、insert() が返す値を itr に代入し、itr が正しいデータを指すようにする。
例えば、データの値が 3 だったら、その前に 0 を挿入するコードは以下のようになる。
std::list<int> lst{3, 4, 3, 2, 4, 3, 1};
for(auto itr = lst.begin(); itr != lst.end(); ++itr) {
if( *itr == 3 ) {
itr = lst.insert(itr, 0); // 3 の前に 0 を挿入、itr は 0 を指す
++itr; // itr を 3 の位置に進める
}
}
慣れないと、少し混乱するかもしれないが、デバッガでトレースするなりしてしっかり理解して欲しい。
演習問題：解答例
※ 処理時間計測方法が分からない場合は、以下を参照してください。
手を動かしてさくさく理解する C/C++ 処理時間計測 入門
最初の要素を削除したい場合は pop_front() を用いる。
std::list<int> v{3, 1, 4, 1, 5};
v.pop_front(); // 先頭データ（この場合は 3）を削除
最後の要素を削除したい場合は pop_back() を用いる。
std::list<int> v{3, 1, 4, 1, 5};
v.pop_back(); // 末尾データ（この場合は 5）を削除
pop_front(), pop_back() ともに、処理時間は O(1) と高速である。
任意の位置の要素を削除したい場合は erase(iterator) を使用する。
std::list<int> v{3, 1, 9, 4};
auto itr = v.begin();
++itr;
++itr; // 3番目の要素に移動
v.erase(itr); // 3番目の要素（9）を削除
erase() は削除した要素の次の要素へのイテレータを返す。
なので、リストに含まれる 1 の要素を全て削除したい場合は、以下のように記述する。
for(auto itr = lst.begin(); itr != v.end(); ) {
if( *itr == 1 ) // 要素が 1 ならば
itr = lst.erae(itr); // 要素を削除し、itr は次の要素を指す
else
++itr; // itr をひとつ進める
}
演習問題：解答例
ここまで、双方向リストの宣言、値の参照・代入・追加・削除方法について説明した。
それらを使えば、挿入削除処理を高速化したい場合等に、通常配列を双方向リストに置き換えることができるはずだ。
実は双方向リストにはこれまで説明してきたもの以外にも便利な機能がメンバ関数としていくつも用意されている。
配列が空かどうかをチェックしたり、要素数を調べたり、サイズを変更することもできる。
これらは通常配列に対する明らかなアドバンテージである。
「bool empty()」は双方向リストが空かどうかを判定する関数。
次に出てくる size() を使って、size() == 0 と判定するのと同等だ。
が、コンテナクラスによっては size() 計算よりも empty() の方が高速な場合がある。
なので、list などのコンテナクラスに対しては empty() を使うことが推奨されている。
「size_t size()」は、要素数を返す関数。
通常配列だと「sizeof(data)/sizeof(data[0])」のように記述しないと、要素数を取得できないが、
list であれば「data.size()」と簡潔かつ分かりやすく書ける。
※ size_t はサイズを表す型で、符号なし整数の組み込み型である。ちなみに、sizeof() も size_t 型を返す。
「front()」は先頭要素を返す関数。「*(lst.begin())」と記述するのと同等。
「back()」は末尾要素を返す関数。「auto itr = lst.end(); *--itr)」と記述するのと同等。
「clear()」は双方向リストを空にする関数。
サイズを0にする。vector とは違い、要素を delete し、メモリが解放される。
「resize(size_t sz)」は要素数を指定サイズに設定する関数。
sz が現在のサイズを超えていれば、型のデフォルト値が格納される。
サイズが増えた部分の値を指定したい場合は、「resize(size_t sz, 値)」と、第2引数で値を指定する。
サイズが減った場合は、要素が delete され、その分のメモリが解放される。
演習問題：解答例
list はクラスなので、list オブジェクトを引数として関数に渡すことが可能です。
例えば、下記の様に list<int> を引数とし、要素の最大値を返す関数を定義することが出来ます。
int max(std::list<int> v)
{
int maxVal = INT_MIN; // 整数最小値
for(auto itr = v.begin(); itr != v.end(); ++itr) {
if( *itr > maxVal )
maxVal = *itr;
}
return maxVal;
}
int main()
{
std::list<int> v;
v に要素を追加;
int mx = max(v);
.....
}
上記関数は正しく動作するのですが、引数の型が実体になっているので、関数コール時にコピーコンストラクタが呼ばれて、
コピーされたオブジェクトが関数に渡されます。
要素数が多い場合、コピーコンストラクタの処理はそれなりに重くなります。
なので、コピーする必然性がなければ、実体ではなく参照渡しにするのが普通です。
int max(std::list<int> &v)
{
..... // 中身はいっしょ
}
こうしておけば、関数に渡されるのはオブジェクトのアドレスなので、処理時間を要することはありません。
さらに言えば、この場合は、関数の中で要素を修正しないので、const std::list<int> &v とした方がよいです。
当然ながら、関数内で要素を修正する場合は、const を付けないようにします。
このように、std::list は簡潔な表記で、関数の引数としてオブジェクトを渡すことが可能です。
それに比べ通常配列だと、サイズ情報を保持していないので、引数に要素数または最後のアドレスを指定する必要があります。
この点も std::list が優れているところです。
実は C++ には結構便利なアルゴリズムがいくつも用意されている。
参照：http://www.cplusplus.com/reference/algorithm/
ここでは、list に対してよく使うかもしれないアルゴリズムを2つだけ簡単に説明する
「accumulate(オブジェクト名.begin(), オブジェクト名.end(), init)」は、双方向リストの最初から最後まで、要素を積算（全加算）するものだ。
最後の引数は初期値で、通常は0を指定する。
なお、accumulate を利用するには「#include <numeric>」が必要。
#include <numeric>
.....
std::list<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::cout << std::accumulate(v.begin(), v.end(), 0) << "\n";
一部を積算したい場合は、「accumulate(first, last, 0)」の様にイテレータで範囲を指定する。
「reverse(オブジェクト名.begin(), オブジェクト名.end())」は、双方向リストの要素を逆順にする関数だ。
演習問題：解答例
本稿で説明したのは、std::list の基本的な部分のみである。説明していないメソッドもたくさんある。
それらについては以下のサイトなどで勉強してほしい。
通常、std::list はテンプレートライブラリになっており、ソースが公開されている。
ソースを探しだして、読んでみると勉強になるかもしれない。
ただし、かなりレベルが高いコードなので、ちゃんと理解するのはそれなりの能力と知識と経験が必要だ。
上級者でないと無理だ。ちょっと見て理解不能と思ったら、すぐに勇気ある撤退をしよう。
型固定の双方向リスト List を実装する演習問題も用意している。
これをやり遂げれば、list の中身がどうなっているか、ある程度想像がつくようになるので、ぜひ挑戦してみて欲しい。
std::list<char> str;
std::list<double> pos(3);
std::list<char> a(10, 'a');
std::list<double> d{1.1, 2.2, 3.3, 4.4};
std::list<int> org{1, 2, 3};
std::list<int> x(org); // コピーコンストラクタ
std::list<int> lst{1, 2, 3, 4, 5, 6, 7};
for(auto itr = lst.begin(); itr != lst.end(); ++itr)
std::cout << *itr << "\n";
std::list<int> lst{1, 2, 3, 4, 5, 6, 7};
for(auto itr = lst.begin(); itr != lst.end(); ++itr)
*itr = 0;
std::list<int> lst;
for(int i = 1; i <= 10; ++i)
lst.push_back(i);
std::list<int> lst(10, 0);
auto itr = lst.begin();
for(int i = 0; i < 5; ++i)
++itr; // itr を先頭から５つ進める
lst.insert(itr, 7);
void listPushBack(int n) // n は繰り返し回数
{
std::list<int> lst;
Timer tm;
tm.restart();
for (int i = 0; i < n; ++i) {
lst.push_back(0);
}
auto dur = tm.elapsed();
std::cout << "count = " << n << ", time = " << dur << "\n";
}
int main()
{
cout << "list.push_back():\n";
listPushBack(10);
listPushBack(100);
listPushBack(1000);
listPushBack(10000);
return 0;
}
void vectorPushBack(int n) // n は繰り返し回数
{
std::vector v;
Timer tm;
tm.restart();
for (int i = 0; i < n; ++i) {
v.push_back(0);
}
auto dur = tm.elapsed();
std::cout << "count = " << n << ", time = " << dur << "\n";
}
int main()
{
cout << "vector.push_back():\n";
vectorPushBack(10);
vectorPushBack(100);
vectorPushBack(1000);
vectorPushBack(10000);
return 0;
}
void listPushFront(int n) // n は繰り返し回数
{
std::list lst;
Timer tm;
tm.restart();
for (int i = 0; i < n; ++i) {
lst.push_back(0);
}
auto dur = tm.elapsed();
std::cout << "count = " << n << ", time = " << dur << "\n";
}
int main()
{
cout << "list.push_front():\n";
listPushFront(10);
listPushFront(100);
listPushFront(1000);
listPushFront(10000);
return 0;
}
void vectorPushFront(int n) // n は繰り返し回数
{
std::vector v;
Timer tm;
tm.restart();
for (int i = 0; i < n; ++i) {
v.insert(v.begin(), 0);
}
auto dur = tm.elapsed();
std::cout << "count = " << n << ", time = " << dur << "\n";
}
int main()
{
cout << "vector.push_front():\n";
vectorPushFront(10);
vectorPushFront(100);
vectorPushFront(1000);
vectorPushFront(10000);
return 0;
}
std::list<int> v{3, 1, 4, 1};
v.pop_front();
std::list<int> v{3, 1, 4, 1};
v.pop_back();
std::list<int> v{3, 1, 4, 1};
auto itr = v.begin();
++itr;
++itr; // 4 まで進める
v.erase(itr);
for(auto itr = v.begin(); itr != v.end(); ++itr) {
std::cout << *itr << "\n";
}
std::list<int> v;
cout << v.empty() << "\n";
cout << v.size() << "\n";
std::list<int> v{3, 1, 4};
cout << v.empty() << "\n";
cout << v.size() << "\n";
std::list<int> v{3, 1, 4};
cout << v.front() << "\n";
cout << v.back() << "\n";
std::list<int> v{3, 1, 4};
v.clear();
cout << v.empty() << "\n";
cout << v.size() << "\n";
std::list<int> v{3, 1, 4};
v.resize(8);
cout << v.empty() << "\n";
cout << v.size() << "\n";
std::list<int> v{3, 1, 4};
v.resize(1);
cout << v.empty() << "\n";
cout << v.size() << "\n";
#include <numeric>
.....
std::list<int> v(10000);
for(auto itr = v.begin(); itr != v.end(); ++itr)
*itr = rand() % 100;
std::cout << std::accumulate(v.begin(), v.end(), 0) << "\n";
std::list lst{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
for (auto itr = lst.begin(); itr != lst.end(); ++itr) {
std::cout << *itr << " ";
}
std::cout << "\n";
reverse(lst.begin(), lst.end());
for (auto itr = lst.begin(); itr != lst.end(); ++itr) {
std::cout << *itr << " ";
}
std::cout << "\n";