C++編【標準ライブラリ】 第6章 list

先頭へ戻る

この章の概要

この章の概要です。

list

list は、STLコンテナの一種で、双方向連結リストアルゴリズムとデータ構造編【データ構造】第4章)を提供します。これを使うには、list という名前の標準ヘッダをインクルードする必要があります。

list は双方向のリストなので、手前の要素へのポインタを保持しており、その分だけメモリ使用量が増加しますし、要素の連結や削除の処理も複雑になります。単方向で構わない場面は割と多いので、この無駄を省きたいこともあるでしょう。まさにこのような場合のために、C++11 には、単方向連結リストを提供する forward_list が追加されています。

list は、次のように定義されています。

namespace std {
    template <typename T, typename Allocator = allocator<T> >
    class list {
    };
}

list はクラステンプレート(【言語解説】第20章)なので、使用時にはテンプレート引数の指定が必要です。テンプレートパラメータ T は、動的配列の要素の型です。例えば、int型の要素を扱いたいのであれば、以下のようになります。

std::list<int> intList;

もう1つのテンプレートパラメータ Allocator は、メモリ確保の方法を定義するアロケータと呼ばれるオブジェクトの指定です。テンプレートパラメータ Allocator はデフォルト値を持っているので省略することができます。多くの場合、省略しても list は活用できるので、本章では解説しません。アロケータについては、第32章で改めて取り上げます。


サイズ

list の場合、vector や string と違い「容量」という概念はありません。要素が1つ追加されるたびに、新たなメモリが割り当てられます。list は連結リストですから、連続的な領域を割り当てる訳ではありません。

「サイズ」の概念は、他のコンテナと同様に存在しており、単に、要素数のことです。sizeメンバ関数を使えば、現在の「サイズ」を取得できます。

サイズが 0 かどうかを知りたいときは、emptyメンバ関数を使用することができます。sizeメンバ関数が返す値が 0 かどうかでも確認できますが、確実な効率を得るためにも emptyメンバ関数を使って下さい。C++03 時点の sizeメンバ関数は、効率が悪い実装があり得ます。

C++11(sizeメンバ関数の計算量)

C++03 の sizeメンバ関数は、実際に連結リストを辿って、要素数をカウントしていく実装も許されていました。そのため、効率が非常に悪い可能性がありました。計算量(アルゴリズムとデータ構造編【導入】第1章)で言えば、O(n) です。

C++11 の sizeメンバ関数は、O(1) の計算量が保証されるようになりました。


サイズの最大値は max_sizeメンバ関数で取得できます。これは std::list<T>::size_type型で表現できる最大値になっている環境が多いですが、システムの都合でより小さい値になっている可能性もあります。

ここまでに登場したメンバ関数の使用例を挙げます。

#include <iostream>
#include <list>

int main()
{
    std::list<int> lst;

    for (int i = 0; i < 5; ++i) {
        lst.push_back(i);
    }

    std::cout << lst.max_size() << "\n"
              << lst.size() << std::endl;
}

実行結果

1073741823
5

resizeメンバ関数を使うと、サイズを変更できます。

現在のサイズよりも大きな値を指定すると、そのサイズになるまで要素を充填します。このとき、要素の型のデフォルトコンストラクタが使用されます。もし、第2引数を指定している場合には、その値を要素の初期化に使用します。現在のサイズよりも小さい値を指定した場合は、指定したサイズになるまで、要素が末尾にあるものから順に取り除かれます。

#include <iostream>
#include <list>

typedef std::list<int> IntList;

void PrintList(const IntList& lst)
{
    const IntList::const_iterator itEnd = lst.end();
    for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntList lst;

    lst.resize(5);
    PrintList(lst);

    lst.resize(10, 99);
    PrintList(lst);

    lst.resize(1);
    PrintList(lst);
}

実行結果

0
0
0
0
0

0
0
0
0
0
99
99
99
99
99

0

生成と初期化

