企业官网建设流程全解析

一、set/multiset

1. 基本概念

• 头文件：#include <set>

• 定义：集合（set）和多重集合（multiset），用于存储键值（key）。

• 特点：

  • set：不允许重复元素，每个键唯一。插入重复元素会被忽略。

  • multiset：允许重复元素。

  • 默认会根据键值自动排序（升序，使用std::less<Key>）。

  • 底层结构通常是红黑树，查找、插入、删除的时间复杂度为O(log n)。

• 元素不可修改：一旦插入，键值不可直接修改（否则破坏有序性），需先删除再插入新值。

2. 常用成员函数

2.1 构造与赋值

set<int> s; // 空set set<int> s2 = {3,1,4,1,5}; // 初始化列表，结果{1,3,4,5} multiset<int> ms = {3,1,4,1,5}; // {1,1,3,4,5} set<int> s3(s.begin(), s.end()); // 迭代器范围构造

2.2 插入元素

// 插入单个值，返回 pair<iterator, bool> auto ret = s.insert(10); // ret.first 是迭代器，指向插入位置（或已存在的元素） // ret.second 为 bool：true表示插入成功，false表示元素已存在 // 提供位置提示（仅作优化，不强制插入位置） auto it = s.insert(s.begin(), 25); // 从 begin() 开始搜索，返回迭代器 // 插入区间 s.insert(other.begin(), other.end()); // multiset 的 insert 总是成功，返回指向新元素的迭代器（无 bool） auto it_ms = ms.insert(5);

2.3 删除元素

// 删除指定值：返回删除元素个数（set为0或1，multiset可>1） size_t count = s.erase(10); // 通过迭代器删除单个元素 s.erase(it); // 返回被删元素后一个位置的迭代器（C++11起） s.erase(s.begin(), s.end()); // 删除区间

2.4 查找

// find(): 返回迭代器，未找到返回 end() auto it = s.find(20); if (it != s.end()) { /* 找到了 */ } // count(): 元素出现的次数，set中只能是0或1，multiset中可以是任意值 int cnt = s.count(5); // lower_bound / upper_bound / equal_range auto lb = s.lower_bound(10); // 第一个 >=10 的元素 auto ub = s.upper_bound(10); // 第一个 >10 的元素 auto range = s.equal_range(10); // 返回 pair<iterator,iterator> 包含所有等于10的元素 // range.first == lower_bound(10), range.second == upper_bound(10)

2.5 容量与判空

s.empty(); // 是否为空 s.size(); // 元素数量 s.max_size(); // 可能容纳的最大元素数

2.6 迭代器

set<int>::iterator it = s.begin(); // 指向最小元素 auto rit = s.rbegin(); // 反向迭代器，指向最大元素 // 所有迭代器均为双向迭代器（Bidirectional），支持++、--，不支持随机访问 // 迭代过程按排序顺序遍历

2.7 观察器（获取比较函数等）

auto comp = s.key_comp(); // 返回键比较函数 auto val_comp = s.value_comp(); // 对于 set，等价于 key_comp

3. 自定义排序规则

set 的默认排序使用std::less<Key>，可以传递自定义仿函数或函数指针：

// 降序set set<int, greater<int>> s_desc = {1,3,2}; // {3,2,1} // 自定义结构体比较 struct Person { string name; int age; }; struct Cmp { bool operator()(const Person& a, const Person& b) const { return a.age < b.age; // 按年龄升序 } }; set<Person, Cmp> people;

注意：比较函数必须满足严格弱序（strict weak ordering），即不能出现a < b和b < a同时为 true 的情况。

4. 使用场景与注意点

• 自动去重 & 排序：需要有序且不重复的数据时用set。

• 允许重复的有序集合：用multiset，可用于实现优先队列等。

• 不可修改键值：如需修改，需删除后插入。

• 时间复杂度：插入/删除/查找均为 O(log n)。

二、map/multimap

1. 基本概念

• 头文件：#include <map>

• 定义：映射（字典），存储键值对（key-value）。

  • map：键唯一，不允许重复 key。

  • multimap：允许重复键。

• 默认按键升序排序。

• 底层通常为红黑树，操作复杂度 O(log n)。

• 元素类型：std::pair<const Key, T>，键不可修改（const），值可修改。

2. 常用成员函数

2.1 构造与赋值

map<string, int> m; // 空map map<string, int> m2 = {{"apple",3}, {"banana",5}}; map<string, int> m3(m2.begin(), m2.end()); multimap<string, int> mm;

2.2 插入元素

// 1. 使用 pair m.insert(pair<string, int>("peach", 7)); m.insert(make_pair("peach", 7)); m.insert({"peach", 7}); // C++11 初始化列表 // 2. insert 返回 pair<iterator, bool> auto ret = m.insert({"apple", 3}); if (!ret.second) { cout << "apple already exists, value = " << ret.first->second << endl; } // 3. 使用下标操作符（仅 map 支持，multimap 无此操作） m["orange"] = 8; // 若"orange"不存在，则插入{"orange", 8} // 若已存在，则修改其 value 为 8 // 注意：使用 m[key] 会先调用默认构造函数创建 value，然后赋值（多了一次构造） // 读取时若不存在会插入带默认值的元素，慎用！ // 4. emplace (C++11) 原地构造，更高效 m.emplace("grape", 12); // multimap 的 insert 和 emplace 都只返回指向新元素的迭代器（无 bool）

2.3 访问元素

// at(): 有边界检查，若 key 不存在抛出 std::out_of_range 异常 int val = m.at("apple"); // 下标操作符 []：若 key 不存在则插入默认值，返回 value 的引用 m["banana"] = 10; // 修改现有值 int x = m["nonexistent"]; // 插入 {"nonexistent", 0} // 遍历查找 auto it = m.find("apple"); if (it != m.end()) { cout << it->first << " -> " << it->second; }

2.4 删除元素

m.erase("apple"); // 按 key 删除，返回删除个数（map：0或1） m.erase(it); // 通过迭代器删除 m.erase(m.begin(), m.end());// 删除区间

2.5 其他查询

size_t cnt = m.count("key"); // map 只能是0或1，multimap可>1 auto lb = m.lower_bound("b"); // 第一个 key>="b" 的迭代器 auto ub = m.upper_bound("b"); auto range = m.equal_range("b"); // pair of iterators

2.6 容量与迭代

m.empty(); m.size(); m.max_size(); for (auto& p : m) { cout << p.first << " : " << p.second << endl; }

3. 自定义排序

与 set 类似，需提供比较键的仿函数：

struct DescCmp { bool operator()(const string& a, const string& b) const { return a > b; // 按 key 降序 } }; map<string, int, DescCmp> desc_map; // 对于 multimap 同理

4.map与multimap的区别

5. 实用技巧与注意事项

• 遍历删除：删除当前迭代器后，返回值可作为下一个迭代器（C++11前使用it++技巧）。

  for (auto it = m.begin(); it != m.end(); ) { if (condition) { it = m.erase(it); // C++11起返回下一个迭代器 } else { ++it; } }

• 避免不必要的默认构造：检查 key 是否存在时，不要使用m[key]，改用find()或count()。

• 键为常量：map<Key,T>::value_type是pair<const Key, T>，不能通过迭代器修改 key（因为 key 是 const）。如果需要修改 key，只能删除再插入。

• 性能对比：对于有序关联容器，红黑树保证了稳定的 O(log n)，若需要纯粹的快速查找且无需排序，考虑unordered_map/unordered_set（哈希表，平均 O(1)）。