最終更新日時(UTC): 2026年02月17日 14時22分33秒
Akira Takahashi が更新

履歴 編集

function
<flat_map>

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

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

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

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

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

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

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

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

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

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

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

## 概要

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

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

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

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

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

- (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) : なし

## 計算量

- (1)~(6) : コンテナサイズ（`size()`）に対して線形
- (7) : Nをこの操作の前の`size()`、Mを`distance(first, last)`として、N + MlogM
- (8) : Nをこの操作のあとの`size()`として、Nに対して線形
- (9) : Nをこの操作の前の`size()`、Mを`il.size()`として、N + MlogM
- (10) : 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++: ??

## 関連項目

名前 | 説明
--- | ---
`flat_map::insert_or_assign` | 要素を挿入、あるいは代入する
`flat_map::insert_range` | Rangeを挿入する
`flat_map::emplace` | 要素を直接構築する
`flat_map::emplace_hint` | ヒントを使って要素を直接構築する
`flat_map::try_emplace` | キーが存在しない場合のみ要素を直接構築する

## 参照

- P3372R3 constexpr containers and adaptors