pair<iterator, bool>
  insert(const value_type& v); // (1) C++11
constexpr pair<iterator, bool>
  insert(const value_type& v); // (1) C++26

pair<iterator, bool>
  insert(value_type&& rv); // (2) C++11
constexpr pair<iterator, bool>
  insert(value_type&& rv); // (2) C++26

template <class K>
constexpr pair<iterator, bool>
  insert(K&& x); // (3) C++26

iterator
  insert(const_iterator position,
         const value_type& v); // (4) C++11
constexpr iterator
  insert(const_iterator position,
         const value_type& v); // (4) C++26

iterator
  insert(const_iterator position,
         value_type&& rv); // (5) C++11
constexpr iterator
  insert(const_iterator position,
         value_type&& rv); // (5) C++26

template <class K>
iterator
  insert(const_iterator hint,
         K&& x); // (6) C++11
template <class K>
constexpr iterator
  insert(const_iterator hint,
         K&& x); // (6) C++26

template <class InputIterator>
void
  insert(InputIterator first,
         InputIterator last); // (7) C++11
template <class InputIterator>
constexpr void
  insert(InputIterator first,
         InputIterator last); // (7) C++26

void
  insert(initializer_list<value_type> il); // (8) C++11
constexpr void
  insert(initializer_list<value_type> il); // (8) C++26

insert_return_type
  insert(node_type&& nh); // (9) C++17
constexpr insert_return_type
  insert(node_type&& nh); // (9) C++26

iterator
  insert(const_iterator hint,
         node_type&& nh); // (10) C++17
constexpr iterator
  insert(const_iterator hint,
         node_type&& nh); // (10) C++26

概要

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

• (1) : 新たな要素vをコピー挿入する
• (2) : 新たな要素rvをムーブ挿入する
• (3) : value_typeに変換可能なK型の新たな要素xを転送して挿入する
• (4) : 新たな要素vをコピー挿入する。hintパラメータに適切な挿入位置を指定すれば、高速に挿入できる
• (5) : 新たな要素rvをムーブ挿入する。hintパラメータに適切な挿入位置を指定すれば、高速に挿入できる
• (6) : value_typeに変換可能なK型の新たな要素xを転送して挿入する。hintパラメータに適切な挿入位置を指定すれば、高速に挿入できる
• (7) : イテレータ範囲[first, last)の要素を挿入する
• (8) : 初期化子リストilの要素を挿入する
• (9) : nhが空の場合、効果はない。それ以外の場合、nh.key()と等価のキーを持つ要素がコンテナにない場合に限り、nhが所有する要素を挿入する。
• (10) : nhが空の場合、効果はなく、(*this).end()を返す。それ以外の場合、nh.key()と等価のキーを持つ要素がコンテナにない場合に限り、nhが所有する要素を挿入する。 nh.key()と同等のキーの要素を指すイテレータを常に返す。要素は、hintの直前の位置のできるだけ近くに挿入される。

テンプレートパラメータ制約

• (3), (6) :
  • Hash::is_transparentおよびPred::is_transparentが妥当な式であること
  • is_convertible_v<K&&, const_iterator> == falseであること
  • is_convertible_v<K&&, iterator> == falseであること
  • value_typeがstd::forward<K>(x)によって直接構築可能であること

適格要件

• (1), (4) : value_type はコンテナに対してコピー挿入可能（CopyInsertable）でなければならない。
  • コンテナに対してコピー挿入可能とは、m をアロケータ型 allocator_type の左辺値、p を要素型 value_type へのポインタとすると、以下の式が適格（well-formed）であるということである。
    • std::allocator_traits<allocator_type>::construct(m, p, v);
• (2), (5) : value_type はコンテナに対してムーブ挿入可能（MoveInsertable）でなければならない。
  • コンテナに対してムーブ挿入可能とは、m をアロケータ型 allocator_type の左辺値、p を要素型 value_type へのポインタとすると、以下の式が適格（well-formed）であるということである。
    • std::allocator_traits<allocator_type>::construct(m, p, std::move(rv));
• (4), (5) : 引数 position は、コンテナの有効な読み取り専用イテレータでなければならない。
  • なお、標準では間接参照可能（dereferenceable）である必要があることになっているが、その必要はない（つまり、最終要素の次を指すイテレータでも良い）ものと思われる。
• (7) : 引数 first、および、lastは、入力イテレータの要件を満たし、かつ、イテレータ範囲 [first, last) が当該コンテナ以外を指す有効な範囲でなければならない。
  • また、このコンテナの要素型 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_type と std::iterator_traits<decltype(first)>::value_type が同一の型でなければならない）ことになっているが、実際にはその必要はなく、上記の直接構築可能の要件を満たすだけで良いものと思われる。
• (8) : value_type はコンテナに対してコピー挿入可能でなければならない。

事前条件

• (9), (10) : nh は空である、または、(*this).get_allocator() == nh.get_allocator()でなければならない。

効果

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

戻り値

• (1), (2), (3) : pair の bool 部分（second 部）は、要素が追加されたら true、追加されなかったら（既にあったら）false。
  • pair の iterator 部分（first 部）は、追加された要素（bool 部分が true の場合）、あるいは、既にあった要素（bool 部分が false の場合）を指すイテレータ。
• (4), (5), (6) : 新たな要素が追加された場合、その追加された要素を指すイテレータ。
  • 新たな要素が追加されなかった場合、既にあった要素を指すイテレータ。
