C++ 无序集合

STL 的 unordered_set 是一个 无序关联容器，它提供了无序集合数据结构的功能。

与常规集合不同，无序集合中值的顺序是未定义的。

此外，无序集合是用 哈希表 数据结构实现的，而常规集合是用 二叉搜索树 数据结构实现的。

创建 C++ STL 无序集合

为了在 C++ 中创建无序集合，我们首先需要包含 unordered_set 头文件。

#include <unordered_set>

导入此文件后，我们可以使用以下语法创建无序集合

unordered_set<data_type> ust;

这里，data_type 表示无序集合值的.数据类型。

例如，

// create an unordered_set of integers
unordered_set<int> ust_integer;

// create an unordered_set of strings
unordered_set<string> ust_string;

初始化无序集合

我们可以通过以下方式初始化 C++ 无序集合

// Initializer List
unordered_set<int> unordered_set1 = {1, 100, 2, 9};

// Uniform Initialization
unordered_set<int> unordered_set2 {1, 100, 2, 9};

在这里，我们通过直接提供值来初始化无序集合。

现在，unordered_set1 和 unordered_set2 都已使用 {1, 100, 2, 9} 初始化。

示例：C++ unordered_set

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {

  // uniform initialization
  unordered_set<int> numbers {1, 100, 10, 70, 100};

  // loop across the unordered set
  // display the value
  cout << "numbers = ";
  for(auto &num: numbers) {
    cout << num << ", ";
  }

  return 0;
}

输出

numbers = 70, 10, 100, 1, 

在上面的示例中，我们使用统一初始化声明并初始化了一个名为 numbers 的无序集合。

unordered_set<int> numbers {1, 100, 10, 70, 100};

然后，我们使用 范围 for 循环 显示了无序集合的内容。

for(auto &num: numbers) {
  cout << num << ", ";
}

这里，我们按顺序初始化了无序集合：1、100、10、70、100。请注意，我们有一个重复值 100。

但在输出中，我们只获得了 **不重复的数字**，顺序不固定（升序、降序、插入顺序）。

// output numbers
70, 10, 100, 1,

unordered_set<string> unordered_set1 {"One", "Two", "Three"};

unordered_set<string> unordered_set2(unordered_set_1.begin(), unordered_set_1.end());

C++ unordered_set 方法

在 C++ 中，unordered_set 类提供了各种方法来对无序集合执行不同的操作。

向无序集合插入元素

我们可以使用 insert() 方法将元素插入到无序集合中。例如，

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {

  unordered_set<string> countries;

  // inserts "Nepal" into countries
  countries.insert("Nepal");

  // inserts "Nepal" , "India", "USA", "Korea" into countries
  countries.insert({"Nepal", "India", "USA", "Korea"});

  cout << "Countries = ";
  // display elements of countries
  for(const auto& country: countries) {
    cout << country << ", ";
  }
  return 0;
}

输出

Countries = Korea, USA, India, Nepal, 

在上面的示例中，我们初始化了一个空的无序集合来存储字符串。

然后，我们使用以下方式插入了元素 "Nepal"

countries.insert("Nepal");

然后，我们使用以下方式插入了多个元素

countries.insert({"Nepal", "India", "USA", "Korea"});

从无序集合中移除元素

我们可以使用 erase() 方法移除无序集合中具有指定值的元素。例如，

#include <iostream>
#include <unordered_set>
using namespace std;

// function prototype for display_unordered_set()
void display_unordered_set(const unordered_set<string> &);

int main() {

  unordered_set<string> languages {"C++", "Python", "Java", "PHP"};

  cout << "Initial unordered set:\n";
  display_unordered_set(languages);

  // remove element with value: "Python"  
  languages.erase("Python");

  cout << "\n\nFinal unordered set: \n";
  display_unordered_set(languages);

  return 0;
}

// utility function to print unordered_set elements
void display_unordered_set(const unordered_set<string> &uset) {
  for(const auto& value: uset) {
    cout << value << ", ";
  }
}

输出

Initial unordered set:
PHP, Java, Python, C++, 

Final unordered set: 
PHP, Java, C++,

在上面的示例中，我们使用 erase() 方法从无序集合中移除了一个元素。

最初，无序集合 languages 是 {"C++", "Python", "Java", "PHP"}。

然后，我们使用 erase() 方法移除了值为 "Python" 的元素。

// remove element with value: "Python"  
languages.erase("Python");

所以最终的无序集合变为 {"PHP", "Java", "C++"}。

注意： 我们可以使用 clear() 方法移除无序集合的所有元素。

检查值是否存在于无序集合中

我们可以使用以下方法检查元素是否存在于无序集合中。

• find() - 如果找到.值，则返回指向该元素的迭代器，否则返回 end() 迭代器
• count() - 如果.值存在，则返回 **1**；如果不存在，则返回 **0**

例如，

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {

  unordered_set<int> primes {2, 3, 5, 7, 11, 13};

  cout << "Using find():" << endl;
  cout << "Does number " << 12 << " exist? ";

  // find() returns primes.end() if the value is not found 
  if (primes.find(12) != primes.end()) {
    cout << "Yes";
  }
  else {
    cout << "No";
  }

  cout << "\n\nUsing count():" << endl;
  cout << "Does number " << 7 << " exist? ";

  // count() returns 0 if the value doesn't exist
  if (primes.count(7)) {
    cout << "Yes";
  }
  else {
    cout << "No";
  }

  return 0;
}

输出

Using find():
Does number 12 exist? No

Using count():
Does number 7 exist? Yes

在上面的示例中，我们使用了 find() 和 count() 来检查给定值是否存在于无序集合中。

最初，我们使用 find() 方法检查值 12 是否存在。

// checks if value 12 exists
if (primes.find(12) != primes.end()) {
  cout << "Yes";
}
else {
  cout << "No";
}

find() 方法在找到元素时返回指向该元素的迭代器。如果该值不存在，它将指向 end() 迭代器。

然后，我们使用 count() 方法检查值 7 是否存在。

// checks if value 7 exists
if (primes.count(7)) {
  cout << "Yes";
}
else {
  cout << "No";
}

获取无序集合的大小

我们可以使用 size() 方法获取无序集合的大小。这会给出 **唯一** 元素的总数。例如，

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {

  unordered_set<int> numbers {1, 100, 10, 70, 100};
  
  cout << "Size: " << numbers.size();
  
  return 0;
}

输出

Size: 4

在上面的示例中，我们使用 size() 方法获取了唯一元素的总数。

请注意，我们使用元素 1、100、10、70、100 初始化了无序集合。但无序列表的大小是 **4**。

这是因为元素 100 有重复，所以实际上只有 4 个唯一元素，而不是 5 个。