• Class / Function / Type

      std::
    • Header file

      <>
    • Other / All

    最終更新日時(UTC):
    が更新

    履歴 編集

    function
    <unordered_set>

    std::unordered_multiset::insert

    iterator insert(const value_type& v);
    iterator insert(value_type&& rv);                              // (1)
    
    iterator insert(const_iterator position, const value_type& v);
    iterator insert(const_iterator position, value_type&& rv);     // (2)
    
    template <class InputIterator>
    void insert(InputIterator first, InputIterator last);          // (3)
    
    void insert(initializer_list<value_type> il);                  // (4)
    
    iterator insert(node_type&& nh);                               // (5) C++17
    iterator insert(const_iterator hint, node_type&& nh);          // (6) C++17
    

    概要

    コンテナに要素を追加する。

    要件

    • v を引数にとる形式((1)、(2)の上側)では、value_type はコンテナに対してコピー挿入可能(CopyInsertable)でなければならない。
      コンテナに対してコピー挿入可能とは、m をアロケータ型 allocator_type の左辺値、p を要素型 value_type へのポインタとすると、以下の式が適格(well-formed)であるということである。

      std::allocator_traits<allocator_type>::construct(m, p, v);

    • rv を引数にとる形式((1)、(2)の下側)では、value_type はコンテナに対してムーブ挿入可能(MoveInsertable)でなければならない。
      コンテナに対してムーブ挿入可能とは、m をアロケータ型 allocator_type の左辺値、p を要素型 value_type へのポインタとすると、以下の式が適格(well-formed)であるということである。

      std::allocator_traits<allocator_type>::construct(m, p, std::move(rv));

    • 引数 position は、コンテナの有効な読み取り専用イテレータでなければならない。
      なお、標準では間接参照可能(dereferenceable)である必要があることになっているが、その必要はない(つまり、最終要素の次を指すイテレータでも良い)ものと思われる。

    • 引数 first、および、lastは、入力イテレータの要件を満たし、かつ、イテレータ範囲 [first, last) が当該コンテナ以外を指す有効な範囲でなければならない。
      また、引数 first、および、last を引数にとる形式((3))では、このコンテナの要素型 value_type は、コンテナに対して *first から直接構築可能(EmplaceConstructible)でなければならない。
      ここで、コンテナに対して *first から直接構築可能とは、m をアロケータ型 allocator_type の左辺値、p を要素型 value_type へのポインタとすると、以下の式が適格(well-formed)であるということである。

      std::allocator_traits<allocator_type>::construct(m, p, *first);

      なお、first、および、lastは、標準では value_type を参照しなければならない(つまり、コンテナの value_typestd::iterator_traits<decltype(first)>::value_type が同一の型でなければならない)ことになっているが、実際にはその必要はなく、上記の直接構築可能の要件を満たすだけで良いものと思われる。

    • (4)の形式では、value_type はコンテナに対してコピー挿入可能でなければならない。

    • (5), (6)の形式では、 nh は空である、または、(*this).get_allocator() == nh.get_allocator()でなければならない。

    効果

    • (1) : 引数 v、あるいは rv で指定した値の要素を追加する。
    • (2) : 引数 v、あるいは rv で指定した値の要素を追加する。
      引数 position は、要素の挿入位置を探し始める場所のヒントとして使用されるが、実装によって無視されるかもしれない。
    • (3) : イテレータ範囲 [first, last) のすべての要素 t に対して、(1)の形式の insert(t) を呼び出した場合と等価である。
    • (4) : (3)の形式を insert(il.begin(), il.end()) として呼び出した場合と等価である。
    • (5) : nhが空の場合、効果はない。そうでなければ、nhが所有する要素を挿入し、新しく挿入された要素を指すイテレータを返す。nh.key() と等価なキーを持つ要素を含む範囲がコンテナ内に存在する場合、要素はその範囲の終端に挿入される。
    • (6) : nhが空の場合、効果はなく、(*this).end()を返す。そうでなければ、 nh によって所有されている要素をコンテナに挿入し、 nh.key() と等価なキーを持つ要素を指すイテレータを返す。 nh.key() と等しいキーを持つ要素を含む範囲がコンテナ内に存在する場合、要素はその範囲の終端に挿入される。要素は、hintの直前の位置のできるだけ近くに挿入される。

    戻り値

    • (1) : 追加された要素を指すイテレータ。
    • (2) : 追加された要素を指すイテレータ。
    • (3) : なし
    • (4) : なし
    • (5), (6) : nh が空の場合は終端イテレータ、そうでなければ挿入された要素を指すイテレータ。

    例外

    単一要素の形式((1)と(2))では、ハッシュ関数以外から例外が投げられた場合には、挿入はされない。

    計算量

    • (1) : 平均的なケースでは定数(O(1))だが、最悪のケースではコンテナの要素数 size() に比例(O(N))。
    • (2) : 平均的なケースでは定数(O(1))だが、最悪のケースではコンテナの要素数 size() に比例(O(N))。
    • (3) : 平均的なケースでは引数の範囲の要素数 std::distance(first, last) に比例(O(N))するが、最悪のケースでは引数の範囲の要素数 std::distance(first, last) とコンテナの要素数 size() に 1 加えたものの積に比例(O(std::distance(first, last) * (size() + 1)))。
    • (4) : (3)の形式を insert(il.begin(), il.end()) として呼び出した場合と等価。
    • (5), (6) : 平均的なケースでは O(1)、最悪のケースでは O(size())

    備考

    • これらの関数が呼ばれた後も、当該コンテナ内の要素を指す参照は無効にはならない。 なお、規格書に明確な記載は無いが、当該コンテナ内の要素を指すポインタも無効にはならない。

    • これらの関数が呼ばれた後も、呼び出しの前後でこのコンテナのバケット数(bucket_count() の戻り値)が変わらなかった場合には当該コンテナを指すイテレータは無効にはならない。
      それ以外の場合は、当該コンテナを指すイテレータは無効になる可能性がある。
      コンテナのバケット数が変わらない場合とは、要素追加後の要素数が、要素追加前のバケット数(bucket_count() の戻り値)×最大負荷率(max_load_factor() の戻り値)よりも小さかった場合である。 なお、条件が「よりも小さい」となっているが、最大負荷率の定義からすると「以下」の方が適切と思われる。reserve も参照。

    • position を引数にとる形式((2))の場合、本関数呼び出しで構築されるオブジェクト t と等価なキーの要素が既に存在する場合、position に応じて既存の要素と新規の要素が順序付けられると期待されるが、規格書にそのような規定は存在しない。 従って、そのような期待はすべきではない。emplace_hintも参照。

    • (5), (6) の場合、要素はコピーもムーブもされない。

    #include <iostream>
    #include <unordered_set>
    #include <forward_list>
    #include <iterator>
    #include <algorithm>
    #include <string>
    
    template <class C>
    void print(const std::string& label, const C& c)
    {
      std::cout << label << " : ";
      std::copy(c.cbegin(), c.cend(), std::ostream_iterator<typename C::value_type>(std::cout, " "));
      std::cout << std::endl;
    }
    
    int main()
    {
      // 一つの要素を挿入((1)の形式)
      {
        std::unordered_multiset<int> ums{ 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, };
    
        auto it1 = ums.insert(6); // 重複のないケース
        std::cout << *it1 << ' ';
        auto it2 = ums.insert(2); // 重複のあるケース
        std::cout << *it2 << std::endl;
        print("insert one element", ums);
      }
    
      // 一つの要素を挿入((2)の形式)
      {
        std::unordered_multiset<int> ums{ 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, };
    
        auto it1 = ums.insert(ums.cbegin(), 6); // 重複のないケース
        std::cout << *it1 << ' ';
        auto it2 = ums.insert(ums.cbegin(), 2); // 重複のあるケース
        std::cout << *it2 << std::endl;
        print("insert one element with hint", ums);
      }
    
      // 複数の要素を挿入((3)の形式)
      {
        std::unordered_multiset<int> ums{ 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, };
    
        std::forward_list<int> fl{ 5, 6, 0, 8, 7, };
        ums.insert(fl.cbegin(), fl.cend()); // forward_list の要素を全部
        print("insert range", ums);
      }
    
      // 複数の要素を挿入((4)の形式)
      {
        std::unordered_multiset<int> ums{ 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, };
    
        ums.insert({ 5, 6, 0, 8, 7, });
        print("insert initializer_list", ums);
      }
    }
    

    出力

    6 2
    insert one element : 6 5 5 4 4 3 3 2 2 2 1 1 0 0 
    6 2
    insert one element with hint : 6 5 5 4 4 3 3 2 2 2 1 1 0 0 
    insert range : 7 8 6 5 5 5 4 4 3 3 2 2 1 1 0 0 0 
    insert initializer_list : 7 8 6 5 5 5 4 4 3 3 2 2 1 1 0 0 0 
    

    注:unordered_multiset は非順序連想コンテナであるため、出力順序は無意味であることに注意

    バージョン

    言語

    • C++11

    処理系

    実装例

    (2)以降の形式は、(1)の形式を使って実装することができる。

    template <class Key, class Hash, class Pred, class Allocator>
    inline iterator unordered_multiset<Key, Hash, Pred, Allocator>::insert(const_iterator, const value_type& v)
    {
      return insert(v);
    }
    
    template <class Key, class Hash, class Pred, class Allocator>
    inline iterator unordered_multiset<Key, Hash, Pred, Allocator>::insert(const_iterator, value_type&& rv)
    {
      return insert(std::move(rv));
    }
    
    template <class Key, class Hash, class Pred, class Allocator>
    template <class InputIterator>
    inline void unordered_multiset<Key, Hash, Pred, Allocator>::insert(InputIterator first, InputIterator last);
    {
      for (; first != last; ++first)
        insert(*first);
    }
    
    template <class Key, class Hash, class Pred, class Allocator>
    inline void unordered_multiset<Key, Hash, Pred, Allocator>::insert(std::initializer_list<Key> il);
    {
      insert(il.begin(), il.end());
    }
    

    関連項目

    名前 説明
    emplace コンテナ内への要素の直接構築
    emplace_hint 挿入位置のヒントを使用したコンテナ内への要素の直接構築
    erase 要素の削除
    clear 全要素の削除
    swap 内容の交換
    bucket_count バケット数の取得
    load_factor 現在の負荷率(バケットあたりの要素数の平均)を取得
    max_load_factor 負荷率の最大値を取得、設定
    rehash 最小バケット数指定によるバケット数の調整
    reserve 最小要素数指定によるバケット数の調整

    参照