コンテナ Ⅱ のオプション — すべての std::vector の使用方法が同じというわけではありません

さて、前回の投稿で optional<T> を入れることについて話しました当時は妥当だと思っていた結論に達しましたが、当然のことながら、人々は私の議論のいくつかの欠陥を指摘しました.

私は先週 ACCU にいたので、以前は回答できませんでした (自分へのメモ:公開してから会議に飛び出さないでください)。どこが間違っていたのか

`std::optional<T>` 対 `std::variant<T, std::monostate>`

私は std::optional<T> と主張しましたと std::variant<T, std::monostate> 同じ目的を果たします:どちらも型 T の値を格納する型を表します

私は今でもこれは有効だと思っています。 std::variant<T, std::monostate> std::optional<T> の代わりに :インターフェースは扱いにくく、単純にタイプするだけです.しかし、概念的には同じタイプです.

std::optional<T> を使うべきではないとも主張しました (または std::variant<T, std::monostate> ) 空の型に「id が無効」などの特別な意味がある場合。代わりに std::variant<T, special_meaning> を使用する必要があります .このアドバイスに従うことで、よりクリーンなコードにつながると今でも考えています。

`std::optional<T>` セットで

std::optional<T> を入れるべきではないと言いましたセットでは、それはやや無意味だからです:とにかくそこに空のオプションを1つしか入れることができず、そこに何も入れないこともできます.したがって、 std::optional<T> を使用しないでくださいセット内 (またはマップ内のキータイプとして)。

std::nullopt かどうかにかかわらず、アルゴリズムの動作が異なる場合はセットに含まれていますが、実際には std::nullopt という意味ではありません、つまり special_meaning std::variant を保存したい .

誰もそれに異議を唱えていないようなので、そのアドバイスは問題ありません。

`std::optional<T>` マップで

std::optional<T> 上記のように、マップのキータイプは意味をなさないため、確認すべき唯一のことは std::optional<T> の使用です。マップされたタイプとして。

私はstd::map<T, std::optional<U>>だと言いましたは部分マップです。キーには値がある場合とない場合があります。それが必要な場合、これは優れた抽象化です。

ただし、オプションのマップはやや扱いにくいです:潜在的な lookup() optional<mapped_type> を返す関数ネストされたオプションにつながりますが、これは使用するのが少し奇妙です.A std::map<T, std::variant<U, no_value>> 私の意見では、ややクリーンな抽象化です。

しかし、最善の解決策は partial_map<T, U> です

そこにも異論はあまりないので、論争の要点に移りましょう:

`std::optional<T>` シーケンスコンテナ内

std::nullopt を入れる必要はないと言いましたシーケンスコンテナー内:代わりに何も入れないでください。

そして、これは多くの人が私が間違っていると考えているところです.そして私は間違っています — しかし、私のアドバイスはまだ有効です, ただ「シーケンスコンテナ」自体のためではありません.

詳しく説明しましょう。

私が取り組んでいる最近のプロジェクト (個人的な使用のための楽しいもの) では、多くの std::vector<T> を使用しています .しかしながら、私は使っていません std::vector<T> を使いたくなるかもしれません .特に、それらを何かを詰め込む場所として使用しているだけで、後でそれらに対して範囲ベースの for を実行する必要があります:

std::vector<int> my_ints;
// fill container up with some integers

for (auto i : my_ints)
    do_sth(i);

// fill container up with some more ints

for (auto i : my_ints)
    do_sth_else(i);

インターフェースはあまり気にしない std::vector<T> になります special:i を要求するので、ランダムアクセスは必要ありません -th 要素は、私の使い方では意味がありません!

順序もあまり気にしません。気にするのは、最終的に要素を処理するかどうかだけですそこにある場合。これは、最後の要素と交換して pop_back() を実行することにより、要素を削除することを意味します、これは O(1) です通常の O(n) と比較して std::vector<T>::erase の .

この種の std::vector<T> の使用法については、私のアドバイスは正:std::optional<T> を保存する必要はありません std::nullopt を処理する必要がないため、コンテナに s. T を保存するだけで、より高速で効率的なコードにつながります std::nullopt の場合は直接、何もしません .

ただし、これは通常ではありません std::vector<T> の使い方 :通常は順序が重要です — 結局は sequence ですコンテナですが、 std::vector<T> の使い方に気づきませんでしたはその使い方に合わないので、そのアドバイスを書きました。

`T` のバッグ

この間違いから学べることがあります:新しいコンテナーの必要性です。std::vector<T> のようなコンテナーです。ただし、順序付けや配列アクセス演算子は提供されず、insert(element) しかありませんと erase(iter) 、どちらも O(1) です .

bag<T> としましょうそれだけだから:要素を入れるバッグ。std::vector<T> の上にシンプルな実装次のようになります:

template <typename T>
class bag
{
    std::vector<T> container_;

public:
    using value_type    = T;
    using iterator       = typename std::vector<T>::iterator;
    using const_iterator = typename std::vector<T>::const_iterator;

    //=== constructors/destructors ===//
    bag() = default;

    // other constructors, assignment if needed

    //=== access ===//
    iterator begin() noexcept
    {
        return container_.begin();
    }
    const_iterator begin() const noexcept
    {
        return container_.begin();
    }
    const_iterator cbegin() const noexcept
    {
        return container_.begin();
    }

    iterator end() noexcept
    {
        return container_.end();
    }
    const_iterator end() const noexcept
    {
        return container_.end();
    }
    const_iterator cend() const noexcept
    {
        return container_.end();
    }
    
    // note: no array access, front, back
    // maybe data() if necessary

    //=== capacity ===//
    bool empty() const noexcept
    {
        return container_.empty();
    }

    size_type size() const noexcept
    {
        return container_.size();
    }

    size_type capacity() const noexcept
    {
        return container_.capacity();
    }

    void reserve(size_type new_capacity)
    {
        container_.reserve(new_capacity);
    }

    void shrink_to_fit()
    {
        container_.shrink_to_fit();
    }

    //=== modifiers ===//
    template <typename... Args>
    void emplace(Args&&... args)
    {
        container_.emplace_back(std::forward<Args>(args)...);
    }

    void insert(const T& value)
    {
        emplace(value);
    }
    void insert(T&& value)
    {
        emplace(std::move(value));
    }

    // range insert if needed

    void clear() noexcept
    {
        container_.clear();
    }

    void erase(iterator iter) 
    {
        if (iter != std::prev(container_.end())
        {
            // swap with last element
            using std::swap;
            swap(*iter, container_.back());
        }
        container_.pop_back();
    }
    
    // range erase if needed
};

さて、このコンテナの場合、そこにオプションを格納することは間違いなく意味がありません.

前回の投稿で、std::vector<std::variant<T...>> の最適化についても言及しました複数の std::vector<T>... にアンラップしますこれは分岐予測に優れており、メモリの使用量も少なくて済みます。もちろん、std::vector<T> を使用する場合、この最適化は意味がありません。シーケンスコンテナーとして。ただし、bag の場合それは理にかなっており、実際に私のサイドプロジェクトの主要なデータ構造です。

なぜわざわざするの?

なぜ私が std::optional<T> に対してそのような十字軍に参加したのか疑問に思う人もいました理由は簡単です。もともと似たようなデザインをしていたのですが、その欠点に気づき、他の人が同じことをするのを防ぎたいと思いました。そこで、一般化して他のコンテナーについても考えました。 std::vector の私の使用通常の使用とは異なりました。

しかし、これはまだ興味深い発見につながると思います:新しいコンテナタイプ bag<T> の必要性です。 .