C++/コンテナ

C++
コンテナ

導入

コンテナとは、複数の要素を格納するためのC++のデータ構造です。プログラミングにおいて、データを効率的に管理し、操作するためにコンテナは不可欠です。C++の標準ライブラリには、さまざまな種類のコンテナが含まれており、それらを適切に使いこなすことが重要です。

配列と動的配列

配列は、同じ型の要素を連続したメモリ領域に格納するC++の基本的なデータ構造です。配列のサイズは宣言時に指定され、その後変更することができません。一方、動的配列は、実行時に必要なサイズでメモリを確保し、サイズを動的に変更できます。

静的配列の宣言と初期化は、以下のように行います。

int staticArray[]{1, 2, 3, 4, 5};

動的配列の場合、new演算子を使用してメモリを動的に確保します。

int size;
cout << "Enter array size: ";
cin >> size;
int *dynamicArray = new int[size];

動的配列のサイズを変更するには、新しいサイズのメモリを確保し、古い配列の要素を新しい配列にコピーします。以下は、動的配列のサイズを2倍に拡張する関数の例です。

void resizeArray(int* &array, int &size) {
    int newSize = size * 2;
    int *newArray = new int[newSize];
    for (int i = 0; i < size; i++) {
        newArray[i] = array[i];
    }
    delete[] array;
    array = newArray;
    size = newSize;
}

new/delete演算子を使ったメモリ管理の欠点と克服法

レガシーなnewおよびdelete演算子を使用したメモリ管理にはいくつかの欠点があります。これらの欠点には、メモリリーク、二重解放、無効なポインタの使用などが含まれます。これらの問題を解決するために、より安全で効率的なメモリ管理技術が開発されました。その主な代替技術には、スマートポインタ、標準コンテナ、およびカスタムアロケータが含まれます。

スマートポインタ

スマートポインタは、C++11以降で導入された機能であり、動的なメモリ管理を行うための安全な方法を提供します。主なスマートポインタには、std::unique_ptr、std::shared_ptr、およびstd::weak_ptrがあります。

std::unique_ptr: 所有権を唯一の所有者に委任し、自動的にメモリを解放します。スコープを抜けるか、所有者がstd::move()を使用して所有権を移動すると、関連するリソースが解放されます。
std::shared_ptr: 複数の所有者を許可し、参照カウントに基づいてメモリを解放します。最後の所有者が参照を解放すると、メモリが解放されます。
std::weak_ptr: std::shared_ptrの循環参照問題を解決するための機能を提供します。弱参照であり、所有者にはカウントされません。

標準コンテナ: 標準コンテナは、メモリ管理の一部としても機能します。動的なメモリ割り当てと解放をコンテナが自動的に処理します。例えば、std::vector、std::list、std::mapなどの標準コンテナは、動的なメモリ管理を必要としますが、ユーザーは手動でメモリを解放する必要はありません。
カスタムアロケータ: カスタムアロケータは、C++でのメモリ管理の柔軟性を向上させるための手法です。アロケータは、特定のメモリ管理ポリシーに基づいてメモリの割り当てと解放を行います。カスタムアロケータを使用することで、メモリの割り当てと解放の方法をカスタマイズし、アプリケーションの要件に合わせることができます。

これらの代替技術は、メモリリークや二重解放などの問題を回避し、メモリ管理をより効率的で安全なものにします。特に、スマートポインタは、手動でメモリ解放を行う必要がなく、リソースの解放を自動化する点で便利です。

標準コンテナライブラリ

C++の標準ライブラリには、さまざまなタイプのコンテナが含まれています。これらは、特定の目的に合わせて設計されており、効率的なデータ管理と操作を提供します。主なカテゴリは以下の通りです。

シーケンスコンテナ

vector: 動的配列。ランダムアクセスが高速で、動的なサイズ変更が可能。
array: 静的配列。ランダムアクセスが高速で、静的なサイズ変更が不可能。
deque: 両端キュー。ベクトルとリストの特性を併せ持つ。
list: 双方向リスト。挿入と削除がリストのサイズに依存せずに高速。
forward_list: シングルトンなリスト。

詳細は「C++/標準ライブラリ/vector」、「C++/標準ライブラリ/array」、「C++/標準ライブラリ/list」、および「C++/標準ライブラリ/deque」を参照

連想コンテナ

