企业官网建设流程全解析

前言

std::map和std::set是标准库里的有序关联容器（ordered associative container）。set存不重复的键，map存键值对；两者都按比较器排好序，查找、插入、删除的复杂度都是对数级。它们底层通常实现为平衡二叉搜索树（主流实现是红黑树），但标准只规定接口和复杂度，不规定具体树形。

典型误解有三个。第一，把std::map当成哈希表；哈希表是std::unordered_map，map保证有序遍历，unordered_map不保证。第二，用m[key]做「只读查找」；如果键不存在，operator[]会插入一个默认构造的值，查找变成了写入。第三，以为insert会覆盖已有值；对map来说，键已存在时insert什么都不做，返回的bool是false。

本文按「共同模型—set—map—自定义比较器—与无序容器对比」展开，最后给出一个词频统计与排序的完整例子。代码基准为 C++17。

一、共同的模型：有序、节点式、对数复杂度

四个有序关联容器：

共同特性：

• 
  
• 有序。默认按std::less<Key>排序，遍历顺序是键的升序（对自定义类型则按比较器定义的顺序）。
• 
  
• 节点式。每个元素单独分配一个节点，节点里保存键、值（对map）和树结构所需的指针。插入不会使其他元素的迭代器失效；删除只使被删元素的迭代器失效。
• 
  
• 双向迭代器。可以++、--，但不支持随机访问（没有it + n）。
• 
  
• 对数复杂度。find、count、insert、erase、lower_bound、upper_bound都是 O(log n)。
• 
  
• 键不可变。set的元素整体是 const；map的元素类型是std::pair<const Key, T>，键不能改，值可以改。
• 
  

因为键不可变，想「修改」一个set元素或map的键，只能先删除再插入；C++17 提供了extract，可以取出节点、改键后再插回，避免重新分配：

// 适用于 C++17
#include <map>
#include <string>
#include <utility>

void rename_key(std::map<std::string, int>& m,
const std::string& oldKey,
const std::string& newKey) {
auto node = m.extract(oldKey); // 取出节点，不销毁
if (node.empty()) {
return; // 键不存在
}
node.key() = newKey; // 修改键
m.insert(std::move(node)); // 插回
}

二、set：去重与有序集合

std::set的核心操作：

用insert的返回值可以同时完成「插入」和「判断是否已存在」：

// 适用于 C++17
#include <set>
#include <string>

bool add_unique(std::set<std::string>& names, const std::string& name) {
const auto result = names.insert(name);
return result.second; // true 表示之前不存在，本次插入成功
}

set最常见的用途是去重。把一段数据全部insert，重复元素会被自动忽略；遍历set得到的是升序结果。如果只关心「是否存在」而不关心顺序，std::unordered_set的平均查找是常数级，通常更快。

区间查询用lower_bound和upper_bound配合：

// 适用于 C++17
#include <set>

void print_range(const std::set<int>& values, int low, int high) {
// [low, high] 闭区间：从第一个 >= low 到第一个 > high
for (auto it = values.lower_bound(low);
it != values.upper_bound(high); ++it) {
// *it 在范围内
}
}

注意upper_bound(high)每次循环条件都会重新计算，虽然它是对数复杂度，但放在循环里仍然浪费。更好的写法是先保存终点迭代器。另外，set的迭代器是双向的，不能写成it + 1。

三、map：键值映射与几个易混接口

std::map的元素类型是std::pair<const Key, T>。遍历时可以用结构化绑定（C++17）：

// 适用于 C++17
#include <iostream>
#include <map>
#include <string>

void dump(const std::map<std::string, int>& m) {
for (const auto& [key, value] : m) {
std::cout << key << " => " << value << '\n';
}
}

3.1 operator[] 会插入

// 适用于 C++17
#include <map>
#include <string>

std::map<std::string, int> scores;
scores["alice"] = 90; // 键不存在：插入 (alice, 0)，再赋值为 90
int a = scores["alice"]; // 已存在：返回引用
int b = scores["bob"]; // 不存在：插入 (bob, 0)，b 为 0

