C++/標準ライブラリ/コンテナライブラリ

C++のコンテナライブラリは、データを効率的に格納および操作するための様々なクラスを提供します。これにより、プログラム内でデータを管理する際の作業が簡素化されます。

ヘッダー一覧

この章で扱うヘッダーファイルは以下の通りです。

シーケンスコンテナ

<array>, <deque>, <forward_list>, <list>, <vector>

連想コンテナ

<map>, <set>

無順序連想コンテナ

<unordered_map>, <unordered_set>

コンテナアダプタ

<queue>, <stack>, <flat_map>, <flat_set>

ビュー

<span>, <mdspan>

要件

コンテナライブラリに挿入される要素は、一般的に以下の要件を満たす必要があります。

コピー可能であること

要素は、コンテナに挿入、コピー、移動される際にコピーされる必要があります。 コピー可能な型には、以下のものがあります。

• プリミティブ型 (int, float, double など)
• ポインタ型
• 標準ライブラリで定義されているコピー可能な型 (例：std::string, std::vector)
• ユーザー定義型 (コピーコンストラクタと代入演算子を定義している場合)

破壊可能であること

要素は、不要になったときに解放される必要があります。 破壊可能な型には、以下のものがあります。

• デストラクタを持つ型
• 標準ライブラリで定義されている破壊可能な型 (例：std::string, std::vector)
• ユーザー定義型 (デストラクタを定義している場合)

比較可能であること

連想コンテナ (例：std::map, std::set) に挿入される要素は、比較演算子 (<, >, <=, >=, ==, !=) を用いて比較できる必要があります。 比較可能な型には、以下のものがあります。

• プリミティブ型 (int, float, double など)
• 標準ライブラリで定義されている比較可能な型 (例：std::string, std::vector)
• ユーザー定義型 (比較演算子を定義している場合)

デフォルトコンストラクタを持つこと

コンテナは、要素のデフォルトコンストラクタを使用して新しい要素を生成することがあります。 従って、要素型はデフォルトコンストラクタを定義する必要があります。 デフォルトコンストラクタを持たない型は、コンテナライブラリの一部操作で使用できない場合があります。

代入演算子を持つこと

コンテナ内の要素は、コピーや移動操作によって更新されることがあります。 従って、要素型は代入演算子 (=) を定義する必要があります。 代入演算子を持たない型は、コンテナライブラリの一部操作で使用できない場合があります。

例外

上記の要件は、コンテナライブラリの一般的な要件です。 一部のコンテナは、特殊な要件を持つ場合があります。 例えば、std::unique_ptr は、移動可能であることのみを要件としています。

また、ユーザー定義型の場合は、コンテナライブラリで定義されている型と同じインターフェースを実装する必要があります。 例えば、std::vector に挿入される要素は、イテレータを使用して反復可能である必要があります。

シーケンスコンテナ

シーケンスコンテナは、要素を順序に保持するコンテナです。要素の追加や削除、並び替えなどの操作を効率的に行うことができます。C++標準ライブラリには、以下のシーケンスコンテナが用意されています。

vector

動的配列。要素の追加や削除を効率的に行うことができます。

list

双方向連結リスト。要素の挿入や削除を効率的に行うことができます。

forward_list

一方向連結リスト。要素の挿入を効率的に行うことができます。

deque

両端キュー。先頭と末尾から要素の追加や削除を行うことができます。

array

固定長の配列。要素数はコンパイル時に決定する必要があります。

string

文字列。文字列の操作に特化した機能が用意されています。

シーケンスコンテナの共通機能

シーケンスコンテナには、以下の共通機能があります。

要素の取得

[] 演算子を使用して、要素にアクセスすることができます。

要素の追加

push_back() メンバ関数を使用して、要素を追加することができます。

要素の削除

erase() メンバ関数を使用して、要素を削除することができます。

要素の反復

begin() と end() メンバ関数を使用して、コンテナ内の要素を反復処理するための反復子を取得することができます。

アルゴリズム

標準ライブラリに用意されているアルゴリズムを使用して、コンテナ内の要素を処理することができます。

