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::lessT比较 std::multisetint ms1; // 2. 使用初始化列表构造 std::multisetint ms2 {5, 2, 8, 2, 5, 1}; // 注意允许重复 // 此时ms2内容为1, 2, 2, 5, 5, 8 (已排序) // 3. 使用迭代器范围构造 std::vectorint vec {9, 3, 3, 6, 1}; std::multisetint 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::multisetint, Greater ms4 {5, 2, 8, 2}; // ms4内容8, 5, 2, 2 (降序) // 或者使用lambda表达式C11及以上 auto cmp [](int a, int b) { return a b; }; std::multisetint, decltype(cmp) ms5(cmp); ms5.insert({5, 2, 8, 2}); // ms5内容8, 5, 2, 2 // 5. 拷贝构造和赋值 std::multisetint ms6(ms2); // 拷贝构造 std::multisetint 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::multisetstd::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::vectorstd::string moreTasks {Review, Deploy}; taskSet.insert(moreTasks.begin(), moreTasks.end());查找 (find,count,equal_range,lower_bound/upper_bound)由于允许重复查找操作比set更丰富。std::multisetint 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 // 注意如果有多个90find只返回第一个 } // 2. count: 返回等价元素的数量 size_t c scores.count(85); std::cout Number of 85: c std::endl; // 输出 Number of 85: 2 // 3. equal_range: 返回一个pairiterator, 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::multisetint 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::multisetchar 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循环 (C11) 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::multisetint largeSet; // 假设我们正在按顺序插入一个已经大致有序的巨大数据集 std::vectorint 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::multisetPlayer 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::multisetPlayer, 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::multisetint ms {5, 1, 4, 4, 2}; std::vectorint vec(ms.begin(), ms.end()); // 利用迭代器范围构造 // vec: 1, 2, 4, 4, 5 // 2. vector 转 multiset (去重不multiset保留所有重复) std::vectorint input {7, 3, 7, 1}; std::multisetint ms2(input.begin(), input.end()); // ms2: 1, 3, 7, 7 // 3. 获取唯一元素集合相当于set的功能 // 方法一使用std::set直接构造 std::setint uniqueSet(ms.begin(), ms.end()); // 方法二利用multiset有序的特性手动遍历去重更高效无需额外比较 std::vectorint 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::multisetGamePlayer players; public: void addOrUpdatePlayer(const std::string uid, int newScore) { // 先查找该玩家是否已在榜上根据uid查找 // 注意我们的排序规则是score和uid无法直接用uid查找。 // 一种方法是线性查找O(n)对于排行榜玩家数量通常可控。 // 更高效的方法是维护一个额外的std::unordered_mapstd::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::vectordouble medianSlidingWindow(const std::vectorint nums, int k) { std::multisetint window(nums.begin(), nums.begin() k); auto mid std::next(window.begin(), k / 2); // 指向“上半部分”的第一个元素 std::vectordouble medians; for (int i k; ; i) { // 计算当前窗口中位数 if (k % 2 0) { // 偶数个元素中位数是中间两个的平均值 auto mid_prev std::prev(mid); medians.push_back((static_castdouble(*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::multisetint 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; } } // 正确做法2C11后erase返回的迭代器指向被删元素的下一个 // 对于删除所有满足条件的元素更简洁的做法是 ms.erase(2); // 直接删除所有值为2的元素自定义比较函数的严格弱序这是最容易出错的地方之一。比较函数必须满足严格弱序否则会导致未定义行为容器内部结构可能被破坏。// 错误示例试图用 来定义比较 struct BadCompare { bool operator()(int a, int b) const { return a b; // 违反了“不可自反性”因为 aa 为 true。 } }; // 使用 BadCompare 实例化 multiset 是危险的。 // 正确做法始终使用 或 来定义“小于”或“大于”关系。lower_bound和upper_bound的误用记住lower_bound(k)返回的是第一个不小于k的元素位置即kupper_bound(k)返回的是第一个大于k的元素位置。对于multisetequal_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我们可以实现一个功能更强大的“可删除优先队列”。templatetypename T, typename Compare std::lessT class DeletablePriorityQueue { private: std::multisetT, Compare data; Compare comp; public: void push(const T value) { data.insert(value); } void pop() { if (!data.empty()) { // 根据比较器决定弹出最大还是最小 if constexpr (std::is_same_vCompare, std::lessT) { // 默认std::lessmultiset升序最大值在末尾 data.erase(std::prev(data.end())); } else { // 如果是std::greatermultiset降序最小值在末尾 // 实际上对于优先队列我们通常想弹出“优先级最高”的。 // 假设Compare定义了“优先级低”的顺序那么优先级最高的在begin() // 这里需要根据Compare语义调整。一个更通用的方法是维护两个堆。 // 简化起见我们假设Compare是std::less弹出最大值。 data.erase(std::prev(data.end())); } } } const T top() const { if constexpr (std::is_same_vCompare, std::lessT) { 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() { // 一个最大堆优先级高的值大 DeletablePriorityQueueint 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)的堆调整通常常数更小。