今回は標準ライブラリ (Standard Template Library) の中から list の基本的な使い方を説明します。
STL の list は「双方向リスト (doubley-linked list)」を実装したコンテナクラスです。単方向リストのセル (Cell) は、データを格納するメンバ変数と、直後のセルへのポインタを格納するメンバ変数から構成されています。双方向リストは名前が示すように、直後のセルだけでなく直前のセルへのポインタを持たせたデータ構造です。双方向リストは「重連結リスト」と呼ばれることもあります。
prev next prev next prev next
┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐
←─┼・│ │・│←─┼・│ │・│←─┼・│ │・│←─
─→│・│ │・┼─→│・│ │・┼─→│・│ │・┼─→
└─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘
data data data
図 : 双方向リストのセル
単方向リストは末尾の方向にしかセルをたどることができませんが、双方向リストでは前後どちらの方向へもセルをたどることができます。セルを削除する場合も、前後のセルがわかるので簡単に削除することができます。
head ──┐
↓
ヘッダセル
┌─┬─┬─┐
┌←─┼ │ │ │←───────────────────┐
│┌→│ │ │ ┼─→─────────────────┐│
││ └─┴─┴─┘ ││
││ next prev ││
││ ││
││ Cell A Cell B Cell C ││
││ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ││
│└←┼ │Ａ│ │←─┼ │Ｂ│ │←─┼ │Ｃ│ │←┘│
└─→│ │ │ ┼─→│ │ │ ┼─→│ │ │ ┼─→┘
└─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘
prev next prev next prev next
図 : 双方向リストの構造
┌───────────┐
│ ┌─┬─┬─┐ │
└←─┼ │ │ │←─┘
┌─→│ │ │ ┼─→┐
│ └─┴─┴─┘ │
└───────────┘
データがない場合はヘッダセル自身を格納
図 : 空の双方向リスト
双方向リストを使う場合、上図のようにヘッダセルを用意して、双方向リストを環状に構成する方法が一般的です。ヘッダセルにはデータを格納しません。ヘッダセルの next が指し示すセルが先頭で、prev が指し示すセルが最後尾になります。ヘッダセルが先頭と最後尾のセルを参照しているので、両端でのデータ操作が簡単にできます。データがない空リストの場合は、上図に示すようにポインタ変数 next と prev の値はヘッダセル自身になります。
なお、これは一般的な話であり、お使いのＣ++標準ライブラリがこのような構造になっているとは限りません。ここでは、双方向リストのセルは前後のセルへのポインタを持っていることを理解してもらえれば十分です。
list を使用するときは、ヘッダファイル list をインクルードしてください。変数の宣言は次のように行います。
list<データ型> 変数名;
list はテンプレートなので、< > の中に格納する要素のデータ型を指定してください。この場合、空 (要素数が 0) のリストが生成されます。list のコンストラクタを下表に示します。
| 書式 | 機能 |
|---|---|
| list(n) | 大きさ n のリストを生成 |
| list(n, m) | 大きさ n のリストを生成して値 m で初期化する |
| list(const list& v) | コピーコンストラクタ |
| list(s, e) | イテレータ s から e の手前までの要素を格納したリストを生成する |
初期値を指定しない場合、list<T> の要素は T() で初期化されます。代入演算子 = による list の代入も可能です。また、最近の規格 (C++11) では、配列と同様に { ... } を使って list を初期化することができるようになりました。
list<int> a{1, 2, 3, 4, 5};
list<int> b = {1, 2, 3, 4, 5};
この方法は list を簡単に初期化できるので、とても便利だと思います。
簡単な使用例を示しましょう。
リスト : list の簡単な使用例 (sample1901.cpp)
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> a(10);
for (int x : a) cout << x << " ";
cout << endl;
list<double> b(10, 1.2345);
for (double x : b) cout << x << " ";
cout << endl;
list<string> c {"foo", "bar", "baz", "oops"};
for (string x : c) cout << x << " ";
cout << endl;
}
list は vector と違って添字演算子 [] やメンバ関数 at() で要素にアクセスすることはできません。範囲 for 文で要素を順番に取り出していくことはできます。プログラムは簡単なので説明は割愛します。実行結果は次のようになります。
$ clang++ sample1901.cpp $ ./a.out 0 0 0 0 0 0 0 0 0 0 1.2345 1.2345 1.2345 1.2345 1.2345 1.2345 1.2345 1.2345 1.2345 1.2345 foo bar baz oops
list は先頭と末尾に対する操作を定数時間 (O(1)) で行うことができます。データの追加と取得を行うメンバ関数を下表に示します。
| メンバ関数 | 機能 |
|---|---|
| void push_front(const T& x) | データ x をリストの先頭に追加 |
| void push_back(const T& x) | データ x をリストの末尾に追加 |
| T& front() | リストの先頭要素の参照を返す |
| T& back() | リストの末尾要素の参照を返す |
| void pop_front() | リストの先頭要素を取り除く |
| void pop_back() | リストの末尾要素を取り除く |
vector は末尾にデータを追加する push_back() と末尾からデータを取り除く pop_back() だけでしたが、list はそれだけではなく、先頭にデータを追加する push_front() と先頭要素を取り除く pop_front() があります。
簡単な使用例を示しましょう。
リスト : データの追加と取り出し (sample1902.cpp)
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> a;
for (int i = 0; i < 5; i++) {
a.push_front(i);
a.push_back(i + 10);
}
for (int x : a) cout << x << " ";
cout << endl;
int& x1 = a.front();
int& x2 = a.back();
cout << x1 << endl;
cout << x2 << endl;
x1 = 100;
x2 = 200;
for (int x : a) cout << x << " ";
cout << endl;
for (int i = 0; i < 4; i++) {
cout << a.front() << " ";
a.pop_front();
}
cout << endl;
for (int i = 0; i < 4; i++) {
cout << a.back() << " ";
a.pop_back();
}
cout << endl;
}
$ clang++ sample1902.cpp $ ./a.out 4 3 2 1 0 10 11 12 13 14 4 14 100 3 2 1 0 10 11 12 13 200 100 3 2 1 200 13 12 11
list は双方向イテレータをサポートしています。++ 演算子で次の要素に進み、-- 演算子で一つ前の要素に戻ることができます。イテレータを生成するメンバ関数を下表に示します。
| メンバ関数 | 機能 |
|---|---|
| begin() | 先頭要素を指し示すイテレータを返す |
| end() | 終端を指し示すイテレータを返す |
| cbegin() | 先頭要素を指し示す const イテレータを返す |
| cend() | 終端を指し示す const イテレータを返す |
| rbegin() | 先頭要素を指し示すリバースイテレータを返す |
| rend() | 終端を指し示すリバースイテレータを返す |
| crbegin() | 先頭要素を指し示す const リバースイテレータを返す |
| crend() | 終端を指し示す const リバースイテレータを返す |
const イテレータは要素を更新することができません。リバースイテレータは末尾要素が先頭で、先頭要素が末尾になります。要素が n 個ある場合、n - 1 番目の要素が先頭で、0 番目の要素が末尾になります。
イテレータのデータ型は次のようになります。
list<T>::iterator // 通常のイテレータ list<T>::const_iterator // const イテレータ list<T>::reverse_iterator // リバースイテレータ list<T>::const_reverse_iterator // const リバースイテレータ
最近の規格 (C++11) を利用できるコンパイラでは auto を使ったほうが簡単でしょう。
簡単な使用例を示します。
リスト : イテレータの使用例 (sample1903.cpp)
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> a = {1,2,3,4,5,6,7,8};
for (list<int>::const_iterator iter = a.cbegin(); iter != a.cend(); ++iter)
cout << *iter << " ";
cout << endl;
for (auto iter = a.begin(); iter != a.end(); ++iter) *iter *= 2;
for (auto iter = a.rbegin(); iter != a.rend(); ++iter)
cout << *iter << " ";
cout << endl;
}
$ clang++ sample1903.cpp $ ./a.out 1 2 3 4 5 6 7 8 16 14 12 10 8 6 4 2
iter が const イテレータの場合、*iter でデータを参照することはできても、*iter = 10 のように書き換えることはできません。コンパイルエラーになります。
list はメンバ関数 insert() でリストの途中にデータを挿入したり、メンバ関数 erase() でリストの途中の要素を取り除くことができます。
| メンバ関数 | 機能 |
|---|---|
| insert(it, x) | イテレータ it の位置にデータ x を挿入する |
| insert(it, n, x) | イテレータ it の位置にデータ x を n 個挿入する |
| insert(it, s, e) | イテレータ it の位置にイテレータ s から e の手前までの要素を挿入する |
| erase(it) | イテレータ it の位置の要素を削除する |
| erase(s, e) | イテレータ s から e の手前までの要素を削除する |
list の場合、イテレータの位置に対するデータの挿入 (または削除) は、セルを挿入 (または削除) するだけです。vector のように要素を移動する必要がないので、操作は定数時間で行うことができます。
簡単な使用例を示しましょう。
リスト : insert と erase の使用例 (sample1904.cpp)
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> a = {1, 2, 3, 4, 5};
list<int> b = {10, 20, 30, 40, 50};
a.insert(a.begin(), 0);
auto iter1 = a.begin();
advance(iter1, 1);
a.insert(iter1, 5, 1);
a.insert(a.end(), b.begin(), b.end());
for (int x: a) cout << x << " ";
cout << endl;
a.erase(a.begin());
auto iter2 = a.begin();
advance(iter2, 5);
a.erase(a.begin(), iter2);
for (int x: a) cout << x << " ";
cout << endl;
}
$ clang++ sample1904.cpp $ ./a.out 0 1 1 1 1 1 1 2 3 4 5 10 20 30 40 50 1 2 3 4 5 10 20 30 40 50
イテレータの移動は関数 advance(it, n) を使って行うことができます。advance() は引数のイテレータ it を n だけ移動します。ランダムイテレータと違って、イテレータの移動は n に比例する時間がかかります。また、関数 distance() でイテレータの距離を求めることもできますが、これも距離に比例した時間がかかります。ご注意くださいませ。
vector と同様に、a.insert(a.end(), b.begin(), b.end()) は list a に list b を連結することになります。
erase() のほかにも、リストの要素を削除する関数に remove() と remove_if() があります。remove() は引数と等しい要素をすべて削除します。remove_if() は叙述関数が真を返す要素をすべて削除します。
Common Lisp にも関数 remove と remove-if がありますが、これらの関数は新しいリストを生成して返すのに対し、list の remove() と remove_if() はリストを破壊的に修正することに注意してください。Common Lisp の delete と delete-if とほぼ同じ動作になります。
簡単な例を示しましょう。
リスト : remove と remove_if の使用例 (sample1905.cpp)
#include <iostream>
#include <list>
using namespace std;
bool is_even(int x) { return x % 2 == 0; }
bool is_odd(int x) { return x % 2 != 0; }
int main()
{
list<int> a = {1,2,1,2,3,1,2,3,4};
a.remove(1);
for (int x : a) cout << x << " ";
cout << endl;
cout << a.size() << endl;
list<int> b = {1,2,3,4,5,6,7,8,9,10};
b.remove_if(is_even);
for (int x : b) cout << x << " ";
cout << endl;
cout << b.size() << endl;
b.remove_if(is_odd);
cout << b.size() << endl;
cout << b.empty() << endl;
}
$ clang++ sample1905.cpp $ ./a.out 2 2 3 2 3 4 6 1 3 5 7 9 5 0 1
メンバ関数 size() はリストの要素数を返します。empty() はリストが空であれば true を返します。リストを空にするメンバ関数 clear() もあります。
メンバ関数 splice() はイテレータで指定した位置に引数のリストを挿入します。このとき、引数のリストから要素が取り除かれます。
1 は x の要素がすべて p の位置に挿入されて、x は空リストになります。2 は x の s にある位置の要素を p の位置に挿入します。s が指し示す要素は削除されます。3 は x の s から e の一つ手前までの要素を p の位置に挿入します。挿入した要素は x から削除されます。
簡単な使用例を示しましょう。
リスト : splice の使用例 (sample1906.cpp)
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> a = {1,2,3,4,5,6,7,8};
list<int> b = {10, 20, 30, 40, 50};
a.splice(a.begin(), b, b.begin());
for (int x : a) cout << x << " ";
cout << endl;
for (int x : b) cout << x << " ";
cout << endl;
a.splice(a.begin(), b);
for (int x : a) cout << x << " ";
cout << endl;
for (int x : b) cout << x << " ";
cout << endl;
}
$ clang++ sample1906.cpp $ ./a.out 10 1 2 3 4 5 6 7 8 20 30 40 50 20 30 40 50 10 1 2 3 4 5 6 7 8
list はランダムアクセスができないので、algorithm の関数 sort() を利用することができません。このため、list のメンバ関数にリストをソートする sort() が用意されています。
簡単な例を示しましょう。
リスト : sort の使用例 (sample1907.cpp)
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> a = {5,6,4,7,3,8,2,9,1,0};
a.sort();
for (int x : a) cout << x << " ";
cout << endl;
a.sort(greater<int>());
for (int x : a) cout << x << " ";
cout << endl;
}
$ clang++ sample1907.cpp $ ./a.out 0 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 0
マージ (merge : 併合) とは、複数のソート済みのリストを一つのソート済みのリストにまとめる操作です。次の図を見てください。
┌─ [1, 3, 5] : リスト a
[] ←┤
└─ [2, 4, 6] : リスト b
小さい方をセットする
┌─ [3, 5] : リスト a
[1] ←┘
[2, 4, 6] : リスト b
1 をセットする
[3, 5] : リスト a
[1, 2] ←┐
└─ [4, 6] : リスト b
2 をセットする
データがなくなるまで繰り返す
図 : リストのマージ
2 つのリスト a と b があります。これらのリストはソート済みとしましょう。これらのリストをソート済みのリストにまとめることを考えます。a と b はソート済みなので先頭のデータがいちばん小さな値です。したがって、上図のように先頭のデータを比較し、小さい方のデータを取り出して順番に並べていけば、ソート済みのリストにまとめることができます。途中でどちらかのリストが空になったら、残ったリストのデータをそのまま追加します。
上図は 2 つのリストをマージして新しいリストを生成しますが、list のメンバ関数 merge() は引数のリストの要素を取り出して、それを自分自身のリストに挿入していくことでマージを行います。引数のリストは空リストになります。
簡単な例を示しましょう。
リスト : merge の使用例 (sample1908.cpp)
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int> a = {2,4,6,8};
list<int> b = {1,3,5,7,9};
a.merge(b);
for (int x : a) cout << x << " ";
cout << endl;
cout << b.size() << endl;
list<int> c = {9,7,5,3,1};
list<int> d = {8, 6, 4, 2};
c.merge(d, greater<int>());
for (int x : c) cout << x << " ";
cout << endl;
}
$ clang++ sample1908.cpp $ ./a.out 1 2 3 4 5 6 7 8 9 0 9 8 7 6 5 4 3 2 1
このほかにも便利なメンバ関数がありますし、vector と同様に algorithm の関数を利用することができます。興味のある方は標準ライブラリのリファレンスをお読みくださいませ。