list には、複数のコンストラクタが定義されているので、様々な方法でインスタンス化できます。

int main()
{
    const int a[] = {0, 1, 2, 3, 4};

    std::list<int> lst1;           // 空
    std::list<int> lst2(10);       // サイズ10 (要素はデフォルトコンストラクタで生成)
    std::list<int> lst3(10, 3);    // サイズ10 (要素はコピーコンストラクタで生成)
    std::list<int> lst4(lst2);     // 他の list からコピー
    std::list<int> lst5(a, a + 5); // イテレータで指定された範囲からコピー
}

この5通りのコンストラクタは、vector のものと同じ意味合いになっています。

lst1、lst3、lst5 の方法の場合は、アロケータを渡すデフォルト引数が隠されています。

lst2、lst3 の方法では、要素数を指定して、その個数分の要素を実際に生成しています。lst2 の場合は、デフォルトコンストラクタによる生成、lst3 の場合は、第2引数に指定した値を使って要素を生成し、コピーしています。

C++11 (生成と初期化)

C++11 で、コンストラクタ周りは強化されています。まず、std::initializer_list を使用できるようになりました。

int main()
{
    std::list<int> v6 {0, 1, 2};       // std::initializer_list
}

また、ムーブコンストラクタが追加されています。

int main()
{
    std::list<int> v7(std::move(v6));  // ムーブコンストラクタ
}

なお、ここまでに取り上げた方法のうち、v2 の形を除いたすべてで、引数の末尾でアロケータを指定できます。

破棄

デストラクタでは、list が内部で確保した連結リストが破棄されます。

仮想デストラクタ(【言語解説】第27章)ではないので、list を継承して使用することは不適切であることに注意して下さい

要素のアクセス

list は、連結リストという特性上、ランダムアクセスができません。そのため、vector のように、添字演算子や atメンバ関数のように、要素を直接アクセスする方法は用意されていません。

vector と共通で存在する関数は、frontメンバ関数backメンバ関数です。それぞれ、先頭要素の参照、末尾要素の参照を返します。型としては、std::list::reference型になります。

なお、list が空の場合に呼び出した場合は未定義の動作となるので注意して下さい

#include <iostream>
#include <vector>

int main()
{
    std::list<int> lst;

    for (int i = 0; i < 10; ++i) {
        lst.push_back(i);
    }

    std::cout << lst.front() << std::endl;
    std::cout << lst.back() << std::endl;
}

実行結果

0
9

list の要素をアクセスしたいときというのは、先頭から末尾までの各要素を順番にアクセスするという用途が多いです。このような操作には、イテレータを使います。

代入

list は、テンプレート引数が同一であれば、代入演算子を使ってコピーできます。

また、assignメンバ関数を使うこともできます。

#include <iostream>
#include <list>

typedef std::list<int> IntList;

void PrintList(const IntList& lst)
{
    const IntList::const_iterator itEnd = lst.end();
    for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntList lst;

    lst.assign(5, 3);  // 5個の 3 を代入
    PrintList(lst);

    const int a[10] = { 0, 10, 20, 30, 40, 50, 60, 70, 80, 90 };
    lst.assign(a, a + 10);  // 範囲内の要素を代入
    PrintList(lst);
}

実行結果

3
3
3
3
3

0
10
20
30
40
50
60
70
80
90

assignメンバ関数の1つ目の使い方は、第2引数に指定した要素のコピーを、第1引数に指定した個数だけ代入します。

2つ目の方は、イテレータを使って範囲を指定し、その範囲内にある要素のコピーを代入します。

C++11 (代入、assign の std::initializer_list対応)

C++11 の代入演算子および assignメンバ関数では、std::initializer_list を使えるようになりました。

#include <iostream>
#include <list>

typedef std::list<int> IntList;

void PrintList(const IntList& lst)
{
    const IntList::const_iterator itEnd = lst.end();
    for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntList lst;

    lst = { 0, 1, 2 };
    PrintList(lst);

    lst.assign({ 0, 10, 20 });
    PrintList(lst);
}

