Class template unordered

Class template unordered_set

boost::unordered_set — An unordered associative container that stores unique values.
boost::unordered_set — 保存唯一值的無序關聯式容器。

Synopsis 概要

template<typename Value, typename Hash = boost::hash<Value>, 
         typename Pred = std::equal_to<Value>, 
         typename Alloc = std::allocator<Value> > 
class unordered_set {
public:
  // types
  typedef Value                                    key_type;            
  typedef Value                                    value_type;          
  typedef Hash                                     hasher;              
  typedef Pred                                     key_equal;           
  typedef Alloc                                    allocator_type;      
  typedef typename allocator_type::pointer         pointer;             
  typedef typename allocator_type::const_pointer   const_pointer;       
  typedef typename allocator_type::reference       reference;             // lvalue of value_type.
  typedef typename allocator_type::const_reference const_reference;       // const lvalue of value_type.
  typedef implementation-defined size_type;
  typedef implementation-defined difference_type;
  typedef implementation-defined iterator;
  typedef implementation-defined const_iterator;
  typedef implementation-defined local_iterator;
  typedef implementation-defined const_local_iterator;

  // construct/copy/destruct
  explicit unordered_set(size_type = implementation-defined, 
                         hasher const& = hasher(), 
                         key_equal const& = key_equal(), 
                         allocator_type const& = allocator_type());
  template<typename InputIterator> 
    unordered_set(InputIterator, InputIterator, 
                  size_type = implementation-defined, 
                  hasher const& = hasher(), key_equal const& = key_equal(), 
                  allocator_type const& = allocator_type());
  unordered_set(unordered_set const&);
  explicit unordered_set(Allocator const&);
  unordered_set(unordered_set const&, Allocator const&);
  ~unordered_set();
  unordered_set& operator=(unordered_set const&);
  allocator_type get_allocator() const;

  // size and capacity
  bool empty() const;
  size_type size() const;
  size_type max_size() const;

  // iterators
  iterator begin();
  const_iterator begin() const;
  iterator end();
  const_iterator end() const;
  const_iterator cbegin() const;
  const_iterator cend() const;

  // modifiers
  template<typename... Args> std::pair<iterator, bool> emplace(Args&&...);
  template<typename... Args> iterator emplace_hint(const_iterator, Args&&...);
  std::pair<iterator, bool> insert(value_type const&);
  iterator insert(const_iterator, value_type const&);
  template<typename InputIterator> void insert(InputIterator, InputIterator);
  iterator erase(const_iterator);
  size_type erase(key_type const&);
  iterator erase(const_iterator, const_iterator);
  void clear();
  void swap(unordered_set&);

  // observers
  hasher hash_function() const;
  key_equal key_eq() const;

  // lookup
  iterator find(key_type const&);
  iterator find(key_type const&) const;
  size_type count(key_type const&) const;
  std::pair<iterator, iterator> equal_range(key_type const&);
  std::pair<const_iterator, const_iterator> equal_range(key_type const&) const;

  // bucket interface
  size_type bucket_count() const;
  size_type max_bucket_count() const;
  size_type bucket_size(size_type) const;
  size_type bucket(key_type const&) const;
  local_iterator begin(size_type);
  const_local_iterator begin(size_type) const;
  local_iterator end(size_type);
  const_local_iterator end(size_type) const;
  const_local_iterator cbegin(size_type) const;
  const_local_iterator cend(size_type);

  // hash policy
  float load_factor() const;
  float max_load_factor() const;
  void max_load_factor(float);
  void rehash(size_type);
};

// Equality Comparisons
template<typename Value, typename Hash, typename Pred, typename Alloc> 
  bool operator==(unordered_set<Value, Hash, Pred, Alloc> const&, 
                  unordered_set<Value, Hash, Pred, Alloc> const&);
template<typename Value, typename Hash, typename Pred, typename Alloc> 
  bool operator!=(unordered_set<Value, Hash, Pred, Alloc> const&, 
                  unordered_set<Value, Hash, Pred, Alloc> const&);

// swap
template<typename Value, typename Hash, typename Pred, typename Alloc> 
  void swap(unordered_set<Value, Hash, Pred, Alloc>&, 
            unordered_set<Value, Hash, Pred, Alloc>&);

Description 說明

For the normative reference see chapter 23 of the working draft of the C++ standard [n2691].
標準化參考請見 C++標準工作草案[n2691] 第23章。

Template Parameters 模板參數