シーケンスコンテナの選択

シーケンスコンテナを選択する際には、以下の要素を考慮する必要があります。

要素の追加や削除の頻度

要素の追加や削除を頻繁に行う場合は、vector または list が適しています。

ランダムアクセス

要素へのランダムアクセスが必要な場合は、vector または array が適しています。

メモリ使用量

固定長の配列である array は、他のシーケンスコンテナよりもメモリ使用量が少ない場合があります。

シーケンスコンテナの使用例

以下に、シーケンスコンテナの使用例を示します。

C++

#include <iostream>
#include <vector>

auto main() -> int {
    // vector の作成
    auto numbers = std::vector{1, 2, 3, 4, 5};

    // 要素へのアクセス
    std::cout << numbers[0] << std::endl;  // 1 を出力

    // 要素の追加
    numbers.push_back(6);

    // 要素の削除
    numbers.erase(numbers.begin() + 2);

    // 要素の反復処理
    for (auto const number : numbers) {
        std::cout << number << " ";
    }
    std::cout << std::endl;

    return 0;
}

この例では、vector を使用して、整数のシーケンスを作成、操作しています。

まとめ

シーケンスコンテナは、C++ でよく使用されるデータ構造です。要素の追加や削除、並び替えなどの操作を効率的に行うことができます。シーケンスコンテナを選択する際には、要素の追加や削除の頻度、ランダムアクセス、メモリ使用量などの要素を考慮する必要があります。

連想コンテナ

連想コンテナは、要素をキーと値のペアで格納するコンテナです。 キーに基づいて要素にアクセスできるため、効率的な検索と挿入が可能です。 C++ 標準ライブラリには、以下の連想コンテナが用意されています。

<map>

順序付き連想コンテナ

<multimap>

重複を許可する順序付き連想コンテナ

std::map

map は、キーと値のペアを順序付きで格納する連想コンテナです。 キーは、比較可能である必要があります。 キーの比較は、std::less などの比較関数を使用して行われます。

主な操作

• insert：要素を挿入する
• erase：要素を削除する
• find：キーに対応する要素を探す
• count：キーに対応する要素の数を数える
• lower_bound：あるキー以上の要素の最初を探す
• upper_bound：あるキーを超える要素の最初を探す

例

C++

#include <iostream>
#include <map>
#include <string>

