iterator insert(const value_type& v);
iterator insert(value_type&& rv); // (1)
iterator insert(const_iterator position, const value_type& v);
iterator insert(const_iterator position, value_type&& rv); // (2)
template <class InputIterator>
void insert(InputIterator first, InputIterator last); // (3)
void insert(initializer_list<value_type> il); // (4)
iterator insert(node_type&& nh); // (5) C++17
iterator insert(const_iterator hint, node_type&& nh); // (6) C++17
概要
コンテナに要素を追加する。
要件
-
v
を引数にとる形式((1)、(2)の上側)では、value_type
はコンテナに対してコピー挿入可能(CopyInsertable)でなければならない。
コンテナに対してコピー挿入可能とは、m
をアロケータ型allocator_type
の左辺値、p
を要素型value_type
へのポインタとすると、以下の式が適格(well-formed)であるということである。std::allocator_traits<allocator_type>::construct(m, p, v);
-
rv
を引数にとる形式((1)、(2)の下側)では、value_type
はコンテナに対してムーブ挿入可能(MoveInsertable)でなければならない。
コンテナに対してムーブ挿入可能とは、m
をアロケータ型allocator_type
の左辺値、p
を要素型value_type
へのポインタとすると、以下の式が適格(well-formed)であるということである。std::allocator_traits<allocator_type>::construct(m, p, std::move(rv));
-
引数
position
は、コンテナの有効な読み取り専用イテレータでなければならない。
なお、標準では間接参照可能(dereferenceable)である必要があることになっているが、その必要はない(つまり、最終要素の次を指すイテレータでも良い)ものと思われる。 -
引数
first
、および、last
は、入力イテレータの要件を満たし、かつ、イテレータ範囲[first, last)
が当該コンテナ以外を指す有効な範囲でなければならない。
また、引数first
、および、last
を引数にとる形式((3))では、このコンテナの要素型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
が同一の型でなければならない)ことになっているが、実際にはその必要はなく、上記の直接構築可能の要件を満たすだけで良いものと思われる。 -
(4)の形式では、
value_type
はコンテナに対してコピー挿入可能でなければならない。 -
(5), (6)の形式では、
nh
は空である、または、(*this).get_allocator() == nh.get_allocator()
でなければならない。
効果
- (1) : 引数
v
、あるいはrv
で指定した値の要素を追加する。 - (2) : 引数
v
、あるいはrv
で指定した値の要素を追加する。
引数position
は、要素の挿入位置を探し始める場所のヒントとして使用されるが、実装によって無視されるかもしれない。 - (3) : イテレータ範囲
[first, last)
のすべての要素t
に対して、(1)の形式のinsert(t)
を呼び出した場合と等価である。 - (4) : (3)の形式を
insert(il.begin(), il.end())
として呼び出した場合と等価である。 - (5) :
nh
が空の場合、効果はない。そうでなければ、nh
が所有する要素を挿入し、新しく挿入された要素を指すイテレータを返す。nh.key()
と等価なキーを持つ要素を含む範囲がコンテナ内に存在する場合、要素はその範囲の終端に挿入される。 - (6) :
nh
が空の場合、効果はなく、(*this).end()
を返す。そうでなければ、nh
によって所有されている要素をコンテナに挿入し、nh.key()
と等価なキーを持つ要素を指すイテレータを返す。nh.key()
と等しいキーを持つ要素を含む範囲がコンテナ内に存在する場合、要素はその範囲の終端に挿入される。要素は、hint
の直前の位置のできるだけ近くに挿入される。
戻り値
- (1) : 追加された要素を指すイテレータ。
- (2) : 追加された要素を指すイテレータ。
- (3) : なし
- (4) : なし
- (5), (6) :
nh
が空の場合は終端イテレータ、そうでなければ挿入された要素を指すイテレータ。
例外
単一要素の形式((1)と(2))では、ハッシュ関数以外から例外が投げられた場合には、挿入はされない。
計算量
- (1) : 平均的なケースでは定数(O(1))だが、最悪のケースではコンテナの要素数
size()
に比例(O(N))。 - (2) : 平均的なケースでは定数(O(1))だが、最悪のケースではコンテナの要素数
size()
に比例(O(N))。 - (3) : 平均的なケースでは引数の範囲の要素数
std::distance(first, last)
に比例(O(N))するが、最悪のケースでは引数の範囲の要素数std::distance(first, last)
とコンテナの要素数size()
に 1 加えたものの積に比例(O(std::distance(first, last) * (size() + 1)
))。 - (4) : (3)の形式を
insert(il.begin(), il.end())
として呼び出した場合と等価。 - (5), (6) : 平均的なケースでは
O(1)
、最悪のケースではO(size())
。
備考
-
これらの関数が呼ばれた後も、当該コンテナ内の要素を指す参照は無効にはならない。 なお、規格書に明確な記載は無いが、当該コンテナ内の要素を指すポインタも無効にはならない。
-
これらの関数が呼ばれた後も、呼び出しの前後でこのコンテナのバケット数(
bucket_count()
の戻り値)が変わらなかった場合には当該コンテナを指すイテレータは無効にはならない。
それ以外の場合は、当該コンテナを指すイテレータは無効になる可能性がある。
コンテナのバケット数が変わらない場合とは、要素追加後の要素数が、要素追加前のバケット数(bucket_count()
の戻り値)×最大負荷率(max_load_factor()
の戻り値)よりも小さかった場合である。 なお、条件が「よりも小さい」となっているが、最大負荷率の定義からすると「以下」の方が適切と思われる。reserve
も参照。 -
position
を引数にとる形式((2))の場合、本関数呼び出しで構築されるオブジェクトt
と等価なキーの要素が既に存在する場合、position
に応じて既存の要素と新規の要素が順序付けられると期待されるが、規格書にそのような規定は存在しない。 従って、そのような期待はすべきではない。emplace_hint
も参照。 -
(5), (6) の場合、要素はコピーもムーブもされない。
例
#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.cbegin(), c.cend(), std::ostream_iterator<typename C::value_type>(std::cout, " "));
std::cout << std::endl;
}
int main()
{
// 一つの要素を挿入((1)の形式)
{
std::unordered_multiset<int> ums{ 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, };
auto it1 = ums.insert(6); // 重複のないケース
std::cout << *it1 << ' ';
auto it2 = ums.insert(2); // 重複のあるケース
std::cout << *it2 << std::endl;
print("insert one element", ums);
}
// 一つの要素を挿入((2)の形式)
{
std::unordered_multiset<int> ums{ 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, };
auto it1 = ums.insert(ums.cbegin(), 6); // 重複のないケース
std::cout << *it1 << ' ';
auto it2 = ums.insert(ums.cbegin(), 2); // 重複のあるケース
std::cout << *it2 << std::endl;
print("insert one element with hint", ums);
}
// 複数の要素を挿入((3)の形式)
{
std::unordered_multiset<int> ums{ 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, };
std::forward_list<int> fl{ 5, 6, 0, 8, 7, };
ums.insert(fl.cbegin(), fl.cend()); // forward_list の要素を全部
print("insert range", ums);
}
// 複数の要素を挿入((4)の形式)
{
std::unordered_multiset<int> ums{ 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, };
ums.insert({ 5, 6, 0, 8, 7, });
print("insert initializer_list", ums);
}
}
#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.cbegin(), c.cend(), std::ostream_iterator<typename C::value_type>(std::cout, " "));
std::cout << std::endl;
}
int main()
{
// 一つの要素を挿入((1)の形式)
出力
6 2
insert one element : 6 5 5 4 4 3 3 2 2 2 1 1 0 0
6 2
insert one element with hint : 6 5 5 4 4 3 3 2 2 2 1 1 0 0
insert range : 7 8 6 5 5 5 4 4 3 3 2 2 1 1 0 0 0
insert initializer_list : 7 8 6 5 5 5 4 4 3 3 2 2 1 1 0 0 0
注:unordered_multiset
は非順序連想コンテナであるため、出力順序は無意味であることに注意
バージョン
言語
- C++11
処理系
- Clang: 3.1 ✅
- GCC: 4.7.0 ✅
- ICC: ?
- Visual C++: ?
実装例
(2)以降の形式は、(1)の形式を使って実装することができる。
template <class Key, class Hash, class Pred, class Allocator>
inline iterator unordered_multiset<Key, Hash, Pred, Allocator>::insert(const_iterator, const value_type& v)
{
return insert(v);
}
template <class Key, class Hash, class Pred, class Allocator>
inline iterator unordered_multiset<Key, Hash, Pred, Allocator>::insert(const_iterator, value_type&& rv)
{
return insert(std::move(rv));
}
template <class Key, class Hash, class Pred, class Allocator>
template <class InputIterator>
inline void unordered_multiset<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_multiset<Key, Hash, Pred, Allocator>::insert(std::initializer_list<Key> il);
{
insert(il.begin(), il.end());
}
関連項目
名前 | 説明 |
---|---|
emplace |
コンテナ内への要素の直接構築 |
emplace_hint |
挿入位置のヒントを使用したコンテナ内への要素の直接構築 |
erase |
要素の削除 |
clear |
全要素の削除 |
swap |
内容の交換 |
bucket_count |
バケット数の取得 |
load_factor |
現在の負荷率(バケットあたりの要素数の平均)を取得 |
max_load_factor |
負荷率の最大値を取得、設定 |
rehash |
最小バケット数指定によるバケット数の調整 |
reserve |
最小要素数指定によるバケット数の調整 |
参照
- N2679 Initializer Lists for Standard Containers(Revision 1)
- (4)の経緯となる提案文書
- LWG Issue 518. Are
insert
anderase
stable forunordered_multiset
andunordered_multimap
?- 安定性の保証が規定された経緯のレポート
- Splicing Maps and Sets(Revision 5)
- (5), (6)経緯となる提案文書
- How useful is the hint passed to the std::unordered_... collections? - The Old New Thing