set: 重複を許さない要素の集合。要素は昇順にソートされる。
map: キーと値のペアを格納する連想配列。キーに基づいて高速な検索が可能。
multiset: 重複を許す要素の集合。要素は昇順にソートされる。
multimap: キーに基づいて重複を許す連想配列。

詳細は「C++/標準ライブラリ/set」、「C++/標準ライブラリ/map」、「C++/標準ライブラリ/multiset」、および「C++/標準ライブラリ/multimap」を参照

アダプタコンテナ

stack: LIFO（Last In, First Out）構造。スタック操作（push、pop）を提供。
queue: FIFO（First In, First Out）構造。キュー操作（push、pop）を提供。
priority_queue: 優先度付きキュー。要素は優先順位に基づいて格納される。

詳細は「C++/標準ライブラリ/stack」、「C++/標準ライブラリ/queue」、および「C++/標準ライブラリ/priority_queue」を参照

これらのコンテナは、それぞれ異なる目的に使用されますが、共通のインターフェースを持ち、汎用性が高いです。

コンテナは共通の基底クラスから派生してはいない

C++の標準テンプレートライブラリ（STL）のコンテナには共通の親クラスはありません。C++は多重継承が可能であり、抽象基底クラスを作成することもできますが、STLの設計では共通の基底クラスを持たないことで、テンプレートの柔軟性とパフォーマンスを最適化しています。

ただし、STLのコンテナは共通のインターフェースや機能を提供するために、テンプレートとイテレータという概念を使用しています。

共通のインターフェース

STLのコンテナは、以下のような共通のメンバ関数を持っています。

size(): 現在の要素数を返す。
empty(): コンテナが空かどうかを確認する。
begin(): コンテナの先頭のイテレータを返す。
end(): コンテナの終端を示すイテレータを返す。

これらの共通のメンバ関数により、さまざまな種類のコンテナに対して統一的な操作が可能です。これにより、アルゴリズムとコンテナを組み合わせる際の柔軟性が高まります。例えば、std::find()やstd::sort()のような汎用アルゴリズムは、コンテナの種類に関わらず使用できます。

イテレータの役割

イテレータは、C++のSTLで重要な役割を担っており、コンテナ内の要素を巡回したり操作したりするための抽象的な方法を提供します。イテレータの主な機能は以下の通りです。

双方向イテレータ (bidirectional_iterator): 前方および後方への移動が可能。std::listなどで使用される。
ランダムアクセスイテレータ (random_access_iterator): 任意の位置に素早く移動可能。std::vectorやstd::arrayで使用される。
入力イテレータ (input_iterator): 読み取り専用のイテレータ。ストリーム入力などで使用される。
出力イテレータ (output_iterator): 書き込み専用のイテレータ。

これらのイテレータは、C++標準ライブラリのアルゴリズムと組み合わせることで、より簡潔で効率的なコードを記述するのに役立ちます。

std::vector<int> numbers = {1, 2, 3, 4, 5};
auto it = std::find(numbers.begin(), numbers.end(), 3);
if (it != numbers.end()) {
    std::cout << "Found: " << *it << std::endl;
}

このように、イテレータはC++のコンテナ操作において柔軟性と統一性を提供します。

コンテナの選択

コンテナを選択する際には、用途に応じて最適なものを選ぶことが重要です。選択の基準として以下の点を考慮することが推奨されます。

ランダムアクセスが必要な場合: std::vector や std::array は、ランダムアクセスが高速で、データの順序を維持する必要がある場合に適しています。
頻繁な挿入・削除が必要な場合: std::list や std::forward_list は、任意の位置での挿入と削除が高速であり、要素の順序が重要である場合に有用です。
キーと値のペアを格納する場合: std::map や std::unordered_map は、キーに基づいて効率的な検索、挿入、削除を行う場合に適しています。
集合データが必要な場合: std::set や std::unordered_set は、重複のない要素の集合を保持し、検索を高速に行いたい場合に適しています。

C++の標準コンテナは、さまざまなシナリオに対応するための多様な機能を提供しています。プログラマは、これらのコンテナの特性を理解し、適切な場面で使い分けることで、効率的で可読性の高いコードを記述できます。コンテナとイテレータの組み合わせにより、データ構造の操作が一層強力になり、コードの柔軟性が向上します。

RTTI

C++
コンテナ

範囲ベースfor