• (7) : なし
• (8) : なし
• (9) : 戻り値としては、insert_return_typeを返す。insert_return_typeのイテレータ型メンバ変数position、bool型メンバ変数insertedに格納される値は(1), (2)のものと同じ情報である。nhが空の場合は、positionは終端イテレータである。node_type型メンバ変数nodeには、
  • 挿入された場合には、空のノードハンドル。
  • 挿入されなかった場合には、nhの値である。
• (10) : nhが空の場合、(*this).end()を返す。そうではない場合、nhと等価のキーの要素を指すイテレータを常に返す。

例外

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

計算量

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

備考

• これらの関数が呼ばれた後も、当該コンテナ内の要素を指す参照は無効にはならない。
  • なお、規格書に明確な記載は無いが、当該コンテナ内の要素を指すポインタも無効にはならない。
• これらの関数が呼ばれた後も、呼び出しの前後でこのコンテナのバケット数（bucket_count() の戻り値）が変わらなかった場合には当該コンテナを指すイテレータは無効にはならない。
  • それ以外の場合は、当該コンテナを指すイテレータは無効になる可能性がある。
  • コンテナのバケット数が変わらない場合とは、以下のいずれかである：
    • 追加しようとした要素と等価なキーの要素が全て既にコンテナに存在したため、要素が追加されなかった。
    • 要素追加後の要素数が、要素追加前のバケット数（bucket_count() の戻り値）×最大負荷率（max_load_factor() の戻り値）よりも小さかった。
  • なお、後者の条件は「よりも小さい」となっているが、最大負荷率の定義からすると「以下」の方が適切と思われる。reserve も参照。
• (9), (10) の場合、要素はコピーもムーブもされない。
• (3), (6) :
  • is_transparentは、HashとPredの両方がメンバ型として持つ必要がある。Predにはis_transparentを定義するstd::equal_to<>が使えるが、Hashには標準ライブラリに該当するものがないため、利用者が定義する必要がある。詳細はstd::hashクラスのページを参照。
  • これらのオーバーロードは、unordered_set<string>のようなコンテナに対し、検索操作で文字列リテラルを渡した際に、キー型の一時オブジェクトが生成されるコストを減らすためにある。

例

#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.begin(), c.end(), std::ostream_iterator<typename C::value_type>(std::cout, " "));
  std::cout << std::endl;
}

int main()
{
  std::cout << std::boolalpha;

  // 一つの要素を挿入（(1), (2), (3)の形式）
  {
    std::unordered_set<int> us{ 0, 1, 2, 3, 4, 5, };

    auto p1 = us.insert(6); // 追加されるケース
    std::cout << p1.second << ' ' << *p1.first << ' ';
    auto p2 = us.insert(2); // 追加されないケース
    std::cout << p2.second << ' ' << *p2.first << std::endl;
    ::print("insert one element", us);
  }

  // 一つの要素を挿入（(4), (5), (6)の形式）
  {
    std::unordered_set<int> us{ 0, 1, 2, 3, 4, 5, };

    auto it1 = us.insert(us.begin(), 6); // 追加されるケース
    std::cout << *it1 << ' ';
    auto it2 = us.insert(us.begin(), 2); // 追加されないケース
    std::cout << *it2 << std::endl;
    ::print("insert one element with hint", us);
  }

  // 複数の要素を挿入（(7)の形式）
  {
    std::unordered_set<int> us{ 0, 1, 2, 3, 4, 5, };

    std::forward_list<int> fl{ 5, 6, 0, 8, 7, };
    us.insert(fl.cbegin(), fl.cend()); // forward_list の要素を全部
    ::print("insert range", us);
  }

  // 複数の要素を挿入（(8)の形式）
  {
    std::unordered_set<int> us{ 0, 1, 2, 3, 4, 5, };

    us.insert({ 5, 6, 0, 8, 7, });
    ::print("insert initializer_list", us);
  }
}

出力例

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

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

バージョン

言語

• C++11

処理系

• Clang: 3.1 ✅
• GCC: 4.7.0 ✅
• Visual C++: ?

実装例

(4), (5), (7), (8)の形式は、(1), (2)の形式を使って実装することができる。

template <class Key, class Hash, class Pred, class Allocator>
inline iterator unordered_set<Key, Hash, Pred, Allocator>::insert(const_iterator, const value_type& v)
{
  return insert(v).first;
}

template <class Key, class Hash, class Pred, class Allocator>
inline iterator unordered_set<Key, Hash, Pred, Allocator>::insert(const_iterator, value_type&& rv)
{
  return insert(std::move(rv)).first;
}

template <class Key, class Hash, class Pred, class Allocator>
template <class InputIterator>
inline void unordered_set<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_set<Key, Hash, Pred, Allocator>::insert(initializer_list<Key> il);
{
  insert(il.begin(), il.end());
}

関連項目

参照

• N2350 Container insert/erase and iterator constness (Revision 1)
• N2679 Initializer Lists for Standard Containers(Revision 1)
  • (8)の経緯となる提案文書
• Splicing Maps and Sets(Revision 5)
  • (9), (10)経緯となる提案文書
• How useful is the hint passed to the std::unordered_... collections? - The Old New Thing
• P2363R5: Extending associative containers with the remaining heterogeneous overloads
  • C++26でtemplate <class K>のバージョンが追加された
• P3372R3 constexpr containers and adaptors
• LWG Issue 676. Moving the unordered containers
  • C++11で、value_type&&を受け取るオーバーロードが追加された。他のコンテナには追加されていたムーブ対応が漏れていたため