実行結果

0
1
2

0
10
20

C++11 (ムーブ代入演算子)

C++11 では、ムーブ代入演算子が追加されています。

#include <iostream>
#include <list>

typedef std::list<int> IntList;

void PrintList(const IntList& lst)
{
    const IntList::const_iterator itEnd = lst.end();
    for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntList lst1(5, 3);
    IntList lst2;

    lst2 = std::move(lst1);
    PrintList(lst1);
    PrintList(lst2);
}

実行結果


3
3
3
3
3

追加・挿入

要素を挿入する方法は幾つかあります。

list の場合、vector と違って、後続の要素をずらす必要性が無いため、コンテナ内の要素を指していたイテレータやポインタが無効化されることはありません。また、「容量」の概念も無いので、再確保&コピーが起こることもありません。この辺りは、連結リストならではの利点でしょう。

1つ目の方法として、push_backメンバ関数があります。これは、末尾に要素を追加します。

2つ目の方法は、push_frontメンバ関数です。こちらは、先頭に要素を追加します。

#include <iostream>
#include <list>

typedef std::list<int> IntList;

void PrintList(const IntList& lst)
{
    const IntList::const_iterator itEnd = lst.end();
    for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntList lst;

    for (int i = 0; i < 5; ++i) {
        lst.push_back(i);
    }

    for (int i = 0; i < 5; ++i) {
        lst.push_front(i);
    }

    PrintList(lst);
}

実行結果

4
3
2
1
0
0
1
2
3
4

3つ目の方法は、insertメンバ関数です。これは、イテレータを使って、任意の位置に要素を挿入します。

#include <iostream>
#include <list>

typedef std::list<int> IntList;

void PrintList(const IntList& lst)
{
    const IntList::const_iterator itEnd = lst.end();
    for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntList lst(5, 3);

    IntList::iterator it;

    it = lst.insert(lst.end()--, 0);   // 末尾に 0 を挿入
    PrintList(lst);

    lst.insert(it, 3, 99);             // 0 の手前に 99 を 3個挿入
    PrintList(lst);

    const int a[] = {10, 11, 12};
    lst.insert(lst.begin(), a, a + 3); // ある範囲から先頭へ挿入
    PrintList(lst);
}

実行結果

3
3
3
3
3
0

3
3
3
3
3
99
99
99
0

10
11
12
3
3
3
3
3
99
99
99
0

使い方が3通りありますが、どれでも第1引数が挿入位置を表しています。挿入位置は、イテレータを使って指定し、そのイテレータが指している位置へ挿入されます。例えば、beginメンバ関数で取得したイテレータを指定すれば、先頭要素になるように挿入できます。

1つ目の使い方では、第2引数に挿入する値を指定します。この形式の場合は、戻り値で、挿入された値を指すイテレータが返されます。

2つ目の使い方では、同じ値を複数個まとめて挿入できます。第2引数が個数、第3引数が挿入する値です。

3つ目の使い方では、第2第3の引数で指定した範囲内にある要素を挿入します。これは、別のコンテナや配列からコピーしたい場合に使います。

C++11(移動による挿入)

C++11 では、移動による挿入ができるようになっています。

まず、push_backメンバ関数が対応しています。

lst.push_back(std::move(value));

同様に、push_frontメンバ関数が対応しています。

lst.push_front(std::move(value));

insertメンバ関数の場合は、挿入する要素が1つだけになる形式のみ対応します。

lst.insert(it, std::move(value));

C++11(emplace_back、emplace)

push_back、push_front、insert の各メンバ関数は、list の外で挿入するオブジェクトを作り、それをコピー(または移動)する必要があります。これは、少なくとも一時オブジェクトを生成するコストが掛かるため(コピーの場合は、更にコピーのコスト)、使い方によっては非効率さがあります。

