Linux Programming

標準ライブラリの基礎知識 (list 編)

今回は標準ライブラリ (Standard Template Library) の中から list の基本的な使い方を説明します。

●双方向リストとは？

STL の list は「双方向リスト (doubley-linked list)」を実装したコンテナクラスです。単方向リストのセル (Cell) は、データを格納するメンバ変数と、直後のセルへのポインタを格納するメンバ変数から構成されています。双方向リストは名前が示すように、直後のセルだけでなく直前のセルへのポインタを持たせたデータ構造です。双方向リストは「重連結リスト」と呼ばれることもあります。

                  図 : 双方向リストのセル

単方向リストは末尾の方向にしかセルをたどることができませんが、双方向リストでは前後どちらの方向へもセルをたどることができます。セルを削除する場合も、前後のセルがわかるので簡単に削除することができます。

双方向リストを使う場合、下図のようにヘッダセルを用意して、双方向リストを環状に構成する方法が一般的です。

                       図 : 双方向リストの構造

ヘッダセルにはデータを格納しません。ヘッダセルの next が指し示すセルが先頭で、prev が指し示すセルが最後尾になります。ヘッダセルが先頭と最後尾のセルを参照しているので、両端でのデータ操作が簡単にできます。

データがない空リストの場合は、下図に示すようにポインタ変数 next と prev の値はヘッダセル自身になります。

  データがない場合はヘッダセル自身を格納

        図 : 空の双方向リスト

なお、これは一般的な話であり、お使いのＣ++標準ライブラリがこのような構造になっているとは限りません。ここでは、双方向リストのセルは前後のセルへのポインタを持っていることを理解してもらえれば十分です。

●list の宣言と初期化

list を使用するときは、ヘッダファイル list をインクルードしてください。変数の宣言は次のように行います。

list<データ型> 変数名;

list はテンプレートなので、< > の中に格納する要素のデータ型を指定してください。この場合、空 (要素数が 0) のリストが生成されます。list のコンストラクタを下表に示します。

初期値を指定しない場合、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)) で行うことができます。データの追加と取得を行うメンバ関数を下表に示します。

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 のイテレータ

list は双方向イテレータをサポートしています。++ 演算子で次の要素に進み、-- 演算子で一つ前の要素に戻ることができます。イテレータを生成するメンバ関数を下表に示します。

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() でリストの途中の要素を取り除くことができます。

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. splice(iterator p, list& x);
2. splice(iterator p, list& x, iterator s);
3. splice(iterator p, list& x, iterator s, iterator e);

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 : 併合) とは、複数のソート済みのリストを一つのソート済みのリストにまとめる操作です。次の図を見てください。

      図 : リストのマージ

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 の関数を利用することができます。興味のある方は標準ライブラリのリファレンスをお読みくださいませ。

標準ライブラリの基礎知識 (map 編)

今回は標準ライブラリ (Standard Template Library) の中から map の基本的な使い方を説明します。

●連想配列とは？

一般に、キー (key) と値 (value) を関連付けて格納するデータ構造を「連想配列 (assocative array)」といいます。連想配列は多くのプログラミング言語でサポートされていて、プログラミング言語によっては、ハッシュ (hash), 辞書 (dictonary), マップ (map) などと呼ばれています。Ｃ++の場合、STL の map が連想配列で、実装には平衡二分木が使われています。スクリプト言語では連想配列の実装に「ハッシュ法」を用いることが多く、連想配列のことを「ハッシュ」と呼ぶようになりました。

●map の宣言と初期化

map を使用するときは、ヘッダファイル map をインクルードしてください。変数の宣言は次のように行います。

map<キーのデータ型, 値のデータ型> 変数名;

map はテンプレートなので、< > の中にキーのデータ型と値のデータ型を指定してください。この場合、空 (要素数が 0) の連想配列が生成されます。キーの比較にはデフォルトで演算子 < が用いられます。キーを表すデータ型に bool operator<() が定義されていないとコンパイルエラーになります。ご注意くださいませ。

map のコンストラクタを下表に示します。

コピーコンストラクタのほかにも代入演算子 = による map の代入も可能です。イテレータを使って map<K, V> を初期化する場合、その要素は構造体 pair<K, V> でなければいけません。また、最近の規格 (C++11) では、配列と同様に { ... } を使って map を初期化することができるようになりました。このときも要素は構造体 pair<K, V> になります。

