#构造函数

empty (1)

 explicit unordered_set ( size_type n = /* see below */,
                  const hasher& hf = hasher(),
                  const key_equal& eql = key_equal(),
                  const allocator_type& alloc = allocator_type() );

 explicit unordered_set ( const allocator_type& alloc );

range (2)

 template <class InputIterator>
  unordered_set ( InputIterator first, InputIterator last,
                  size_type n = /* see below */,
                  const hasher& hf = hasher(),
                  const key_equal& eql = key_equal(),
                  const allocator_type& alloc = allocator_type() );

copy (3)

 unordered_set ( const unordered_set& ust );
 unordered_set ( const unordered_set& ust, const allocator_type& alloc );

move (4)

 unordered_set ( unordered_set&& ust );
 unordered_set ( unordered_set&& ust, const allocator_type& alloc );

initializer list (5)

 unordered_set ( initializer_list<value_type> il,
         size_type n = /* see below */,
         const hasher& hf = hasher(),
         const key_equal& eql = key_equal(),
         const allocator_type& alloc = allocator_type() );

示例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


// constructing unordered_sets
#include <iostream>
#include <string>
#include <unordered_set>

template<class T>
T cmerge (T a, T b) { T t(a); t.insert(b.begin(),b.end()); return t; }

int main ()
{
  std::unordered_set<std::string> first;                                // empty
  std::unordered_set<std::string> second ( {"red","green","blue"} );    // init list
  std::unordered_set<std::string> third ( {"orange","pink","yellow"} ); // init list
  std::unordered_set<std::string> fourth ( second );                    // copy
  std::unordered_set<std::string> fifth ( cmerge(third,fourth) );       // move
  std::unordered_set<std::string> sixth ( fifth.begin(), fifth.end() ); // range

  std::cout << "sixth contains:";
  for (const std::string& x: sixth) std::cout << " " << x;
  std::cout << std::endl;

  return 0;
}

赋值运算符

copy (1)

unordered_set& operator= ( const unordered_set& ust );

move (2)

unordered_set& operator= ( unordered_set&& ust );

initializer list (3)

unordered_set& operator= ( intitializer_list<value_type> il );

示例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


// unordered_set::operator=
#include <iostream>
#include <string>
#include <unordered_set>

template<class T>
T cmerge (T a, T b) {
  T t(a); t.insert(b.begin(),b.end()); return t;
}

int main ()
{
  std::unordered_set<std::string> first, second, third;
  first = {"red","green","blue"};      // init list
  second = {"orange","pink","yellow"}; // init list
  third = cmerge (first, second);      // move
  first = third;                       // copy

  std::cout << "first contains:";
  for (const std::string& x: first) std::cout << " " << x;
  std::cout << std::endl;

  return 0;
}

容量

迭代器

begin函数

container iterator (1)

      iterator begin() noexcept;
const_iterator begin() const noexcept;

bucket iterator (2)

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

返回开始迭代器

返回指向unordered_set容器（1）或其中一个存储桶（2）中的第一个元素的迭代器。

请注意，unordered_set对象不能保证哪个特定元素被认为是其第一个元素。但是，无论如何，从开始到结束的范围涵盖容器（或存储桶）中的所有元素，直到无效。

unordered_set中的所有迭代器都具有对元素的const访问（即使那些类型不以const_为前缀的元素）：元素可以插入或移除，但在容器中未被修改。

示例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


// unordered_set::begin/end example
#include <iostream>
#include <string>
#include <unordered_set>

int main ()
{
  std::unordered_set<std::string> myset =
  {"Mercury","Venus","Earth","Mars","Jupiter","Saturn","Uranus","Neptune"};

  std::cout << "myset contains:";
  for ( auto it = myset.begin(); it != myset.end(); ++it )
    std::cout << " " << *it;
  std::cout << std::endl;

  std::cout << "myset's buckets contain:\n";
  for ( unsigned i = 0; i < myset.bucket_count(); ++i) {
    std::cout << "bucket #" << i << " contains:";
    for ( auto local_it = myset.begin(i); local_it!= myset.end(i); ++local_it )
      std::cout << " " << *local_it;
    std::cout << std::endl;
  }

  return 0;
}

end函数

container iterator (1)

      iterator end() noexcept;
const_iterator end() const noexcept;

bucket iterator (2)

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

返回结束迭代器

返回指向unordered_set容器（1）或其中一个存储桶（2）中的过去元素的迭代器。

由end返回的迭代器不指向任何元素，而是指向在unordered_set容器（其过去到结束位置）之后的最后一个元素的位置。因此，返回的值不应被解引用.

请注意，unordered_set对象不会保证它的元素如何被排序。但是，无论如何，从开始到结束的范围涵盖容器（或桶）中的所有元素，直到无效。unordered_set中的所有迭代器都具有对元素的const访问（即使那些类型不以const_为前缀的元素）：元素可以插入或移除，但在容器中未被修改。

示例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


#include <iostream>
#include <string>
#include <unordered_set>

