namespace std {
template <class Key,
class Hash = std::hash<Key>,
class Pred = std::equal_to<Key>,
class Allocator = std::allocator<Key> >
class unordered_set;
namespace pmr {
template <class Key,
class Hash = hash<Key>,
class Pred = equal_to<Key>>
using unordered_set = std::unordered_set<Key, Hash, Pred,
polymorphic_allocator<Key>>; // C++17から
}
}
概要
unordered_set
は、同一キーの要素を複数格納できず、格納順が規定されていないコンテナである。
一般的には hash set
と呼ばれるコンテナであるが、標準への採用が遅かったことから、既に存在する各種コンテナとの名前の衝突を避けるため、unordered_set
と名付けられた。
unordered_set
の特徴は以下の通りである。
- 連想
標準の配列やstd::vector
と異なり、コンテナ内の要素へのアクセスは絶対的な位置(添え字)によるのではなく、キーによる。 - 非順序
コンテナ内の各要素は、キーのハッシュ値に基づきハッシュテーブルに格納されるため、決められた順序で並んでいるわけではない。 - セット(set)
キーそのものが要素でもあり、かつ、同一のキー値を格納することはできない。
テンプレートパラメータ Hash
は、以下に示す Hash requirements を満たし、テンプレートパラメータ Key
のハッシュ関数として振る舞わなければならない。
- 関数オブジェクト型である。
- CopyConstructible requirements と Destructible requirements の要件を満たす。
h
をHash
型のオブジェクト、Key
をHash
型のオブジェクトの引数の型、u
をKey
型の lvalue、k
をKey
型(あるいはconst Key
型)に変換可能な値とすると、以下の要件を満たす。h(k)
は戻り値の型がstd::size_t
で、戻り値は引数k
のみにしかよらないh(u)
はu
を変更しない
テンプレートパラメータ Pred
は二項述語で、テンプレートパラメータ Key
に対する同値関係でなければならない。
テンプレートパラメータ Allocator
は、Allocator requirements を満たさなければならない。
メンバ関数
構築/コピー/破棄
名前 | 説明 | 対応バージョン |
---|---|---|
(constructor) |
コンストラクタ | C++11 |
(destructor) |
デストラクタ | C++11 |
operator= |
代入演算子 | C++11 |
領域
名前 | 説明 | 対応バージョン |
---|---|---|
empty |
コンテナが空かどうかを判定 | C++11 |
size |
要素数の取得 | C++11 |
max_size |
格納可能な最大の要素数の取得 | C++11 |
イテレータ
名前 | 説明 | 対応バージョン |
---|---|---|
begin |
先頭要素を指すイテレータの取得 | C++11 |
end |
最終要素の次を指すイテレータの取得 | C++11 |
cbegin |
先頭要素を指す読み取り専用イテレータの取得 | C++11 |
cend |
最終要素の次を指す読み取り専用イテレータの取得 | C++11 |
アロケータ
名前 | 説明 | 対応バージョン |
---|---|---|
get_allocator |
アロケータオブジェクトの取得 | C++11 |
コンテナの変更
名前 | 説明 | 対応バージョン |
---|---|---|
emplace |
コンテナ内への要素の直接構築 | C++11 |
emplace_hint |
挿入位置のヒントを使用したコンテナ内への要素の直接構築 | C++11 |
insert |
要素の追加 | C++11 |
insert_range |
Rangeの要素を挿入する | C++23 |
erase |
要素の削除 | C++11 |
clear |
全要素の削除 | C++11 |
swap |
内容の交換 | C++11 |
extract |
ノードハンドルを取得する | C++17 |
merge |
他のオブジェクトの要素をマージする | C++17 |
オブザーバー
名前 | 説明 | 対応バージョン |
---|---|---|
hash_function |
ハッシュ関数オブジェクトの取得 | C++11 |
key_eq |
キー比較用関数オブジェクトの取得 | C++11 |
検索
名前 | 説明 | 対応バージョン |
---|---|---|
find |
指定したキーの位置を検索 | C++11 |
count |
指定したキーの要素数を取得 | C++11 |
contains |
指定したキーの要素が含まれているかを判定する | C++20 |
equal_range |
指定したキーの範囲を取得 | C++11 |
バケットインタフェース
名前 | 説明 | 対応バージョン |
---|---|---|
bucket_count |
バケット数の取得 | C++11 |
max_bucket_count |
最大バケット数の取得 | C++11 |
bucket_size |
インデックス(添え字)で指定したバケット内の要素数を取得 | C++11 |
bucket |
キーで指定したバケットのインデックス(添え字)を取得 | C++11 |
begin(size_type) |
インデックス(添え字)で指定したバケット内の先頭要素を指すイテレータを取得 | C++11 |
end(size_type) |
インデックス(添え字)で指定したバケット内の最終要素の次を指すイテレータを取得 | C++11 |
cbegin(size_type) |
インデックス(添え字)で指定したバケット内の先頭要素を指す読み取り専用イテレータを取得 | C++11 |
cend(size_type) |
インデックス(添え字)で指定したバケット内の最終要素の次を指す読み取り専用イテレータを取得 | C++11 |
ハッシュポリシー
名前 | 説明 | 対応バージョン |
---|---|---|
load_factor |
現在の負荷率(バケットあたりの要素数の平均)を取得 | C++11 |
max_load_factor |
負荷率の最大値を取得、設定 | C++11 |
rehash |
最小バケット数指定によるバケット数の調整 | C++11 |
reserve |
最小要素数指定によるバケット数の調整 | C++11 |
メンバ型
名前 | 説明 | 対応バージョン |
---|---|---|
key_type |
キーの型。テンプレートパラメータ Key 。 |
C++11 |
value_type |
要素の型。テンプレートパラメータ Key 。 |
C++11 |
hasher |
キーのハッシュ関数の型。テンプレートパラメータ Hash 。 |
C++11 |
key_equal |
キーが等値か否かを判断するための二項述語の型。C++11 : テンプレートパラメータ Pred 。 |
C++11 |
allocator_type |
アロケータの型。テンプレートパラメータ Allocator 。 |
C++11 |
pointer |
要素 value_type (= Key ) へのポインタ。スマートポインタも可であるが、通常は value_type* 。規格書では、 allocator_type::pointer となっているが、これは規格書の誤りで、ドラフト N3376 で既に std::allocator_traits<Allocator>::pointer に修正されている。(さもないと、必須である allocator_type::value_type のみを定義したユーザ定義のアロケータを使用することができないため) |
C++11 |
const_pointer |
要素 value_type (= Key ) へのコンストポインタ。スマートポインタも可であるが、通常は const value_type* 。規格書では、 allocator_type::const_pointer となっているが、これは規格書の誤りで、ドラフト N3376 で既に std::allocator_traits<Allocator>::const_pointer に修正されている。(さもないと、必須である allocator_type::value_type のみを定義したユーザ定義のアロケータを使用することができないため) |
C++11 |
reference |
要素 value_type (= Key ) への参照。規格書では、 allocator_type::reference となっているが、これは規格書の誤りで、ドラフト N3376 で既に value_type& に修正されている。(さもないと、必須である allocator_type::value_type のみを定義したユーザ定義のアロケータを使用することができないため) |
C++11 |
const_reference |
要素 value_type (= Key ) へのコンスト参照。規格書では、 allocator_type::const_reference となっているが、これは規格書の誤りで、ドラフト N3376 で既に const value_type& に修正されている。(さもないと、必須である allocator_type::value_type のみを定義したユーザ定義のアロケータを使用することができないため) |
C++11 |
size_type |
要素数を表す符号なし整数型。difference_type で表現可能な非負整数(0以上の整数)を表すことが可能。(通常はsize_t ) |
C++11 |
difference_type |
同一のコンテナを指す iterator の差を表す符号付き整数型(通常はptrdiff_t ) std::iterator_traits<iterator>::difference_type 、および、std::iterator_traits<const_iterator>::difference_type と同じ。 |
C++11 |
iterator |
"読み取り専用"前方向イテレータ(誤植ではない) 規格書に記載はないが、(連想コンテナがそうであるように) const_iterator と同じ型か否かは実装依存であるものと思われる。従って、ODR(One Definition Rule)に違反しないようにするため、関数のパラメータ型には常に const_iterator を使用したほうが良いだろう。 |
C++11 |
const_iterator |
読み取り専用前方向イテレータ | C++11 |
local_iterator |
同一バケット内のみで有効なイテレータ。 規格書に記載はないが、( iterator と同様)const_local_iterator と同じ型か否かは実装依存であるものと思われる。iterator と、iterator_category 、value_type 、difference_type 、pointer 、reference は同一である。 |
C++11 |
const_local_iterator |
同一バケット内のみで有効な読み取り専用イテレータ。const_iterator と、iterator_category 、value_type 、difference_type 、pointer 、reference は同一である。 |
C++11 |
node_type |
node_handle クラステンプレートの特殊化。 |
C++17 |
insert_return_type |
ノードを挿入した結果を記述するために使用されるクラス型。以下に示すinsert-return-type テンプレートの特殊化である。ただし、これは説明用のクラスであり、実装定義である。 |
C++17 |
template <class Iterator, class NodeType>
struct insert-return-type {
Iterator position;
bool inserted;
NodeType node;
};
非メンバ関数
比較演算子
名前 | 説明 | 対応バージョン |
---|---|---|
operator== |
等値比較 | C++11 |
operator!= |
非等値比較 | C++11 |
入れ替え
名前 | 説明 | 対応バージョン |
---|---|---|
swap |
内容の交換 | C++11 |
要素削除
名前 | 説明 | 対応バージョン |
---|---|---|
erase_if |
指定した条件に合致する要素とその分の領域を、コンテナから削除する | C++20 |
推論補助
名前 | 説明 | 対応バージョン |
---|---|---|
(deduction_guide) |
クラステンプレートの推論補助 | C++17 |
例
#include <iostream>
#include <unordered_set>
#include <iterator>
#include <algorithm>
#include <string>
template <class C>
void print(const C& c, std::ostream& os = std::cout)
{
std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, ", "));
os << std::endl;
}
int main()
{
std::unordered_set<std::string> us{ "1st element", "2nd element", "3rd element", };
print(us);
us.emplace("4th element");
print(us);
us.erase("2nd element");
print(us);
}
xxxxxxxxxx
#include <iostream>
#include <unordered_set>
#include <iterator>
#include <algorithm>
#include <string>
template <class C>
void print(const C& c, std::ostream& os = std::cout)
{
std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, ", "));
os << std::endl;
}
int main()
{
std::unordered_set<std::string> us{ "1st element", "2nd element", "3rd element", };
print(us);
us.emplace("4th element");
print(us);
us.erase("2nd element");
print(us);
}
出力
3rd element, 2nd element, 1st element,
4th element, 3rd element, 2nd element, 1st element,
4th element, 3rd element, 1st element,
バージョン
言語
- C++11
参照
- Unordered associative containers do not use allocator_traits to define member types (上記の
pointer
、const_pointer
、reference
、const_reference
の問題に対する修正案) - P0919R3 Heterogeneous lookup for unordered containers