C++11 では、要素のコンストラクタに渡す引数だけを指定し、メンバ関数内でオブジェクトを作らせるという方法が使えるようになりました。push_backメンバ関数なら emplace_backメンバ関数が、push_frontメンバ関数なら emplace_frontメンバ関数が、insertメンバ関数なら emplaceメンバ関数が対応します。

std::list<MyClass> lst;

lst.push_back(MyClass(10, "abc"));   // 一時オブジェクトを作ってコピー
lst.emplace_back(10, "abc");         // コンストラクタの引数だけ指定し、関数内で生成

lst.push_front(MyClass(10, "abc"));  // 一時オブジェクトを作ってコピー
lst.emplace_front(10, "abc");        // コンストラクタの引数だけ指定し、関数内で生成

lst.insert(it, MyClass(10, "abc"));  // 一時オブジェクトを作ってコピー
lst.emplace(it, 10, "abc");          // コンストラクタの引数だけ指定し、関数内で生成

insertメンバ関数はオーバーロードされていますが、emplaceメンバ関数は1つだけです。

C++11(insert の std::initializer_list対応)

C++11 では、insertメンバ関数が std::initializer_list に対応しています。

lst.insert(it, {10, 20, 30});

C++11(insert のイテレータの const化)

C++03 までの insertメンバ関数は、要素の挿入位置を指定する第1引数の型が、std::list<T>::iterator型になっていました。そのため、この引数の意味は、挿入位置を示すことだけなので constイテレータで問題ないはずなのに、constイテレータを渡すことができません。

C++11 では、第1引数の型が std::list<T>::const_iterator型に改められています。

削除

「削除」は、コンテナから要素を取り除くということです。格納されている要素が new で生成されたものであるのなら、取り除くだけではなく delete を行わなければなりません。「削除」はそういった、必要な解放処理までは面倒を見ないことに注意して下さい。

まず、pop_backメンバ関数pop_frontメンバ関数があります。前者は末尾にある要素を削除し、後者は先頭にある要素を削除します。

#include <iostream>
#include <list>

typedef std::list<int> IntList;

void PrintList(const IntList& lst)
{
    const IntList::const_iterator itEnd = lst.end();
    for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntList lst;

    for (int i = 0; i < 5; ++i) {
        lst.push_back(i);
    }

    lst.pop_front();
    lst.pop_back();

    PrintList(lst);
}

実行結果

1
2
3

次に、eraseメンバ関数を使う方法です。

#include <iostream>
#include <list>
#include <iterator>

typedef std::list<int> IntList;

void PrintList(const IntList& lst)
{
    const IntList::const_iterator itEnd = lst.end();
    for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntList lst;

    for (int i = 0; i < 5; ++i) {
        lst.push_back(i);
    }

    lst.erase(lst.begin());  // 先頭要素を削除
    PrintList(lst);

    IntList::iterator it = lst.begin();
    std::advance(it, 1);
    lst.erase(it, lst.end());  // 先頭の次から末尾まで削除
    PrintList(lst);
}

実行結果

1
2
3
4

1

eraseメンバ関数の使い方は2通りで、イテレータを1つ渡すか、2つ渡すかの違いです。前者の場合はイテレータが指す要素を削除し、後者の場合は2つのイテレータで作られる範囲内の要素が削除されます。

eraseメンバ関数は、削除された要素の次の有効な要素を指すイテレータが返されます

std::advance関数は、イテレータを指定した要素数分だけ進める標準の関数です。vector のイテレータと違って、list のイテレータは +演算子や -演算子で進めたり戻したりすることができないので、代わりに std::advance関数を使います。なお、この関数を使うには、iterator という名前のヘッダをインクルードする必要があります。

std::advance関数のようなイテレータに関する補助関数は、第14章で改めて取り上げます。

次に、removeメンバ関数、および remove_ifメンバ関数です。前者は指定した値を持った要素をすべて削除し、後者は指定した条件に合う要素をすべて削除します。

#include <iostream>
#include <list>

typedef std::list<int> IntList;