最后一行是陷阱：只想读取，却意外增加了元素。只读查找用find或at：

// 适用于 C++17
auto it = scores.find("carol");
if (it != scores.end()) {
int value = it->second;
}

// 或者：不存在时抛 std::out_of_range
int value = scores.at("carol");

operator[]还要求mapped_type可默认构造，因为它必须先造一个值再返回引用。at没有这个要求，但键不存在时抛异常。C++17 的try_emplace则只在键不存在时构造值，避免不必要的临时对象：

// 适用于 C++17
auto [it, inserted] = scores.try_emplace("dave", 75);

3.2 insert 不覆盖已有值

// 适用于 C++17
std::map<std::string, int> m;
m.insert({"alice", 90});
m.insert({"alice", 100}); // 键已存在，什么也不做
// m["alice"] 仍是 90

要「存在则覆盖、不存在则插入」，有三种写法：

• 
  
• m[key] = value;：简单，但要求值可默认构造，且会先构造再赋值。
• 
  
• m.insert_or_assign(key, value);（C++17）：语义最直接，返回pair<iterator, bool>。
• 
  
• 先find，再决定赋值或emplace：控制最细，但代码更长。
• 
  

3.3 erase 的正确写法

删除指定键：m.erase(key)，返回删除个数。删除迭代器指向的元素时，C++11 起erase返回下一个迭代器：

// 适用于 C++17
for (auto it = m.begin(); it != m.end(); ) {
if (it->second == 0) {
it = m.erase(it); // 用返回值继续
} else {
++it;
}
}

如果写成m.erase(it); ++it;，it在erase之后已经失效，再自增是未定义行为。

3.4 用 emplace 构造复杂值

emplace把参数直接转发给元素类型的构造函数，省去临时pair：

// 适用于 C++17
#include <map>
#include <string>
#include <vector>

std::map<std::string, std::vector<int>> groups;
groups.emplace("evens", std::vector<int>{2, 4, 6});

对map，emplace的实参需要能构造pair<const Key, T>；即使键已存在，待插入的元素也可能被构造后立即销毁，所以实参的构造开销省不掉。try_emplace则保证键存在时连 mapped 值都不构造，对昂贵的值类型更友好。

四、比较器、无序容器与完整示例

map和set的第三个模板参数是比较器类型，默认std::less<Key>。自定义比较器必须满足严格弱序（strict weak ordering）：

• 
  
• 对任意 a，comp(a, a)必须为false（非自反）；
• 
  
• 若comp(a, b)为真，则comp(b, a)必须为假（非对称）；
• 
  
• 传递性；
• 
  
• 等价关系可传递。
• 
  

用<=作为比较器会破坏非自反性，属于未定义行为——std::sort、std::set、std::map都要求严格弱序，这不是「结果可能不太对」，而是标准明确规定的 UB。

按长度给字符串排序的set：

// 适用于 C++17
#include <set>
#include <string>

struct ByLength {
bool operator()(const std::string& a, const std::string& b) const {
if (a.size() != b.size()) {
return a.size() < b.size();
}
return a < b; // 长度相同时按字典序，保证严格弱序
}
};

std::set<std::string, ByLength> words;

如果只按长度比较、长度相同就返回false，那么两个等长但内容不同的字符串会被视为「等价」，set会认为它们重复，只保留其中一个。加上字典序作为次级比较，才能既按长度排序又保留所有不同字符串。

比较器是有状态的也可以：把状态存在比较器对象里，构造容器时传入实例。注意比较器会被拷贝，状态变化不会反映到容器中，所以不要写依赖可变状态的比较逻辑。

C++14 起可以用透明比较器std::less<>支持异质查找（heterogeneous lookup），例如用const char*直接在std::set<std::string>里查找而不构造临时std::string：

// 适用于 C++17
#include <functional>
#include <set>
#include <string>

