std::flat_map::insert(C++23)

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

iterator insert(const_iterator position,
                const value_type& x);             // (3) C++23
iterator insert(const_iterator position,
                value_type&& x);                  // (4) C++23

template<class P>
pair<iterator, bool> insert(P&& x);               // (5) C++23

template<class P>
iterator insert(const_iterator position,
                P&&);                             // (6) C++23

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

template<class InputIterator>
void insert(sorted_unique_t,
            InputIterator first,
            InputIterator last);                  // (8) C++23

void insert(initializer_list<value_type> il);     // (9) C++23

void insert(sorted_unique_t s,
            initializer_list<value_type> il);     // (10) C++23

概要

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

これは、挿入された要素の数だけコンテナの size() を増やす。

flat_map コンテナは重複したキーを持つ要素を許さないため、挿入操作はそれぞれの要素が他のコンテナ内の既存要素と同じキーかどうかをチェックする。もし同じであれば要素は挿入されず、戻り値を持つ関数の場合はそれへのイテレータなどを返す。

重複した値を許す、類似したコンテナについては flat_multimap を参照。

内部的に flat_map コンテナは、コンストラクト時に指定された比較オブジェクトによって要素を下位から上位へとソートして保持する。

この操作は、適切な引数 position を提供することで効率を飛躍的に改善することができる。

• (1) : 単一要素を挿入する
• (2) : 単一要素の一時オブジェクトを挿入する
• (3) : 指定された位置に、単一要素を挿入する
• (4) : 指定された位置に、単一要素の一時オブジェクトを挿入する
• (5) : 単一要素として要素型value_typeのコンストラクタ引数を受け取って挿入する
• (6) : 指定された位置に、要素型value_typeのコンストラクタ引数を受け取って挿入する
• (7) : イテレータ範囲[first, last)を挿入する
• (8) : ソート済みかつ重複要素のないイテレータ範囲[first, last)を挿入する
• (9) : 初期化子リストを挿入する
• (10) : ソート済みかつ重複要素のない初期化子リストを挿入する

要件

• (5), (6) : is_constructible_v<pair<key_type, mapped_type>, P>がtrueであること

効果

• (1) :
  

  return emplace(x);
  

• (2) :
  

  return emplace(std::move(x));
  

• (3) :
  

  return emplace_hint(position, x);
  

• (4) :
  

  return emplace_hint(position, std::move(x));
  

• (5) : 以下と等価：
  

  return emplace(std::forward<P>(x));
  

• (6) : 以下と等価：
  

  return emplace_hint(position, std::forward<P>(x));.
  

• (7) : メンバ変数として保持しているコンテナcに、以下のように挿入する：
  

  for (; first != last; ++first) {
      value_type value = *first;
      c.keys.insert(c.keys.end(), std::move(value.first));
      c.values.insert(c.values.end(), std::move(value.second));
  }
  

  • 次に、新しく挿入された要素の範囲をvalue_comp()を基準にソートする
  • 次に、ソートされた結果の範囲と、既存の要素のソートされた範囲をひとつのソートされた範囲にマージする
  • 最後に、重複する要素を以下のように削除する：

  auto zv = ranges::zip_view(c.keys, c.values);
  auto it = ranges::unique(zv, key_equiv(compare)).begin();
  auto dist = distance(zv.begin(), it);
  c.keys.erase(c.keys.begin() + dist, c.keys.end());
  c.values.erase(c.values.begin() + dist, c.values.end());
  

• (8) : メンバ変数として保持しているコンテナcに、以下のように挿入する：
  

  for (; first != last; ++first) {
      value_type value = *first;
      c.keys.insert(c.keys.end(), std::move(value.first));
      c.values.insert(c.values.end(), std::move(value.second));
  }
  

  • 次に、ソートされた結果の範囲と、既存の要素のソートされた範囲をひとつのソートされた範囲にマージする
  • 最後に、重複する要素を以下のように削除する：

  auto zv = ranges::zip_view(c.keys, c.values);
  auto it = ranges::unique(zv, key_equiv(compare)).begin();
  auto dist = distance(zv.begin(), it);
  c.keys.erase(c.keys.begin() + dist, c.keys.end());
  c.values.erase(c.values.begin() + dist, c.values.end());
  

• (9) :
  

  insert(il.begin(), il.end());
  

• (10) :
  

  insert(s, il.begin(), il.end());
  

戻り値

• (1), (2), (5) : 戻り値としては、イテレータとbool値の組を返す。
  • 挿入された場合には、first に挿入された要素へのイテレータ、 second に true が設定される。
  • 挿入されなかった場合には、 first に x と等価のキーを持つ要素へのイテレータ、 second に false が設定される。
• (3), (4), (6) :
  • 挿入された場合には、新しく挿入された要素を指すイテレータを返す。
  • 挿入されなかった場合には、xのキーと等価のキーを持つ要素へのイテレータを返す。
• (7), (8), (9), (10) : なし

計算量

• (7) : Nをこの操作の前のsize()、Mをdistance(first, last)として、N + MlogM
• (8) : Nをこの操作のあとのsize()として、Nに対して線形

備考

• (7), (8) : この操作はインプレース・マージを行うため、追加のメモリ確保を行う可能性がある

例

#include <iostream>
#include <flat_map>

int main()
{
  std::flat_map<int, char> fm;

  // 単一要素を挿入する
  fm.insert(std::pair{3, 'a'});
  fm.insert({3, 'a'});

  std::flat_map<int, char> fm2 = {
    {5, 'd'},
    {15, 'e'}
  };

  // シーケンスを挿入する
  fm.insert(fm2.begin(), fm2.end());

  // 挿入するシーケンスがソート済みかつ重複要素がないことがわかっている場合、
  // 以下のように指定した方が高速になる
  fm.insert(std::sorted_unique, fm2.begin(), fm2.end());

  for (const auto& [key, value] : fm) {
    std::cout << key << " : " << value << std::endl;
  }
}

出力

3 : a
5 : d
15 : e

バージョン

処理系

• Clang: ??
• GCC: ??
• Visual C++: ??

関連項目