void PrintList(const IntList& lst)
{
    const IntList::const_iterator itEnd = lst.end();
    for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

bool IsOdd(int value)
{
    return (value & 1);
}

int main()
{
    std::list<int> lst;

    for (int i = 0; i < 10; ++i) {
        lst.push_back(i / 2);
    }

    lst.remove(2);         // 2 を削除
    PrintList(lst);

    lst.remove_if(IsOdd);  // 奇数を削除
    PrintList(lst);
}

実行結果

0
0
1
1
3
3
4
4

0
0
4
4

removeメンバ関数は、引数に指定した値と、コンテナ内の各要素とを ==演算子で比較した結果が真であれば、その要素を削除します。

remove_ifメンバ関数の引数には、関数ポインタや関数オブジェクト(第19章)を渡すことができます。この引き渡した関数を op、コンテナ内の各要素を elem と表現すると、op(elem) が真を返したとき、その要素を削除します。このような、真偽を表す論理値を返す関数を、叙述関数(プレディケート)と呼びます。

STLアルゴリズム(第18章)にも remove という関数がありますが、list の場合はメンバ関数の remove を使う方が効率的です。また、STLアルゴリズムの remove は、実際には要素を削除しないという直感的ではない仕様になっているので、list::remove とは動作が異なることに注意が必要です。

最後に、要素をすべて削除する場合ですが、これは clearメンバ関数を使うだけです。

#include <iostream>
#include <list>

int main()
{
    std::list<int> lst;

    for (int i = 0; i < 5; ++i) {
        lst.push_back(i);
    }

    lst.clear();
    assert(lst.empty());
}

実行結果





C++11(erase のイテレータの const化)

C++03 までの eraseメンバ関数は、要素の位置を指定するイテレータが、std::list<T>::iterator型になっていました。そのため、この引数の意味は、位置を示すことだけなので constイテレータで問題ないはずなのに、constイテレータを渡すことができません。

C++11 では、イテレータの型が std::list<T>::const_iterator型に改められています。

イテレータ

イテレータに関する詳細は、第14章で改めて取り上げますが、ここでは、list におけるイテレータについて、簡単に紹介します。

他のコンテナと同様に、最初の要素を指すイテレータを beginメンバ関数で、最後の要素の次を指すイテレータを endメンバ関数で取得できます。また、逆方向に走査するための逆イテレータの場合に最初の要素を指すイテレータを rbeginメンバ関数で、最後の要素の次を指すイテレータを rendメンバ関数で取得できます。

#include <iostream>
#include <list>

int main()
{
    typedef std::list<int> IntList;

    IntList lst;

    for (int i = 0; i < 10; ++i) {
        lst.push_back(i);
    }

    IntList::const_iterator itEnd = lst.end();
    for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;

    IntList::const_reverse_iterator ritEnd = lst.rend();
    for (IntList::const_reverse_iterator rit = lst.rbegin(); rit != ritEnd; ++rit) {
        std::cout << *rit << "\n";
    }
    std::cout << std::endl;
}

実行結果

0
1
2
3
4
5
6
7
8
9

9
8
7
6
5
4
3
2
1
0

beginメンバ関数や endメンバ関数で取得できるイテレータの型は、std::list<T>::iterator型、あるいはその const版である std::list<T>::const_iterator型です。後者の場合は、イテレータを通して要素を書き換えることができません。

また、rbeginメンバ関数、rendメンバ関数の場合は、std::list<T>::reverse_iterator型、あるいはその const版である std::list<T>::const_reverse_iterator型になります。

これらイテレータの型は、list内部で typedef されているものですが、その正体(typedef の元になる型) が何であるかは実装依存ですから、ポインタのつもりで扱うことは避けなくてはなりません。

string や vector のイテレータの場合は、+演算子や -演算子を使って、指している先を前方や後方へ移動させることができますが、list の場合はできません。これは、list が提供するイテレータは、ランダムアクセスをサポートしていないためです。STL のイテレータには、このような機能性による分類が規定されています(第14章)。

list でイテレータを移動させるには、++演算子や --演算子で1要素分ずつ移動させるか、std::advance関数第14章)を使用します。