int main ()
{
  std::unordered_set<std::string> myset =
  {"Mercury","Venus","Earth","Mars","Jupiter","Saturn","Uranus","Neptune"};

  std::cout << "myset contains:";
  for ( auto it = myset.begin(); it != myset.end(); ++it )
    std::cout << " " << *it;
  std::cout << std::endl;

  std::cout << "myset's buckets contain:\n";
  for ( unsigned i = 0; i < myset.bucket_count(); ++i) {
    std::cout << "bucket #" << i << " contains:";
    for ( auto local_it = myset.begin(i); local_it!= myset.end(i); ++local_it )
      std::cout << " " << *local_it;
    std::cout << std::endl;
  }

  return 0;
}

元素查找

find函数

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

获取元素迭代器

搜索容器的一个元素，其中k为值，如果找到则返回一个迭代器，否则返回一个迭代器到unordered_set :: end（元素超过容器的末尾）。

示例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


// unordered_set::find
#include <iostream>
#include <string>
#include <unordered_set>

int main ()
{
  std::unordered_set<std::string> myset = { "red","green","blue" };

  std::string input;
  std::cout << "color? ";
  getline (std::cin,input);

  std::unordered_set<std::string>::const_iterator got = myset.find (input);

  if ( got == myset.end() )
    std::cout << "not found in myset";
  else
    std::cout << *got << " is in myset";

  std::cout << std::endl;

  return 0;
}

##count函数 size_type count（const key_type＆k）const;

用特定的键计数元素

搜索容器的值为k的元素，并返回找到的元素数量。因为unordered_set容器不允许重复的值，这意味着如果在容器中存在具有该值的元素，则该函数实际返回1，否则返回0。

示例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


// unordered_set::count
#include <iostream>
#include <string>
#include <unordered_set>

int main ()
{
  std::unordered_set<std::string> myset = { "hat", "umbrella", "suit" };

  for (auto& x: {"hat","sunglasses","suit","t-shirt"}) {
    if (myset.count(x)>0)
      std::cout << "myset has " << x << std::endl;
    else
      std::cout << "myset has no " << x << std::endl;
  }

  return 0;
}

##equal_range函数

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

使用特定键获取元素的范围

返回范围的范围，该范围包含所有等于k的元素。在unordered_set容器中，键是唯一的，范围最多只包含一个元素。

如果k与容器中的任何元素不匹配，则返回的范围都以其下限范围和上限范围结束。unordered_set中的

所有迭代器都具有对元素的const访问（即使那些类型不以const_为前缀的元素）：元素可以插入或移除，但在容器中未被修改。

使用方法与multiset::equal_range相同

修改

桶

bucket_count

size_type bucket_count（）const noexcept;

返回桶数

返回unordered_set容器中的桶数。

桶是容器内部哈希表中的一个槽，根据哈希值为其分配元素。

桶的数量直接影响容器散列表的负载因子（因此影响碰撞的概率）。容器自动增加桶的数目保持低于特定阈值（其负载因子max_load_factor），引起一个rehash每个需要桶的数目要增加时间。

示例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


#include <iostream>
#include <string>
#include <unordered_set>

int main ()
{
  std::unordered_set<std::string> myset =
  {"Mercury","Venus","Earth","Mars","Jupiter","Saturn","Uranus","Neptune"};

  unsigned n = myset.bucket_count();

  std::cout << "myset has " << n << " buckets.\n";

  for (unsigned i=0; i<n; ++i) {
    std::cout << "bucket #" << i << " contains:";
    for (auto it = myset.begin(i); it!=myset.end(i); ++it)
      std::cout << " " << *it;
    std::cout << "\n";
  }

  return 0;
}

max_bucket_count函数

size_type max_bucket_count（）const noexcept;

返回最大桶数

返回unordered_set容器可以具有的最大桶数。

这是由于系统限制或对其库实现的限制，容器可能存在的桶的最大潜在数量

示例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


#include <iostream>
#include <unordered_set>

int main ()
{
  std::unordered_set<int> myset;

  std::cout << "max_size = " << myset.max_size() << std::endl;
  std::cout << "max_bucket_count = " << myset.max_bucket_count() << std::endl;
  std::cout << "max_load_factor = " << myset.max_load_factor() << std::endl;

  return 0;
}

bucket_size函数

size_type bucket_size（size_type n）const;

返回桶大小

返回桶n中的元素数。

桶是容器内部哈希表中的一个槽，根据哈希值为其分配元素。

桶中的元素数量会影响访问存储桶中特定元素所需的时间。容器自动增加桶的数量，以保持负载因子（平均桶大小）低于其max_load_factor。

示例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


// unordered_set::bucket_size
#include <iostream>
#include <string>
#include <unordered_set>

int main ()
{
  std::unordered_set<std::string> myset =
  { "red", "green", "blue", "yellow", "purple", "pink" };

  unsigned nbuckets = myset.bucket_count();

  std::cout << "myset has " << nbuckets << " buckets:\n";

  for (unsigned i=0; i<nbuckets; ++i) {
    std::cout << "bucket #" << i << " has " << myset.bucket_size(i) << " elements.\n";
  }

  return 0;
}

bucket函数

size_type bucket（const key_type＆k）const;

找到元素的桶

