std::unordered_set<Key,Hash,KeyEqual,Allocator>::insert

 

C++

コンパイラサポート

フリースタンディングとホスト

言語

標準ライブラリ

標準ライブラリヘッダー

名前付き要件

機能テストマクロ (C++20)

言語サポートライブラリ

コンセプトライブラリ (C++20)

診断ライブラリ

メモリ管理ライブラリ

メタプログラミングライブラリ (C++11)

汎用ユーティリティライブラリ

コンテナライブラリ

イテレータライブラリ

Rangesライブラリ (C++20)

アルゴリズムライブラリ

文字列ライブラリ

テキスト処理ライブラリ

数値ライブラリ

日付と時刻ライブラリ

入出力ライブラリ

ファイルシステムライブラリ (C++17)

並行サポートライブラリ (C++11)

実行制御ライブラリ (C++26)

Technical specifications (技術仕様)

シンボルインデックス

外部ライブラリ

 

コンテナライブラリ

シーケンス

array (C++11)

vector

vector<bool>

inplace_vector (C++26)

hive (C++26)

deque

forward_list (C++11)

list

連想

set

multiset

map

multimap

非順序連想

unordered_set (C++11)

unordered_multiset (C++11)

unordered_map (C++11)

unordered_multimap (C++11)

アダプタ

stack

queue

priority_queue

flat_set (C++23)

flat_multiset (C++23)

flat_map (C++23)

flat_multimap (C++23)

表示

span (C++20)

mdspan (C++23)

表

イテレータの無効化

メンバ関数テーブル

非メンバ関数テーブル

 

std::unordered_set

メンバ型
メンバ関数
unordered_set::unordered_set unordered_set::~unordered_set unordered_set::operator= unordered_set::get_allocator イテレータ unordered_set::beginunordered_set::cbegin unordered_set::endunordered_set::cend 容量 unordered_set::size unordered_set::max_size unordered_set::empty 変更 unordered_set::clear unordered_set::erase unordered_set::swap unordered_set::extract (C++17) unordered_set::merge (C++17) unordered_set::insert unordered_set::insert_range (C++23)   unordered_set::emplace unordered_set::emplace_hint	検索 unordered_set::count unordered_set::find unordered_set::contains (C++20) unordered_set::equal_range バケットインターフェース unordered_set::begin(size_type)unordered_set::cbegin(size_type) unordered_set::end(size_type)unordered_set::cend(size_type) unordered_set::bucket_count unordered_set::max_bucket_count unordered_set::bucket_size unordered_set::bucket ハッシュポリシー unordered_set::load_factor unordered_set::max_load_factor unordered_set::rehash unordered_set::reserve 監視 unordered_set::hash_function unordered_set::key_eq
非メンバ関数
operator==operator!= (C++20まで)	std::swap(std::unordered_set) erase_if(std::unordered_set) (C++20)
推論補助 (C++17)

 

std::pair<iterator,bool> insert( const value_type& value );	(1)	(C++11以降)
std::pair<iterator,bool> insert( value_type&& value );	(2)	(C++11以降)
iterator insert( const_iterator hint, const value_type& value );	(3)	(C++11以降)
iterator insert( const_iterator hint, value_type&& value );	(4)	(C++11以降)
template< class InputIt > void insert( InputIt first, InputIt last );	(5)	(C++11以降)
void insert( std::initializer_list<value_type> ilist );	(6)	(C++11以降)
insert_return_type insert( node_type&& nh );	(7)	(C++17以降)
iterator insert( const_iterator hint, node_type&& nh );	(8)	(C++17以降)
template< class K > std::pair<iterator, bool> insert( K&& obj );	(9)	(C++23から)
template< class K > iterator insert( const_iterator hint, K&& obj );	(10)	(C++23から)

コンテナに要素を挿入します。コンテナが既に同等のキーを持つ要素を格納している場合は、挿入は行われません。

1,2) value を挿入します。

3,4) value を挿入します。 挿入位置の探索を開始する非拘束のヒントとして hint を使用します。

5) 範囲 [first, last) から要素を挿入します。 範囲内の複数の要素のキーが等価である場合、どの要素が挿入されるかは未規定です（LWG2844 参照）。