#include <iostream>
#include <list>
#include <iterator>  // std::advance

int main()
{
    typedef std::list<int> IntList;
    IntList lst;

    for (int i = 0; i < 10; ++i) {
        lst.push_back(i);
    }

    IntList::const_iterator it = lst.begin();
    std::cout << *it << std::endl;	// 0番目

    it++;
    std::cout << *it << std::endl;	// 1番目

    std::advance(it, 5);
    std::cout << *it << std::endl;	// 6番目

    it--;
    std::cout << *it << std::endl;	// 5番目
}

実行結果

0
1
6
5

std::advance関数を使う際には、iterator という標準ヘッダをインクルードして下さい。この関数は、list だけでなく、他のコンテナのイテレータにも使用できる汎用的な補助関数になっています。

C++11(const版のイテレータ取得関数)

C++11 には、必ず constイテレータを返す cbegin、cend、crbegin、crend の各メンバ関数が追加されています。

元々、begin、end、rbegin、rend の各メンバ関数は、非constイテレータを返すものと constイテレータを返すものとでオーバーロードされており、constイテレータ型の変数で受け取れば、const版を使えました。

新たにこれらのメンバ関数が追加された意義は幾つかあると思いますが、例えば、C++11 で追加された auto(【言語解説】第2章)を使いやすくすることが考えられます。

std::list<int> lst;
auto it = lst.begin();   // こう書くと std::list<int>::iterator型
auto it = lst.cbegin();  // こう書くと std::list<int>::const_iterator型

整列

list の要素を整列(ソート)することは非常に簡単に行えるようになっており、sortメンバ関数を呼び出すだけです。

#include <iostream>
#include <list>

typedef std::list<int> IntList;

void PrintList(const IntList& lst)
{
    const IntList::const_iterator itEnd = lst.end();
    for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntList lst;

    lst.push_back(7);
    lst.push_back(3);
    lst.push_back(5);
    lst.push_back(2);
    lst.push_back(6);

    lst.sort();
    PrintList(lst);
}

実行結果

2
3
5
6
7

sortメンバ関数は、デフォルトでは <演算子を使って整列を行います。従って、実行結果にあるように、昇順に整列されます。

逆に、降順に整列したければ、引数に叙述関数を渡せるバージョンを使用します。これはよく使うものなので、標準で用意されています。

#include <iostream>
#include <list>
#include <functional>

typedef std::list<int> IntList;

void PrintList(const IntList& lst)
{
    const IntList::const_iterator itEnd = lst.end();
    for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntList lst;

    lst.push_back(7);
    lst.push_back(3);
    lst.push_back(5);
    lst.push_back(2);
    lst.push_back(6);

    lst.sort(std::greater<int>());
    PrintList(lst);
}

実行結果

7
6
5
3
2

sortメンバ関数の引数に、std::greater という関数オブジェクトを渡すと、要素の比較を >演算子で行うように指示できます。従って、降順の整列させることができます。これを使うには、functional という標準ヘッダをインクルードする必要があります。関数オブジェクトについては、第19章で取り上げます。

ちなみに、sortメンバ関数の引数を指定しない場合は、std::less という関数オブジェクトを渡しています。こちらは <演算子を使うことを意味しています。

なお、sortメンバ関数は、安定なソート(アルゴリズムとデータ構造編【整列】第0章)です。

sortメンバ関数の引数には、任意の関数ポインタや関数オブジェクトを渡すことができるので、より複雑な条件で整列を行わせることもできます。ただし、次のシグネチャに従う必要があります。

bool cmp_func(const T1 &a, const T2 &b);

なお、STLアルゴリズム(第18章)にも std::sort関数第21章)が存在しています。STLアルゴリズムは、コンテナの種類に極力依存しないように実装されていますが、ランダムアクセスができないという事情があることから、list には適用できません。そのため、代わりの手段としてメンバ関数の sort が用意されています。

