突破编程_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。

相关文章

在Ubuntu上部署SpringBoot应用的操作步骤

在Ubuntu上部署SpringBoot应用的操作步骤

《在Ubuntu上部署SpringBoot应用的操作步骤》随着云计算和容器化技术的普及,Linux服务器已成为部署Web应用程序的主流平台之一,Java作为一种跨平台的编程语言,具有广泛的应用场景,本... 目录一、部署准备二、安装 Java 环境1. 安装 JDK2. 验证 Java 安装三、安装 mys
阅读更多...
Python中构建终端应用界面利器Blessed模块的使用

Python中构建终端应用界面利器Blessed模块的使用

《Python中构建终端应用界面利器Blessed模块的使用》Blessed库作为一个轻量级且功能强大的解决方案,开始在开发者中赢得口碑,今天,我们就一起来探索一下它是如何让终端UI开发变得轻松而高... 目录一、安装与配置：简单、快速、无障碍二、基本功能：从彩色文本到动态交互1. 显示基本内容2. 创建链
阅读更多...
深入理解C++ 空类大小

深入理解C++ 空类大小

《深入理解C++空类大小》本文主要介绍了C++空类大小,规定空类大小为1字节,主要是为了保证对象的唯一性和可区分性,满足数组元素地址连续的要求,下面就来了解一下... 目录1. 保证对象的唯一性和可区分性2. 满足数组元素地址连续的要求3. 与C++的对象模型和内存管理机制相适配查看类对象内存在C++中，规
阅读更多...
使用Nginx来共享文件的详细教程

使用Nginx来共享文件的详细教程

《使用Nginx来共享文件的详细教程》有时我们想共享电脑上的某些文件,一个比较方便的做法是,开一个HTTP服务,指向文件所在的目录,这次我们用nginx来实现这个需求,本文将通过代码示例一步步教你使用... 在本教程中，我们将向您展示如何使用开源 Web 服务器 Nginx 设置文件共享服务器步骤 0 —
阅读更多...
Golang使用minio替代文件系统的实战教程

Golang使用minio替代文件系统的实战教程

《Golang使用minio替代文件系统的实战教程》本文讨论项目开发中直接文件系统的限制或不足,接着介绍Minio对象存储的优势,同时给出Golang的实际示例代码,包括初始化客户端、读取minio对... 目录文件系统 vs Minio文件系统不足：对象存储：miniogolang连接Minio配置Min
阅读更多...
Node.js 中 http 模块的深度剖析与实战应用小结

Node.js 中 http 模块的深度剖析与实战应用小结

《Node.js中http模块的深度剖析与实战应用小结》本文详细介绍了Node.js中的http模块,从创建HTTP服务器、处理请求与响应,到获取请求参数,每个环节都通过代码示例进行解析,旨在帮... 目录Node.js 中 http 模块的深度剖析与实战应用一、引言二、创建 HTTP 服务器：基石搭建（一
阅读更多...
手把手教你idea中创建一个javaweb(webapp)项目详细图文教程

手把手教你idea中创建一个javaweb(webapp)项目详细图文教程

《手把手教你idea中创建一个javaweb(webapp)项目详细图文教程》：本文主要介绍如何使用IntelliJIDEA创建一个Maven项目,并配置Tomcat服务器进行运行,过程包括创建... 1.启动idea2.创建项目模板点击项目-新建项目-选择maven，显示如下页面输入项目名称，选择
阅读更多...
java中VO PO DTO POJO BO DO对象的应用场景及使用方式

java中VO PO DTO POJO BO DO对象的应用场景及使用方式

《java中VOPODTOPOJOBODO对象的应用场景及使用方式》文章介绍了Java开发中常用的几种对象类型及其应用场景,包括VO、PO、DTO、POJO、BO和DO等,并通过示例说明了它... 目录Java中VO PO DTO POJO BO DO对象的应用VO (View Object) - 视图对象
阅读更多...
Python基于火山引擎豆包大模型搭建QQ机器人详细教程(2024年最新)

Python基于火山引擎豆包大模型搭建QQ机器人详细教程(2024年最新)

《Python基于火山引擎豆包大模型搭建QQ机器人详细教程(2024年最新)》：本文主要介绍Python基于火山引擎豆包大模型搭建QQ机器人详细的相关资料,包括开通模型、配置APIKEY鉴权和SD... 目录豆包大模型概述开通模型付费安装 SDK 环境配置 API KEY 鉴权Ark 模型接口Prompt
阅读更多...
在 VSCode 中配置 C++ 开发环境的详细教程

在 VSCode 中配置 C++ 开发环境的详细教程

《在VSCode中配置C++开发环境的详细教程》本文详细介绍了如何在VisualStudioCode（VSCode）中配置C++开发环境,包括安装必要的工具、配置编译器、设置调试环境等步骤,通... 目录如何在 VSCode 中配置 C++ 开发环境：详细教程1. 什么是 VSCode？2. 安装 VSCo
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2