MENU
  1. ホーム
  2. C++
  3. STL
  4. コンテナ
  5. list
  6. 【C++】std::listの使い方について詳しく解説

【C++】std::listの使い方について詳しく解説

list

C++の標準ライブラリには、データを効率的に管理するためのさまざまなコンテナが用意されています。

その中でも、std::listは双方向リスト(ダブルリンクリスト)を実装したコンテナで、要素の追加や削除が簡単に行える特徴があります。

このガイドでは、std::listの基本的な使い方から、具体的な操作方法、パフォーマンスの比較、実践的な例までを初心者向けにわかりやすく解説します。

この記事を読むことで、std::listの利点や適切な使用シーンを理解し、効果的に活用できるようになります。

目次から探す

std::listとは

std::listの概要

std::listはC++標準ライブラリに含まれるコンテナの一つで、双方向リスト(ダブルリンクリスト)を実装しています。

双方向リストは各要素が前後の要素へのポインタを持つため、要素の挿入や削除が効率的に行えます。

std::listはこの特性を活かし、特に頻繁に要素の追加や削除が行われる場面で有用です。

#include <iostream>
#include <list>
int main() {
    std::list<int> myList = {1, 2, 3, 4, 5};
    for (int value : myList) {
        std::cout << value << " ";
    }
    return 0;
}

上記のコードは、std::listを使って整数のリストを作成し、その要素を出力する例です。

出力結果は以下の通りです。

1 2 3 4 5

std::vectorとの違い

std::vectorとstd::listはどちらもシーケンスコンテナですが、その内部構造と特性には大きな違いがあります。

比較項目std::vectorstd::list
メモリ配置連続したメモリ領域に要素を格納各要素が独立したメモリ領域に格納され、ポインタでリンク
要素のアクセスランダムアクセス可能。インデックスを使って高速にアクセスランダムアクセス不可。イテレータを使って順次アクセス
要素の挿入と削除末尾以外の位置での挿入や削除が遅い。要素の移動が必要任意の位置での挿入や削除が高速。ポインタの更新のみ

使用する場面と利点

std::listは以下のような場面で特に有用です。

  • 頻繁な挿入と削除:

要素の挿入や削除が頻繁に行われる場合、std::listは効率的です。

例えば、キューやデックの実装に適しています。

  • 順次アクセス:

ランダムアクセスが不要で、順次アクセスが主な操作となる場合に適しています。

例えば、リンクリストを使ったアルゴリズムの実装などです。

  • メモリの効率的な利用:

要素のサイズが大きく、メモリの断片化を避けたい場合に有用です。

std::listは各要素が独立したメモリ領域に格納されるため、メモリの再配置が不要です。

以下は、std::listを使って要素の挿入と削除を行う例です。

#include <iostream>
#include <list>
int main() {
    std::list<int> myList = {1, 2, 3, 4, 5};
    // 先頭に要素を追加
    myList.push_front(0);
    // 末尾に要素を追加
    myList.push_back(6);
    // 3番目の要素を削除
    auto it = myList.begin();
    std::advance(it, 2);
    myList.erase(it);
    for (int value : myList) {
        std::cout << value << " ";
    }
    return 0;
}

このコードの出力結果は以下の通りです。

0 1 3 4 5 6

このように、std::listは特定の用途において非常に強力なツールとなります。

適切な場面で使用することで、効率的なプログラムを作成することができます。

std::listの基本操作

std::listの宣言と初期化

デフォルトコンストラクタ

std::listを使うためには、まず宣言と初期化が必要です。

デフォルトコンストラクタを使用すると、空のリストが作成されます。

#include <iostream>
#include <list>
int main() {
    std::list<int> myList; // 空のリストを作成
    std::cout << "リストのサイズ: " << myList.size() << std::endl; // 出力: 0
    return 0;
}

初期値を指定したコンストラクタ

初期値を指定してリストを作成することもできます。

以下の例では、5つの要素を持つリストを作成し、すべての要素が10で初期化されます。

