C++ 无序映射

在 C++ 中，STL 的 unordered_map 是一个无序关联容器，它提供了无序映射或字典数据结构的功能。

与普通映射不同，无序映射中的键的顺序是未定义的。

此外，无序映射是作为哈希表数据结构实现的，而普通映射是二叉搜索树数据结构。

创建 C++ STL unordered_map

为了在 C++ 中创建无序映射，我们首先需要包含 unordered_map 头文件。

#include <unordered_map>

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

unordered_map<key_type, value_type> ump;

这里，

• key_type 表示 **键** 的数据类型
• value_type 表示 **值** 的数据类型

例如，

// create an unordered_map with integer key and value
unordered_map<int, int> ump_integer;

// create an unordered_map with string key and int value
unordered_map<string, int> ump_string;

初始化无序映射

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

// Initializer List 
unordered_map<string, int> unordered_map1 = {
  {"One", 1},
  {"Two", 2},
  {"Three", 3}
};

// Uniform Initialization
unordered_map<string, int> unordered_map2 {
  {"One", 1},
  {"Two", 2},
  {"Three", 3}
};

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

现在，unordered_map1 和 unordered_map2 都已初始化为 {{"One", 1}, {"Two", 2}, {"Three", 3}}。

示例：C++ unordered_map

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

int main() {

  // uniform initialization
  unordered_map<string, int> unordered_map1  {
  {"One", 1},
  {"Two", 2},
  {"Three", 3}
 };

  cout << "Key - Value" << endl;

  // loop across the unordered map
  // display the key-value pairs
  for(const auto& key_value: unordered_map1) {
    string key = key_value.first;
    int value = key_value.second;
    
    cout << key << " - " << value << endl;
  }
  
  return 0;
}

输出

Key - Value
Three - 3
Two - 2
One - 1

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

unordered_map<string, int> unordered_map1 {
  {"One", 1},
  {"Two", 2},
  {"Three", 3}
};

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

for(const auto& key_value: unordered_map1) {
  string key = key_value.first;
  int value = key_value.second;    
  cout << key << " - " << value << endl;
}

在上面的代码中，无序映射的每个元素（键值对）都存储在变量 key_value 中。

然后，我们通过以下方式获取键和值：

• key_value.first - 提供键
• key_value.second - 提供值

请注意，我们按键的顺序创建了无序映射："One"、"Two"、"Three"。但是，输出的顺序是未定义的。

这是因为元素不是根据键或值以任何特定顺序存储的。

for(const auto& [key, value]: unordered_map1) {
  cout << key << " -  " << value << endl; 
}

unordered_map<string, int> unordered_map_1 {
  {"One", 1},
  {"Two", 2},
  {"Three", 3}
};

unordered_map<string, int> unordered_map_2(unordered_map_1.begin(), unordered_map_1.end());

C++ Unordered Map 方法

在 C++ 中，unordered_map 类提供了多种方法来对无序映射执行不同的操作。

向无序映射插入键值对

我们可以使用以下方法向无序映射插入键值对：

• insert() - 插入键值对
• [] - 插入键和值

例如，

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

int main() {

  unordered_map<string, int> unordered_map1;
  
  // insert key-value pair {"One", 1}
  unordered_map1["One"] = 1;

  // insert a pair {"Two", 2}
  unordered_map1.insert({"Two", 2});

  // insert two pairs {"Three", 3}, {"Four", 4}	
  unordered_map1.insert({{"Three", 3}, {"Four", 4}});
  
  cout << "Key - Value" << endl;

  // display elements of unordered_map1   
  for(const auto& key_value: unordered_map1) {
    string key = key_value.first;
    int value = key_value.second;
    
    cout << key << " - " << value << endl;
  }
 
  return 0;
}

输出

Key - Value
Four - 4
Two - 2
Three - 3
One - 1

在上面的示例中，我们初始化了一个空的无序映射来存储字符串和整数的键值对。

然后，我们使用 [] 插入了对 {"One", 1}。

unordered_map1["One"] = 1;

然后，我们使用 insert() 方法插入了另一个对。

unordered_map1.insert({"Two", 2});

最后，我们使用 insert() 插入了两个对。

unordered_map1.insert({{"Three", 3}, {"Four", 4}});

访问无序映射的值

我们可以使用以下方法访问无序映射指定键的值

• at() - 返回指定键的值
• [] - 返回指定键的值

例如，

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

int main() {

  unordered_map<string, string> capital_city {
    {"Nepal", "Kathmandu"},
    {"India", "New Delhi"},
    {"Australia", "Canberra"}
  };
  
  cout << "Capital of Nepal is " << capital_city["Nepal"] << endl;
  cout << "Capital of Australia is " << capital_city.at("Australia");
  
  return 0;
}

