STL关联式容器介绍

embedded/2024/11/19 2:05:28/

在前文中介绍了STL的序列式容器;

STL序列式容器之vector-CSDN博客

STL序列式容器之list-CSDN博客

STL序列式容器之deque-CSDN博客

STL序列式容器之stack-CSDN博客

STL序列式容器之queue-CSDN博客

STL序列式容器之heap(堆)-CSDN博客

STL序列式容器之priority_queue-CSDN博客

STL序列式容器之slist-CSDN博客

接下来对关联式容器(associative containers)进行学习及分享;

        根据“数据在容器中的排列”特性,容器可概分为序列式(Sequence)和关联式(associative)两种。

        标准的STL关联式容器分为set(集合)和map(映射表)两大类,以及两大类的衍生体multiset(多键集合)和multimap(多键映射表)。这些容器底层机制均以RB-tree(红黑树)完成。RB-tree也是独立容器,但并不开放给外界使用。

        此外,SGI STL还提供了一个不在标准规格之类的关联式容器:hash table(散列表),以及以此hash table为底层机制完成的hash_set(散列集合)、hash_map(散列映射表)、hash_mulitset(散列多键集合)、hash_mulitmap(散列多键映射表)。

关联式容器,观念上类似关联式数据库:每条数据(每个元素)都有一个键值(key)和实值(value)。当元素被插入到关联式容器中时,容器内部结构便依据其键值大小,以某种特定规则将这个元素放置于适当位置。关联式容器没有所谓头尾、所以不会有push_back,push_front,pop_back,pop_front这样的操作行为。

        begin()、end()可以在遍历时使用

        一般而言,关联式容器的内部结构是一个balanced binary tree (平衡二叉树),以便获得良好的搜索效率。balanced binary tree有许多种类型,包括AVL-tree,RB-tree,AA-tree,其中最被广泛运用于STL的是RB-tree(红黑树)。为了探讨STL的关联式容器,我们必须先探讨RB-tree。

        进入RB-tree主题之前,让我们先对tree的来龙去脉有个概念。以下讨论都和最终目标RB-tree有密切关联。

        树因为耳熟能详此处就不做过多的解释了;

二叉搜索树(binary search tree)

        所谓二叉树,其意义是:“任何节点最多只允许两个子节点”。这两个子节点称为左子结点和右子节点。如果以递归方式来定义二叉树,我们可以说:“如果一个二叉树不为空,便是由一个根节点和左右两子树构成;左右子树都有可能为空”。二叉树的应用极广;

        所谓二叉搜索数(binary search tree),可提供对数时间(logarithmic time)的元素插入和访问。二叉搜索树的节点放置规则是:任何节点的键值一定大于其左子树中的每一个节点的键值,并小于其右子树中的每一个节点的键值。因此,从根节点一直往左走,直到无左路可走,即得最小元素;从根节点一直往右走,直至无右路可走,即得最大元素。下图即为一颗二叉搜索树

现在简要介绍二叉搜索树的插入节点及删除节点;

对于插入节点,首先进行查找,将插入值与当前节点key进行比较,如果比当前节点大就进入左子树,如果比当前节点大进入右子树,如果和当前节点key相等,则退出(找到了key值相同的节点说明节点已经存在则不进行插入操作),直到叶子节点后,将节点插入;比如插入节点11,则其查找路径(沿着淡蓝色箭头往下)如下所示:

沿着10->20->14的路径向下,发现14为叶子节点,然后将11加入到其左子树。

对于删除操作,分为三种情况;1,删除节点为叶子节点,2:删除节点只有一个子节点,3:删除节点由两个子节点。

对于情况1:直接将节点移除出即可;比如删除节点为9;则删除节点后,状态为:

为了演示方便,在8和9之间新增了一个虚线箭头,事实上8的右节点置为了空,此时9节点将会被删除。最终节点状态为:

对于情况2,比如删除节点8,此时8正好有一个子节点;将8的子节点替换掉待删除的节点,即可完成删除操作;如下图所示

节点6将替换节点8

最后树将变成:

再来看情况3;比如删除节点key为20,此时节点20,存在两个节点,首先找到20,右子树的最小节点,21,而后,将21替换到20;过程如下

第一步定位到节点20,发现节点20存在两个子节点;然后查找右子树的最小节点,并将最小节21点替换当前节点20;如下所示:

最终二叉搜索树转换为:

参考文档《STL源码剖析--侯捷》


http://www.ppmy.cn/embedded/138667.html

相关文章

HTML之列表学习记录

练习题&#xff1a; 图所示为一个问卷调查网页&#xff0c;请制作出来。要求&#xff1a;大标题用h1标签&#xff1b;小题目用h3标签&#xff1b;前两个问题使用有序列表&#xff1b;最后一个问题使用无序列表。 代码&#xff1a; <!DOCTYPE html> <html> <he…

构建SSH僵尸网络

import argparse import paramiko# 定义一个名为Client的类&#xff0c;用于表示SSH客户端相关操作 class Client:# 类的初始化方法&#xff0c;接收主机地址、用户名和密码作为参数def __init__(self, host, user, password):self.host hostself.user userself.password pa…

从 Rust 官方文档理解 Ownership

Rust 的 Ownership 感觉仍然很复杂&#xff0c;但 Rust 官方文档 The Rust Programming Language - Understanding Ownership 所费篇幅似乎并不多。下面就阅读该文档并记录下来对 Rust Ownership 的理解&#xff0c;相信官方的文档会表述的比准确而清晰。 本文中对 Ownership,…

QT_CONFIG宏使用

时常在Qt代码中看到QT_CONFIG宏&#xff0c;之前以为和#define、DEFINES 差不多&#xff0c;看了定义才发现不是那么回事&#xff0c;定义如下&#xff1a; 看注释就知道了QT_CONFIG宏&#xff0c;其实是&#xff1a;实现了一个在编译时期安全检查&#xff0c;检查指定的Qt特性…

uni-app快速入门(七)--组件路由跳转和API路由跳转及参数传递

uni-app有两种页面路由跳转模式&#xff0c;即使用navigator组件跳转和调用API跳转&#xff0c;API调转不要理解为调用后台接口的API&#xff0c;而是指脚本函数中使用跳转函数。 一、组件路由跳转 1.1 打开新页面 打开新页面使用组件的open-type"navigate",见下面…

【WPF】Prism学习(二)

Prism Commands 1.命令&#xff08;Commanding&#xff09; 1.1. ViewModel的作用&#xff1a; ViewModel不仅提供在视图中显示或编辑的数据&#xff0c;还可能定义一个或多个用户可以执行的动作或操作。这些用户可以通过用户界面&#xff08;UI&#xff09;执行的动作或操作…

Chrome 浏览器开启打印模式

打开开发者工具ctrl shift p输入print 找到 Emulate CSS print media type

Java基础-组件及事件处理(下)

(创作不易&#xff0c;感谢有你&#xff0c;你的支持&#xff0c;就是我前行的最大动力&#xff0c;如果看完对你有帮助&#xff0c;请留下您的足迹&#xff09; 目录 面板组件 说明 常见组件 JScrollPane常用构造方法 JScrollPane设置面板滚动策略的方法 JScrollPane滚…