Value	Value must be Assignable and CopyConstructible Value 必須是可賦值和可複製構造的
Hash	A unary function object type that acts a hash function for a `Value`. It takes a single argument of type `Value` and returns a value of type std::size_t. 一元函數對像類型，用作 `Value` 的散列函數。它接受單個類型為 `Value` 的參數，返回類型為 std::size_t 的值。
Pred	A binary function object that implements an equivalence relation on values of type `Value`. A binary function object that induces an equivalence relation on values of type Key. It takes two arguments of type Key and returns a value of type bool. 二元函數對象，實現類型 `Value` 的等同性關係。它接受兩個類型為 `Value` 的參數，返回類型為 bool 的值。
Alloc	An allocator whose value type is the same as the container's value type. 分配器，它的值類型與容器的值類型相同。

The elements are organized into buckets. Keys with the same hash code are stored in the same bucket.
容器中的元素存放在多個桶中。具有相同散列碼的鍵存放在同一個桶中。

The number of buckets can be automatically increased by a call to insert, or as the result of calling rehash.
桶的數量可以通過調用 insert 自動增加，或者調用 rehash 進行調整。

`unordered_set` public types 公有類型

typedef implementation-defined size_type;

An unsigned integral type.
無符號整數類型。

size_type can represent any non-negative value of difference_type.
size_type 可以表示 difference_type 的任一非負值。
typedef implementation-defined difference_type;

A signed integral type.
有符號整數類型。

Is identical to the difference type of iterator and const_iterator.
與 iterator 和 const_iterator 的距離類型相同。
typedef implementation-defined iterator;

A constant iterator whose value type is value_type.
一個常量迭代器，它的值類型為 value_type。

Any iterator category except output iterator.
除輸出迭代器以外的任意迭代器類別。

Convertible to const_iterator.
可轉換為 const_iterator。
typedef implementation-defined const_iterator;

A constant iterator whose value type is value_type.
一個常量迭代器，它的值類型為 value_type。

Any iterator category except output iterator.
除輸出迭代器以外的任意迭代器類別。
typedef implementation-defined local_iterator;

An iterator with the same value type, difference type and pointer and reference type as iterator.
具有與 iterator 相同值類型、距離類型和指針、引用類型的迭代器。

A local_iterator object can be used to iterate through a single bucket.
local_iterator 對象可用於遍歷單個桶。
typedef implementation-defined const_local_iterator;

A constant iterator with the same value type, difference type and pointer and reference type as const_iterator.
具有與 const_iterator 相同值類型、距離類型和指針、引用類型的迭代器。

A const_local_iterator object can be used to iterate through a single bucket.
const_local_iterator 對象可用於遍歷單個桶。

`unordered_set` public construct/copy/destruct 公有構造/複製/析構

```
explicit unordered_set(size_type n = implementation-defined, 
                       hasher const& hf = hasher(), 
                       key_equal const& eq = key_equal(), 
                       allocator_type const& a = allocator_type());
```
Constructs an empty container with at least n buckets, using hf as the hash function, eq as the key equality predicate, a as the allocator and a maximum load factor of 1.0.
構造一個帶至少 n 個桶的空容器，以 hf 作為散列函數，eq 作為鍵值等同性謂詞，a 作為分配器，最大負載因子為 1.0。

Postconditions:
後置條件：
size() == 0
```
template<typename InputIterator> 
  unordered_set(InputIterator f, InputIterator l, 
                size_type n = implementation-defined, 
                hasher const& hf = hasher(), 
                key_equal const& eq = key_equal(), 
                allocator_type const& a = allocator_type());
```
Constructs an empty container with at least n buckets, using hf as the hash function, eq as the key equality predicate, a as the allocator and a maximum load factor of 1.0 and inserts the elements from [f, l) into it.
構造一個帶至少 n 個桶的空容器，以 hf 作為散列函數，eq 作為鍵值等同性謂詞，a 作為分配器，最大負載因子為 1.0，並插入 [f,l) 的元素。
```
unordered_set(unordered_set const&);
```
The copy constructor. Copies the contained elements, hash function, predicate, maximum load factor and allocator.
複製構造函數。複製所含的元素、散列函數、謂詞、最大負載因子和分配器。
```
explicit unordered_set(Allocator const& a);
```
Constructs an empty container, using allocator a.
構造一個空容器，使用分配器 a。
```
unordered_set(unordered_set const& x, Allocator const& a);
```
Constructs an container, copying x's contained elements, hash function, predicate, maximum load factor, but using allocator a.
構造一個容器，複製 x 所含的元素、散列函數、謂詞、最大負載因子，但使用分配器 a。
```
~unordered_set();
```