auto main() -> int {
    std::map<std::string, int> scores;

    scores["Alice"] = 90;
    scores["Bob"] = 80;
    scores["Charlie"] = 70;

    for (const auto& pair : scores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

実行結果

Alice: 90
Bob: 80
Charlie: 70

この例では、map を使用して学生の名前と点数のペアを格納しています。 insert メソッドを使用して要素を挿入し、範囲ベースのfor文を使って要素を順に参照しています。

std::multimap

multimap は、キーと値のペアを順序付きで格納する連想コンテナです。 キーは、比較可能である必要があります。 キーの比較は、std::less などの比較関数を使用して行われます。 同じキーを持つ複数の要素を格納することができます。

主な操作

• insert：要素を挿入する
• erase：要素を削除する
• find：キーに対応する要素の範囲を探す
• count：キーに対応する要素の数を数える
• lower_bound：あるキー以上の要素の最初を探す
• upper_bound：あるキーを超える要素の最初を探す

例

C++

#include <iostream>
#include <map>
#include <utility>

auto main() -> int {
    std::multimap<std::string, int> scores;

    scores.insert({"Alice", 90});
    scores.insert({"Alice", 85});
    scores.insert({"Bob", 80});
    scores.insert({"Charlie", 70});

    for (const auto& pair : scores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    std::cout << std::endl;
}

実行結果

Alice: 90
Alice: 85
Bob: 80
Charlie: 70

この例は、multimap を使用して学生の名前と点数のペアを格納しています。 insert メソッドを使用して要素を挿入し、範囲ベースのfor文を使って要素を順に参照しています。

連想コンテナの選択

どの連想コンテナを使用するかは、以下の要素を考慮する必要があります。

順序

要素の順序を保持する必要がある場合は、map または multimap を使用します。 順序が不要な場合は、unordered_map または unordered_multimap を使用します。

重複

同じキーを持つ複数の要素を許可する必要がある場合は、multimap または unordered_multimap を使用します。 同じキーを持つ要素を 1 つだけ許可する場合は、map または unordered_map を使用します。

検索速度

高速な検索が必要な場合は、unordered_map または unordered_multimap を使用します。 順序付きの検索が必要な場合は、map または multimap を使用します。

まとめ

連想コンテナは、キーと値のペアを効率的に格納および検索するための強力なツールです。 適切な連想コンテナを選択することで、アプリケーションのパフォーマンスと使いやすさを向上させることができます。

無順序連想コンテナ

無順序連想コンテナは、キーと値のペアを格納するコンテナですが、キーの順序は保持されません。つまり、要素は挿入された順序ではなく、ランダムな順序で格納されます。無順序連想コンテナは、高速な検索と挿入を提供し、キーの順序が重要でない場合に適しています。

主な無順序連想コンテナ

C++標準ライブラリには、以下の無順序連想コンテナが用意されています。

std::unordered_map

キーと値のペアを格納するハッシュテーブルです。

std::unordered_multimap

キーと値のペアを格納するハッシュテーブルですが、同じキーを持つ複数の値を格納できます。

std::unordered_set

キーのみを格納するハッシュテーブルです。

無順序連想コンテナの操作

無順序連想コンテナは、以下の操作をサポートしています。

insert()

キーと値のペアを挿入します。

erase()

キーに基づいて要素を削除します。

find()

キーに基づいて要素を検索します。

count()

特定のキーを持つ要素の数をカウントします。

begin()

要素の最初のイテレータを取得します。

end()

要素の最後のイテレータを取得します。

std::unordered_map

unordered_map は、キーと値のペアを非順序付きで格納する連想コンテナです。 キーは、ハッシュ関数を使用してハッシュ値に変換されます。 ハッシュ値に基づいて要素にアクセスするため、map よりも高速に検索と挿入を行うことができます。

主な操作

• insert：要素を挿入する
• erase：要素を削除する
• find：キーに対応する要素を探す
• count：キーに対応する要素の数を数える
• at：キーに対応する要素にアクセスする

例

C++

#include <iostream>
#include <string>
#include <unordered_map>

auto main() -> int {
    std::unordered_map<std::string, int> scores;

    scores["Alice"] = 90;
    scores["Bob"] = 80;
    scores["Charlie"] = 70;

    for (const auto& pair : scores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

実行結果

Charlie: 70
Bob: 80
Alice: 90

この例は、unordered_map を使用して学生の名前と点数のペアを格納しています。 insert メソッドを使用して要素を挿入し、範囲ベースのfor文を使って要素を順に参照しています。

std::unordered_multimap

unordered_multimap は、キーと値のペアを非順序付きで格納する連想コンテナです。 キーは、ハッシュ関数を使用してハッシュ値に変換されます。 ハッシュ値に基づいて要素にアクセスするため、multimap よりも高速に検索と挿入を行うことができます。 同じキーを持つ複数の要素を格納することができます。

主な操作

• insert：要素を挿入する
• erase：要素を削除する
• find：キーに対応する要素の範囲を探す
• count：キーに対応する要素の数を数える
• at：キーに対応する要素にアクセスする

例

C++

#include <iostream>
#include <unordered_map>
#include <utility>

auto main() -> int {
    std::unordered_multimap<std::string, int> scores;

    scores.insert({"Alice", 90});
    scores.insert({"Alice", 85});
    scores.insert({"Bob", 80});
    scores.insert({"Charlie", 70});

    for (const auto& pair : scores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

実行結果

Charlie: 70
Bob: 80
Alice: 85
Alice: 90

この例は、unordered_multimap を使用して学生の名前と点数のペアを格納しています。 insert メソッドを使用して要素を挿入し、範囲ベースのfor文を使って要素を順に参照しています。

無順序連想コンテナの注意点

無順序連想コンテナを使用する際には、以下の点に注意する必要があります。

• キーの順序は保持されないため、ループ処理などで要素を順序的に処理したい場合は、std::vectorなどの順序付きコンテナを使用する必要があります。
• ハッシュテーブルは衝突が発生する可能性があるため、パフォーマンスはキーの散らし具合に依存します。

まとめ

無順序連想コンテナは、高速な検索と挿入を提供する便利なコンテナですが、キーの順序が重要でない場合にのみ使用してください。

コンテナアダプタ

コンテナアダプタとは、既存のコンテナクラスを利用して、新たなインターフェースや動作を提供するクラスのことです。これは、基本的なコンテナ（例えば、std::vector や std::deque）に新たな機能や制約を追加するためのラッパークラスとして機能します。C++の標準ライブラリには、いくつかの代表的なコンテナアダプタが含まれています。

主なコンテナアダプタ

スタック（std::stack）

用途

LIFO（Last In, First Out、後入れ先出し）のデータ構造を提供します。

内部コンテナ

デフォルトでは std::deque を使用しますが、std::vector など他のシーケンスコンテナを使用することも可能です。

主な操作

push（要素の追加）、pop（要素の削除）、top（最上位の要素へのアクセス）。

キュー（std::queue）

用途

FIFO（First In, First Out、先入れ先出し）のデータ構造を提供します。

内部コンテナ

デフォルトでは std::deque を使用しますが、他のシーケンスコンテナを使用することも可能です。

主な操作

push（要素の追加）、pop（要素の削除）、front（先頭要素へのアクセス）、back（末尾要素へのアクセス）。

優先度付きキュー（std::priority_queue）

用途

常に優先度の高い要素を先に処理するデータ構造を提供します。

内部コンテナ

デフォルトでは std::vector を使用し、ヒープ（通常は最大ヒープ）として機能します。

主な操作

push（要素の追加）、pop（最大または最小の要素の削除）、top（最大または最小の要素へのアクセス）。

フラットマップ（std::flat_map）およびフラットセット（std::flat_set）

用途

ソートされた連続メモリにキーと値を格納するデータ構造を提供します。

内部コンテナ

通常、ソートされた std::vector を内部で使用します。

主な操作

insert（要素の追加）、erase（要素の削除）、find（要素の検索）。

コンテナアダプタの利点

抽象化

内部実装の詳細を隠蔽し、単純なインターフェースを提供する。

カスタマイズ

内部コンテナを柔軟に選択できる。

再利用性

既存のコンテナをラップすることで、新たなデータ構造を簡単に実装できる。

使用例

以下に std::stack の簡単な使用例を示します。

 
#include <stack>
#include <vector>
#include <iostream>

auto main() -> int {
    std::stack<int, std::vector<int>> stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    
    std::cout << "Top element: " << stack.top() << std::endl; // 3
    stack.pop();
    std::cout << "Top element after pop: " << stack.top() << std::endl; // 2

    return 0;
}

このように、コンテナアダプタは既存のコンテナの力を借りて、新しい機能や動作を提供するために非常に有用です。

1. <queue>, <stack>, <flat_map>, <flat_set> ヘッダの定義

   ヘッダファイル <queue>, <stack>, <flat_map>, および <flat_set> には、それぞれ queue、priority_queue、stack、flat_map、flat_multimap、flat_set、flat_multiset というコンテナアダプタが定義されています。

2. コンテナアダプタのテンプレートパラメータ

   各コンテナアダプタは、Container、KeyContainer、または MappedContainer という名前のテンプレートパラメータを取ります。これらはアダプタが適用されるコンテナの型を示します。各コンテナアダプタには、これらのテンプレートパラメータへの参照を引数として取るコンストラクタが少なくとも1つあります。コンストラクタは参照引数として与えられたコンテナをコピーします。もしコンテナがアロケータを使用する場合、アダプタのコンストラクタには互換性のあるアロケータを渡すことができます。そうでない場合は、通常のコピーまたはムーブコンストラクションが使用されます。単一のコンテナテンプレートパラメータ Container を取るコンテナアダプタについては、アダプタの最初のテンプレートパラメータ T は Container::value_type と同じ型を示す必要があります。

3. 例外のスローに関する規則

   コンテナアダプタの swap 関数は、そのアダプタの Container、KeyContainer、MappedContainer、または Compare オブジェクト（存在する場合）の swap が例外をスローしない限り、例外をスローしません。

4. コンストラクタテンプレートのオーバーロード解決への参加禁止条件

   コンテナアダプタのコンストラクタテンプレートは、InputIterator テンプレートパラメータを持ち、そのパラメータに対して入力イテレータと見なされない型が推論される場合、オーバーロード解決に参加しません。

5. イテレータの有効性に関する影響

   コンテナアダプタに insert、emplace、および erase メンバーがある場合、それらのメンバーは、コンテナの対応するメンバーと同じように、イテレータ、参照、およびポインタの有効性に影響を与えます。

   例

   flat_map<Key, T>::insert の呼び出しは、その flat_map のすべてのイテレータを無効にする可能性があります。

6. 推論ガイドのオーバーロード解決への参加禁止条件

   コンテナアダプタの推論ガイドは、次のいずれかに該当する場合、オーバーロード解決に参加しません：

   • InputIterator テンプレートパラメータがあり、そのパラメータに入力イテレータと見なされない型が推論される。
   • Compare テンプレートパラメータがあり、そのパラメータにアロケータと見なされる型が推論される。
   • Container、KeyContainer、または MappedContainer テンプレートパラメータがあり、そのパラメータにアロケータと見なされる型が推論される。
   • Container、KeyContainer、MappedContainer テンプレートパラメータがなく、Allocator テンプレートパラメータがあり、そのパラメータにアロケータと見なされない型が推論される。
   • Container および Allocator テンプレートパラメータがあり、uses_allocator_v<Container, Allocator> が偽である。
   • KeyContainer および Allocator テンプレートパラメータがあり、uses_allocator_v<KeyContainer, Allocator> が偽である。
   • KeyContainer および Compare テンプレートパラメータがあり、is_invocable_v<const Compare&, const typename KeyContainer::value_type&, const typename KeyContainer::value_type&> が有効な式でないか偽である。
   • MappedContainer および Allocator テンプレートパラメータがあり、uses_allocator_v<MappedContainer, Allocator> が偽である。

7. エクスポジション専用エイリアステンプレート

   iter-value-type、iter-key-type、iter-mapped-type、range-key-type、および range-mapped-type といったエクスポジション専用エイリアステンプレートは、コンテナアダプタの推論ガイドに登場することがあります。

8. 追加のエクスポジション専用エイリアステンプレート

   次のエイリアステンプレートは、コンテナアダプタの推論ガイドに登場することがあります：

   template<class Allocator, class T>
   using alloc-rebind = // exposition only
   typename allocator_traits<Allocator>::template rebind_alloc<T>;
   

ビュー

ビュー（view）は、データコンテナの内容に対する非所有権的な抽象化を提供するオブジェクトです。ビューは、コンテナ自体を保持せず、既存のデータの上に軽量なアクセス手段を提供するためのもので、データのコピーや移動を行うことなく、そのデータに対する操作や処理を可能にします。C++20のレンジライブラリ（Ranges Library）におけるビューは、特に効果的に使われます。

24.7.1 一般 (views.general)

1. <span> ヘッダー

   ヘッダー <span> には、ビューとして span が定義されています。span は、固定サイズの連続したメモリブロックを表現するためのクラステンプレートです。

2. <mdspan> ヘッダー

   ヘッダー <mdspan> には、多次元ビューと相互作用するためのクラステンプレート mdspan およびその他の機能が定義されています。mdspan は、異なる次元のデータを効率的に操作するための多次元ビューを提供します。

ビューは、効率的なメモリ管理と安全なデータアクセスを提供するために設計されており、特にパフォーマンスが重要なアプリケーションにおいて強力なツールとなります。

([Category:C++|こんてならいふらり])