重複を取り除く

uniqueメンバ関数を使うと、同じ値を持つ要素が連続して重複している場合に、重複を取り除くことができます。

#include <iostream>
#include <list>

typedef std::list<int> IntList;

void PrintList(const IntList& lst)
{
    const IntList::const_iterator itEnd = lst.end();
    for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntList lst;

    lst.push_back(3);
    lst.push_back(4);
    lst.push_back(4);
    lst.push_back(4);
    lst.push_back(5);
    lst.push_back(5);
    lst.push_back(3);

    lst.unique();
    PrintList(lst);
}

実行結果

3
4
5
3

重複が「連続して」いる場合にしか取り除かれないことに注意して下さい。このサンプルプログラムで言えば、最初と最後に 3 がありますが、これらは連続していないので取り除かれません。

連続していない場合でも取り除きたいのなら、事前に整列しておく必要があります。ただし、元の要素の並び順は維持できなくなります。

sort 同様、unique も STLアルゴリズムに存在しますが、やはりメンバ関数版の方が効率的です。STLアルゴリズム版の unique では、要素は実際には削除されないので、list::unique とは動作が異なることに注意が必要です。

併合

2つの list を併合(マージ)するには、mergeメンバ関数を使います。この関数の使い方は、少し理解を必要とします。

まず前提として、2つの list は整列済みでなければなりません。また、併合された後の list もまた、整列済みな状態になります。この整列の条件は、mergeメンバ関数の引数で指定することもできますし、指定しなければ <演算子による整列になります。つまり、sortメンバ関数と同じルールです。

これらを踏まえると、2つの list は事前に sortメンバ関数を呼ぶなどして整列済みにしておく必要があります。また、事前の整列の条件と、mergeメンバ関数に指定する整列の条件も揃えておくべきです。

#include <iostream>
#include <list>

typedef std::list<int> IntList;

void PrintList(const IntList& lst)
{
    const IntList::const_iterator itEnd = lst.end();
    for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntList lst1, lst2;

    lst1.push_back(5);
    lst1.push_back(3);
    lst1.push_back(6);

    lst2.push_back(4);
    lst2.push_back(7);
    lst2.push_back(2);


    lst1.sort();
    lst2.sort();
    lst1.merge(lst2);
    PrintList(lst1);
}

実行結果

2
3
4
5
6
7

unique と同様に、merge も STLアルゴリズムに存在しますが、メンバ関数版の方が効率的です。

C++11(右辺値参照版の追加)

C++11 の mergeメンバ関数では、引数を右辺値参照にしたバージョンが追加されています。

lst1.merge(std::move(lst2));

反転

list 内の要素の並び順を反転させるために、reverseメンバ関数があります。これはもう本当に、ただ呼び出すだけなので非常に簡単です。

#include <iostream>
#include <list>

typedef std::list<int> IntList;

void PrintList(const IntList& lst)
{
    const IntList::const_iterator itEnd = lst.end();
    for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntList lst;

    lst.push_back(7);
    lst.push_back(3);
    lst.push_back(5);
    lst.push_back(2);
    lst.push_back(6);

    lst.reverse();
    PrintList(lst);
}

実行結果

6
2
5
3
7

unique 同様に、reverse も STLアルゴリズムに存在しますが、メンバ関数版の方が効率的です。

ない継ぎ

list の要素は、ポインタによって互いを連結している状態なので、ポインタを付け替えるだけで要素の順序を変更できます。このような操作を「ない継ぎ」と呼び、spliceメンバ関数によってサポートされます。

1つ目の使い方として、別の list にある要素を、任意の位置に移動します。

#include <iostream>
#include <list>

typedef std::list<int> IntList;