unordered_set& operator=(unordered_set const&);

The assignment operator. Copies the contained elements, hash function, predicate and maximum load factor but not the allocator.
賦值操作符。複製所含的元素、散列函數、謂詞、最大負載因子，但不複製分配器。

allocator_type get_allocator() const;

`unordered_set` size and capacity 大小與容量

```
bool empty() const;
```
Returns:
返回：
size() == 0
```
size_type size() const;
```
Returns:
返回：
std::distance(begin(), end())
```
size_type max_size() const;
```
Returns:
返回：
size() of the largest possible container.
最大可能容器的 size()。

`unordered_set` iterators 迭代器

iterator begin();
const_iterator begin() const;

Returns:

An iterator referring to the first element of the container, or if the container is empty the past-the-end value for the container.
一個迭代器，引向容器的第一個元素，或者如果容器為空，引向容器的 past-the-end 值。

```
iterator end();
const_iterator end() const;
```
Returns:
返回：
An iterator which refers to the past-the-end value for the container.
一個迭代器，引向容器的 past-the-end 值。

const_iterator cbegin() const;

Returns:

A constant iterator referring to the first element of the container, or if the container is empty the past-the-end value for the container.
一個常量迭代器，引向容器的第一個元素，或者如果容器為空，引向容器的 past-the-end 值。

```
const_iterator cend() const;
```
Returns:
返回：
A constant iterator which refers to the past-the-end value for the container.
一個常量迭代器，引向容器的 past-the-end 值。

`unordered_set` modifiers 修改器

template<typename... Args> std::pair<iterator, bool> emplace(Args&&... args);

Inserts an object, constructed with the arguments args, in the container if and only if there is no element in the container with an equivalent value.
插入一個從參數 args 構造的對象到容器中，當且僅當空器中沒有相同鍵值的元素。

Returns:

The bool component of the return type is true if an insert took place.
如果插入成功，則返回類型的 bool 部分為 true。

If an insert took place, then the iterator points to the newly inserted element. Otherwise, it points to the element with equivalent value.
如果插入成功，則迭代器指向新插入的元素。否則，指向具有相同鍵值的元素。

Throws:

拋出：

If an exception is thrown by an operation other than a call to hasher the function has no effect.

如果從對 hasher 的調用以外拋出異常，該函數沒有作用。

Notes:

說明：

Can invalidate iterators, but only if the insert causes the load factor to be greater to or equal to the maximum load factor.
可能使迭代器失效，但僅當插入操作導致負載因子大於或等於最大負載因子時。

Pointers and references to elements are never invalidated.
指向元素的指針和引用不會失效。

Only available on compilers with support for variadic template arguments and rvalue references.
僅在支持可變參數模板和右值引用的編譯器上可用。

template<typename... Args> 
  iterator emplace_hint(const_iterator hint, Args&&... args);

hint is a suggestion to where the element should be inserted.
hint 是一個插入元素的建議點。

Returns:

Throws:

拋出：

If an exception is thrown by an operation other than a call to hasher the function has no effect.

如果從對 hasher 的調用以外拋出異常，該函數沒有作用。

Notes:

說明：

The standard is fairly vague on the meaning of the hint. But the only practical way to use it, and the only way that Boost.Unordered supports is to point to an existing element with the same value.

標準對於提示的意義相當含糊。不過使用它的唯一可行的方法，也是 Boost.Unordered 支持的唯一方法是，指向具有相同值的元素。

Pointers and references to elements are never invalidated.
指向元素的指針和引用不會失效。

Only available on compilers with support for variadic template arguments and rvalue references.
僅在支持可變參數模板和右值引用的編譯器上可用。

std::pair<iterator, bool> insert(value_type const& obj);

Inserts obj in the container if and only if there is no element in the container with an equivalent value.
插入 obj 到容器中，當且僅當空器中沒有相同鍵值的元素。

Returns:

The bool component of the return type is true if an insert took place.
如果插入成功，則返回類型的 bool 部分為 true。

Throws:

拋出：

If an exception is thrown by an operation other than a call to hasher the function has no effect.

如果從對 hasher 的調用以外拋出異常，該函數沒有作用。

Notes:

說明：

Pointers and references to elements are never invalidated.
指向元素的指針和引用不會失效。

iterator insert(const_iterator hint, value_type const& obj);