std::set<std::string, std::less<>> names;
names.insert("alice");
auto it = names.find("alice"); // 不构造临时 std::string（C++14 起）

与无序容器怎么选

选择标准很直接：需要按序遍历、范围查询、稳定最坏复杂度，用map/set；只做点查找、不关心顺序、有合适的哈希函数，用无序版本。不要因为「哈希是 O(1)」就无脑选unordered_map——它的常数并不小，最坏情况还会退化，而且std::hash对自定义类型需要自己特化。

完整示例：词频统计并按键值排序

下面的例子统计单词出现次数，再把结果按「次数降序、单词升序」输出。map负责去重和计数，vector负责按值排序，这是两者最常见的配合方式。

// 适用于 C++17
#include <algorithm>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

std::map<std::string, int> count_words(const std::string& text) {
std::map<std::string, int> freq;
std::istringstream iss(text);
std::string word;
while (iss >> word) {
++freq[word]; // 不存在时插入 0，再自增
}
return freq;
}

int main() {
const std::string text = "apple banana apple cherry banana apple";
auto freq = count_words(text);

std::vector<std::pair<std::string, int>> ranked(freq.begin(), freq.end());
std::sort(ranked.begin(), ranked.end(),
[](const auto& lhs, const auto& rhs) {
if (lhs.second != rhs.second) {
return lhs.second > rhs.second; // 次数降序
}
return lhs.first < rhs.first; // 同次数按单词升序
});

for (const auto& [word, count] : ranked) {
std::cout << word << ' ' << count << '\n';
}
return 0;
}

几个检查点：freq[word]在这里是合适的，因为确实需要「不存在就插入」。std::vector的区间构造接受两个迭代器，把map的pair<const std::string, int>转成pair<std::string, int>需要一次拷贝，这是允许的。排序 lambda 必须满足严格弱序：次数相等时用单词比较兜底，两个条件覆盖了所有不等情况，相等时返回false。

如果单词量很大且只取前 K 个，全量排序就浪费了；可以用std::partial_sort或维护一个大小为 K 的小顶堆。具体选择取决于数据规模和 K 的大小，应当按复杂度分析而不是凭感觉。

常见坑点

1. 
   
2. ❌ 用m[key]做「查一下有没有」，结果容器里多出一堆默认值。
3. 
   

✅ 只读用find或at；operator[]的语义是「不存在就插入」。

1. 
   
2. ❌ 以为m.insert({key, value})会覆盖旧值。
3. 
   

✅ 键已存在时insert不修改；要覆盖用insert_or_assign（C++17）或m[key] = value。

1. 
   
2. ❌ 比较器写成return a <= b;。
3. 
   

✅ 必须是严格弱序，用<；<=违反非自反性，行为是未定义。

1. 
   
2. ❌ 遍历时m.erase(it); ++it;。
3. 
   

✅it = m.erase(it);，使用返回的下一个迭代器。

1. 
   
2. ❌ 试图修改set里的元素，或修改map的键。
3. 
   

✅ 键是 const；删除后重新插入，或 C++17 用extract取出节点改键再插回。

1. 
   
2. ❌ 认为std::map的遍历顺序是插入顺序。
3. 
   

✅ 遍历顺序由比较器决定，默认是键升序；需要插入顺序得另存一个vector。

1. 
   
2. ❌ 用std::map却对每个元素再调用一次find，把 O(n log n) 的操作做成 O(n log² n)。
3. 
   

✅ 直接遍历迭代器，或用lower_bound加 hint 插入；已有迭代器就不要重新查。

1. 
   
2. ❌ 把指针作为map的键，期待按指向的内容排序。
3. 
   

✅ 默认比较的是地址；需要内容比较就自定义比较器，或用std::string/值类型作键。

总结

map和set的接口不难，难的是记住每个操作对「已存在的键」采取什么策略：operator[]插入、insert忽略、insert_or_assign覆盖、try_emplace不构造。把这四个语义分清，再守住比较器的严格弱序和迭代器失效规则，日常使用基本不会出问题。