std::unordered_set 参考 | C++ 编程语言

注意

请注意，本文尚未完成！您可以通过编辑此文档页面来提供帮助。

概述

简化版 (C++98 起)
详细

template< class Key, /* ... */ >
class unordered_set;

常规版 (C++98 起)
多态版 (C++17 起)

template<
    class Key,
    class Hash = std::hash<Key>,
    class Compare = std::equal_to<Key>,
    class Allocator = std::allocator<Key>
>
class unordered_set;

namespace pmr {
    template <class Key,
              class Hash = std::hash<Key>,
              class Compare = std::equal_to<Key>>
    using unordered_set = std::unordered_set<Key, Hash, Compare,
                                             std::pmr::polymorphic_allocator<Key>>;
}

std::unordered_set 是一个用于存储唯一对象的关联容器。

使用示例

本节中的示例非常简单。有关更多示例，请导航到底部的示例部分。

创建
插入
搜索

C++17
C++17 之前
从范围

使用CTAD

#include <unordered_set>

int main() {
  std::unordered_set ints{1, 2, 3, 2, 1, 4, 5, 5};

 // Content: 1, 2, 3, 4, 5
}

即使我们在构造时重复元素，元素仍将保持唯一。

#include <unordered_set>

int main() {
  std::unordered_set<int> ints{1, 2, 3, 2, 1, 4, 5, 5};

 // Content: 1, 2, 3, 4, 5
}

我们可以使用迭代器从其他容器构造几乎所有容器。

#include <unordered_set>
#include <array>

int main() {
  std::array<int, 5> array{1, 4, 3, 3, 2};
  std::unordered_set<int> ints(array.cbegin(), array.cend());

 // Content: 1, 2, 3, 4
}

元素顺序

重要的是要注意，尽管示例注释中选择了任意顺序，但内部元素保持无序（正如容器名称所示），这意味着我们在遍历无序集合时不能保证有任何特定顺序。

普通
一次多个
从范围

无论如何，集合将始终保持唯一。

#include <unordered_set>

int main() {
  std::unordered_set<int> ints;
  
  ints.insert(1);
  ints.insert(2);
  ints.insert(1);
  ints.insert(2);

  // Content: 1 2
}

我们可以一次插入多个值。

#include <unordered_set>

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

  ints.insert({4, 3, 2, 1, 1});

  // Content: 1, 2, 3, 4
}

我们也可以像在构造中一样，从其他范围插入。

#include <unordered_set>
#include <array>

int main() {
  std::array<int, 5> array = {1, 2, 3, 3, 4};
  std::unordered_set<int> ints;

  ints.insert(array.cbegin(), array.cend());

  // Content: 1, 2, 3, 4
}

包含（自 C++20 起）
计数
查找

自 C++20 起，我们可以简单地在集合上使用 .contains() 来确定是否存在某个任意值。

#include <unordered_set>
#include <iostream>

int main() {
  std::unordered_set<int> ints{1, 2, 3, 4, 5};

  if(ints.contains(3)) {
    std::cout << "3 exists in the set.";
  } else {
    std::cout << "3 doesn't exist in the set.";
  }
}

.count() 是确定集合中元素存在的另一种方法。

#include <unordered_set>
#include <iostream>

int main() {
  std::unordered_set<int> ints{1, 2, 3, 4, 5};

  if(ints.count(3) == 1) { // or  simply if(ints.count(3)) , same effect
    std::cout << "3 exists in the set.";
  } else {
    std::cout << "3 doesn't exist in the set.";
  }
}

我们可以使用 .find() 方法在集合中查找特定值。如果该值不在集合中，则返回的迭代器将等于结束迭代器（通过 .end() 或 .cend() 获取）。

#include <unordered_set>
#include <iostream>

int main() {
  std::unordered_set<int> ints{1, 2, 3, 4, 5};

  const auto it = ints.find(3); // we can use auto to deduce the type of the iterator returned

  if(it != ints.cend()) {
    // if the iterator is not equal to ints.cend(), the value is in the set
    std::cout << "3 exists in the set.";
  } else {
    std::cout << "3 doesn't exist in the set.";
  }
}

技术细节

unordered_set 的技术定义

std::unordered_set 是一个关联容器，包含一组类型为 Key 的唯一对象。

搜索、插入和移除具有平均常数时间复杂度。

在内部，元素不按任何特定顺序排序，而是组织成桶。元素放置在哪个桶中完全取决于其值的哈希。这允许快速访问单个元素，因为一旦计算出哈希，它就指向元素所放置的确切桶。

容器元素不能被修改（即使是非 const 迭代器），因为修改可能会改变元素的哈希并破坏容器。

std::unordered_set 符合 Container、AllocatorAwareContainer、UnorderedAssociativeContainer 的要求。