返回值为k的元素所在的存储桶编号。

桶是容器内部哈希表中的一个槽，根据哈希值为其分配元素。桶的编号从0到（bucket_count -1）。

可以通过由unordered_set :: begin和unordered_set :: end返回的范围迭代器访问桶中的各个元素。

示例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


// unordered_set::bucket
#include <iostream>
#include <string>
#include <unordered_set>

int main ()
{
  std::unordered_set<std::string> myset = {"water","sand","ice","foam"};

  for (const std::string& x: myset) {
    std::cout << x << " is in bucket #" << myset.bucket(x) << std::endl;
  }

  return 0;
}

hash

load_factor函数

返回负载系数

返回unordered_set容器中的当前负载因子。

负载因子是容器中元素数量（它的大小）和桶数（bucket_count）之间的比率：

load_factor = size / bucket_count

负载因子影响散列表中的冲突概率（即，两个元素位于相同的桶中）。容器自动增加桶的数目保持低于特定阈值（其负载因子max_load_factor）.

示例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


// unordered_set hash table stats
#include <iostream>
#include <unordered_set>

int main ()
{
  std::unordered_set<int> myset;

  std::cout << "size = " << myset.size() << std::endl;
  std::cout << "bucket_count = " << myset.bucket_count() << std::endl;
  std::cout << "load_factor = " << myset.load_factor() << std::endl;
  std::cout << "max_load_factor = " << myset.max_load_factor() << std::endl;

  return 0;
}

max_load_factor函数

get (1)

float max_load_factor() const noexcept;

set (2)

void max_load_factor ( float z );

获取或设置最大负载系数

第一个版本（1）返回unordered_set容器的当前最大载入系数。第二个版本（2）将z设置为unordered_set容器的新的最大负载因子。

负载因子是容器中元素数量（它的大小）和桶数（bucket_count）之间的比率。

默认情况下，unordered_set容器的max_load_factor为1.0。

负载因子影响散列表中的冲突概率（即两个元素位于同一个数据桶中的概率）。

示例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


// unordered_set::max_load_factor
#include <iostream>
#include <string>
#include <unordered_set>

int main ()
{
  std::unordered_set<std::string> myset =
  {"New York", "Paris", "London", "Hong Kong", "Bangalore", "Tel Aviv"};

  std::cout << "current max_load_factor: " << myset.max_load_factor() << std::endl;
  std::cout << "current size: " << myset.size() << std::endl;
  std::cout << "current bucket_count: " << myset.bucket_count() << std::endl;
  std::cout << "current load_factor: " << myset.load_factor() << std::endl;

  float z = myset.max_load_factor();
  myset.max_load_factor ( z / 2.0 );
  std::cout << "[max_load_factor halved]" << std::endl;

  std::cout << "new max_load_factor: " << myset.max_load_factor() << std::endl;
  std::cout << "new size: " << myset.size() << std::endl;
  std::cout << "new bucket_count: " << myset.bucket_count() << std::endl;
  std::cout << "new load_factor: " << myset.load_factor() << std::endl;

  return 0;
}

rehash函数

void rehash ( size_type n );

将容器中的桶数设置为n或更多。

如果n大于容器中桶的当前数量（bucket_count），则强制执行重新排列。新的桶计数可以等于或大于n。

如果n低于容器中桶的当前数量（bucket_count），则该功能可能对桶计数没有影响，也可能不会强制重新刷新。

rehash是哈希表的重构：在容器中的所有元素根据它们的哈希值到新的一组桶的重新排列。这可能会改变容器内元素的迭代顺序。

当操作中负载因子将超过其max_load_factor时，容器将自动执行Rehash。

请注意，此函数希望将桶数作为参数。存在类似的函数unordered_set :: reserve，它将容器中的元素数量作为参数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


// unordered_set::rehash
#include <iostream>
#include <string>
#include <unordered_set>

int main ()
{
  std::unordered_set<std::string> myset;

  myset.rehash(12);

  myset.insert("office");
  myset.insert("house");
  myset.insert("gym");
  myset.insert("parking");
  myset.insert("highway");

  std::cout << "current bucket_count: " << myset.bucket_count() << std::endl;

  return 0;
}

reserve函数

void reserve ( size_type n );

请求容量更改

将容器中的桶数（bucket_count）设置为最适合至少包含n个元素。

如果n大于当前bucket_count乘以max_load_factor，则容器的bucket_count将增加，并且强制执行rehash。

如果n低于该值，则该功能可能不起作用。

通过调用reverse我们对unordered_set容器的大小进行修改，我们避免了容器大小增加可能产生和优化哈希表大小的多次rehash。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


// unordered_set::reserve
#include <iostream>
#include <string>
#include <unordered_set>

int main ()
{
  std::unordered_set<std::string> myset;

  myset.reserve(5);

  myset.insert("office");
  myset.insert("house");
  myset.insert("gym");
  myset.insert("parking");
  myset.insert("highway");

  std::cout << "myset contains:";
  for (const std::string& x: myset) std::cout << " " << x;
  std::cout << std::endl;

  return 0;
}

unordered_set操作总结

文章目录