在C++ STL中的unordered_map

unordered_map是C++ STL中用于描述哈希表的容器之一，它可以在O(1)的时间复杂度内完成查找、插入和删除等操作。本文将介绍unordered_map的基本操作和使用方法，以及一些应用场景。

基本操作

插入元素

我们可以用以下方式向unordered_map中插入元素：

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

int main() {
    unordered_map<string, int> umap;
    umap["apple"] = 1;
    umap["banana"] = 2;
    umap.insert({"orange", 3});
    return 0;
}

上述代码中，我们定义了一个无序映射umap，其中键类型为string，值类型为int。然后我们通过[]操作符和insert函数向umap中插入了三个元素。需要注意的是，如果umap中已经存在相同的键，插入操作将会失败。

访问元素

我们可以通过[]操作符或者at函数访问unordered_map中的元素。[]操作符在访问不存在的键时，会自动插入一个默认值。而at函数在访问不存在的键时，会抛出一个out_of_range异常。

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

int main() {
    unordered_map<string, int> umap = {{"apple", 1}, {"banana", 2}, {"orange", 3}};
    cout << umap["apple"] << endl;  // 输出1
    cout << umap["watermelon"] << endl;  // 输出0
    cout << umap.at("banana") << endl;  // 输出2
    umap.at("watermelon");  // 抛出out_of_range异常
    return 0;
}

删除元素

我们可以通过erase函数删除unordered_map中的元素。erase函数可以删除给定键的元素，或者删除一个迭代器指向的元素。如果要删除所有元素，我们可以使用clear函数。

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

int main() {
    unordered_map<string, int> umap = {{"apple", 1}, {"banana", 2}, {"orange", 3}};
    umap.erase("apple");
    auto iter = umap.find("banana");
    umap.erase(iter);
    umap.clear();
    return 0;
}

遍历元素

我们可以使用范围for循环或者迭代器遍历unordered_map中的元素。

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

int main() {
    unordered_map<string, int> umap = {{"apple", 1}, {"banana", 2}, {"orange", 3}};
    for (auto& p : umap) {
        cout << p.first << ": " << p.second << endl;
    }
    auto iter = umap.begin();
    while (iter != umap.end()) {
        cout << iter->first << ": " << iter->second << endl;
        iter++;
    }
    return 0;
}

其他操作

unordered_map还支持以下操作：

size()：返回unordered_map中元素的个数。
empty()：检查unordered_map是否为空。
count(key)：返回unordered_map中具有给定键的元素的个数。
find(key)：返回一个迭代器指向具有给定键的元素。如果无法找到，返回umap.end()。
bucket_count()：返回哈希表中的桶的数量。
max_bucket_count()：返回哈希表可容纳的最大桶数。

应用场景

统计单词出现频率

在一些字符串处理的场景下，我们需要统计一段文本中各个单词出现的频率。unordered_map可以轻松实现这一功能。

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

int main() {
    unordered_map<string, int> word_count;
    string text = "This isa test, this is only a test.";
    istringstream iss(text);
    string word;
    while (iss >> word) {
        word_count[word]++;
    }
    for (auto& p : word_count) {
        cout << p.first << ": " << p.second << endl;
    }
    return 0;
}

上述代码中，我们将字符串text中的单词逐个读取出来，并将其插入到word_count中。最后，我们遍历word_count，输出每个单词出现的次数。

实现LRU缓存

LRU（Least Recently Used）指的是最近最少使用的页面置换算法。在内存不足时，通过该算法可以选择那些近期最少使用的页面予以淘汰，从而释放内存空间。我们可以使用unordered_map和双向链表结合的方式实现一个LRU缓存。

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

class LRUCache {
public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        auto iter = umap.find(key);
        if (iter == umap.end()) {
            throw invalid_argument("key not exist");
        }
        int val = iter->second->second;
        lru_list.erase(iter->second);
        lru_list.push_front({key, val});
        umap[key] = lru_list.begin();
        return val;
    }

    void put(int key, int value) {
        auto iter = umap.find(key);
        if (iter != umap.end()) {
            lru_list.erase(iter->second);
        }
        else if (lru_list.size() == cap) {
            umap.erase(lru_list.back().first);
            lru_list.pop_back();
        }
        lru_list.push_front({key, value});
        umap[key] = lru_list.begin();
    }

private:
    int cap;
    list<pair<int, int>> lru_list;
    unordered_map<int, list<pair<int, int>>::iterator> umap;
};

int main() {
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl;  // 输出1
    cache.put(3, 3);
    try {
        cache.get(2);
    }
    catch (invalid_argument& e) {
        cout << e.what() << endl;  // 输出key not exist
    }
    return 0;
}

上述代码中，我们定义了一个LRUCache类，其中使用了一个双向链表lru_list来存储键值对，以及一个unordered_map umap来存储每个key所对应的链表中的节点位置。在get和put操作中，我们都需要将被操作的节点移到链表头部并更新umap。如果链表已满，在进行插入操作时，我们需要先删除链表尾部的节点。