6) 初期化子リスト ilist から要素を挿入します。 範囲内の複数の要素のキーが等価である場合、どの要素が挿入されるかは未規定です（LWG2844 参照）。

7) nh が空の ノードハンドル の場合、何も行いません。それ以外の場合、コンテナが nh.key() と等価なキーを持つ要素をまだ含んでいない場合、nh が所有する要素をコンテナに挿入します。 nh が空でなく、かつ get_allocator() != nh.get_allocator() である場合、動作は未定義です。

8) nh が空の ノードハンドル の場合、何も行わず、末尾イテレータを返します。それ以外の場合、コンテナが nh.key() と等価なキーを持つ要素をまだ含んでいない場合、nh が所有する要素をコンテナに挿入し、nh.key() と等価なキーを持つ要素を指すイテレータ（挿入が成功したか失敗したかに関わらず）を返します。挿入が成功した場合、nh はムーブされます。それ以外の場合、nh は要素の所有権を保持します。hint は、探索を開始する非拘束のヒントとして使用されます。 nh が空でなく、かつ get_allocator() != nh.get_allocator() である場合、動作は未定義です。

9) *this が既に obj と透過的に比較して等価な要素を含んでいる場合、何も行いません。それ以外の場合、value_type のオブジェクト u を std::forward<K>(obj) を使用して構築し、その後 u を *this に挿入します。 equal_range(u) != hash_function()(obj) || contains(u) が true の場合、動作は未定義です。value_type は、std::forward<K>(obj) から unordered_set へ EmplaceConstructible である必要があります。 このオーバーロードは、Hash::is_transparent および KeyEqual::is_transparent が有効で、それぞれが型を指している場合にのみオーバーロード解決に参加します。これは、そのような Hash が K および Key の両方の型で呼び出し可能であり、KeyEqual が透過的であると仮定しています。これにより、Key のインスタンスを構築することなくこの関数を呼び出すことができます。

10) *this が既に obj と透過的に比較して等価な要素を含んでいる場合、何も行いません。

それ以外の場合、value_type のオブジェクト u を std::forward<K>(obj) を使用して構築し、その後 u を *this に挿入します。Template:hint は、探索を開始する非拘束のヒントとして使用されます。 equal_range(u) != hash_function()(obj) || contains(u) が true の場合、動作は未定義です。value_type は、std::forward<K>(obj) から unordered_set へ EmplaceConstructible である必要があります。このオーバーロードは、

• std::is_convertible_v<K&&, const_iterator> および std::is_convertible_v<K&&, iterator> が両方とも false であり、
• Hash::is_transparent および KeyEqual::is_transparent が有効で、それぞれが型を指している場合にのみ参加します。

これにより、Key のインスタンスを構築することなくこの関数を呼び出すことができます。

操作後、要素の新しい数が max_load_factor() * bucket_count() より大きい場合、再ハッシュが行われます。
挿入による再ハッシュが発生した場合、すべてのイテレータは無効になります。それ以外の場合（再ハッシュが発生しない場合）、イテレータは無効になりません。挿入が成功した場合、ノードハンドル内で保持されている間、その要素へのポインタと参照は無効になります。また、要素がノードハンドルから抽出される前に取得したその要素へのポインタと参照は有効になります。(C++17 以降)

パラメータ

hint	-	挿入するコンテンツのヒントとして使用されるイテレータ
value	-	挿入する要素の値
first, last	-	挿入する要素のソース 範囲 を定義するイテレータのペア
ilist	-	挿入する値の初期化子リスト
nh	-	互換性のある node handle
obj	-	キーと透過的に比較できる任意の型の値
型要件
- InputIt は LegacyInputIterator の要件を満たす必要があります。

戻り値

1,2) 挿入された要素（または挿入を妨げた要素）へのイテレータと、挿入が行われたかどうかを示す bool 値のペア。挿入が行われた場合は true、それ以外の場合は false となります。

3,4) 挿入された要素、または挿入を妨げた要素へのイテレータ。

5,6) （なし）

