大二上数据结构与算法20241025

landboat / 2024-11-26 / 原文

1.红黑树

2.unordered_map（哈希表实现）

unordered_map 是 C++ 标准库中的一个容器，它基于哈希表实现，用于存储键值对（key-value pairs）。以下是 unordered_map 的一些基本用法和代码示例：

包含头文件

要使用 unordered_map，你需要包含 <unordered_map> 头文件。

    ##### #include <unordered_map>

声明 `unordered_map`

声明 unordered_map 时，需要指定键（key）和值（value）的类型。例如，如果你想存储整数键和字符串值，可以这样声明：

std::unordered_map<int, std::string> myMap;

插入元素

你可以使用 insert 成员函数或者 [] 运算符来插入元素。

// 使用 insert 成员函数
myMap.insert(std::make_pair(1, "one"));
myMap.insert(std::make_pair(2, "two"));

// 使用 [] 运算符
myMap[3] = "three";

访问元素

你可以通过键来访问对应的值。

std::cout << "Value for key 1: " << myMap[1] << std::endl;

查找元素

你可以使用 find 成员函数来查找元素。如果找到了，find 会返回一个指向该元素的迭代器；如果没有找到，它会返回 end()。

auto it = myMap.find(2);
if (it != myMap.end()) {
    std::cout << "Found key 2 with value: " << it->second << std::endl;
} else {
    std::cout << "Key 2 not found." << std::endl;
}

删除元素

你可以使用 erase 成员函数来删除元素，它可以接受一个键或者一个迭代器。

// 通过键删除
myMap.erase(2);

// 通过迭代器删除
auto it = myMap.find(3);
if (it != myMap.end()) {
    myMap.erase(it);
}

遍历 `unordered_map`

你可以使用迭代器来遍历 unordered_map 中的所有元素。

for (auto it = myMap.begin(); it != myMap.end(); ++it) {
    std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
}

完整的代码示例

下面是一个完整的示例，展示了如何使用 unordered_map：

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    // 创建一个 unordered_map，键为 int，值为 string
    std::unordered_map<int, std::string> myMap;

    // 插入元素
    myMap.insert(std::make_pair(1, "one"));
    myMap[2] = "two"; // 使用 [] 运算符

    // 访问元素
    std::cout << "Value for key 1: " << myMap[1] << std::endl;

    // 查找元素
    auto it = myMap.find(2);
    if (it != myMap.end()) {
        std::cout << "Found key 2 with value: " << it->second << std::endl;
    } else {
        std::cout << "Key 2 not found." << std::endl;
    }

    // 删除元素
    myMap.erase(2);

    // 检查元素是否被删除
    if (myMap.find(2) == myMap.end()) {
        std::cout << "Key 2 has been erased." << std::endl;
    }

    // 遍历 unordered_map
    std::cout << "Contents of myMap:" << std::endl;
    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    }

    return 0;
}

这个示例展示了如何声明 unordered_map，插入、访问、查找、删除元素，以及如何遍历 unordered_map。