5. insert

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

履歴 編集

function
<set>

std::set::insert

pair<iterator,bool> insert(const value_type& x);           // (1) C++03
pair<iterator,bool> insert(value_type&& y);                // (2) C++11

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

iterator insert(iterator hint, const value_type& x);       // (4) C++03
iterator insert(const_iterator hint, const value_type& x); // (4) C++11

iterator insert(const_iterator hint, value_type&& y);      // (5) C++11

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

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

void insert(initializer_list<value_type> init);            // (8) C++03

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

概要

新しく一つの要素(引数 x, yを使う)または要素のシーケンス(入力イテレータまたは initializer_list を使う)を挿入することにより、 set コンテナを拡張する。

set コンテナは重複した値を許さないため、挿入操作はそれぞれの要素が他のコンテナ内の既存要素と同じ値かどうかをチェックし、同じ要素がすでにあれば挿入されない。multisetの場合には、同じ値の要素でも挿入される。

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

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

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

戻り値

  • (1), (2), (3) : first に新しく挿入された要素またはすでに set に格納されていた同じ値の要素を指すイテレータを設定する。second には、要素が挿入されたときに true を、同じ値の要素が存在したときに false を設定する。
  • (4), (5), (6) : 新しく挿入された要素またはすでに set に格納されていた同じ値の要素を指すイテレータを返す。
  • (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), (3) : 対数時間
  • (4), (5), (6) : 一般に対数時間だが、x または y が hint が指す要素の直前に挿入された場合は償却定数時間
  • (7), (8) : 一般に N log(size + N)
    • ※ ここで N は first と last の間の距離であり size は挿入前のコンテナの size()
  • (9) : 対数時間
  • (10) : 一般に対数時間だが、指定された新たな要素が hint が指す要素の直前に挿入された場合は償却定数時間。

備考

  • これらの関数が呼ばれた後も、当該コンテナ内の要素を指す参照やイテレータは無効にはならない。
    なお、規格書に明確な記載は無いが、当該コンテナ内の要素を指すポインタも無効にはならない。
  • 内部的に set コンテナは、コンストラクト時に指定された比較オブジェクトによって要素を下位から上位へとソートして保持する。 (9), (10) の場合、要素はコピーもムーブもされない。
  • (3), (6) :
    • is_transparentは、標準ライブラリのstd::less、std::greaterといった関数オブジェクトの、voidに対する特殊化で定義される。それ以外のテンプレートパラメータでis_transparentが定義されないのは、互換性のためである。
    • これらのオーバーロードは、map<string, int>のようなコンテナに対し、検索操作で文字列リテラルを渡した際に、キー型の一時オブジェクトが生成されるコストを減らすためにある。

例

#include <iostream>
#include <set>

int main ()
{
  std::set<int> c1;
  std::set<int> c2;

  c1.insert(10);
  c1.insert(20);
  c1.insert(30);

  std::cout << c1.size() << std::endl;

  c2.insert(c1.begin(), c1.end());
  c2.insert(40);

  std::cout << c2.size() << std::endl;
}

出力

3
4

関連項目

名前 説明
erase 要素を削除する
find 指定したキーで要素を探す

参照