#include <iostream>
#include <list>
int main() {
    std::list<int> myList(5, 10); // 5つの要素を持つリストを作成し、すべての要素が10で初期化
    for (int value : myList) {
        std::cout << value << " "; // 出力: 10 10 10 10 10
    }
    return 0;
}

イテレータを使った初期化

他のコンテナからイテレータを使ってリストを初期化することも可能です。

以下の例では、std::vectorからstd::listを初期化しています。

#include <iostream>
#include <list>
#include <vector>
int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::list<int> myList(vec.begin(), vec.end()); // vectorの要素を使ってリストを初期化
    for (int value : myList) {
        std::cout << value << " "; // 出力: 1 2 3 4 5
    }
    return 0;
}

要素の追加

push_backとpush_front

std::listには要素を追加するためのメソッドがいくつかあります。

push_backはリストの末尾に要素を追加し、push_frontはリストの先頭に要素を追加します。

#include <iostream>
#include <list>
int main() {
    std::list<int> myList;
    myList.push_back(1); // 末尾に1を追加
    myList.push_back(2); // 末尾に2を追加
    myList.push_front(0); // 先頭に0を追加
    for (int value : myList) {
        std::cout << value << " "; // 出力: 0 1 2
    }
    return 0;
}

emplace_backとemplace_front

emplace_backとemplace_frontは、要素を直接リストに構築するためのメソッドです。

これにより、不要なコピーやムーブ操作を避けることができます。

#include <iostream>
#include <list>
class MyClass {
public:
    int value;
    MyClass(int v) : value(v) {
        std::cout << "コンストラクタ呼び出し: " << value << std::endl;
    }
};
int main() {
    std::list<MyClass> myList;
    myList.emplace_back(1); // 末尾に1を持つMyClassオブジェクトを直接構築
    myList.emplace_front(0); // 先頭に0を持つMyClassオブジェクトを直接構築
    for (const MyClass& obj : myList) {
        std::cout << obj.value << " "; // 出力: 0 1
    }
    return 0;
}

要素の削除

pop_backとpop_front

pop_backはリストの末尾の要素を削除し、pop_frontはリストの先頭の要素を削除します。

#include <iostream>
#include <list>
int main() {
    std::list<int> myList = {0, 1, 2, 3};
    myList.pop_back(); // 末尾の要素を削除
    myList.pop_front(); // 先頭の要素を削除
    for (int value : myList) {
        std::cout << value << " "; // 出力: 1 2
    }
    return 0;
}

removeとremove_if

removeは指定した値と一致するすべての要素を削除し、remove_ifは条件に一致するすべての要素を削除します。

#include <iostream>
#include <list>
int main() {
    std::list<int> myList = {1, 2, 3, 2, 4, 2};
    myList.remove(2); // 値が2の要素をすべて削除
    for (int value : myList) {
        std::cout << value << " "; // 出力: 1 3 4
    }
    myList.remove_if([](int value) { return value % 2 == 0; }); // 偶数の要素をすべて削除
    for (int value : myList) {
        std::cout << value << " "; // 出力: 1 3
    }
    return 0;
}

clear

clearメソッドはリストのすべての要素を削除します。

#include <iostream>
#include <list>
int main() {
    std::list<int> myList = {1, 2, 3, 4, 5};
    myList.clear(); // すべての要素を削除
    std::cout << "リストのサイズ: " << myList.size() << std::endl; // 出力: 0
    return 0;
}

以上が、std::listの基本操作に関する解説です。

次のセクションでは、std::listのイテレータについて詳しく見ていきます。

std::listのイテレータ

イテレータの基本

イテレータは、コンテナ内の要素にアクセスするためのオブジェクトです。

std::listのイテレータは双方向イテレータであり、前後に移動することができます。

イテレータを使うことで、std::listの要素を簡単に操作することができます。

イテレータを使った要素のアクセス

イテレータを使ってstd::listの要素にアクセスする方法を見てみましょう。

以下のコードは、std::listの要素をイテレータを使って出力する例です。

