如何在C++ STL map中删除重复值条目（保留首个键对应条目）

嘿，我来帮你搞定这个需求！要在STL map里删除值重复的条目，只保留每个值对应的第一个出现的键（也就是按map默认的键升序排列最早的那个，比如你的例子里保留'a'而非'e'，保留'd'而非'f'、'h'），同时追求时间和空间复杂度最优，咱们可以用这个高效的方案：

核心思路 #

因为std::map本身是有序容器（默认按键的升序存储），所以每个值第一次出现时对应的键就是我们要保留的那个。我们只需要遍历一次map，用一个哈希集合记录已经见过的值：

• 遇到没见过的值：把它加入集合，继续遍历下一个元素
• 遇到已经见过的值：直接删除当前条目

要注意的是，遍历map时删除元素不能用普通的for循环，否则会导致迭代器失效，得用erase()的返回值来更新迭代器。

完整代码示例 #

#include <iostream>
#include <map>
#include <unordered_set>

int main() {
    // 初始化你的map
    std::map<char, int> mymap = {
        {'a', 111}, {'b', 567}, {'c', 956}, {'d', 222},
        {'e', 111}, {'f', 222}, {'h', 222}, {'i', 492}
    };

    std::unordered_set<int> seen_values;
    auto it = mymap.begin();

    while (it != mymap.end()) {
        if (seen_values.find(it->second) != seen_values.end()) {
            // 值已存在，删除当前元素，迭代器指向erase返回的下一个元素
            it = mymap.erase(it);
        } else {
            // 值未出现过，加入集合，迭代器后移
            seen_values.insert(it->second);
            ++it;
        }
    }

    // 打印处理后的结果验证
    for (const auto& pair : mymap) {
        std::cout << "<'" << pair.first << "', " << pair.second << "> ";
    }
    return 0;
}

运行这段代码后，输出会是：<'"a", 111> <'"b", 567> <'"c", 956> <'"d", 222> <'"i", 492>，完全符合你的要求。

复杂度分析 #

• 时间复杂度：平均O(n)。map的遍历是O(n)，unordered_set的insert和find操作平均都是O(1)，所以整体平均时间复杂度是线性的，这是能达到的最优水平。
• 空间复杂度：O(k)，其中k是map中不同值的数量。我们必须记录已经出现过的值，这是无法避免的最小空间开销，所以也是最优的。

为什么不用std::set？ #

可能有人会想到用std::set来记录见过的值，但set的插入和查找是O(logk)的时间复杂度，整体会变成O(n logk)，比用unordered_set的平均O(n)要慢，所以优先选哈希集合。

内容的提问来源于stack exchange，提问作者devdebug