void PrintList(const IntList& lst)
{
    const IntList::const_iterator itEnd = lst.end();
    for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntList lst1, lst2;

    for (int i = 0; i < 5; ++i) {
        lst1.push_back(i);
    }
    for (int i = 0; i < 5; ++i) {
        lst2.push_back(10 + i);
    }


    IntList::iterator it = lst1.begin();
    std::advance(it, 2);

    lst1.splice(it, lst2);
    PrintList(lst1);
    std::cout << "-----" << std::end;
    PrintList(lst2);
}

実行結果

0
1
10
11
12
13
14
2
3
4

-----

ない継ぎの操作は、要素の「移動」を行っているので、lst2 の方は空になっていることに注意して下さい。使用感は insertメンバ関数と似ていますが、「追加・挿入」の操作とはこの点で異なります。

2つ目の使い方は、指定した list の指定の位置にある要素を、指定の位置に移動します。この使い方の場合は、同じ list でも構いません。

#include <iostream>
#include <list>

typedef std::list<int> IntList;

void PrintList(const IntList& lst)
{
    const IntList::const_iterator itEnd = lst.end();
    for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntList lst1, lst2;

    for (int i = 0; i < 5; ++i) {
        lst1.push_back(i);
    }
    for (int i = 0; i < 5; ++i) {
        lst2.push_back(10 + i);
    }


    IntList::iterator it = lst1.begin();
    std::advance(it, 2);

    lst1.splice(it, lst2, lst2.begin());
    PrintList(lst1);
    std::cout << "-----" << std::end;
    PrintList(lst2);
}

実行結果

0
1
10
2
3
4

-----
11
12
13
14

実行結果を見ると、何が起きているのか分かると思います。「移動」なので、lst2 の方からは要素が無くなっていることに注目して下さい。

3つ目の使い方は、2つ目の使い方が範囲指定に変わっただけです。

#include <iostream>
#include <list>

typedef std::list<int> IntList;

void PrintList(const IntList& lst)
{
    const IntList::const_iterator itEnd = lst.end();
    for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntList lst1, lst2;

    for (int i = 0; i < 5; ++i) {
        lst1.push_back(i);
    }
    for (int i = 0; i < 5; ++i) {
        lst2.push_back(10 + i);
    }


    IntList::iterator it = lst1.begin();
    std::advance(it, 2);

    IntList::iterator it2 = lst2.begin();
    std::advance(it2, 3);

    lst1.splice(it, lst2, lst2.begin(), it2);
    PrintList(lst1);
    std::cout << "-----" << std::endl;
    PrintList(lst2);
}

実行結果

0
1
10
11
12
2
3
4

-----
13
14

C++11(右辺値参照版の追加)

C++11 の spliceメンバ関数では、list を指定する引数を右辺値参照にしたバージョンが追加されています。

lst1.splice(it, std::move(lst2));
lst1.splice(it, std::move(lst2), it2);
lst1.splice(it, std::move(lst2), it2begin, it2end);


練習問題

問題① list内の要素を、既に生成済みの vector へ書き出して、list と同じ要素の並びにするプログラムを作成して下さい。できるだけ多くの方法を考えて下さい。

問題② 非効率さを覚悟の上で、list の要素へ添字を使ってランダムアクセスしたいとします。そのような関数を実装してみて下さい。

問題③ list の中から、特定の値を持った要素の数をカウントするプログラムを作成して下さい。


解答ページはこちら

参考リンク



更新履歴

'2018/1/5 コンパイラの対応状況について、対応している場合は明記しない方針にした。

'2017/7/30 clang 3.7 (Xcode 7.3) を、Xcode 8.3.3 に置き換え。

'2017/3/25 VisualC++ 2017 に対応。

'2016/10/15 clang の対応バージョンを 3.7 に更新。

'2015/10/12 clang の対応バージョンを 3.4 に更新。

≪更に古い更新履歴を展開する≫



前の章へ(第5章 vector)

次の章へ(第7章 deque)

C++編のトップページへ

Programming Place Plus のトップページへ


このエントリーをはてなブックマークに追加
rss1.0 取得ボタン RSS