[leetcode]map和unodered_map的使用场景

一.使用场景总结

1.1 std::map 的使用场景

1. 需要按键值排序：当需要按键值进行排序时，std::map 是一个很好的选择。例如，统计字符出现次数并按字符的ASCII值排序输出。

2. 频繁的范围查询：如果需要频繁地进行范围查询（如查找某个区间内的键值对），std::map 的有序性可以方便地进行范围查询。

3. 需要保持插入顺序：虽然 std::map 是按键值排序的，但如果你需要保持插入顺序，可以结合其他数据结构使用。

1.2 std::unordered_map 的使用场景

1. 快速查找、插入和删除：当需要快速的查找、插入和删除操作时，std::unordered_map 的平均 O(1) 时间复杂度非常有优势。例如，在两数之和问题中，快速查找目标值的补数。

2. 不关心顺序：如果键值对的顺序不重要，只是需要快速访问键值对，std::unordered_map 是更好的选择。

3. 大数据量的场景：在处理大数据量时，std::unordered_map 的高效性能可以显著提升程序的运行速度。

二.map和unordered_map使用场景的举例

  std::map 和 std::unordered_map 是 C++ 中两个常用的关联容器，它们都用于存储键值对，但在实现原理、性能和使用场景上有所不同。下面分别介绍它们的用途，并通过简单的算法题来演示它们的使用，最后总结它们的使用场景。

2.1 std::map

std::map 是基于红黑树（一种自平衡二叉搜索树）实现的，因此它具有以下特点：

• 有序性：键值对会按照键的值进行排序（默认是升序）。

• 查找、插入和删除的时间复杂度：均为 O(logn)。

算法题示例：统计字符串中每个字符出现的次数，并按字符的ASCII值排序输出

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() {
    string s = "hello world";
    map<char, int> charCount;

    // 统计每个字符出现的次数
    for (char c : s) {
        charCount[c]++;
    }

    // 按字符的ASCII值排序输出
    for (const auto& pair : charCount) {
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

2.2 std::unordered_map

std::unordered_map 是基于哈希表实现的，因此它具有以下特点：

• 无序性：键值对不按任何顺序存储。

• 查找、插入和删除的时间复杂度：平均情况下为 O(1)，最坏情况下为 O(n)（哈希冲突严重时）。

算法题示例：两数之和

给定一个整数数组 nums 和一个目标值 target，请找到数组中和为目标值的两个数的索引。

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> numMap;
    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i];
        if (numMap.find(complement) != numMap.end()) {
            return {numMap[complement], i};
        }
        numMap[nums[i]] = i;
    }
    return {};
}

int main() {
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    vector<int> result = twoSum(nums, target);
    
    cout << "Indices: " << result[0] << ", " << result[1] << endl;
    
    return 0;
}