突破编程_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++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
C++初始化数组的几种常见方法(简单易懂)

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化（推荐方式）1.2、初始化部分列表1.3、使用std::
阅读更多...
C++ Primer 多维数组的使用

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没
阅读更多...
使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

《使用sql-research-assistant进行SQL数据库研究的实战指南(代码实现演示)》本文介绍了sql-research-assistant工具,该工具基于LangChain框架,集... 目录技术背景介绍核心原理解析代码实现演示安装和配置项目集成LangSmith 配置（可选）启动服务应用场景
阅读更多...
Ubuntu固定虚拟机ip地址的方法教程

Ubuntu固定虚拟机ip地址的方法教程

《Ubuntu固定虚拟机ip地址的方法教程》本文详细介绍了如何在Ubuntu虚拟机中固定IP地址,包括检查和编辑`/etc/apt/sources.list`文件、更新网络配置文件以及使用Networ... 1、由于虚拟机网络是桥接，所以ip地址会不停地变化，接下来我们就讲述ip如何固定 2、如果apt安
阅读更多...
PyCharm 接入 DeepSeek最新完整教程

PyCharm 接入 DeepSeek最新完整教程

《PyCharm接入DeepSeek最新完整教程》文章介绍了DeepSeek-V3模型的性能提升以及如何在PyCharm中接入和使用DeepSeek进行代码开发,本文通过图文并茂的形式给大家介绍的... 目录DeepSeek-V3效果演示创建API Key在PyCharm中下载Continue插件配置Con
阅读更多...
Deepseek R1模型本地化部署+API接口调用详细教程(释放AI生产力)

Deepseek R1模型本地化部署+API接口调用详细教程(释放AI生产力)

《DeepseekR1模型本地化部署+API接口调用详细教程(释放AI生产力)》本文介绍了本地部署DeepSeekR1模型和通过API调用将其集成到VSCode中的过程,作者详细步骤展示了如何下载和... 目录前言一、deepseek R1模型与chatGPT o1系列模型对比二、本地部署步骤1.安装oll
阅读更多...
在不同系统间迁移Python程序的方法与教程

在不同系统间迁移Python程序的方法与教程

《在不同系统间迁移Python程序的方法与教程》本文介绍了几种将Windows上编写的Python程序迁移到Linux服务器上的方法,包括使用虚拟环境和依赖冻结、容器化技术（如Docker）、使用An... 目录使用虚拟环境和依赖冻结1. 创建虚拟环境2. 冻结依赖使用容器化技术（如 docker）1. 创
阅读更多...
Spring Boot整合log4j2日志配置的详细教程

Spring Boot整合log4j2日志配置的详细教程

《SpringBoot整合log4j2日志配置的详细教程》：本文主要介绍SpringBoot项目中整合Log4j2日志框架的步骤和配置,包括常用日志框架的比较、配置参数介绍、Log4j2配置详解... 目录前言一、常用日志框架二、配置参数介绍1. 日志级别2. 输出形式3. 日志格式3.1 PatternL
阅读更多...
MySQL8.2.0安装教程分享

MySQL8.2.0安装教程分享

《MySQL8.2.0安装教程分享》这篇文章详细介绍了如何在Windows系统上安装MySQL数据库软件,包括下载、安装、配置和设置环境变量的步骤... 目录mysql的安装图文1.python访问网址2javascript.点击3.进入Downloads向下滑动4.选择Community Server5.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2