Inserts obj in the container if and only if there is no element in the container with an equivalent value.
插入 obj 到容器中，當且僅當空器中沒有相同鍵值的元素。

hint is a suggestion to where the element should be inserted.
hint 是一個插入元素的建議點。

Returns:

Throws:

拋出：

If an exception is thrown by an operation other than a call to hasher the function has no effect.

如果從對 hasher 的調用以外拋出異常，該函數沒有作用。

Notes:

說明：

The standard is fairly vague on the meaning of the hint. But the only practical way to use it, and the only way that Boost.Unordered supports is to point to an existing element with the same value.
標準對於提示的意義相當含糊。不過使用它的唯一可行的方法，也是 Boost.Unordered 支持的唯一方法是，指向具有相同值的元素。

Pointers and references to elements are never invalidated.
指向元素的指針和引用不會失效。

template<typename InputIterator> 
  void insert(InputIterator first, InputIterator last);

Inserts a range of elements into the container. Elements are inserted if and only if there is no element in the container with an equivalent value.
插入一組元素到容器中。元素當且僅當空器中沒有相同鍵值的元素時被插入。

Throws:

拋出：

When inserting a single element, if an exception is thrown by an operation other than a call to hasher the function has no effect.

當插入單個元素時，如果從對 hasher 的調用以外拋出異常，該函數沒有作用。

Notes:

說明：

Pointers and references to elements are never invalidated.
指向元素的指針和引用不會失效。

iterator erase(const_iterator position);

Erase the element pointed to by position.
刪除 position 所指元素。

Returns:

The iterator following position before the erasure.

在刪除前緊跟 position 的迭代器。

Throws:

拋出：

Only throws an exception if it is thrown by hasher or key_equal.
僅當從 hasher 或 key_equal 拋出異常時拋出該異常。

In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.
在該實現中，這一重載不會調用函數對像方法，所以它不會拋出，不過在其它實現中不一定也是如此。

size_type erase(key_type const& k);

Erase all elements with key equivalent to k.
刪除所有鍵值等於 k 的元素。

Returns:

The number of elements erased.

被刪除的元素數量。

Throws:

拋出：

Only throws an exception if it is thrown by hasher or key_equal.
僅當從 hasher 或 key_equal 拋出異常時拋出該異常。

iterator erase(const_iterator first, const_iterator last);

Erases the elements in the range from first to last.
刪除從 first 到 last 的元素。

Returns:

The iterator following the erased elements - i.e. last.

緊隨被刪除元素之後的迭代器 - 即 last。

Throws:

拋出：

Only throws an exception if it is thrown by hasher or key_equal.
僅當從 hasher 或 key_equal 拋出異常時拋出該異常。

```
void clear();
```
Erases all elements in the container.
刪除容器中所有元素。

Postconditions:
後置條件：

size() == 0

Throws:
拋出：

Never throws an exception.
不會拋出。

void swap(unordered_set&);

Throws:

拋出：

If the allocators are equal, doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of key_equal or hasher.

如果分配器是相同的，則不會拋出，除非異常是從 key_equal 或 hasher 的複製構造函數或複製賦值操作符拋出的。

Notes:

說明：

For a discussion of the behavior when allocators aren't equal see the implementation details.

有關分配器不同時的行為的討論，請見實現細節。

`unordered_set` observers 觀察器

```
hasher hash_function() const;
```
Returns:
返回：
The container's hash function.
容器的散列函數。
```
key_equal key_eq() const;
```
Returns:
返回：
The container's key equality predicate.
容器的鍵值等同性謂詞。

`unordered_set` lookup 查找

iterator find(key_type const& k);
iterator find(key_type const& k) const;

Returns:

An iterator pointing to an element with key equivalent to k, or b.end() if no such element exists.

一個迭代器，指向鍵值等於 k 的元素，如果該元素不存在，返回 b.end()。

```
size_type count(key_type const& k) const;
```
Returns:
返回：

The number of elements with key equivalent to k.
鍵值等於 k 的元素數量。

std::pair<iterator, iterator> equal_range(key_type const& k);
std::pair<const_iterator, const_iterator> equal_range(key_type const& k) const;

Returns:

A range containing all elements with key equivalent to k. If the container doesn't container any such elements, returns std::make_pair(b.end(),b.end()).
包含所有鍵值等於 k 的元素的區間。如果容器中沒有這樣的元素，返回 std::make_pair(b.end(),b.end()).

`unordered_set` bucket interface 桶接口