要素のアクセスは添字演算子 [] で行うことができます。map は平衡二分木を使って実装されています。要素数を N とすると、map はデータの探索、挿入、削除を log₂ N に比例する時間で実行することができます。拙作のページで作成した単純な二分探索木は、左右の部分木のバランスが崩れることがあるので、最悪の場合は N に比例する時間がかかります。平衡木は最悪の場合でも log₂ N に比例する時間で実行することができます。

たとえば、マップが map<string, int> a と宣言されている場合、a["foo"] = 10 でマップ a のキー "foo" に 10 をセットすることができます。キーが存在しない場合は、マップにキーが登録されます。キーが存在する場合、キーに対応する値が書き換えられます。a["foo"] でキー "foo" の値を求めることができます。キーが存在しない場合、値のデフォルト値 V() が返されます。なお、キーの有無はメンバ関数 find() で判定することができます。これはあとで説明します。

それでは簡単な使用例を示しましょう。

リスト : map の簡単な使用例 (sample1909.cpp)

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main()
{
  map<string, int> a;
  a["foo"] = 1;
  a["bar"] = 2;
  a["baz"] = 3;
  cout << a["foo"] << endl;
  cout << a["oops"] << endl;
  for (pair<string, int> x : a)
    cout << "(" << x.first << "," << x.second << ")\n";

  vector<pair<string, int>> b = {
    {"Foo", 10}, {"Bar", 20}, {"Baz", 30}
  };
  map<string, int> c(b.begin(), b.end());
  for (pair<string, int> x : c)
    cout << "(" << x.first << "," << x.second << ")\n";

  map<string, int> d = {
    {"FOO", 10}, {"BAR", 20}, {"BAZ", 30}
  };
  for (pair<string, int> x : c)
    cout << "(" << x.first << "," << x.second << ")\n";
}

構造体 pair のメンバ変数 (public) は first と second の 2 つがあります。map で pair を使用する場合、first にキーを、second に値をセットします。pair は構造体なので、{ ... } でメンバ変数を初期化することができます。map は範囲 for 文で要素を順番に取り出していくこともできます。プログラムは簡単なので説明は割愛します。実行結果は次のようになります。

$ clang++ sample1909.cpp
$ ./a.out
1
0
(bar,2)
(baz,3)
(foo,1)
(oops,0)
(Bar,20)
(Baz,30)
(Foo,10)
(Bar,20)
(Baz,30)
(Foo,10)

●map のイテレータ

map は双方向イテレータをサポートしています。++ 演算子で次の要素に進み、-- 演算子で一つ前の要素に戻ることができます。イテレータを生成するメンバ関数を下表に示します。

const イテレータは要素を更新することができません。map の場合、先頭要素が一番小さなキー、末尾の要素が一番大きなキーになります。マップの要素をイテレータで順番に取り出すと、キーは昇順に出力されます。つまり、二分木を通りがけ順で巡回するわけです。リバースイテレータはその逆になります。

イテレータのデータ型は次のようになります。

map<K, V>::iterator               // 通常のイテレータ
map<K, V>::const_iterator         // const イテレータ
map<K, V>::reverse_iterator       // リバースイテレータ
map<K, V>::const_reverse_iterator // const リバースイテレータ

最近の規格 (C++11) を利用できるコンパイラでは auto を使ったほうが簡単でしょう。

簡単な使用例を示します。

リスト : イテレータの使用例 (sample1910.cpp)

#include <iostream>
#include <map>
using namespace std;

int main()
{
  map<string, int> a = {
    {"foo", 1}, {"bar", 2}, {"baz", 3}, {"oops", 4}, {"hello", 5}
  };
  for (map<string, int>::const_iterator iter = a.cbegin(); iter != a.end(); ++iter)
    cout << "(" << iter->first << "," << iter->second << ")\n";
  for (auto iter = a.begin(); iter != a.end(); ++iter)
    iter->second *= 10;
  for (auto iter = a.rbegin(); iter != a.rend(); ++iter)
    cout << "(" << iter->first << "," << iter->second << ")\n";
}

$ clang++ sample1910.cpp
$ ./a.out
(bar,2)
(baz,3)
(foo,1)
(hello,5)
(oops,4)
(oops,40)
(hello,50)
(foo,10)
(baz,30)
(bar,20)