7) insert_return_type のオブジェクトで、メンバは以下のように初期化されます。

• nh が空の場合、inserted は false、position は end()、node は空になります。
• それ以外の場合で、挿入が行われた場合、inserted は true、position は挿入された要素を指し、node は空になります。
• 挿入が失敗した場合、inserted は false、node は nh の以前の値になり、position は nh.key() と同等のキーを持つ要素を指します。

8) nh が空だった場合は末尾イテレータ、挿入が行われた場合は挿入された要素を指すイテレータ、挿入に失敗した場合は nh.key() と等価なキーを持つ要素を指すイテレータ。

9) 挿入された要素（または挿入を妨げた要素）を指すイテレータと、挿入が行われた場合にのみ bool 値が true に設定されるペア。

10) 挿入された要素、または挿入を妨げた要素を指すイテレータ。

例外

1-4) どの操作で例外がスローされた場合でも、挿入は効果がありません。

計算量

1-4) 平均ケース: O(1)、最悪ケース: O(size())。

5,6) 平均ケース: 挿入する要素数 N に対し O(N)。最悪ケース: O(N * size() + N)。

7-10) 平均ケース: O(1)、最悪ケース: O(size())。

注釈

ヒント付き挿入 (3,4) は、std::vector::insert のようなシーケンシャルコンテナのポジショナル挿入とシグネチャ互換性を持たせるために、ブール値を返しません。これにより、std::inserter のようなジェネリックインサータを作成できます。ヒント付き挿入の成功を確認する一つの方法は、挿入の前後に size() を比較することです。

機能テストマクロ	値	規格	機能
__cpp_lib_associative_heterogeneous_insertion	202311L	(C++26)	順序付きおよび順序なし連想コンテナの他のメンバ関数の異種オーバーロード。(9,10)

例

このコードを実行

#include <array>
#include <iostream>
#include <unordered_set>
 
std::ostream& operator<<(std::ostream& os, std::unordered_set<int> const& s)
{
    for (os << '[' << s.size() << "] { "; int i : s)
        os << i << ' ';
    return os << "}\n";
}
 
int main ()
{
    std::unordered_set<int> nums{2, 3, 4};
 
    std::cout << "1) Initially: " << nums << std::boolalpha;
    auto p = nums.insert(1); // insert element, overload (1)
    std::cout << "2) '1' was inserted: " << p.second << '\n';
    std::cout << "3) After insertion: " << nums;
 
    nums.insert(p.first, 0); // insert with hint, overload (3)
    std::cout << "4) After insertion: " << nums;
 
    std::array<int, 4> a = {10, 11, 12, 13};
    nums.insert(a.begin(), a.end()); // insert range, overload (5)
    std::cout << "5) After insertion: " << nums;
 
    nums.insert({20, 21, 22, 23}); // insert initializer_list, (6)
    std::cout << "6) After insertion: " << nums;
 
    std::unordered_set<int> other_nums = {42, 43};
    auto node = other_nums.extract(other_nums.find(42));
    nums.insert(std::move(node)); // insert node, overload (7)
    std::cout << "7) After insertion: " << nums;
 
    node = other_nums.extract(other_nums.find(43));
    nums.insert(nums.begin(), std::move(node)); // insert node with hint, (8)
    std::cout << "8) After insertion: " << nums;
}

実行結果の例

1) Initially: [3] { 4 3 2 }
2) '1' was inserted: true
3) After insertion: [4] { 1 2 3 4 }
4) After insertion: [5] { 0 1 2 3 4 }
5) After insertion: [9] { 13 12 11 10 4 3 2 1 0 }
6) After insertion: [13] { 23 22 13 12 11 10 21 4 20 3 2 1 0 }
7) After insertion: [14] { 42 23 22 13 12 11 10 21 4 20 3 2 1 0 }
8) After insertion: [15] { 43 42 23 22 13 12 11 10 21 4 20 3 2 1 0 }

関連項目

emplace	要素を直接構築する (公開メンバ関数)
emplace_hint	ヒントを使用して要素を直接構築する (公開メンバ関数)
inserter	引数から推論された型の std::insert_iterator を作成する (関数テンプレート)