当前位置： 首页 > news >正文

C++ stdset 与 stdmultiset 深度比较

news 2025/8/5 12:43:26

C++ std::set 与 std::multiset 深度比较

两者都基于红黑树实现，元素自动排序，但关键区别在于元素唯一性要求。下面我将全面分析它们的差异，并提供详细的代码示例。

1. 核心差异概览

特性std::setstd::multiset
元素唯一性要求元素唯一允许重复元素
插入返回值pair<iterator, bool>iterator
count() 行为返回0或1返回元素出现次数
find() 行为返回唯一元素位置返回第一个匹配元素位置
equal_range()范围大小为1或0范围大小可能大于1
erase(key)删除0或1个元素删除所有匹配元素

2. 详细差异分析（含代码示例）

2.1 元素唯一性要求

std::set：强制元素唯一性，插入重复元素会被忽略

#include <iostream>
#include <set>int main() {std::set<int> uniqueSet;// 插入元素auto [it1, inserted1] = uniqueSet.insert(10);std::cout << "Inserted 10: " << std::boolalpha << inserted1 << "\n"; // trueauto [it2, inserted2] = uniqueSet.insert(10);std::cout << "Inserted 10 again: " << inserted2 << "\n"; // falsestd::cout << "Set elements: ";for (int n : uniqueSet) std::cout << n << " "; // 10std::cout << "\n\n";
}

std::multiset：允许元素重复

#include <iostream>
#include <set>int main() {std::multiset<int> multiSet;// 插入重复元素auto it1 = multiSet.insert(20);auto it2 = multiSet.insert(20);std::cout << "Multiset elements: ";for (int n : multiSet) std::cout << n << " "; // 20 20std::cout << "\n\n";
}

2.2 插入操作返回值差异

std::set：返回pair<iterator, bool>

  • first: 指向插入/存在的元素
  • second: 是否成功插入
std::set<std::string> animalSet;// 新元素插入
auto [lionIt, lionInserted] = animalSet.insert("Lion");
std::cout << "Inserted Lion: " << lionInserted << "\n"; // true// 重复元素
auto [dupIt, dupInserted] = animalSet.insert("Lion");
std::cout << "Inserted Lion again: " << dupInserted << "\n"; // false
std::cout << "Existing element: " << *dupIt << "\n"; // Lion

std::multiset：返回指向新元素的迭代器

std::multiset<std::string> fruitMultiSet;// 总是返回新元素的迭代器
auto appleIt1 = fruitMultiSet.insert("Apple");
auto appleIt2 = fruitMultiSet.insert("Apple");std::cout << "First Apple at: " << std::distance(fruitMultiSet.begin(), appleIt1) << "\n";
std::cout << "Second Apple at: " << std::distance(fruitMultiSet.begin(), appleIt2) << "\n";

2.3 查找与计数行为差异

count() 方法：

std::set<int> singleSet = {1, 2, 3};
std::multiset<int> multiSet = {1, 1, 2, 2, 2, 3};std::cout << "Set count(2): " << singleSet.count(2) << "\n";      // 1
std::cout << "Multiset count(2): " << multiSet.count(2) << "\n"; // 3

find() 方法：

std::multiset<int> numbers = {10, 20, 20, 20, 30};// 返回第一个匹配元素
auto foundIt = numbers.find(20);
if (foundIt != numbers.end()) {std::cout << "First 20 found at position: " << std::distance(numbers.begin(), foundIt) << "\n"; // 1// 遍历所有20std::cout << "All 20s: ";auto [begin, end] = numbers.equal_range(20);for (auto it = begin; it != end; ++it) {std::cout << *it << " "; // 20 20 20}
}

2.4 范围查询差异

equal_range()：

// Set示例
std::set<int> uniqueNums = {5, 10, 15, 20};
auto [setLow, setHigh] = uniqueNums.equal_range(10);
std::cout << "Set range size: " << std::distance(setLow, setHigh) << "\n"; // 1// Multiset示例
std::multiset<int> duplicateNums = {5, 10, 10, 10, 15, 20};
auto [multiLow, multiHigh] = duplicateNums.equal_range(10);
std::cout << "Multiset range size: " << std::distance(multiLow, multiHigh) << "\n"; // 3

2.5 删除操作差异

erase(key)：

std::multiset<int> data = {1, 2, 2, 3, 3, 3, 4};// 删除所有2
size_t count = data.erase(2);
std::cout << "Erased " << count << " elements\n"; // 2// 删除单个3
auto it = data.find(3);
if (it != data.end()) {data.erase(it); // 只删除第一个3
}// 结果: 1, 3, 3, 4
std::cout << "After erasures: ";
for (int n : data) std::cout << n << " ";

2.6 迭代器稳定性

std::multiset 中重复元素的迭代器：

std::multiset<std::string> taskSet = {"Write", "Test", "Debug"};// 获取迭代器
auto writeIt = taskSet.find("Write");
auto testIt = taskSet.find("Test");// 插入重复元素
taskSet.insert("Test");
taskSet.insert("Test");// 原始迭代器仍然有效
std::cout << "Original Test: " << *testIt << "\n"; // Test
std::cout << "Write still exists: " << *writeIt << "\n"; // Write// 但新元素可能插入在等价元素之间
std::cout << "All tasks: ";
for (const auto& t : taskSet) std::cout << t << " "; // Debug Test Test Test Write

3. 性能对比

操作std::setstd::multiset说明
插入 (insert)O(log n)O(log n)两者相同
查找 (find)O(log n)O(log n)两者相同
计数 (count)O(log n)O(log n + k)k为元素出现次数
范围删除 (erase)O(k log n)O(k log n)k为删除元素数量
按值删除 (erase)O(log n)O(log n + k)multiset需要删除所有副本
内存使用通常较少可能更多取决于重复元素数量

