multiset底层原理,红黑树原理

简介: multiset底层原理,红黑树原理

multiset 底层实现原理

mulitiset 默认采用 less ,即由小到大的顺序排序

平衡二插搜索树

//AVL树
typedef struct TreeNode {
  struct TreeNode *parent;
  struct TreeNode *left;
  struct TreeNode *right;
  int key;  //维持有序
  int data;  //节点尔达斯信息
  //bool color 红黑树当中还具有color信息
} TreeNode;
void inorder (TreeNode *node) {
  if (node != nullptr) {
    inorder(node->left);
    printf("k:%d v:%d", node->key, node->data);
    inorder(node->right);
  }
}

STL中红黑树的实现

记录的信息:a. 根节点位置;b. 最左侧节点位置;c. 最右侧节点位置。迭代器采用中序遍历的方式进行遍历。

类比 set、multiset、map、multimap

  1. set和multiset会根据特定的排序准则自动将元素排序,set中元素不允许重复,multiset可以重复.
  2. map和multimap将key和value组成的pair作为元素,根据key的排序准则自动将元素排序(因为红黑树也是二叉搜索树,所以map默认是按key排序的),map中元素的key不允许重复,multimap可以重复 。
#include <set>
#include <map>
#include <iostream>
using namespace std;
int main() {
  set<int> s;
  multiset<int> ms;
  map<int,int> m;
  multimap<int,int> mm;
  return 0;
}

充电站

推荐一个零声学院免费公开课程,个人觉得老师讲得不错,分享给大家:Linux,Nginx,ZeroMQ,MySQL,Redis,fastdfs,MongoDB,ZK,流媒体,CDN,P2P,K8S,Docker,TCP/IP,协程,DPDK等技术内容,立即学习


相关文章
|
12月前
|
消息中间件 Java 调度
深入探讨进程、线程和协程之间的区别和联系
本文深入解析进程、线程与协程的核心区别与联系,涵盖资源分配、调度机制、通信方式及性能对比。结合代码示例与实际场景,阐明三者在高并发系统中的协同应用,助你掌握现代并发编程设计精髓。(239字)
874 11
|
Ubuntu 安全 Linux
在Ubuntu 20.04上安装和配置VNC的方法
在Ubuntu 20.04上安装和配置VNC的方法
3077 0
|
前端开发 数据处理 Android开发
Android项目架构设计问题之业务间的解耦合如何解决
Android项目架构设计问题之业务间的解耦合如何解决
324 1
|
存储 并行计算 算法
[Eigen中文文档] 概述(总目录)
Eigen是基于线性代数的C ++模板库,主要用于矩阵,向量,数值求解器和相关算法。常用的Ceres、G2O等项目均是基于Eigen库。 本系列文章将通过官方文档带你了解Eigen。
4140 1
|
存储 SQL druid
​十分钟了解 Apache Druid
​十分钟了解 Apache Druid
2160 1
|
存储 算法 搜索推荐
Python高级数据结构——图(Graph)
Python高级数据结构——图(Graph)
847 0
|
存储 编译器 对象存储
详解map、set、multimap、multiset的使用
详解map、set、multimap、multiset的使用
889 0
|
JavaScript
vue项目中使用svg并设置大小颜色等样式
vue项目中使用svg并设置大小颜色等样式
1035 0
|
自然语言处理 程序员 数据安全/隐私保护
GitHub 标星 4.9k,李笑来开源的英语学习课
GitHub 标星 4.9k,李笑来开源的英语学习课
1889 0