1. 项目概述：为什么你需要深入了解Multiset？
如果你在C++项目中处理过需要频繁插入、删除，同时又需要快速查找、并且允许元素重复的集合数据，那么你很可能已经接触过或者听说过std::multiset。它不像std::vector那样强调线性顺序和随机访问，也不像std::unordered_set那样追求极致的O(1)平均查找时间。multiset的定位非常独特：它是一个基于红黑树实现的有序关联容器，核心价值在于自动排序和允许重复键。这意味着，你无需在每次插入后手动调用std::sort，容器内部始终维持着元素的有序状态；同时，你可以存放多个完全相同的值，这在统计频率、管理具有相同优先级的多任务等场景下至关重要。
很多初学者容易将multiset与set、multimap混淆。简单来说，set是元素唯一且有序的集合；multimap是允许键重复的键值对有序集合；而multiset更像是set的“宽容版”，放弃了元素的唯一性约束。与unordered_multiset相比，虽然后者在平均情况下插入和查找更快（哈希表实现），但它不保证元素顺序，迭代顺序是未定义的。因此，选择multiset还是unordered_multiset，本质上是在“需要元素有序”和“追求极致性能”之间做权衡。
在实际开发中，multiset的应用场景比你想象的更广泛。例如，在游戏开发中管理同一优先级下的多个游戏对象；在金融分析中维护一个实时更新的、允许重复的价格列表；在日志系统中存储带时间戳的日志条目（时间戳可能相同）；甚至是在算法竞赛中，快速实现一些需要动态维护有序序列且支持重复元素的题目。理解multiset，不仅是掌握一个容器，更是理解一种基于平衡二叉搜索树的数据管理思想。接下来，我将从设计思路、核心操作到实战避坑，为你彻底拆解这个强大而优雅的容器。
2. 核心设计思路与内部机制剖析
2.1 底层数据结构：红黑树如何支撑Multiset的特性？
std::multiset的几乎所有行为都源于其底层实现——红黑树。红黑树是一种自平衡的二叉搜索树，它通过在节点中增加一个颜色标记（红或黑）和一套复杂的旋转、变色规则，来确保树的高度大致平衡。这种平衡性保证了对于multiset的核心操作（插入、删除、查找）的时间复杂度都能稳定在O(log n)，这里n是容器中元素的数量。这是multiset性能的基石。
为什么是红黑树而不是其他平衡树（如AVL树）？这涉及到STL设计时的权衡。AVL树是更严格的平衡树，其查找性能略优于红黑树，但为了维持更严格的平衡，在插入和删除时需要更频繁的旋转操作。红黑树放宽了平衡条件，它只要求从根到叶子的任何路径上，不能有两个连续的红色节点，并且从根到所有叶子节点的路径上，黑色节点的数量相同。这种“近似平衡”减少了插入和删除时的旋转次数，使得红黑树在整体性能上，尤其是对于修改操作频繁的场景，综合表现更优。STL选择红黑树，正是看重其在频繁增删场景下依然能保持良好性能的平衡能力。
对于multiset允许重复元素的特性，红黑树是如何处理的呢？它并没有采用在每个树节点存储一个链表来挂载重复值的方式（那会退化成哈希桶的思想）。相反，红黑树的标准实现中，对于键值比较相等的节点（即!comp(a,b) && !comp(b,a)），它允许它们同时存在于树中。在插入时，如果遇到键值相等的节点，根据具体的实现策略（通常是插入到相等范围的任意位置，但必须保持树的有序性），新节点会被安放进去。当你使用equal_range或count函数时，算法会利用二叉搜索树的有序性，高效地定位到所有相等元素的区间。
注意：由于底层是红黑树，
multiset中的元素必须是可比较的。这意味着元素类型需要支持<运算符，或者你在构造multiset时传入一个自定义的比较函数对象。这个比较关系定义了树的“序”，至关重要。
2.2 关键特性与性能权衡
理解了底层是红黑树，我们就能系统地把握multiset的关键特性：
- 自动排序：元素在插入时即被放置在正确的位置，整个容器始终有序。这是通过红黑树的插入算法保证的。
- 允许重复：这是与
set最根本的区别。比较函数（默认为std::less）定义“小于”关系，当两个元素a和b互不小于对方时（即a不小于b且b不小于a），它们被视为“等价”而非“相等”。multiset允许存在多个彼此“等价”的元素。 - 稳定的对数时间复杂度：插入(
insert)、查找(find)、删除(erase一个迭代器)单个元素都是O(log n)。遍历整个容器是O(n)。这里“稳定”指的是最坏情况下的复杂度，得益于红黑树的自平衡。 - 双向迭代器：你可以使用
++和--操作符向前或向后遍历元素。由于是有序序列，正向迭代器（begin()到end()）遍历得到的是升序序列。迭代器在元素被删除后（除了被删除的那个元素的迭代器）通常不会失效，除非发生了树的重新平衡导致节点内存地址变化，但STL的实现保证了除指向被删除元素的迭代器外，其他迭代器、引用和指针的稳定性。 - 空间开销：每个元素存储在一个树节点中，节点除了存储元素值，还需要存储左右子节点指针、父节点指针以及颜色标记。因此，它的内存开销比
vector、array这类连续存储容器要大。
与std::priority_queue的对比常让人困惑。两者都提供了一种“有序”的视图。主要区别在于：
- 访问权限：
priority_queue（优先队列）只允许访问顶部的最大（或最小）元素（top()），而multiset允许你访问、迭代任何一个元素。 - 底层结构：
priority_queue默认底层是vector配合堆算法，multiset是红黑树。 - 用途：
priority_queue适用于需要不断处理当前最高/最低优先级任务的场景（如任务调度）。multiset适用于需要维护一个完全有序的、可随机访问（通过查找）和遍历的集合的场景。 - 重复元素：两者都支持重复元素。
选择哪一个，取决于你的需求是“只需要处理当前极值”还是“需要操作整个有序集合”。
3. 核心操作详解与实战代码示例
理论说得再多，不如一行代码。让我们进入实战环节，我会结合具体场景，展示multiset最常用和最关键的操作。
3.1 容器的创建与初始化
创建multiset非常灵活。最常用的是使用默认构造函数和范围构造函数。
#include <iostream> #include <set> // multiset 和 set 都在这个头文件 #include <vector> int main() { // 1. 默认构造：空multiset，使用默认的std::less<T>比较 std::multiset<int> ms1; // 2. 使用初始化列表构造 std::multiset<int> ms2 = {5, 2, 8, 2, 5, 1}; // 注意：允许重复 // 此时ms2内容为：1, 2, 2, 5, 5, 8 (已排序) // 3. 使用迭代器范围构造 std::vector<int> vec = {9, 3, 3, 6, 1}; std::multiset<int> ms3(vec.begin(), vec.end()); // ms3内容：1, 3, 3, 6, 9 // 4. 自定义比较函数：实现降序排列 // 使用函数对象（仿函数） struct Greater { bool operator()(int a, int b) const { return a > b; // 降序 } }; std::multiset<int, Greater> ms4 = {5, 2, 8, 2}; // ms4内容：8, 5, 2, 2 (降序) // 或者使用lambda表达式（C++11及以上） auto cmp = [](int a, int b) { return a > b; }; std::multiset<int, decltype(cmp)> ms5(cmp); ms5.insert({5, 2, 8, 2}); // ms5内容：8, 5, 2, 2 // 5. 拷贝构造和赋值 std::multiset<int> ms6(ms2); // 拷贝构造 std::multiset<int> ms7 = ms3; // 拷贝赋值 return 0; }提示：自定义比较函数时，必须确保它满足严格弱序关系。简单说，它需要像
<运算符一样，不可自反（comp(a, a)为false）、可传递（如果comp(a, b)和comp(b, c)为真，则comp(a, c)为真）、可比较（任意两个元素，comp(a,b)和comp(b,a)至少有一个为真，除非它们“等价”）。使用std::greater<>是一个常见的降序方案。
3.2 元素的插入、查找与删除
这是multiset最核心的三个操作。
插入 (insert)
std::multiset<std::string> taskSet; // 1. 插入单个值，返回指向新元素的迭代器 auto it = taskSet.insert("Debug"); // it 指向新插入的"Debug" // 2. 插入单个值（带提示位置）。提示位置hint是一个迭代器， // 表示搜索起点，可能提高插入效率（如果提示准确）。 // 返回指向新元素的迭代器。 auto hint = taskSet.find("Debug"); taskSet.insert(hint, "Test"); // 在hint附近开始搜索插入位置 // 3. 插入一个初始化列表 taskSet.insert({"Build", "Commit", "Test", "Build"}); // 容器现在包含：Build, Build, Commit, Debug, Test, Test (按字母序) // 4. 使用迭代器范围插入 std::vector<std::string> moreTasks = {"Review", "Deploy"}; taskSet.insert(moreTasks.begin(), moreTasks.end());查找 (find,count,equal_range,lower_bound/upper_bound)由于允许重复，查找操作比set更丰富。
std::multiset<int> scores = {85, 90, 78, 90, 92, 85, 88}; // 1. find: 返回指向第一个找到的等价元素的迭代器，未找到则返回end() auto it = scores.find(90); if (it != scores.end()) { std::cout << "Found: " << *it << std::endl; // 输出 Found: 90 // 注意：如果有多个90，find只返回第一个 } // 2. count: 返回等价元素的数量 size_t c = scores.count(85); std::cout << "Number of 85: " << c << std::endl; // 输出 Number of 85: 2 // 3. equal_range: 返回一个pair<iterator, iterator>， // 表示等价元素的范围 [first, last)。这是处理重复键最强大的工具。 auto range = scores.equal_range(90); std::cout << "All 90s: "; for (auto it = range.first; it != range.second; ++it) { std::cout << *it << " "; } std::cout << std::endl; // 输出 All 90s: 90 90 // 4. lower_bound / upper_bound: // lower_bound(k): 返回第一个不小于k的元素的迭代器（即第一个>=k的） // upper_bound(k): 返回第一个大于k的元素的迭代器 // 两者结合也可以用来获取范围，等同于equal_range auto low = scores.lower_bound(85); // 指向第一个85 auto up = scores.upper_bound(85); // 指向第一个大于85的元素（88） std::cout << "Range of 85: "; for (auto it = low; it != up; ++it) { std::cout << *it << " "; } std::cout << std::endl; // 输出 Range of 85: 85 85删除 (erase)删除操作需要小心处理迭代器失效问题。
std::multiset<int> data = {1, 3, 3, 3, 5, 7}; // 1. 通过迭代器删除单个元素。最安全，时间复杂度O(1) 或 O(log n)。 auto it = data.find(5); if (it != data.end()) { data.erase(it); // 删除找到的那个5 } // data: 1, 3, 3, 3, 7 // 2. 通过值删除。删除所有等价于该值的元素，返回被删除的元素个数。 size_t num_removed = data.erase(3); // 删除所有的3 std::cout << "Removed " << num_removed << " elements." << std::endl; // 输出 Removed 3 elements. // data: 1, 7 // 3. 通过迭代器范围删除。删除[first, last)区间内的元素。 auto first = data.lower_bound(5); auto last = data.upper_bound(10); data.erase(first, last); // 删除所有 >=5 且 <=10 的元素？注意：upper_bound(10)可能指向end() // 更安全的做法是确保范围有效。 // data: 1 // 重要：删除元素后，指向被删除元素的迭代器、引用和指针会失效。 // 但其他元素的迭代器通常保持有效（得益于红黑树的实现）。3.3 迭代与容量查询
遍历multiset很简单，因为它提供了双向迭代器。
std::multiset<char> letters = {'b', 'a', 'c', 'a', 'd'}; // 1. 正向迭代 (升序) std::cout << "Ascending: "; for (auto it = letters.begin(); it != letters.end(); ++it) { std::cout << *it << " "; } // 输出：Ascending: a a b c d // 2. 反向迭代 (降序) std::cout << "\nDescending: "; for (auto rit = letters.rbegin(); rit != letters.rend(); ++rit) { std::cout << *rit << " "; } // 输出：Descending: d c b a a // 3. 基于范围的for循环 (C++11) std::cout << "\nRange-for: "; for (const auto& ch : letters) { std::cout << ch << " "; } // 输出：Range-for: a a b c d // 容量查询 std::cout << "\nSize: " << letters.size() << std::endl; // 元素个数: 5 std::cout << "Empty? " << std::boolalpha << letters.empty() << std::endl; // 是否为空: false // multiset 没有 capacity() 成员函数，因为其内存不是预分配的。4. 高级用法与性能优化技巧
掌握了基本操作，我们来看看如何更高效、更安全地使用multiset。
4.1 利用Hint提升插入性能
insert函数有一个重载版本，接受一个迭代器作为“提示”。如果这个提示位置恰好是新元素的正确插入位置（或者非常接近），那么插入操作可以从O(log n)优化到分摊常数时间。
std::multiset<int> largeSet; // 假设我们正在按顺序插入一个已经大致有序的巨大数据集 std::vector<int> sortedData = {/* ... 大量数据，基本有序 ... */}; auto hint = largeSet.end(); // 初始提示设为end() for (int value : sortedData) { // 因为数据大致有序，新值很可能插入在现有集合的末尾附近。 // 使用hint作为插入起点。 hint = largeSet.insert(hint, value); // insert返回新插入元素的位置，作为下一次插入的hint。 }这个技巧在批量插入有序或近乎有序的数据时非常有效。但如果提示位置离正确位置很远，性能可能反而比普通插入更差，因为搜索需要从提示位置开始并可能回溯。
4.2 自定义比较函数与复杂对象存储
multiset的强大之处在于它能存储任何定义了严格弱序的类型。对于自定义类或结构体，你需要提供比较方法。
#include <string> struct Player { std::string name; int score; int level; // 按score降序排列，如果score相同则按level升序排列 bool operator<(const Player& other) const { if (score != other.score) { return score > other.score; // 分数高的在前（降序） } return level < other.level; // 分数相同时，等级低的在前（升序） } }; int main() { // 使用默认的 operator< 进行比较 std::multiset<Player> leaderboard; leaderboard.insert({"Alice", 100, 10}); leaderboard.insert({"Bob", 150, 5}); leaderboard.insert({"Charlie", 100, 8}); // 与Alice分数相同，但level不同 std::cout << "Leaderboard:\n"; for (const auto& p : leaderboard) { std::cout << p.name << " - Score: " << p.score << ", Level: " << p.level << std::endl; } // 输出： // Bob - Score: 150, Level: 5 // Alice - Score: 100, Level: 10 // Charlie - Score: 100, Level: 8 // 注意：Bob分数最高排第一。Alice和Charlie分数相同，但Charlie等级(8) < Alice等级(10)，所以Charlie排在Alice前面。 return 0; }你也可以使用独立的函数对象，这在不想修改类定义或者需要多种排序方式时非常有用。
struct Player { std::string name; int score; }; // 自定义比较仿函数：只按分数升序排 struct CompareByScore { bool operator()(const Player& a, const Player& b) const { return a.score < b.score; } }; int main() { std::multiset<Player, CompareByScore> leaderboard; leaderboard.insert({"Alice", 100}); leaderboard.insert({"Bob", 150}); leaderboard.insert({"Charlie", 100}); // 允许重复分数 for (const auto& p : leaderboard) { std::cout << p.name << ": " << p.score << std::endl; } // 输出：Alice: 100, Charlie: 100, Bob: 150 return 0; }4.3 与其它容器的交互与数据迁移
你经常需要将multiset的数据与其他容器进行转换。
// 1. multiset 转 vector (例如需要随机访问或调用vector特有算法时) std::multiset<int> ms = {5, 1, 4, 4, 2}; std::vector<int> vec(ms.begin(), ms.end()); // 利用迭代器范围构造 // vec: 1, 2, 4, 4, 5 // 2. vector 转 multiset (去重？不，multiset保留所有重复) std::vector<int> input = {7, 3, 7, 1}; std::multiset<int> ms2(input.begin(), input.end()); // ms2: 1, 3, 7, 7 // 3. 获取唯一元素集合（相当于set的功能） // 方法一：使用std::set直接构造 std::set<int> uniqueSet(ms.begin(), ms.end()); // 方法二：利用multiset有序的特性，手动遍历去重（更高效，无需额外比较） std::vector<int> uniqueVec; if (!ms.empty()) { auto prev = ms.begin(); uniqueVec.push_back(*prev); for (auto it = std::next(ms.begin()); it != ms.end(); ++it) { if (*it != *prev) { uniqueVec.push_back(*it); } prev = it; } }5. 实战场景深度剖析与避坑指南
理论结合实战，才能真正掌握。下面我们通过几个典型场景，并总结常见的“坑”。
5.1 场景一：实时排行榜维护
假设你正在开发一个游戏，需要维护一个实时更新的玩家分数排行榜，允许并列。
#include <iostream> #include <set> #include <string> #include <chrono> #include <random> struct GamePlayer { std::string uid; int score; // 按分数降序排列，分数相同按uid升序（确保唯一序） bool operator<(const GamePlayer& other) const { if (score != other.score) { return score > other.score; // 降序 } return uid < other.uid; // 打破平局 } }; class Leaderboard { private: std::multiset<GamePlayer> players; public: void addOrUpdatePlayer(const std::string& uid, int newScore) { // 先查找该玩家是否已在榜上（根据uid查找） // 注意：我们的排序规则是score和uid，无法直接用uid查找。 // 一种方法是线性查找（O(n)），对于排行榜，玩家数量通常可控。 // 更高效的方法是维护一个额外的std::unordered_map<std::string, iterator>来快速定位。 // 这里为了演示简单，使用线性查找。 auto it = std::find_if(players.begin(), players.end(), [&uid](const GamePlayer& p) { return p.uid == uid; }); if (it != players.end()) { // 找到，先删除旧记录 players.erase(it); } // 插入新记录 players.insert({uid, newScore}); } void printTopN(int n) const { std::cout << "--- Top " << n << " Players ---\n"; int rank = 1; int lastScore = -1; int skipRank = 0; for (auto it = players.begin(); it != players.end() && rank <= n + skipRank; ++it) { // 处理并列排名 if (it->score != lastScore) { lastScore = it->score; if (rank > n) break; // 已经打印完前N名（考虑并列） std::cout << "Rank " << rank << ": " << it->uid << " - " << it->score << std::endl; rank++; } else { // 分数相同，并列排名 std::cout << "Rank " << rank-1 << ": " << it->uid << " - " << it->score << " (tied)" << std::endl; skipRank++; // 因为并列多打印了一个，需要调整循环条件 } } } const GamePlayer* getPlayerAtRank(int rank) const { if (rank < 1 || rank > players.size()) return nullptr; auto it = players.begin(); std::advance(it, rank - 1); // 注意：advance是O(n)操作，谨慎使用！ return &(*it); } }; int main() { Leaderboard lb; lb.addOrUpdatePlayer("player_001", 2500); lb.addOrUpdatePlayer("player_002", 1800); lb.addOrUpdatePlayer("player_003", 3100); lb.addOrUpdatePlayer("player_004", 1800); // 与player_002并列 lb.addOrUpdatePlayer("player_002", 2000); // 更新player_002分数 lb.printTopN(5); // 输出： // --- Top 5 Players --- // Rank 1: player_003 - 3100 // Rank 2: player_002 - 2000 // Rank 3: player_001 - 2500 // Rank 4: player_004 - 1800 // Rank 5: player_002 - 1800 (tied) // 注意：这里逻辑有误，player_002分数已更新，不应出现。 // 这个例子揭示了更新逻辑的一个潜在问题：我们按(score, uid)排序，但更新时只根据uid删除。 // 如果uid相同但score不同，旧的记录可能无法被正确找到和删除（因为find_if用的是uid，但multiset的序是score和uid）。 // 更健壮的做法是使用两个数据结构：一个set按(score,uid)排序用于排名，一个map(uid->iterator)用于快速查找。 return 0; }这个例子揭示了使用单一multiset处理复杂更新逻辑时的挑战。对于需要频繁通过非排序键（如uid）进行查找和更新的场景，通常需要结合unordered_map来维护从键到迭代器的映射，以实现O(1)的查找和O(log n)的更新。
5.2 场景二：滑动窗口中的中位数查找
LeetCode上有一道经典题目“滑动窗口中位数”，multiset是其中一种高效的解法。它能够动态维护一个有序集合，并快速获取中位数。
#include <vector> #include <set> #include <iostream> #include <iterator> // for std::advance std::vector<double> medianSlidingWindow(const std::vector<int>& nums, int k) { std::multiset<int> window(nums.begin(), nums.begin() + k); auto mid = std::next(window.begin(), k / 2); // 指向“上半部分”的第一个元素 std::vector<double> medians; for (int i = k; ; ++i) { // 计算当前窗口中位数 if (k % 2 == 0) { // 偶数个元素，中位数是中间两个的平均值 auto mid_prev = std::prev(mid); medians.push_back((static_cast<double>(*mid_prev) + *mid) / 2.0); } else { // 奇数个元素，中位数就是中间那个 medians.push_back(*mid); } if (i == nums.size()) break; // 窗口滑动：删除左端元素，添加右端新元素 int toRemove = nums[i - k]; int toAdd = nums[i]; // 插入新元素 window.insert(toAdd); if (toAdd < *mid) { // 新元素插入在mid左侧，mid需要左移（因为集合大小增加了） --mid; } // 注意：必须先插入再处理删除，否则迭代器可能失效 // 删除旧元素 // 找到要删除元素的迭代器。由于有重复元素，需要找到正确的那个。 // 使用 lower_bound 找到第一个 >= toRemove 的位置 auto it_remove = window.lower_bound(toRemove); // 确保找到的元素就是我们要删除的值（理论上应该总是成立） if (it_remove != window.end() && *it_remove == toRemove) { if (it_remove == mid) { // 如果要删除的正好是mid，需要先移动mid再删除 mid = window.erase(it_remove); // erase返回被删除元素的下一个 // 但此时mid已经指向了下一个元素，对于奇数k，这可能是正确的，但需要调整 // 更安全的做法是：记录删除操作对mid的影响，然后统一调整mid // 这里简化处理，采用另一种策略：先调整mid，再删除 } else { if (toRemove <= *mid) { // 删除的元素在mid左侧（或就是mid），且不是mid本身，mid需要右移 ++mid; } window.erase(it_remove); } } // 上面的删除逻辑非常复杂且容易出错，特别是处理mid迭代器时。 // 更稳健的方法是维护两个multiset（大小平衡的），分别存储窗口的左半部分和右半部分。 // 这引出了下一个要点：使用multiset实现大小平衡堆。 } return medians; } // 注意：上述代码作为思路演示，其中删除逻辑存在缺陷，在实际应用或面试中需要更严谨的实现。5.3 常见陷阱与性能坑点实录
迭代器失效的微妙之处：对于
multiset，只有指向被删除元素的迭代器会失效。但是，如果你在循环中删除元素，需要特别注意。std::multiset<int> ms = {1, 2, 2, 3, 4}; // 错误示范：在基于范围的for循环中删除元素 for (auto it = ms.begin(); it != ms.end(); ++it) { if (*it == 2) { ms.erase(it); // 错误！erase(it)后，it失效，后续的++it是未定义行为 } } // 正确做法1：使用erase的返回值（它返回被删除元素之后元素的迭代器） for (auto it = ms.begin(); it != ms.end(); ) { if (*it == 2) { it = ms.erase(it); // 正确，it被更新为下一个有效位置 } else { ++it; } } // 正确做法2：C++11后，erase返回的迭代器指向被删元素的下一个 // 对于删除所有满足条件的元素，更简洁的做法是： ms.erase(2); // 直接删除所有值为2的元素自定义比较函数的严格弱序：这是最容易出错的地方之一。比较函数必须满足严格弱序，否则会导致未定义行为，容器内部结构可能被破坏。
// 错误示例：试图用 <= 来定义比较 struct BadCompare { bool operator()(int a, int b) const { return a <= b; // 违反了“不可自反性”，因为 a<=a 为 true。 } }; // 使用 BadCompare 实例化 multiset 是危险的。 // 正确做法：始终使用 < 或 > 来定义“小于”或“大于”关系。lower_bound和upper_bound的误用：记住，lower_bound(k)返回的是第一个不小于k的元素位置（即>=k），upper_bound(k)返回的是第一个大于k的元素位置。对于multiset，equal_range(k)通常比手动组合lower_bound/upper_bound更安全便捷。性能误区：遍历查找替代
find：由于multiset已排序，find是O(log n)的二分查找。绝对不要用线性遍历（O(n)）来替代它。同样，count也是O(log n + k)，其中k是重复元素个数，对于重复很多的情况，它可能接近O(n)，此时如果需要遍历这些元素，直接用equal_range获取迭代器范围更高效。与
set的混淆导致逻辑错误：在需要元素唯一的场景误用了multiset，或者在允许重复的场景误用了set，都会导致数据丢失或逻辑错误。在设计阶段就要明确需求。内存开销：如果存储的是小对象（如内置类型），
multiset每个元素的节点开销（指针、颜色标记等）可能比数据本身还大。在内存敏感的场景，如果不需要实时排序，可以考虑用std::vector定期排序，或者用std::unordered_multiset。
6. 进阶：基于Multiset实现可删除的优先队列（对顶堆）
我们之前提到了priority_queue不支持删除任意元素。结合multiset，我们可以实现一个功能更强大的“可删除优先队列”。
template<typename T, typename Compare = std::less<T>> class DeletablePriorityQueue { private: std::multiset<T, Compare> data; Compare comp; public: void push(const T& value) { data.insert(value); } void pop() { if (!data.empty()) { // 根据比较器决定弹出最大还是最小 if constexpr (std::is_same_v<Compare, std::less<T>>) { // 默认std::less，multiset升序，最大值在末尾 data.erase(std::prev(data.end())); } else { // 如果是std::greater，multiset降序，最小值在末尾 // 实际上，对于优先队列，我们通常想弹出“优先级最高”的。 // 假设Compare定义了“优先级低”的顺序，那么优先级最高的在begin()？ // 这里需要根据Compare语义调整。一个更通用的方法是维护两个堆。 // 简化起见，我们假设Compare是std::less，弹出最大值。 data.erase(std::prev(data.end())); } } } const T& top() const { if constexpr (std::is_same_v<Compare, std::less<T>>) { return *std::prev(data.end()); } else { return *std::prev(data.end()); // 需要根据实际比较器调整 } } bool erase_one(const T& value) { auto it = data.find(value); if (it != data.end()) { data.erase(it); return true; } return false; } size_t erase_all(const T& value) { return data.erase(value); } bool empty() const { return data.empty(); } size_t size() const { return data.size(); } // 额外功能：获取迭代器，可用于遍历（但会破坏优先队列的抽象） auto begin() const { return data.begin(); } auto end() const { return data.end(); } }; int main() { // 一个最大堆（优先级高的值大） DeletablePriorityQueue<int> maxPQ; maxPQ.push(3); maxPQ.push(1); maxPQ.push(4); maxPQ.push(1); std::cout << "Top: " << maxPQ.top() << std::endl; // 4 maxPQ.erase_one(1); // 删除一个1 std::cout << "Size after erase one 1: " << maxPQ.size() << std::endl; // 3 maxPQ.pop(); std::cout << "Top after pop: " << maxPQ.top() << std::endl; // 3 return 0; }这个实现虽然简单，但pop和top操作是O(1)（通过访问首尾迭代器），push和erase是O(log n)。它比标准的priority_queue功能更强，但代价是每次插入删除都有O(log n)的树操作开销，而priority_queue的push和pop是O(log n)的堆调整，通常常数更小。
)
