突破编程_C++_STL教程（ multiset 的实战应用）

2024-03-09 13:20
文章标签 实战 c++ 应用 教程 编程 stl multiset 突破

本文主要是介绍突破编程_C++_STL教程（ multiset 的实战应用），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 std::multiset 的主要应用场景

std::multiset的主要特性是允许存储多个具有相同值的元素，并按照一定的排序规则对这些元素进行排序。它的底层实现通常基于红黑树，这使得它的插入、删除和查找操作的时间复杂度均为O(log n)。

std::multiset 的主要应用场景包括：

（1）需要存储重复元素的排序序列： 当需要存储一个元素可能出现多次的序列，并且希望这个序列保持有序时，std::multiset是一个很好的选择。例如，你可能需要存储一个班级中所有学生的成绩，由于可能有多个学生获得相同的分数，因此使用std::multiset可以方便地存储和排序这些成绩。

（2）需要频繁进行插入、删除和查找操作的场景： 由于std::multiset的底层实现是红黑树，它提供了高效的插入、删除和查找操作。因此，当需要在大量增加、删除数据的同时，还要进行大量数据的查找时，std::multiset是一个很好的选择。

（3）作为数据结构的中间处理结果： 在处理复杂的算法和数据结构问题时，可能需要生成一系列的中间结果，这些中间结果可能是包含重复元素的排序序列。在这些情况下，可以使用 std::multiset 作为临时存储结构，方便后续处理。

需要注意的是，虽然 std::multiset 提供了方便的元素插入、删除和查找操作，但由于其内部维护了元素的排序状态，因此在插入或删除元素时可能需要调整整个树的结构，这可能会带来一定的性能开销。因此，在选择使用 std::multiset 时，需要根据具体的应用场景和需求进行权衡。

1.1 std::multiset 应用于存储重复元素的排序序列

以下是一个使用 std::multiset 存储重复元素的排序序列的示例：

#include <iostream>  
#include <set>  
#include <vector>  int main() 
{// 创建一个 multiset 容器，用于存储 int 类型的元素  std::multiset<int> ms;// 向 multiset 中插入元素  ms.insert(3);ms.insert(1);ms.insert(1);ms.insert(2);ms.insert(5);ms.insert(2);ms.insert(4);ms.insert(4);// 输出 multiset 中的元素，由于 multiset 是排序的，所以输出也将是排序的  for (const auto& elem : ms) {std::cout << elem << " ";}std::cout << std::endl;// 查找元素  int value_to_find = 2;auto it = ms.find(value_to_find);if (it != ms.end()) {std::cout << "Found " << value_to_find << " in the multiset." << std::endl;}else {std::cout << "Did not find " << value_to_find << " in the multiset." << std::endl;}// 删除元素  size_t count_removed = ms.erase(4);std::cout << "Removed " << count_removed << " elements with value 4." << std::endl;// 再次输出 multiset 中的元素  std::cout << "Current elements in the multiset: ";for (const auto& elem : ms) {std::cout << elem << " ";}std::cout << std::endl;return 0;
}

上面代码的输出为：

1 1 2 2 3 4 4 5
Found 2 in the multiset.
Removed 2 elements with value 4.
Current elements in the multiset: 1 1 2 2 3 5

在这个示例中，首先创建了一个 std::multiset<int> 对象 ms，然后向其中插入了一些整数。由于 multiset 允许存储重复的元素，因此可以多次插入相同的值。接下来，通过一个范围 for 循环遍历 multiset 并输出其中的元素，由于 multiset 是有序的，因此输出也将是排序的。

然后，尝试查找一个特定的值（在这个例子中是 2），并检查它是否存在于 multiset 中。如果找到了该值，将输出一条消息。

接下来，使用 erase 函数删除值为 4 的所有元素，并输出被删除的元素数量。

最后，再次遍历并输出 multiset 中的剩余元素，以展示删除操作的效果。

1.2 std::multiset 应用于需要频繁进行插入、删除和查找操作的场景