```
size_type bucket_count() const;
```
Returns:
返回：

The number of buckets.
桶的數量。
```
size_type max_bucket_count() const;
```
Returns:
返回：

An upper bound on the number of buckets.
桶數量的上限。
```
size_type bucket_size(size_type n) const;
```
Requires:
要求：

n < bucket_count()

Returns:
返回：

The number of elements in bucket n.
桶 n 中的元素數量。

size_type bucket(key_type const& k) const;

Returns:

The index of the bucket which would contain an element with key k.

包含鍵值為 k 的元素的桶的索引。

Postconditions:

後置條件：

The return value is less than bucket_count()

返回值小於 bucket_count()

local_iterator begin(size_type n);
const_local_iterator begin(size_type n) const;

Requires:

要求：

n shall be in the range [0, bucket_count()).

n 應位於區間 [0, bucket_count()).

Returns:

A local iterator pointing the first element in the bucket with index n.

一個局部迭代器，指向索引為 n 的桶中的第一個元素。

local_iterator end(size_type n);
const_local_iterator end(size_type n) const;

Requires:

要求：

n shall be in the range [0, bucket_count()).

n 應位於區間 [0, bucket_count()).

Returns:

A local iterator pointing the 'one past the end' element in the bucket with index n.

一個局部迭代器，指向索引為 n 的桶中的最後一個元素之後。

const_local_iterator cbegin(size_type n) const;

Requires:

要求：

n shall be in the range [0, bucket_count()).

n 應位於區間 [0, bucket_count()).

Returns:

A constant local iterator pointing the first element in the bucket with index n.

一個常量局部迭代器，指向索引為 n 的桶中的第一個元素。

const_local_iterator cend(size_type n);

Requires:

要求：

n shall be in the range [0, bucket_count()).

n 應位於區間 [0, bucket_count()).

Returns:

A constant local iterator pointing the 'one past the end' element in the bucket with index n.

一個常量局部迭代器，指向索引為 n 的桶中的最後一個元素之後。

`unordered_set` hash policy 散列策略

```
float load_factor() const;
```
Returns:
返回：

The average number of elements per bucket.
每個桶中元素的平均數量。
```
float max_load_factor() const;
```
Returns:
返回：

Returns the current maximum load factor.
返回當前的最大負載因子。
```
void max_load_factor(float z);
```
Effects:
作用：

Changes the container's maximum load factor, using z as a hint.
修改容器的最大負載因子，以 z 為提示。

void rehash(size_type n);

Changes the number of buckets so that there at least n buckets, and so that the load factor is less than the maximum load factor.
修改桶的數量，使得最少有 n 個桶，且負載因子小於最大負載因子。

Invalidates iterators, and changes the order of elements. Pointers and references to elements are not invalidated.
使迭代器失效，並會改變元素的順序。指向元素的指針和引用不會失效。

Throws:

拋出：

The function has no effect if an exception is thrown, unless it is thrown by the container's hash function or comparison function.

如果拋出異常，則該函數沒有作用，除非異常是從容器的散列函數或比較函數中拋出的。

`unordered_set` Equality Comparisons 等同性比較

template<typename Value, typename Hash, typename Pred, typename Alloc> 
  bool operator==(unordered_set<Value, Hash, Pred, Alloc> const& x, 
                  unordered_set<Value, Hash, Pred, Alloc> const& y);

Notes:

說明：

This is a boost extension.

這是 boost 的擴展。

template<typename Value, typename Hash, typename Pred, typename Alloc> 
  bool operator!=(unordered_set<Value, Hash, Pred, Alloc> const& x, 
                  unordered_set<Value, Hash, Pred, Alloc> const& y);

Notes:

說明：

This is a boost extension.

這是 boost 的擴展。

`unordered_set` swap 交換

template<typename Value, typename Hash, typename Pred, typename Alloc> 
  void swap(unordered_set<Value, Hash, Pred, Alloc>& x, 
            unordered_set<Value, Hash, Pred, Alloc>& y);

Effects:

作用：

x.swap(y)

Throws:

拋出：

If the allocators are equal, doesn't throw an exception unless it is thrown by the copy constructor or copy assignment operator of Hash or Pred.

如果分配器是相同的，則不會拋出異常，除非異常是從 Hash 或 Pred 的複製構造函數或複製賦值操作符拋出的。

Notes:

說明：

For a discussion of the behavior when allocators aren't equal see the implementation details.

有關分配器不同時的行為的討論，請見實現細節。