C++ のコンテナとイテレーター

必要なルックアップ、走査、挿入、削除、メモリー局所性、および参照の安定性に基づいてコンテナを選択します。計算量は事前条件を満たす操作を記述します。無効化と所有権は、変更後も設計が正しく保たれるかを決定します。

コンテナの選択 #

• std::vector は、連続したストレージ、ランダムアクセス、キャッシュ局所性、および data() を介した C との相互運用におけるデフォルトのシーケンスです。末尾への追加は償却定数時間です。容量が増加すると、すべてのイテレーター、ポインター、参照が無効になります。容量が増加しない場合でも、挿入位置以降のイテレーターと参照は無効になります。
• std::deque はインデックスによるアクセスをサポートします。末尾への挿入はイテレーターを無効化しますが、参照は無効化しません。ストレージは非連続であり、中央への挿入はイテレーターと参照を無効化します。
• std::list と std::forward_list は、挿入と削除の際に、影響を受けないノードへのイテレーターと参照を維持します。ノード割り当てとポインター追跡が必要なため、デフォルトではなく、測定に基づいて選択します。
• std::map と std::set は、順序付き走査と対数時間のルックアップを提供します。削除された要素を除き、挿入によってイテレーターや参照は無効化されません。
• std::unordered_map と std::unordered_set は、平均定数時間のルックアップを提供します。再ハッシュはイテレーターを無効化しますが、要素への参照とポインターは有効なままです。削除では、削除された要素だけが無効になります。

reserve() は予測される vector の再割り当てを避け、unordered_* の再ハッシュも減らせます。文書化された規則によってイテレーターが無効になる操作の後で、そのイテレーターを有効にするものではありません。

値の挿入と移動 #

insert は要素または範囲を受け取り、emplace は引数からコンテナのストレージ内に要素を構築します。

#include <string>
#include <utility>
#include <vector>

std::vector<std::string> names;
std::string name = "Ada";

names.push_back(name);            // copies; name remains owned by the caller
names.push_back(std::move(name)); // moves; name stays valid but has unspecified value
names.emplace_back(3, 'x');       // constructs "xxx" in the vector

オブジェクトがすでに存在する場合、insert または push_back(std::move(value)) によって所有権の移動が明示されます。emplace が一時オブジェクトの生成を避けるのは、コンストラクター引数を利用できる場合だけです。常に高速なわけではなく、要素コンストラクターの検証を代替するものでもありません。連想コンテナの emplace は、キーがすでに存在する場合に要素を構築して破棄する可能性があります。try_emplace は、その重複キーの場合にマップ値の構築を避け、insert_or_assign は置換ポリシーを明示します。

ノードベースのコンテナでは、extract が、挿入または破棄されるまで削除したノードを所有するノードハンドルを生成します。格納された値を移動せずに互換性のあるノードを移せますが、アロケーターの互換性とコンテナで文書化された事前条件は引き続き適用されます。

イテレーターと事前条件 #

アルゴリズムは必要とするイテレーターカテゴリーを宣言します。入力イテレーターは単一パス、前方イテレーターは複数パス、双方向イテレーターはデクリメントを追加し、ランダムアクセスイテレーターは算術演算と順序付けを追加し、連続イテレーターはさらに隣接するストレージを表します。あるコンテナのイテレーターが別のコンテナと同様に振る舞うと仮定せず、アルゴリズムが必要とするカテゴリーを渡してください。

アルゴリズムまたはコンテナのメンバーを呼び出す前に、範囲の事前条件を検証します。

auto first = values.begin();
auto last = values.end();
if (first != last) {
    values.erase(first); // `first` is valid and dereferenceable
}

end() はセンチネルであり、要素ではありません。決して参照を外さず、API が明示的に許可する場合を除いて、異なるコンテナのイテレーターを比較しないでください。変更をまたいでイテレーターを保持する前に、対象コンテナ固有の無効化表を確認してください。範囲 for ループと標準アルゴリズムは手動のイテレーター操作を減らしますが、それらの規則を停止させるものではありません。