イテレータが指し示す要素のデータ型は pair<const K, V> です。値は書き換えることができますが、キーは参照することしかできません。

●データの探索

map は添字演算子 [] でキーの有無をチェックすることはできません。この場合、メンバ関数 find() を使います。find() はキーを見つけたらそれを指し示すイテレータを返します。見つからない場合は終端を指し示すイテレータを返します。

簡単な使用例を示します。

リスト : find の使用例 (sample1911.cpp)

#include <iostream>
#include <map>
using namespace std;

int main()
{
  map<string, int> a = {
    {"foo", 1}, {"bar", 2}, {"baz", 3}, {"oops", 4}, {"hello", 5}
  };
  auto iter = a.find("baz");
  if (iter != a.end()) {
    cout << iter->second << endl;
  } else{
    cout << "not found\n";
  }
  iter = a.find("world");
  if (iter != a.end()) {
    cout << iter->second << endl;
  } else{
    cout << "not found\n";
  }
}

$ clang++ sample1911.cpp
$ ./a.out
3
not found

このほかにも、マップの最初の要素 (最小値) を求めるメンバ関数 lower_bound() や最後の要素 (最大値) を求める upper_bound() があります。これらの関数の返り値は find() と同じです。

●データの挿入

データの挿入はメンバ関数 insert() でも行うことができます。引数のデータ型は pair<K, V> で、返り値のデータ型は pair<iterator, bool> です。実際にデータを挿入した場合、bool は true になります。同じキーが存在している場合、値は書き換えられずに、bool は false になります。iterator は要素へのイテレータです。

簡単な例を示しましょう。

リスト : insert の使用例 (sample1912.cpp)

#include <iostream>
#include <map>
using namespace std;

int main()
{
  map<string, int> a = {
    {"foo", 1}, {"bar", 2}, {"baz", 3}
  };
  auto r = a.insert(pair<string, int>("oops", 4));
  cout << r.second << endl;
  r = a.insert(pair<string, int>("foo", 10));
  cout << r.second << endl;
  for (auto p : a)
    cout << "(" << p.first << "," << p.second << ")\n";
}

$ clang++ sample1912.cpp
$ ./a.out
1
0
(bar,2)
(baz,3)
(foo,1)
(oops,4)

●データの削除

データの削除はメンバ関数 erase() で行います。引数はキーで返り値は削除した要素の個数です。map の場合、キーと値の組は一つしかないので、要素を削除したら 1 を返し、キーが見つからない場合は 0 を返します。

簡単な使用例を示します。

リスト : erase の使用例 (sample1913.cpp)

#include <iostream>
#include <map>
using namespace std;

int main()
{
  map<string, int> a = {
    {"foo", 1}, {"bar", 2}, {"baz", 3}
  };
  string key[] = {
    "oops", "foo", "bar", "baz"
  };
  for (string k : key) {
    cout << a.erase(k) << endl;
    cout << a.size() << endl;
  }
  cout << a.empty() << endl;
}

$ clang++ sample1913.cpp
$ ./a.out
0
3
1
2
1
1
1
0
1

メンバ関数 size() は map の要素数を返します。empty() は map が空であれば true を、そうでなければ false を返します。また、map を空にするメンバ関数 clear() も用意されています。

●テンプレートで比較関数を指定する

キーの比較関数はテンプレートの第 3 引数で指定することができます。たとえば、比較関数 greater<string> を渡すと、キーを取り出すときは降順になります。簡単な使用例を示します。

リスト : 比較関数を指定する (sample1914.cpp)

#include <iostream>
#include <map>
using namespace std;

int main()
{
  map<string, int> a = {
    {"foo", 1}, {"bar", 2}, {"baz", 3}, {"oops", 4}
  };
  for (auto p : a)
    cout << p.first << endl;
  map<string, int, greater<string>> b = {
    {"foo", 1}, {"bar", 2}, {"baz", 3}, {"oops", 4}
  };
  for (auto p : b)
    cout << p.first << endl;
}

$ clang++ sample1914.cpp
$ ./a.out
bar
baz
foo
oops
oops
foo
baz
bar

このほかにも便利なメンバ関数がありますし、algorithm の関数で map に適用できるものもあります。興味のある方は標準ライブラリのリファレンスをお読みくださいませ。