Skip to content

Latest commit

 

History

History
260 lines (192 loc) · 15.9 KB

unordered_set.md

File metadata and controls

260 lines (192 loc) · 15.9 KB
Raw

unordered_set

  • unordered_set[meta header]
  • std[meta namespace]
  • class template[meta id-type]
  • cpp11[meta cpp]
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から
  }
}
  • std::hash[link /reference/functional/hash.md]
  • std::equal_to[link /reference/functional/equal_to.md]
  • polymorphic_allocator[link /reference/memory_resource/polymorphic_allocator.md]

概要

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
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);
}
  • std::unordered_set[color ff0000]
  • std::ostream[link /reference/ostream.md]
  • us.emplace[link unordered_set/emplace.md]
  • us.erase[link unordered_set/erase.md]

出力

3rd element, 2nd element, 1st element, 
4th element, 3rd element, 2nd element, 1st element, 
4th element, 3rd element, 1st element,

バージョン

言語

  • C++11

参照