输出

Capital of Nepal is Kathmandu
Capital of Australia is Canberra

在上面的例子中：

• capital_city["Nepal"] - 返回键为 "Nepal" 的元素
• capital_city.at("Australia") - 返回键为 "Australia" 的元素

// key "Japan" doesn't exist
// so the key "Japan" is paired with a garbage value
cout << "Capital of Japan is: " << capital_city["Japan"];

更改无序映射的值

我们可以使用 at() 方法或 [] 运算符来更改无序映射的值。例如，

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

int main() {

  unordered_map<string, string> capital_city {
    {"India", "Calcutta"},
    {"Pakistan", "Karachi"},
  };
  
  cout << "Old Capitals:" << endl;
  cout << "India : " << capital_city["India"] << endl;
  cout << "Pakistan : " << capital_city["Pakistan"];
 
  // change value for "India" using []
  capital_city["India"] = "New Delhi";

  // change value for "Pakistan" using at()
  capital_city.at("Pakistan") = "Islamabad";
  
  cout << "\n\nNew Capitals:" << endl;
  cout << "India : " << capital_city["India"] << endl;
  cout << "Pakistan : " << capital_city["Pakistan"];
  
  return 0;
}

输出

Old Capitals: 
India : Calcutta
Pakistan : Karachi

New Capitals: 
India : New Delhi
Pakistan : Islamabad

在上面的示例中，capital_city 的初始键值对是 {"India", "Calcutta"} 和 {"Pakistan", "Karachi"}。

然后，我们使用 [] 运算符通过以下方式更改键 "India" 的值：

capital_city["India"] = "New Delhi";

同样，我们使用 at() 方法更改键 "Pakistan" 的值，如下所示：

capital_city.at("Pakistan") = "Islamabad";

从无序映射中删除元素

我们可以使用 erase() 方法删除无序映射的指定键的元素。例如，

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

// function prototype for display_unordered_map()
void display_unordered_map(const unordered_map<int, string> &);

int main() {

  unordered_map<int, string> student {
    {111, "John"},
    {132, "Mark"},
    {143, "Chris"}
  };
  
  cout << "Initial Unordered Map:\n";
  display_unordered_map(student);

  // remove element with key: 143  
  student.erase(143);
  
  cout << "\nFinal Unordered Map: \n";
  display_unordered_map(student);

  return 0;
}

// utility function to print unordered_map elements
void display_unordered_map(const unordered_map<int, string> &umap){

  for(const auto& key_value: umap) {
    int key = key_value.first;
    string value = key_value.second;
    
    cout << key << " - " << value << endl;
  }
}

输出

Initial Unordered Map:
143 - Chris
132 - Mark
111 - John

Final Unordered Map: 
132 - Mark
111 - John

在上面的示例中，我们使用 erase() 方法从无序映射中删除一个元素。

最初，名为 student 的无序映射的内容是 {{"143": Chris}, {"132": Mark}, {"111": John}}。

然后，我们使用 erase() 方法删除了键为 143 的元素。

// removes element with the key 143
student.erase(143);

因此，最终内容变为 {{"132": Mark}, {"111": John}}。

注意：我们可以使用 clear() 方法删除无序映射的所有元素。

检查无序映射中是否存在键

我们可以使用以下方法检查无序映射中是否存在指定的键。

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

例如，

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

int main() {

  unordered_map<int, string> student{
      {111, "John"},
      {132, "Mark"},
      {143, "Chris"}
  };

  cout << "Using find():" << endl;
  cout << "Does id " << 143 << " exist? ";

  // find() returns student.end() if the key is not found 
  if (student.find(143) != student.end()) {
    cout << "Yes";
  }
  else {
    cout << "No";
  }

  cout << "\n\nUsing count():" << endl;
  cout << "Does id " << 1433 << " exist? ";

  // count() returns 0 if the key doesn't exist
  if (student.count(1433)) {
    cout << "Yes";
  }
  else {
    cout << "No";
  }

  return 0;
}

输出

Using find():
Does id 143 exist? Yes

Using count():
Does id 1433 exist? No

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

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

// checks if key 143 exists
if (student.find(143) != student.end()) {
  cout << "Yes";
}
else {
  cout << "No";
}

find() 方法返回一个指向元素（如果存在）的迭代器。如果键不存在，它将指向 end() 迭代器。

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

// checks if key 1433 exists
if (student.count(1433)) {
  cout << "Yes";
}
else {
  cout << "No";
}