std::multiset 是一个适用于需要频繁进行插入、删除和查找操作的场景的数据结构。由于其底层通常基于红黑树实现，这些操作都可以在对数时间复杂度内完成，使得 std::multiset 在处理大量数据时仍能保持高效的性能。

以下是一个使用 std::multiset 来处理频繁插入、删除和查找操作的示例：

#include <iostream>  
#include <set>  
#include <vector>  
#include <chrono>  
#include <random>  // 生成一个随机整数  
int generateRandomInt(int min, int max) 
{std::random_device rd;std::mt19937 gen(rd());std::uniform_int_distribution<> dis(min, max);return dis(gen);
}int main() 
{// 创建一个 multiset 容器，用于存储 int 类型的元素  std::multiset<int> ms;// 插入元素 - 假设有大量的插入操作  const int numElements = 100000;const int minValue = 0;const int maxValue = 1000000;for (int i = 0; i < numElements; ++i) {ms.insert(generateRandomInt(minValue, maxValue));}// 查找元素 - 假设有频繁的查找操作  int valueToFind = generateRandomInt(minValue, maxValue);auto it = ms.find(valueToFind);if (it != ms.end()) {std::cout << "Found " << valueToFind << " in the multiset." << std::endl;}else {std::cout << "Did not find " << valueToFind << " in the multiset." << std::endl;}// 删除元素 - 假设有删除操作  size_t countRemoved = ms.erase(valueToFind);std::cout << "Removed " << countRemoved << " elements with value " << valueToFind << "." << std::endl;// 再次插入元素，模拟插入操作  for (int i = 0; i < 1000; ++i) {ms.insert(generateRandomInt(minValue, maxValue));}// 性能测试：频繁插入、查找和删除  auto start = std::chrono::high_resolution_clock::now();for (int i = 0; i < numElements; ++i) {int newValue = generateRandomInt(minValue, maxValue);ms.insert(newValue); // 插入  if (i % 1000 == 0) {ms.find(newValue); // 查找  ms.erase(newValue); // 删除  }}auto end = std::chrono::high_resolution_clock::now();std::chrono::duration<double> diff = end - start;std::cout << "Time taken for " << numElements << " operations: " << diff.count() << " seconds." << std::endl;return 0;
}

上面代码的输出为：

Found 572705 in the multiset.
Removed 1 elements with value 572705.
Time taken for 100000 operations: 0.445264 seconds.

在这个示例中，首先生成大量随机整数，并将它们插入到 std::multiset 中。然后，查找一个随机值，并删除所有具有该值的元素。接下来，模拟了一个性能测试的场景，其中反复执行插入、查找和删除操作，并测量所需的时间。

由于 std::multiset 的内部实现保证了这些操作的效率，因此即使在大规模数据集上，这个示例也应该能够保持相对稳定的性能。这显示了 std::multiset 在需要频繁进行插入、删除和查找操作的场景中的适用性。

需要注意的是，虽然 std::multiset 提供了这些操作的效率，但在某些特定场景下，其他数据结构（如哈希表）可能更适合，尤其是当不需要排序特性时。因此，在选择数据结构时，需要根据具体的应用场景和需求进行权衡。

1.3 std::multiset 应用于作为数据结构的中间处理结果

std::multiset 在处理复杂的算法和数据结构问题时，经常作为中间处理结果使用，特别是在需要临时存储包含重复元素的排序序列时。以下是一个这样的示例，它展示了在算法处理过程中使用 std::multiset 存储中间结果，并随后利用这些结果进一步处理。

假设有一个任务，需要找出给定整数数组中所有数字的频率，并且需要找出频率最高的数字。在处理过程中，可以使用 std::multiset 来存储每个数字的频率，因为频率可能会有重复（即多个数字可能有相同的频率）。

