AllocatorAwareContainer:Propagate_on_container_XXX デフォルトの導入と落とし穴

foonathan/memory の std_allocator アダプターを作成しているときに、STL 356 についてあまり知られていない事実をいくつか学びました。 と 364 共有したい概念について説明します。深呼吸をして、STL コンテナーの、まだ十分にカバーされていない側面に飛び込みましょう:アロケーター ストレージです。

C++11 376 を示して、アロケータの比較プロパティについて説明します。 特性と、この 2 つの組み合わせが不必要な悲観化につながり、おそらくあまり知られていない未定義の動作のケースにつながる可能性があります。

問題の紹介

次のアロケータから始めます:

#include <memory>

std::size_t alloc_count = 0u;

template <typename T>
class my_allocator
{
public:
 using value_type = T;

 my_allocator()
 : id_(++alloc_count) {}

 template <typename U>
 my_allocator(const my_allocator<U> &other)
 : id_(other.id_)
 {}

 T* allocate(std::size_t n)
 {
 return std::allocator<T>().allocate(n);
 }

 void deallocate(T *ptr, std::size_t n)
 {
 std::allocator<T>().deallocate(ptr, n);
 }

 std::size_t id() const
 {
 return id_;
 }

private:
 std::size_t id_;

 template <typename T1, typename T2>
 friend bool operator==(const my_allocator<T1> a, const my_allocator<T2>&b);
};

template <typename T, typename U>
bool operator==(const my_allocator<T> a, const my_allocator<U>&b)
{
 return a.id_ == b.id_;
}

template <typename T, typename U>
bool operator!=(const my_allocator<T>&a, const my_allocator<U>&b)
{
 return !(a == b);
}

上記のクラス 382 はナイーブで、(この投稿のために) 名前を持つアロケーターの非常に単純化された実装です.作成された各アロケーターは、デバッグ目的に役立つ一意の識別子を取得します.2 つのアロケーターは、同じ識別子を持つ場合、等しいと見なされます.

実際の実装では、グローバル整数変数の値を識別子として使用せず、単に 394 に転送しません。 実際の割り当て関数で、しかし、この実装は今のところ忙しくするのに十分です.

int main()
{
 std::vector<int, my_allocator<int>> a, b, c;

 a.push_back(0);

 b.push_back(2);
 b.push_back(4);

 c.push_back(1);
 c.push_back(3);

 a = std::move(c);
 std::swap(a, b);

 std::cout << a[0] << ' ' << b[0] << '\n';
}

上記のスニペットでは、アロケーター クラスを 3 つの 404 で使用しています。 オブジェクト。コンテナが読み込まれ、次に 417 ムーブは 428 に割り当てられています 、 438 と 447 スワップされ、452 の最初の値 と 464

コードは期待どおりにコンパイル、実行、出力されます 473 GCC と Clang の下で.Everything は大丈夫です - それが未定義の動作であり、MSVC の下でクラッシュすることを除いて.

また、未定義の動作とは別に、おそらく予想よりも高価で危険な操作が 1 つあります。

その理由を理解するには、一歩下がって、アロケーターの比較と 480 を確認する必要があります。 クラス。

すべてのアロケータが (不) 等しく作成される

496ごと (不) 等号の比較演算子を提供する必要があります。

アロケータが等しいかどうかは、1 つのアロケータでメモリを割り当て、別のアロケータでメモリを解放する機能によって決まります。つまり、2 つのアロケータ 507 および 511 526 によってメモリが割り当てられた場合、等しいと比較されます 537 で割り当てを解除できます

比較は、例えば540 で使用 アロケーターが既に等しい場合に不必要な操作を避けるためのクラス。

C++17 以降、独自のアロケーター クラスで typedef 552 を指定できるようになりました .

これが 566 の場合 、2 つのアロケーター オブジェクトは常に等しいと見なされます。この typedef が提供されない場合、579 586 に転送します :Empty、つまり、ステートレス型には等しくない状態がないため、常に等しいです。これは、追加の最適化として、特に 593 で使用できます。 後で明らかになる仕様。

AllocatorAwareContainer

609 は C++11 の新しい概念であり、613 の方法を説明しています。 オブジェクトは、コンテナー内で処理する必要があります。623 を除くすべての STL コンテナー この概念をモデル化しています。

638 のようなあまり面白くないものが必要です 関数またはすべての割り当てが 645 を介して行われること だけでなく、アロケータ オブジェクトをコピーまたは移動する方法とタイミングも指定します。この動作には興味深い結果があります。