#include <iostream>
#include <list>
int main() {
    std::list<int> myList = {1, 2, 3, 4, 5};
    // イテレータを使って要素を出力
    for (std::list<int>::iterator it = myList.begin(); it != myList.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    return 0;
}

このコードを実行すると、以下のように出力されます。

1 2 3 4 5

イテレータの種類

std::listにはいくつかの種類のイテレータが用意されています。

それぞれのイテレータの使い方を見ていきましょう。

beginとend

beginはコンテナの最初の要素を指すイテレータを返し、endはコンテナの最後の要素の次を指すイテレータを返します。

これにより、範囲ベースのループを簡単に実装できます。

#include <iostream>
#include <list>
int main() {
    std::list<int> myList = {1, 2, 3, 4, 5};
    // beginとendを使って要素を出力
    for (auto it = myList.begin(); it != myList.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    return 0;
}

rbeginとrend

rbeginはコンテナの最後の要素を指す逆イテレータを返し、rendはコンテナの最初の要素の前を指す逆イテレータを返します。

これにより、コンテナを逆順に走査することができます。

#include <iostream>
#include <list>
int main() {
    std::list<int> myList = {1, 2, 3, 4, 5};
    // rbeginとrendを使って要素を逆順に出力
    for (auto it = myList.rbegin(); it != myList.rend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    return 0;
}

このコードを実行すると、以下のように出力されます。

5 4 3 2 1

cbeginとcend

cbeginはコンテナの最初の要素を指す定数イテレータを返し、cendはコンテナの最後の要素の次を指す定数イテレータを返します。

定数イテレータは、要素を変更することができないイテレータです。

#include <iostream>
#include <list>
int main() {
    std::list<int> myList = {1, 2, 3, 4, 5};
    // cbeginとcendを使って要素を出力
    for (auto it = myList.cbegin(); it != myList.cend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    return 0;
}

このコードを実行すると、以下のように出力されます。

1 2 3 4 5

イテレータを使うことで、std::listの要素を効率的に操作することができます。

次のセクションでは、std::listの操作メソッドについて詳しく解説します。

std::listの操作メソッド

要素の挿入

insert

std::listでは、insertメソッドを使用して特定の位置に要素を挿入することができます。

以下の例では、リストの2番目の位置に新しい要素を挿入しています。

#include <iostream>
#include <list>
int main() {
    std::list<int> myList = {1, 2, 3, 4};
    auto it = myList.begin();
    std::advance(it, 1); // 2番目の位置に移動
    myList.insert(it, 10);
    for (int n : myList) {
        std::cout << n << " ";
    }
    return 0;
}

このコードの実行結果は以下の通りです。

1 10 2 3 4

emplace

emplaceメソッドは、insertと似ていますが、オブジェクトをその場で構築するため、パフォーマンスが向上する場合があります。

以下の例では、リストの2番目の位置に新しい要素を挿入しています。

#include <iostream>
#include <list>
int main() {
    std::list<int> myList = {1, 2, 3, 4};
    auto it = myList.begin();
    std::advance(it, 1); // 2番目の位置に移動
    myList.emplace(it, 20);
    for (int n : myList) {
        std::cout << n << " ";
    }
    return 0;
}

このコードの実行結果は以下の通りです。

1 20 2 3 4

要素の検索

find

std::listには直接的なfindメソッドはありませんが、std::findアルゴリズムを使用して要素を検索することができます。

以下の例では、リスト内の特定の要素を検索しています。

#include <iostream>
#include <list>
#include <algorithm>
int main() {
    std::list<int> myList = {1, 2, 3, 4, 5};
    auto it = std::find(myList.begin(), myList.end(), 3);
    if (it != myList.end()) {
        std::cout << "Found: " << *it << std::endl;
    } else {
        std::cout << "Not Found" << std::endl;
    }
    return 0;
}

このコードの実行結果は以下の通りです。

Found: 3

count

std::listには直接的なcountメソッドもありませんが、std::countアルゴリズムを使用して特定の要素の出現回数を数えることができます。

#include <iostream>
#include <list>
#include <algorithm>
int main() {
    std::list<int> myList = {1, 2, 3, 4, 3, 3, 5};
    int count = std::count(myList.begin(), myList.end(), 3);
    std::cout << "Count of 3: " << count << std::endl;
    return 0;
}

このコードの実行結果は以下の通りです。

Count of 3: 3

要素のソートと並べ替え

sort

std::listにはsortメソッドがあり、リスト内の要素を昇順にソートすることができます。

以下の例では、リストをソートしています。

#include <iostream>
#include <list>
int main() {
    std::list<int> myList = {5, 2, 9, 1, 5, 6};
    myList.sort();
    for (int n : myList) {
        std::cout << n << " ";
    }
    return 0;
}

このコードの実行結果は以下の通りです。

1 2 5 5 6 9

reverse

reverseメソッドを使用すると、リスト内の要素の順序を逆にすることができます。

#include <iostream>
#include <list>
int main() {
    std::list<int> myList = {1, 2, 3, 4, 5};
    myList.reverse();
    for (int n : myList) {
        std::cout << n << " ";
    }
    return 0;
}

このコードの実行結果は以下の通りです。

5 4 3 2 1

unique

uniqueメソッドは、連続する重複要素を削除します。

以下の例では、リスト内の連続する重複要素を削除しています。

#include <iostream>
#include <list>
int main() {
    std::list<int> myList = {1, 2, 2, 3, 3, 3, 4, 5, 5};
    myList.unique();
    for (int n : myList) {
        std::cout << n << " ";
    }
    return 0;
}

このコードの実行結果は以下の通りです。

1 2 3 4 5

その他のメソッド

merge

mergeメソッドは、2つのソートされたリストを1つにマージします。

以下の例では、2つのリストをマージしています。

#include <iostream>
#include <list>
int main() {
    std::list<int> list1 = {1, 3, 5};
    std::list<int> list2 = {2, 4, 6};
    list1.merge(list2);
    for (int n : list1) {
        std::cout << n << " ";
    }
    return 0;
}

このコードの実行結果は以下の通りです。

1 2 3 4 5 6

splice

spliceメソッドは、他のリストから要素を移動します。

以下の例では、リスト2の要素をリスト1に移動しています。

#include <iostream>
#include <list>
int main() {
    std::list<int> list1 = {1, 2, 3};
    std::list<int> list2 = {4, 5, 6};
    auto it = list1.begin();
    std::advance(it, 1); // 2番目の位置に移動
    list1.splice(it, list2);
    for (int n : list1) {
        std::cout << n << " ";
    }
    return 0;
}

このコードの実行結果は以下の通りです。

1 4 5 6 2 3

swap

swapメソッドは、2つのリストの内容を交換します。

以下の例では、リスト1とリスト2の内容を交換しています。

#include <iostream>
#include <list>
int main() {
    std::list<int> list1 = {1, 2, 3};
    std::list<int> list2 = {4, 5, 6};
    list1.swap(list2);
    std::cout << "List1: ";
    for (int n : list1) {
        std::cout << n << " ";
    }
    std::cout << "\nList2: ";
    for (int n : list2) {
        std::cout << n << " ";
    }
    return 0;
}

このコードの実行結果は以下の通りです。

List1: 4 5 6 
List2: 1 2 3

以上が、std::listの操作メソッドに関する詳細な解説です。

これらのメソッドを活用することで、リストの操作がより柔軟かつ効率的に行えるようになります。

std::listのパフォーマンスと注意点

メモリ管理とパフォーマンス

std::listは双方向連結リストとして実装されており、各要素は個別のノードとしてメモリに格納されます。

各ノードは次と前の要素へのポインタを持っているため、メモリのオーバーヘッドが発生します。

この構造により、要素の挿入や削除が効率的に行える一方で、メモリの断片化が発生しやすくなります。

#include <iostream>
#include <list>
int main() {
    std::list<int> myList = {1, 2, 3, 4, 5};
    myList.push_back(6); // 要素の追加
    myList.push_front(0); // 要素の追加
    for (int n : myList) {
        std::cout << n << " ";
    }
    return 0;
}

このコードでは、std::listに要素を追加しています。

push_backとpush_frontはそれぞれリストの末尾と先頭に要素を追加します。

これらの操作は定数時間で行われますが、メモリの断片化が発生する可能性があります。

std::vectorとのパフォーマンス比較

std::vectorとstd::listのパフォーマンスは、使用する操作によって大きく異なります。

std::vectorは連続したメモリ領域に要素を格納するため、ランダムアクセスが高速です。

一方、std::listは双方向連結リストであるため、ランダムアクセスは遅くなりますが、要素の挿入や削除が効率的に行えます。

#include <iostream>
#include <vector>
#include <list>
#include <chrono>
int main() {
    const int N = 100000;
    std::vector<int> vec;
    std::list<int> lst;
    // std::vectorのパフォーマンステスト
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) {
        vec.push_back(i);
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> duration = end - start;
    std::cout << "std::vector push_back: " << duration.count() << " seconds\n";
    // std::listのパフォーマンステスト
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) {
        lst.push_back(i);
    }
    end = std::chrono::high_resolution_clock::now();
    duration = end - start;
    std::cout << "std::list push_back: " << duration.count() << " seconds\n";
    return 0;
}

このコードでは、std::vectorとstd::listに対して大量の要素を追加する際のパフォーマンスを比較しています。

結果として、std::vectorの方が高速であることが多いですが、特定の操作(例えば、リストの途中への挿入や削除)ではstd::listが有利です。

注意点とベストプラクティス

std::listを使用する際には、以下の点に注意する必要があります。

  1. ランダムアクセスの非効率性: std::listはランダムアクセスが遅いため、頻繁にランダムアクセスが必要な場合はstd::vectorを使用する方が良いです。
  2. メモリのオーバーヘッド: 各要素が個別のノードとして格納されるため、メモリのオーバーヘッドが発生します。

メモリ効率を重視する場合はstd::vectorを検討してください。

  1. イテレータの無効化: 要素の挿入や削除によってイテレータが無効化されることがあります。

イテレータの無効化に注意し、適切に再取得するようにしましょう。

ベストプラクティスとしては、以下のようなシナリオでstd::listを使用することが推奨されます。

  • 頻繁に要素の挿入や削除が行われる場合
  • 要素の順序が重要であり、順序を保ちながら操作を行いたい場合
  • メモリの断片化が許容される場合

これらの点を考慮して、適切なデータ構造を選択することが重要です。

実践例

基本的な使い方の例

まずは、std::listの基本的な使い方を見ていきましょう。

以下のコードは、std::listを使って整数のリストを作成し、いくつかの基本操作を行う例です。

#include <iostream>
#include <list>
int main() {
    // std::listの宣言と初期化
    std::list<int> myList = {1, 2, 3, 4, 5};
    // 要素の追加
    myList.push_back(6);  // リストの末尾に6を追加
    myList.push_front(0); // リストの先頭に0を追加
    // 要素の削除
    myList.pop_back();    // リストの末尾の要素を削除
    myList.pop_front();   // リストの先頭の要素を削除
    // イテレータを使った要素のアクセス
    std::cout << "リストの要素: ";
    for (auto it = myList.begin(); it != myList.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    return 0;
}

このコードを実行すると、以下のような出力が得られます。

リストの要素: 1 2 3 4 5

この例では、std::listの宣言、初期化、要素の追加と削除、イテレータを使った要素のアクセスを行っています。

複雑なデータ構造の例

次に、std::listを使って複雑なデータ構造を扱う例を見てみましょう。

ここでは、カスタムクラスをリストに格納する方法を紹介します。

#include <iostream>
#include <list>
#include <string>
class Person {
public:
    std::string name;
    int age;
    Person(std::string n, int a) : name(n), age(a) {}
};
int main() {
    // std::listにカスタムクラスを格納
    std::list<Person> people;
    people.emplace_back("Alice", 30);
    people.emplace_back("Bob", 25);
    people.emplace_back("Charlie", 35);
    // イテレータを使った要素のアクセス
    for (const auto& person : people) {
        std::cout << "Name: " << person.name << ", Age: " << person.age << std::endl;
    }
    return 0;
}

このコードを実行すると、以下のような出力が得られます。

Name: Alice, Age: 30
Name: Bob, Age: 25
Name: Charlie, Age: 35

この例では、Personというカスタムクラスを定義し、そのインスタンスをstd::listに格納しています。

emplace_backを使うことで、リストに直接オブジェクトを追加しています。

std::listを使ったアルゴリズムの例

最後に、std::listを使って簡単なアルゴリズムを実装する例を見てみましょう。

ここでは、リスト内の要素をソートし、重複を削除する方法を紹介します。

#include <iostream>
#include <list>
int main() {
    // std::listの宣言と初期化
    std::list<int> myList = {5, 3, 1, 4, 2, 3, 5, 1};
    // リストのソート
    myList.sort();
    // 重複要素の削除
    myList.unique();
    // イテレータを使った要素のアクセス
    std::cout << "ソート後、重複削除後のリストの要素: ";
    for (const auto& elem : myList) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    return 0;
}

このコードを実行すると、以下のような出力が得られます。

ソート後、重複削除後のリストの要素: 1 2 3 4 5

この例では、std::listのsortメソッドを使ってリストをソートし、uniqueメソッドを使って重複する要素を削除しています。

これにより、リスト内の要素が昇順に並び、重複が取り除かれます。

以上が、std::listの基本的な使い方、複雑なデータ構造の例、そしてアルゴリズムの例です。

これらの例を通じて、std::listの強力な機能と柔軟性を理解していただけたと思います。

まとめ

std::listの利点と欠点

利点:

  1. 双方向リストの特性: std::listは双方向リストとして実装されており、前後の要素へのアクセスが容易です。

これにより、要素の挿入や削除が効率的に行えます。

  1. 効率的な要素の挿入・削除: std::listは要素の挿入や削除がO(1)の時間で行えるため、大量の要素を頻繁に追加・削除する場合に適しています。
  2. 安定したイテレータ: std::listのイテレータは、要素の挿入や削除によって無効化されることが少ないため、イテレータを使った操作が安全に行えます。

欠点:

  1. ランダムアクセスの非効率性: std::listはランダムアクセスがO(n)の時間を要するため、特定の位置にある要素へのアクセスが遅くなります。

頻繁にランダムアクセスが必要な場合には不向きです。

  1. メモリのオーバーヘッド: 各要素が前後の要素へのポインタを持つため、std::vectorに比べてメモリの使用量が多くなります。
  2. キャッシュ効率の低下: std::listはメモリ上で連続して配置されないため、キャッシュ効率が低くなることがあります。

これにより、パフォーマンスが低下する場合があります。

適切な使用シーン

  1. 頻繁な要素の挿入・削除が必要な場合: std::listは要素の挿入や削除が効率的に行えるため、頻繁に要素を追加・削除する必要がある場合に適しています。

例えば、タスクの管理やイベントの処理などが挙げられます。

  1. 順次アクセスが主な操作の場合: std::listは順次アクセスが得意なため、要素を順番に処理する場合に適しています。

例えば、キューやスタックの実装に利用できます。

  1. イテレータの安定性が重要な場合: std::listのイテレータは要素の挿入や削除によって無効化されにくいため、イテレータを使った操作が多い場合に適しています。

例えば、複雑なデータ構造の操作やアルゴリズムの実装に利用できます。

  1. メモリの断片化が問題にならない場合: std::listはメモリ上で連続して配置されないため、メモリの断片化が問題にならない場合に適しています。

例えば、メモリ使用量が少ないアプリケーションや、メモリ管理が自動的に行われる環境での使用が考えられます。

以上のように、std::listは特定のシーンで非常に有用なデータ構造です。

適切な場面で使用することで、効率的なプログラムを作成することができます。

目次に戻る

当サイトはリンクフリーです。出典元を明記していただければ、ご自由に引用していただいて構いません。

list

関連記事

関連する記事はまだ見つかりませんでした。

目次から探す