#include <iostream>  
#include <vector>  
#include <set>  
#include <algorithm>  int main() 
{// 假设这是输入的数组  std::vector<int> numbers = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5 };// 使用 multiset 存储频率，key 为频率，value 为该频率对应的数字  std::multiset<std::pair<int, int>> freqSet;// 计算每个数字的频率，并将频率和数字的配对存储到 multiset 中  for (int num : numbers) {// 查找当前数字的频率  auto it = freqSet.find({ 1, num });if (it != freqSet.end()) {// 如果找到了，增加频率  freqSet.erase(it);freqSet.insert({ it->first + 1, num });}else {// 如果没有找到，插入新的频率（1）和数字的配对  freqSet.insert({ 1, num });}}// 现在 freqSet 包含了每个数字的频率，并且这些频率是排序的  // 找出频率最高的数字  if (!freqSet.empty()) {// 频率最高的数字对应的频率在 multiset 的末尾  auto maxFreqPair = *freqSet.rbegin();int maxFreq = maxFreqPair.first;int numWithMaxFreq = maxFreqPair.second;std::cout << "Number with the highest frequency: " << numWithMaxFreq << std::endl;std::cout << "Frequency: " << maxFreq << std::endl;}else {std::cout << "The input vector is empty." << std::endl;}return 0;
}

上面代码的输出为：

Number with the highest frequency: 4
Frequency: 2

在这个示例中，首先创建了一个 std::multiset 来存储频率和数字的配对。然后，遍历输入数组，对于每个数字，需要检查它是否已经在 multiset 中有对应的频率。如果有，则增加它的频率；如果没有，则插入一个新的频率（初始为1）和数字的配对。由于 multiset 是自动排序的，因此频率也是排序的。

最后，通过访问 multiset 的末尾元素（即频率最高的元素）来找出频率最高的数字。这个例子展示了 std::multiset 如何作为算法处理过程中的中间数据结构，帮助我们有效地存储和处理包含重复元素的排序序列。

2 实现一个简单的 std::multiset 容器

实现一个完整的 std::multiset 容器是一个相当复杂的任务，因为需要考虑到许多细节，比如红黑树的实现、迭代器、异常安全性等。但是，为了展示基本的思路，可以简化这个过程，使用红黑树作为底层数据结构，实现元素的插入与打印。

注意红黑树具有以下五个关键性质：

（1）每个节点要么是红色，要么是黑色。
（2）根节点是黑色。
（3）所有叶子节点（NIL或空节点）是黑色。
（4）如果一个节点是红色的，则它的两个子节点都是黑色。
（5）对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点。

这些性质确保了红黑树在插入、删除节点后仍然能够保持相对平衡，从而保证了树的查找、插入和删除操作的时间复杂度为O(log n)。

如下是使用红黑树作为底层数据结构的 std::multiset 容器实现：