AllocatorAwareContainer:コンストラクターのコピー/移動

658 のコンストラクターをコピーおよび移動する アロケーター オブジェクトをそれぞれコピーまたは移動します。移動は、その移動コンストラクターを呼び出すことによって直接行われます。コピーは、特別な関数 665 を介して制御できます。 .

676 の場合 アロケーターのコピー コンストラクターで呼び出されるこのメンバー関数を提供します。メンバー関数が存在しない場合、既定では、渡されたアロケーターのコピーが返されます。

681 696 を許可します コンテナーのコピーを追跡したり、コピーされたアロケーターの状態を変更したりするためのライター。私はこの関数が (またはまったく) 有用であるとは思いません。Github で検索するとほぼ 30,000 の結果が得られますが、それらのほとんどは標準ライブラリのテストです。実装、転送が必要なアダプター クラス、または MSVC の回避策。

AllocatorAwareContainer:コピー/移動代入演算子

移動コンストラクターは非常に簡単で、コピー コンストラクターはやや一般的すぎましたが、これまでのところ、非常に直感的な動作でした.まあ、それは代入演算子で変わります.

代入の問題は、コンテナーに既にオブジェクトが含まれていることです (通常は)。新しいコンテナーを割り当てるには、それらを取り除き、新しいコンテナーを取得する必要があります。アロケーター オブジェクトが等しい場合、これは非常に簡単です。そうでない場合は興味深いものになります。

例外の安全性を無視して、コンテナーは最初に古いオブジェクトを破棄し、古いアロケーターでそれらのメモリの割り当てを解除する必要があります。次に、新しいメモリを割り当てます。そのために、新しいアロケータを使用します。それとも古いアロケーター… コンテナーが割り当てられている場合、アロケーターは割り当てられていますか?

通常、次の 3 つのオプションがあります。

