C++关联容器map与set：红黑树实现、性能对比与实战应用

1. 容器选择为什么是 map 和 set在 C 的日常开发里处理数据集合是家常便饭。数组和向量vector固然好用但当你需要快速判断某个元素是否存在或者需要根据一个特定的“键”来查找对应的“值”时它们就显得力不从心了。这时候std::map和std::set就该登场了。很多刚接触它们的朋友容易把这两个容器和vector混为一谈觉得不过是另一种存东西的“盒子”。但实际上它们背后的设计和应用场景有着本质的区别。简单来说std::set是一个“纯集合”。它的核心任务是确保唯一性并维护某种有序性对于标准set而言。你可以把它想象成一个数学上的集合或者一个不允许重复元素的、自动排好队的清单。当你需要快速检查“某个身份证号是否已经登记过”、“某个单词是否出现在词典里”时set是你的首选。它的元素既是“键”也是“值”你存入什么取出的就是什么。而std::map则是一个“键值对字典”。它存储的是成对的数据一个唯一的“键”key对应一个“值”value。这就像一本电话簿你通过“人名”键去查找对应的“电话号码”值。map同样保证了键的唯一性和有序性。它的强大之处在于提供了基于键的快速访问、插入和删除操作。那么为什么选择它们而不是自己用数组实现查找核心在于效率。无论是map还是set在标准库的实现中通常是红黑树它们的查找、插入和删除操作的平均时间复杂度都是O(log n)。这意味着即使数据量增长到十万、百万级别操作所需时间的增长也非常缓慢。相比之下在无序数组中查找一个元素是 O(n) 的线性时间数据量大时性能差距是指数级的。这种效率优势是它们在 C 中被广泛使用的根本原因。1.1 理解底层红黑树与有序性当你使用#include map和#include set引入的std::map和std::set时你使用的是基于红黑树的实现。这是一种自平衡的二叉搜索树。理解这一点至关重要因为它直接决定了容器的几个关键特性自动排序元素对于set或键对于map会按照严格的弱序默认是std::less即升序自动排列。当你遍历容器时元素是有序输出的。查找效率红黑树保持了大致平衡使得从根节点到任意叶子节点的最长路径不会超过最短路径的两倍从而保证了 O(log n) 的稳定性能。迭代器稳定性除了被删除的元素指向其他元素的迭代器、引用和指针在插入操作后通常不会失效这与vector在扩容时迭代器全部失效形成鲜明对比。但是有序性也带来了成本每次插入和删除都可能需要旋转和重新着色来维持树的平衡。如果你不需要元素有序C11 引入了std::unordered_map和std::unordered_set它们基于哈希表实现能提供平均 O(1) 的查找性能但元素是无序的。选择有序还是无序是使用关联容器的第一个决策点。注意std::map和std::set的“有序性”是默认且强制的。如果你在项目中需要一个“不重复的集合”但又不关心顺序并且对查找性能有极致要求那么std::unordered_set往往是更好的选择。同理对于键值对考虑std::unordered_map。2. std::set 集合去重与判重的利器std::set是一个关联容器它包含唯一的键key并且键本身也是值value。它的主要用途就是维护一个不重复的集合并支持高效的成员查询。2.1 基础操作与初始化让我们从一个简单的例子开始看看set如何工作#include iostream #include set #include vector int main() { // 初始化一个空的 set std::setint mySet; // 插入元素 mySet.insert(3); mySet.insert(1); mySet.insert(4); mySet.insert(1); // 重复插入会被忽略 mySet.insert(5); // 范围插入 (C11) std::vectorint vec {2, 7, 2, 8}; mySet.insert(vec.begin(), vec.end()); // 插入 2, 7, 8 // 遍历并观察自动排序和去重 std::cout Set elements: ; for (int num : mySet) { std::cout num ; // 输出: 1 2 3 4 5 7 8 } std::cout std::endl; // 查找元素 auto it mySet.find(4); if (it ! mySet.end()) { std::cout Found element: *it std::endl; } else { std::cout Element not found. std::endl; } // 检查元素是否存在 (C20 更简洁) // if (mySet.contains(4)) { ... } // 删除元素 mySet.erase(3); // 通过值删除 auto eraseIt mySet.find(7); if (eraseIt ! mySet.end()) { mySet.erase(eraseIt); // 通过迭代器删除 } return 0; }从输出可以看到无论我们以什么顺序插入set中的元素总是按照升序排列并且重复的1和2只出现了一次。find操作返回一个迭代器如果找到则指向该元素否则指向end()。2.2 自定义比较函数与结构体存储默认的set使用std::lessKey进行比较这对于基础数据类型和定义了运算符的类足够了。但如果你想存储自定义结构体或者想改变排序规则例如降序就需要提供自定义的比较方式。场景我们需要管理一组学生每个学生有学号id和姓名name并希望按照学号从大到小排序。#include iostream #include set #include string struct Student { int id; std::string name; // 为了方便输出重载 运算符 friend std::ostream operator(std::ostream os, const Student s) { os [ s.id : s.name ]; return os; } }; // 方法一定义一个仿函数函数对象作为比较器 struct CompareByDescendingId { bool operator()(const Student a, const Student b) const { return a.id b.id; // 降序学号大的排在前面 } }; int main() { // 使用自定义比较器的 set std::setStudent, CompareByDescendingId studentSet; studentSet.insert({101, Alice}); studentSet.insert({103, Bob}); studentSet.insert({102, Charlie}); studentSet.insert({101, Alice}); // 重复id不会被插入 std::cout Students sorted by ID (descending):\n; for (const auto stu : studentSet) { std::cout stu std::endl; } // 输出: [103: Bob] [102: Charlie] [101: Alice] // 方法二使用 Lambda 表达式 (C11) // 注意Lambda 的类型需要被捕获通常用于局部或作为函数参数传递。 // 直接定义 set 类型时需要 decltype 和构造函数传递比较器实例稍显复杂。 // 更常见的做法是使用 std::function 或直接传递函数指针如果比较逻辑简单。 return 0; }实操心得为自定义类型使用set时关键是要确保比较规则满足严格弱序。简单说就是不能出现a b和b a同时为真的情况并且如果!(a b) !(b a)则认为a和b等价对于set就是重复。对于上面的Student我们只比较id所以两个id相同但name不同的学生会被视为“等价”而无法同时存入。如果业务上需要id和name都相同才算重复就需要在比较函数里同时判断两者。2.3 进阶用法lower_bound 与 upper_bound这两个成员函数在处理有序区间时非常强大常用于范围查询。lower_bound(key)返回指向第一个不小于key的元素的迭代器。upper_bound(key)返回指向第一个大于key的元素的迭代器。它们通常成对使用来获取一个左闭右开区间[lower_bound, upper_bound)这个区间包含了所有等于key的元素如果存在的话。#include iostream #include set int main() { std::setint s {10, 20, 20, 20, 30, 40, 50}; int key 20; auto low s.lower_bound(key); // 指向第一个 20 auto up s.upper_bound(key); // 指向 30 std::cout Elements equal to key : ; for (auto it low; it ! up; it) { std::cout *it ; // 输出: 20 20 20 } std::cout std::endl; // 更简洁的方法equal_range它返回一个 pairlower_bound, upper_bound auto range s.equal_range(key); std::cout Using equal_range: ; for (auto it range.first; it ! range.second; it) { std::cout *it ; } std::cout std::endl; // 查找一个不存在的键的范围 key 25; low s.lower_bound(key); // 指向 30 (第一个不小于25的) up s.upper_bound(key); // 也指向 30 (第一个大于25的) if (low up) { std::cout No element equal to key found. std::endl; } return 0; }这个特性使得set不仅可以用于判重还能高效地进行区间统计和范围查找例如在游戏排行榜中查找某个分数区间的所有玩家。3. std::map 字典键值关联的基石如果说set是“是否存在”的检查器那么map就是“是什么”的查询表。它将唯一的键与特定的值绑定在一起形成键值对std::pairconst Key, Value。3.1 基础操作插入、访问与更新map最核心的操作就是通过键来访问或修改对应的值。#include iostream #include map #include string int main() { // 初始化一个 map键是字符串值是整数 std::mapstd::string, int wordCount; // 插入键值对 wordCount.insert({apple, 1}); // 方法1: 使用 initializer_list wordCount.insert(std::make_pair(banana, 2)); // 方法2: 使用 make_pair wordCount[cherry] 3; // 方法3: 使用下标运算符最常用 // 访问元素 std::cout Count of apple: wordCount[apple] std::endl; // 输出: 1 std::cout Count of banana: wordCount.at(banana) std::endl; // 输出: 2 // 使用 at() 与下标运算符 [] 的关键区别 // 1. at(key): 如果 key 不存在会抛出 std::out_of_range 异常。 // 2. operator[](key): 如果 key 不存在会使用默认构造函数创建一个 value 并插入然后返回其引用。 // 因此[] 运算符在“读”的同时可能执行“写”操作这是一个易踩的坑。 // 示例使用 [] 访问不存在的键 std::cout Count of durian: wordCount[durian] std::endl; // 输出: 0 (int的默认值) // 此时map 中已经自动插入了键 durian其值为 0。 std::cout Map size after accessing durian: wordCount.size() std::endl; // 大小增加了 // 安全的查找使用 find auto it wordCount.find(elderberry); if (it ! wordCount.end()) { std::cout Found: it-first - it-second std::endl; } else { std::cout Elderberry not found. std::endl; // 会执行这里 } // 更新值 wordCount[apple] 5; // 直接赋值更新 wordCount[banana]; // 递增操作 // 遍历 map std::cout \nAll word counts:\n; for (const auto kvPair : wordCount) { // kvPair 是 std::pairconst std::string, int std::cout kvPair.first : kvPair.second std::endl; } // 输出顺序按键的字母升序排列 return 0; }3.2 插入操作的语义与效率考量向map中插入元素有几种方法它们的语义和效率有细微差别。#include map #include string int main() { std::mapint, std::string m; // 方法1: insert make_pair auto ret1 m.insert(std::make_pair(1, One)); // ret1 是一个 std::pairiterator, bool // ret1.first 是指向插入元素或阻止插入的已存在元素的迭代器 // ret1.second 是一个 bool表示插入是否成功true表示新插入false表示键已存在 // 方法2: insert 初始化列表 (C11) auto ret2 m.insert({2, Two}); // 方法3: emplace (C11) - 原地构造避免临时对象拷贝/移动通常更高效 auto ret3 m.emplace(3, Three); // 参数直接传递给 pair 的构造函数 // 方法4: operator[] - 如果键不存在先插入默认值再赋值可能多一步构造 m[4] Four; // 等价于先 m.insert({4, std::string()})再赋值 Four // 检查插入结果 if (ret1.second) { std::cout Inserted key 1 successfully. std::endl; } // 尝试插入一个已存在的键 auto ret4 m.insert({1, ONE}); // 键1已存在插入失败 if (!ret4.second) { std::cout Key 1 already exists with value: ret4.first-second std::endl; } // 使用 emplace_hint (C11) - 提供插入位置提示可能提升性能 // 需要提供一个迭代器作为“提示”表示新元素可能插入在它附近 auto hint m.find(2); if (hint ! m.end()) { // 假设我们想在2后面插入但键是5提示可能无效实现会自行优化 m.emplace_hint(hint, 5, Five); } return 0; }注意事项在性能敏感的循环中插入大量元素时优先考虑emplace。如果你能提供一个好的位置提示例如你知道正在按顺序插入键emplace_hint可以带来小幅性能提升。但大多数情况下直接使用emplace或insert即可。3.3 自定义键类型与比较规则和set一样map的键也需要满足严格弱序。对于自定义类型作为键必须提供比较规则。#include iostream #include map #include string struct Point { int x; int y; }; // 为 Point 定义比较规则按 x 升序若 x 相同则按 y 升序 bool operator(const Point lhs, const Point rhs) { if (lhs.x ! rhs.x) return lhs.x rhs.x; return lhs.y rhs.y; } int main() { // 使用重载了 运算符的 Point 作为键 std::mapPoint, std::string pointMap; pointMap[{1, 2}] A; pointMap[{3, 4}] B; pointMap[{1, 2}] C; // 更新键 {1,2} 对应的值 pointMap[{0, 5}] D; for (const auto entry : pointMap) { const Point p entry.first; std::cout Point( p.x , p.y ) - entry.second std::endl; } // 输出将按 Point 定义的 规则排序 // 也可以使用自定义仿函数类似于 set 的例子 struct ComparePointByDescendingX { bool operator()(const Point a, const Point b) const { return a.x b.x; // 按 x 降序 } }; std::mapPoint, std::string, ComparePointByDescendingX pointMapDescX; // ... 操作类似 return 0; }4. 性能剖析、常见陷阱与高级技巧理解了基本操作后我们需要深入一层探讨如何高效、正确地使用这两个容器。4.1 迭代器失效与删除操作关联容器的迭代器失效规则比序列式容器如vector简单得多。插入操作不会使任何迭代器失效除了被插入元素的位置迭代器当然它本来也不存在。删除操作只有指向被删除元素的迭代器会失效其他迭代器仍然有效。这是一个非常重要的特性意味着你可以在遍历容器的过程中安全地删除元素除了当前正在被迭代的那个。#include iostream #include set int main() { std::setint s {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 错误示范使用基于范围的 for 循环删除元素迭代器失效 // for (int val : s) { // if (val % 2 0) { // s.erase(val); // 运行时可能崩溃或行为未定义 // } // } // 正确方法1使用返回值获取下一个有效的迭代器 (C11) for (auto it s.begin(); it ! s.end(); /* 这里不递增 */) { if (*it % 2 0) { it s.erase(it); // erase 返回被删除元素之后元素的迭代器 } else { it; } } // 正确方法2C11 前的方法略显繁琐但有效 std::setint s2 {1, 2, 3, 4, 5}; for (std::setint::iterator it s2.begin(); it ! s2.end(); ) { if (*it % 2 0) { std::setint::iterator toErase it; s2.erase(toErase); } else { it; } } // 对于 map逻辑完全相同 std::mapint, std::string m {{1, a}, {2, b}, {3, c}}; for (auto it m.begin(); it ! m.end(); ) { if (it-first % 2 0) { it m.erase(it); } else { it; } } std::cout Elements left after erasing evens:\n; for (int val : s) { std::cout val ; // 输出: 1 3 5 7 9 } std::cout std::endl; return 0; }4.2 查找性能优化与[]运算符的陷阱查找优化对于map频繁的查找操作是核心。确保键的类型具有高效的比较操作对于自定义类型operator或比较函数应尽量简单。如果键是字符串且长度变化大考虑使用std::string_view作为键C17或使用自定义的哈希容器unordered_map。[]运算符的陷阱这是map最易出错的地方之一。std::mapstd::string, int m; int count m[someKey]; // 问题1如果 someKey 不存在它会被插入值为0。 // 这可能导致意外的副作用比如 map 的大小被改变。 // 意图是检查键是否存在如果存在则获取值。 if (m[key] 0) { // 问题2如果 key 不存在它会被创建并赋值为0然后判断 00 为 false。 // 逻辑上你可能以为这里表示键存在且值0但实际上对于不存在的键它也进入了 else 分支。 } // 正确的做法先查找再判断。 auto it m.find(key); if (it ! m.end() it-second 0) { // 键存在且值大于0 }4.3 合并容器与提取节点 (C17)C17 为关联容器引入了非常实用的merge成员函数和节点句柄node handle功能。merge尝试将另一个容器的所有元素合并到当前容器。对于map如果源容器中有键冲突则该键值对不会被转移保留在源容器中。#include iostream #include map #include string int main() { std::mapint, std::string src {{1, a}, {3, c}, {5, e}}; std::mapint, std::string dst {{2, b}, {3, x}, {4, d}}; dst.merge(src); std::cout Destination after merge:\n; for (const auto p : dst) { std::cout p.first : p.second std::endl; } // 输出: 1:a, 2:b, 3:x (冲突保留dst的), 4:d, 5:e std::cout \nSource after merge (conflict key remains):\n; for (const auto p : src) { std::cout p.first : p.second std::endl; } // 输出: 3:c (键3冲突仍留在src中) return 0; }节点句柄允许将容器内的一个节点“提取”出来然后“插入”到另一个容器而无需拷贝或移动键值对本身。这在进行容器间元素转移时可以避免不必要的拷贝开销特别是当键或值是不可拷贝或移动成本很高时。#include iostream #include map #include string int main() { std::mapint, std::string m1 {{1, very long string ...}, {2, another long string ...}}; std::mapint, std::string m2; // 从 m1 中提取键为 1 的节点 auto node m1.extract(1); if (!node.empty()) { // 检查提取是否成功 // 修改节点的键注意对于 map只能修改非 const 的键部分前提是保证不破坏顺序 node.key() 10; // 将键从1改为10 // 将节点插入到 m2 m2.insert(std::move(node)); } std::cout m1 size: m1.size() std::endl; // 输出: 1 (只剩下键2) std::cout m2 size: m2.size() std::endl; // 输出: 1 (拥有键10值为长字符串) // 注意长字符串本身没有被拷贝只是所有权转移了。 return 0; }4.4 与 unordered_map/unordered_set 的选择这是实际项目中必须面对的选择。std::map/set(有序) 和std::unordered_map/unordered_set(无序基于哈希) 各有优劣。特性std::map/std::set(有序)std::unordered_map/std::unordered_set(无序)底层实现红黑树哈希表查找/插入/删除平均复杂度O(log n)O(1)查找/插入/删除最坏复杂度O(log n)O(n) (哈希冲突严重时)元素顺序按键排序无特定顺序取决于哈希函数和桶迭代器稳定性插入/删除非当前元素时稳定插入可能导致 rehash所有迭代器失效内存开销相对较低每个节点有左右指针相对较高需要维护桶数组和链表/树关键要求键类型必须定义或自定义比较器键类型必须提供哈希函数和比较选择指南需要元素有序遍历、范围查询如lower_bound选map/set。只需要判断存在性、单一键查找且对遍历顺序无要求追求极致的平均查找速度选unordered_map/unordered_set。键类型自定义且难以提供良好的哈希函数map/set更容易实现只需定义。对内存非常敏感或需要稳定的迭代器避免 rehash 失效map/set可能更合适。数据量巨大且哈希函数质量很高unordered_map/unordered_set的性能优势会非常明显。我个人在项目中的经验是对于小规模数据例如几百个元素以内或者需要频繁进行有序操作时优先使用map/set。对于大规模的、以查找为主且不需要顺序的缓存、索引等场景unordered_map/unordered_set是首选。在做决定前最好用实际数据 profile 一下。4.5 一个综合案例简单的单词统计程序让我们用一个完整的例子来串联map的使用。这个程序读取一段文本统计每个单词出现的频率并输出出现次数最多的几个单词。#include iostream #include map #include string #include vector #include algorithm #include cctype // 辅助函数将字符串转为小写并移除标点 std::string normalizeWord(const std::string word) { std::string result; for (char ch : word) { if (std::isalpha(static_castunsigned char(ch))) { // 只保留字母 result.push_back(std::tolower(static_castunsigned char(ch))); } } return result; } int main() { std::string text R(Hello world! Hello C. World of C is amazing. Lets explore the world.); std::mapstd::string, int wordFrequency; // 简单分词按空格分割实际应用可能需要更复杂的分词器 std::string delimiter ; size_t start 0, end 0; while ((end text.find(delimiter, start)) ! std::string::npos) { std::string token text.substr(start, end - start); std::string word normalizeWord(token); if (!word.empty()) { wordFrequency[word]; // 使用[]运算符如果单词不存在会自动插入0然后 } start end delimiter.length(); } // 处理最后一个单词 std::string lastToken text.substr(start); std::string lastWord normalizeWord(lastToken); if (!lastWord.empty()) { wordFrequency[lastWord]; } // 输出所有单词及其频率 std::cout Word Frequency:\n; for (const auto entry : wordFrequency) { std::cout entry.first : entry.second std::endl; } // 找出频率最高的单词 // 由于 map 是按键排序的我们需要按值排序。一种方法是将 pair 拷贝到 vector 中排序。 std::vectorstd::pairstd::string, int sortedWords(wordFrequency.begin(), wordFrequency.end()); std::sort(sortedWords.begin(), sortedWords.end(), [](const auto a, const auto b) { return a.second b.second; }); // 按频率降序 std::cout \nTop 3 frequent words:\n; int topN std::min(3, static_castint(sortedWords.size())); for (int i 0; i topN; i) { std::cout i 1 . sortedWords[i].first ( sortedWords[i].second times)\n; } return 0; }这个例子展示了map如何自然地作为计数器使用以及如何结合其他 STL 组件如vector和algorithm来解决实际问题。注意这里的分词非常原始真实场景中需要考虑连字符、缩写、撇号等更复杂的情况。