#include <iostream>  
#include <vector>  
#include <algorithm>enum Color { RED, BLACK };template <typename T>
struct Node {std::vector<T> datas;Color color;Node* left;Node* right;Node* parent;Node(std::vector<T> value, Color c = RED, Node* p = nullptr, Node* l = nullptr, Node* r = nullptr): datas(value), color(c), parent(p), left(l), right(r) {}
};template <typename T>
class SimpleMultiset
{
public:SimpleMultiset() : root(nullptr) {}// 插入元素  void insert(const T& value) {root = insert(root, value);}// 打印元素  void print() {inorderTraversal(root);std::cout << std::endl;}// 析构函数，用于释放内存  ~SimpleMultiset() {// 递归删除所有节点  deleteTree(root);}
private:// 递归删除树void deleteTree(Node<T>* node) {if (node != nullptr) {deleteTree(node->left);deleteTree(node->right);delete node;}}// 辅助函数：检查节点是否是红色或黑色  bool isRed(Node<T>* node) const {if (node == nullptr) return false;return node->color == RED;}bool isBlack(Node<T>* node) const {if (node == nullptr) return true;return node->color == BLACK;}// 左旋  void leftRotate(Node<T>*& x) {Node<T>* y = x->right;x->right = y->left;if (y->left) y->left->parent = x;y->parent = x->parent;if (!x->parent) root = y;else if (x == x->parent->left) x->parent->left = y;else x->parent->right = y;y->left = x;x->parent = y;}// 右旋  void rightRotate(Node<T>*& x) {Node<T>* y = x->left;x->left = y->right;if (y->right) y->right->parent = x;y->parent = x->parent;if (!x->parent) root = y;else if (x == x->parent->right) x->parent->right = y;else x->parent->left = y;y->right = x;x->parent = y;}// 插入修复  void fixInsert(Node<T>*& k) {while (k != root && isRed(k->parent)) {if (isRed(k->parent->parent->left) == (k == k->parent->right)) {Node<T>* u = k->parent->parent->left;if (u) u->color = RED;k->parent->color = BLACK;k->parent->parent->color = RED;k = k->parent->parent;}else {if (k == k->parent->left) {k = k->parent;rightRotate(k);}k->parent->color = BLACK;k->parent->parent->color = RED;leftRotate(k->parent->parent);}}root->color = BLACK;}// 插入节点  Node<T>* insert(Node<T>*& node, const T& value) {if (node == nullptr) {return new Node<T>(std::vector<T>{value});}if (value < node->datas[0]) {node->left = insert(node->left, value);node->left->parent = node;}else if (value > node->datas[0]) {node->right = insert(node->right, value);node->right->parent = node;}else {node->datas.emplace_back(value);return node;}// 修复红黑树性质  if (isRed(node->right) && isRed(node->left)) {node->color = RED;node->left->color = BLACK;node->right->color = BLACK;}else if (isRed(node->parent) && isRed(node->parent->parent) &&(node == node->parent->right ||(node->parent == node->parent->parent->left &&node == node->parent->left))) {node->parent->color = BLACK;node->parent->parent->color = RED;if (node == node->parent->left) {rightRotate(node->parent->parent);}else {leftRotate(node->parent->parent);}}if (node->parent == nullptr) {root = node;}fixInsert(node);return node;}// 中序遍历打印，用于验证  void inorderTraversal(Node<T>* node) {if (node != nullptr) {inorderTraversal(node->left);for_each(node->datas.begin(), node->datas.end(), [](T& val){std::cout << val << " ";});			inorderTraversal(node->right);}}private:Node<T>* root;};int main()
{SimpleMultiset<int> vals;vals.insert(5);vals.insert(3);vals.insert(8);vals.insert(1);vals.insert(2);vals.insert(2);vals.insert(6);vals.insert(6);vals.print(); // 打印集合return 0;
}

上面代码的输出为：

1 2 2 3 5 6 6 8

上面的这段代码定义了一个简单的集合类 SimpleMultiset，但请注意，它并不是真正的红黑树实现，尽管代码中有一些红黑树的元素，如颜色枚举、左旋和右旋操作。它更接近于一个多值 B 树（B 树的一个变种），其中每个节点可以包含多个键值对。
可以参考对比前面教程"突破编程_C++_STL教程（ set 的实战应用）"中"实现一个简单的 std::set 容器"的章节，最大的区别就是，将 struct Node 中的 T data 调整成为 std::vector<T> datas; ，这样便可以存储重复元素。

这篇关于突破编程_C++_STL教程（ multiset 的实战应用）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/790808。

相关文章

C++中unordered_set哈希集合的实现

C++中unordered_set哈希集合的实现

《C++中unordered_set哈希集合的实现》std::unordered_set是C++标准库中的无序关联容器,基于哈希表实现,具有元素唯一性和无序性特点,本文就来详细的介绍一下unorder... 目录一、概述二、头文件与命名空间三、常用方法与示例1. 构造与析构2. 迭代器与遍历3. 容量相关4
阅读更多...
C++中悬垂引用(Dangling Reference) 的实现

C++中悬垂引用(Dangling Reference) 的实现

《C++中悬垂引用(DanglingReference)的实现》C++中的悬垂引用指引用绑定的对象被销毁后引用仍存在的情况,会导致访问无效内存,下面就来详细的介绍一下产生的原因以及如何避免,感兴趣... 目录悬垂引用的产生原因1. 引用绑定到局部变量，变量超出作用域后销毁2. 引用绑定到动态分配的对象，对象
阅读更多...
Java AOP面向切面编程的概念和实现方式

Java AOP面向切面编程的概念和实现方式

《JavaAOP面向切面编程的概念和实现方式》AOP是面向切面编程,通过动态代理将横切关注点（如日志、事务）与核心业务逻辑分离,提升代码复用性和可维护性,本文给大家介绍JavaAOP面向切面编程的概... 目录一、AOP 是什么？二、AOP 的核心概念与实现方式核心概念实现方式三、Spring AOP 的关
阅读更多...
Python版本信息获取方法详解与实战

Python版本信息获取方法详解与实战

《Python版本信息获取方法详解与实战》在Python开发中,获取Python版本号是调试、兼容性检查和版本控制的重要基础操作,本文详细介绍了如何使用sys和platform模块获取Python的主... 目录1. python版本号获取基础2. 使用sys模块获取版本信息2.1 sys模块概述2.1.1
阅读更多...
全网最全Tomcat完全卸载重装教程小结

全网最全Tomcat完全卸载重装教程小结

《全网最全Tomcat完全卸载重装教程小结》windows系统卸载Tomcat重新通过ZIP方式安装Tomcat,优点是灵活可控,适合开发者自定义配置,手动配置环境变量后,可通过命令行快速启动和管理... 目录一、完全卸载Tomcat1. 停止Tomcat服务2. 通过控制面板卸载3. 手动删除残留文件4.
阅读更多...
Python爬虫HTTPS使用requests,httpx,aiohttp实战中的证书异步等问题

Python爬虫HTTPS使用requests,httpx,aiohttp实战中的证书异步等问题

《Python爬虫HTTPS使用requests,httpx,aiohttp实战中的证书异步等问题》在爬虫工程里,“HTTPS”是绕不开的话题,HTTPS为传输加密提供保护,同时也给爬虫带来证书校验、... 目录一、核心问题与优先级检查（先问三件事）二、基础示例：requests 与证书处理三、高并发选型：
阅读更多...
利用Python操作Word文档页码的实际应用

利用Python操作Word文档页码的实际应用

《利用Python操作Word文档页码的实际应用》在撰写长篇文档时,经常需要将文档分成多个节,每个节都需要单独的页码,下面：本文主要介绍利用Python操作Word文档页码的相关资料,文中通过代码... 目录需求：文档详情：要求：该程序的功能是：总结需求：一次性处理24个文档的页码。文档详情：1、每个
阅读更多...
Python的pandas库基础知识超详细教程

Python的pandas库基础知识超详细教程

《Python的pandas库基础知识超详细教程》Pandas是Python数据处理核心库,提供Series和DataFrame结构,支持CSV/Excel/SQL等数据源导入及清洗、合并、统计等功能... 目录一、配置环境二、序列和数据表2.1 初始化2.2  获取数值2.3 获取索引2.4 索引取内容2
阅读更多...
python依赖管理工具UV的安装和使用教程

python依赖管理工具UV的安装和使用教程

《python依赖管理工具UV的安装和使用教程》UV是一个用Rust编写的Python包安装和依赖管理工具,比传统工具（如pip）有着更快、更高效的体验,：本文主要介绍python依赖管理工具UV... 目录前言一、命令安装uv二、手动编译安装2.1在archlinux安装uv的依赖工具2.2从github
阅读更多...
C++读写word文档(.docx)DuckX库的使用详解

C++读写word文档(.docx)DuckX库的使用详解

《C++读写word文档(.docx)DuckX库的使用详解》DuckX是C++库,用于创建/编辑.docx文件,支持读取文档、添加段落/片段、编辑表格,解决中文乱码需更改编码方案,进阶功能含文本替换... 目录一、基本用法1. 读取文档3. 添加段落4. 添加片段3. 编辑表格二、进阶用法1. 文本替换2
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2