<オール>
  • アロケータを割り当てないでください。コンテナーは、以前と同じアロケーターを使用するだけです。
  • 他のアロケーター オブジェクトのコピー/移動を使用して、アロケーターを割り当てます。
  • アロケータをまったく別のオブジェクトに割り当てます。

    • オプション 3 は (幸いなことに) 問題外です。したがって、選択肢はオプション 1 と 2 の間のみです。この選択はユーザーが行うことができます。デフォルトはオプション 1 です。

    このオプションは 708 で選択できます と 717 .

    721 の場合 クラスはこれらの 1 つを提供します - すばらしい名前の - ブール型の typedef で、アロケータが代入時に伝播するかどうか、つまり代入されるかどうかを制御します。クラスがそれらを提供しない場合、730 - 悪い - デフォルトの 744 を提供します アロケータの割り当てを妨げています。

    割り当ては、アロケータのコピーまたは移動割り当て演算子をそれぞれ呼び出すことによって行われます。

    AllocatorAwareContainer:スワップ

    スワッピングは割り当てと同様に動作します。等しくないアロケータは、759 の場合にのみスワップされます 適切な値 (または型) を持っています。デフォルトは 763 です。 .

    AllocatorAwareContainer:概要

    つまり、アロケーターが異なる 2 つのコンテナーについてまとめると、次のようになります。

    • コピー コンストラクターは、772 をコピーします。 781 経由 関数。
    • move コンストラクターは 793 を構成します . 807 なしで直接
    • 移動代入演算子は 819 を移動代入します 824 の場合 831 です (デフォルトではありません)。
    • コピー代入演算子は 843 をコピー代入します 858 の場合 867 です (デフォルトではありません) 872 はありません。 コピー コンストラクタのように。
    • Swap は 883 を交換します 899 の場合 903 です (デフォルトではありません)。

    この動作は、予期しない動作の 2 つのケースにつながる可能性があります。

    落とし穴 #1:ムーブの割り当て

    コンテナーの移動割り当ては非常に簡単な操作です。ポインターをコピーして、古いポインターを 914 に設定するだけです。 そして、あなたは行ってもいいです。右？違います。

    最初から移動操作をもう一度考えてみましょう:

    a = std::move(c);

    移動すると、メモリの所有権が譲渡されます。925 の割り当て 933 へ 所有権の譲渡、949 所有する 951 からの記憶 操作後。961 971 の責任者です のメモリ、つまり、必要に応じて割り当てを解除します。

    これを別のアロケータと組み合わせると、興味深い動作になります:When 982 破棄されるか、拡張する必要がある場合、アロケータを使用してメモリの割り当てを解除します。ただし、メモリは 996 によって割り当てられました のアロケータです!あるアロケータからメモリを割り当て、別のアロケータからメモリの割り当てを解除することは、おそらく良い考えではありません.[引用が必要 ]

    したがって、コンテナーは、異なるアロケーターを使用した移動割り当てで所有権を単純に転送することはできません。コピー割り当てと同様の作業を行う必要があります。 個々の要素、古い割り当ての解除、ポインターの調整、他のオブジェクトを移動元としてマークする何かを行います。

    この操作はおそらく予想よりもコストがかかります。さらに重要なことに、潜在的なスロー操作です!コンテナ移動の割り当ては 1019 のみです。 1025 の場合 1037 です 、この場合、アロケーターはポインターと共に移動され、高速バージョンが使用されます。それ以外の場合、アロケーターが比較され、結果に応じて低速移動が必要になります。

    落とし穴 #2:スワップ

    スワッピングは移動に似ています:ポインタを交換するだけで問題ありません - 1047 ではない不等アロケータを扱っている場合を除きます .例として、もう一度スワップ操作を最初から見てみましょう:

    std::swap(a, b);

    1050以降 と 1061 のアロケーターが等しくないため、ポインターを単純に交換することはできません。これは、間違ったアロケーターを介して再び割り当て解除につながります。

    したがって、操作はもう少し複雑にする必要があります。両方のコンテナに新しいメモリを割り当ててから 1071 を割り当てる必要があります。 元の要素 - 正確にはどこから?すべての要素は古いメモリにあり、新しいメモリにはスワップするオブジェクトが含まれていません!

    わかりましたので、デフォルト コンストラクターを使用して新しいメモリに要素を作成する必要があります。これは、デフォルト コンストラクターのない型では機能しません。

    よし、1080 にする必要がある -最初のコンテナの新しいメモリ内の他のコンテナの古いメモリから新しいメモリ内の要素を構築します。その後、古いメモリの割り当てを解除でき、準備完了です。

    ただし、それはできません。

    §23.2.1[container.requirements.general] セクション 8 および 10:

    説明されている方法は、要素移動コンストラクターを呼び出し、メモリ割り当てステップで例外をスローして、all を無効にすることができます。 all を参照する参照、ポインタ、またはイテレータ したがって、コンテンツを交換する必要があることを除いて、コンテナー スワップ関数のすべての要件に違反します。

    そのため、例外をスローせずに新しいメモリを割り当て、格納された型に対する操作を呼び出さずにオブジェクトを新しいメモリにスワップし、要素へのすべての外部ポインタを調整して、古い場所ではなく新しい場所のオブジェクトを指すようにする必要があります.

    標準では、セクション 8 の残りの部分で通常どおりこの状況を解決します。

    伝播されないアロケータが等しくない 2 つのコンテナを交換することは、未定義の動作です。

    デフォルトでは非伝播がアクティブであるため、コンテナーを交換すると、初期コードで未定義の動作が発生します。

    結論

    これらの落とし穴を避けるために、1095 および 1108 両方とも 1116 でなければなりません .一貫性のために、1123 そうでなければ、移動とコピーは異なるセマンティクスを持ちます。

    したがって、C++11 の最小アロケーターは、悪い - デフォルトを使用するためだけに記述しないことを提案します。代わりに、次の最小アロケーターを作成して、3 つの typedef を追加する必要があります。

    template <typename T>
struct min_allocator
{
 using value_type = T;

 using propagate_on_container_copy_assignment = std::true_type; // for consistency
 using propagate_on_container_move_assignment = std::true_type; // to avoid the pessimization
 using propagate_on_container_swap = std::true_type; // to avoid the undefined behavior

 // to get the C++17 optimization: add this line for non-empty allocators which are always equal
 // using is_always_equal = std::true_type;

 template <class U>
 min_allocator(const min_allocator<U>&);

 T* allocate(std::size_t n);
 void deallocate(T* ptr, std::size_t n);
};

template <typename T, typename U>
bool operator==(const min_allocator<T>&, const min_allocator<U>&);

template <typename T, typename U>
bool operator!=(const min_allocator<T>&, const min_allocator<U>&);

    また、アロケータの比較では、あるオブジェクトからメモリを割り当て、別のオブジェクトからメモリの割り当てを解除できるかどうかのみを反映する必要があります。これにより、コストがかかる可能性のある不要なコピーが回避されます。

    更新:フォローアップ風の投稿が利用できるようになりました.