4. 使用场景对比

何时使用 std::set

  1. 需要确保元素唯一性的场景

    std::set<std::string> uniqueUsers;
void addUser(const std::string& name) {auto [_, inserted] = uniqueUsers.insert(name);if (inserted) {std::cout << "User added\n";} else {std::cout << "User already exists\n";}
}

  2. 需要检查元素是否存在的场景

    std::set<int> validCodes = {200, 201, 204, 400, 404};
bool isValid(int code) {return validCodes.find(code) != validCodes.end();
}

  3. 需要键值对但不需要映射的场景（使用set）

    std::set<std::pair<int, int>> coordinateSet;
coordinateSet.insert({10, 20});
coordinateSet.insert({30, 40});

何时使用 std::multiset

  1. 需要保留重复元素的排序序列

    std::multiset<double> temperatureReadings;
void recordTemp(double temp) {temperatureReadings.insert(temp);
}void printSortedReadings() {for (double t : temperatureReadings) {std::cout << t << "°C ";}
}

  2. 需要统计元素频率

    std::multiset<std::string> wordBag;
// 填充数据...void wordFrequency(const std::string& word) {size_t count = wordBag.count(word);std::cout << word << " appears " << count << " times\n";
}

  3. 需要处理等价元素的序列

    struct CaseInsensitiveCompare {bool operator()(const std::string& a, const std::string& b) const {return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(),[](char c1, char c2) {return std::tolower(c1) < std::tolower(c2);});}
};std::multiset<std::string, CaseInsensitiveCompare> caseInsensitiveSet;
caseInsensitiveSet.insert("Apple");
caseInsensitiveSet.insert("apple"); // 视为不同元素

5. 高级技巧

5.1 安全修改元素 (C++17+)

std::set<Person> people = {{"Alice", 30}, {"Bob", 25}};// 提取并修改
auto node = people.extract({"Alice", 30});
if (!node.empty()) {node.value().age = 31; // 安全修改people.insert(std::move(node));
}// 在multiset中也可使用
std::multiset<int> nums = {1, 2, 2, 3};
auto node = nums.extract(2); // 提取第一个2
if (!node.empty()) {node.value() = 4; // 修改为4nums.insert(std::move(node));
}

5.2 高效合并容器 (C++17+)

std::set<int> set1 = {1, 3, 5};
std::set<int> set2 = {2, 4, 5}; // 注意重复元素// 合并set
set1.merge(set2);
// set1: {1,2,3,4,5}, set2: {5}std::multiset<int> mset1 = {1, 1, 2};
std::multiset<int> mset2 = {1, 2, 3};// 合并multiset
mset1.merge(mset2);
// mset1: {1,1,1,2,2,3}, mset2: 空

总结

std::set和std::multiset的主要差异在于元素唯一性处理：

  • 使用std::set时，每个元素必须是唯一的，适用于需要确保唯一性的场景
  • 使用std::multiset时，允许元素重复，适用于需要保留重复元素的排序序列

选择建议：

  1. 需要唯一性保证 → 选择std::set
  2. 需要保留重复元素 → 选择std::multiset
  3. 需要高效元素频率统计 → 选择std::multiset
  4. 需要范围查询且结果唯一 → 选择std::set

两者共享相同的底层实现（红黑树），提供O(log n)的查找、插入和删除操作。从C++17开始，两者都支持高效的节点操作（extract/merge），可以安全修改元素内容并高效合并容器。

http://www.lryc.cn/news/610229.html

相关文章：

  • pathspec ‘with_def_layout‘ did not match any file(s) known to git`
  • jenkins+gitlab自动发布系统
  • IntelliJIDEA上传GitHub全攻略
  • JVM学习专题（四）对象创建过程
  • 数据结构：如何判断一个链表中是否存在环（Check for LOOP in Linked List）
  • IDM（Internet Download Manager）是什么？它有什么作用
  • 微帧GPU视频硬编优化引擎：面向人工智能大时代的AI算法与硬编协同优化方案
  • C语言实现Elasticsearch增删改查API
  • 部署 Kibana 8.2.2 可视化管理 Elasticsearch 8.2.2 集群
  • 解决 PS暂存盘已满的五种方法
  • PSOFT Pencil+ 4.25 插件安装教程（适用于 3ds Max 2022-2025）
  • 【c51单片机利用p2口，外接八个流水灯实现流水灯效果1.3.5.7.2.4.6.8亮】2022-10-9
  • MinIO 服务日志与监控实战：日志配置、Webhook、事件通知、Prometheus+Grafana 可视化全流程指南
  • AI 编程学习网站分享：vibe-coding-tutorial
  • SpringCloud相关知识
  • 【测试】⾃动化测试常⽤函数
  • 银河麒麟V10一键安装DM8的脚本及高阶运维SQL分享
  • 力扣-994.腐烂的橘子
  • RHCA02
  • 飞算JavaAI编程插件：以AI之力赋能Java开发，让编码效率再升级
  • 0基礎網站開發技術教學(三) --(後端PHP篇)-- [內有2025最新可用 phpstudy2018下載鏈接]
  • ShowDoc与Docmost对比分析：开源文档管理工具的选择指南
  • numpy基础知识2
  • 《P1462 通往奥格瑞玛的道路》
  • 图的存储方式-邻接表
  • 超急评估：用提前计算分摊性能成本
  • C + +
  • 机器学习（12）：拉索回归Lasso
  • Linux环境下（Ubuntu）Fortran语言如何安装配置NetCDF
  • Integer Types Range and varieties