分类：C嘎嘎 - 枫叶先生的网络日志

24_「C++进阶」六、红黑树

C嘎嘎

「前言」文章的大致内容是红黑树。一、红黑树的概念红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是 Red 或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。如下图就是一棵红黑树：二

23_「C++进阶」五、AVL树

C嘎嘎

「前言」前面对 map/multimap/set/multiset 进行了简单的介绍，在其文档介绍中发现，这几个容器有个共同点是：其底层都是按照红黑树（二叉搜索树）来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因

22_「C++进阶」四、STL---set和map的介绍和使用

C嘎嘎

「前言」文章的大致内容是 set 和 map 的介绍和使用。一、关联式容器前面已经接触过 STL 中的部分容器，比如：vector、list、deque等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身什么是关联式容器？关联式容器也是用来存储数据的，与序列式容

21_「C++进阶」三、二叉搜索树

C嘎嘎

「前言」文章的大致内容是二叉搜索树。二叉搜索树是数据结构初阶二叉树的一部分，二叉搜索树为后序所学的 map 和 set 做准备。一、二叉搜索树 1.1 概念二叉搜索树（BST，Binary Search Tree）又称二叉排序树，它或者是一棵空树，二叉树搜索树具有以下性质: 若它的左子树不为空，

20_「C++进阶」二、多态详解

C嘎嘎

「前言」文章的大致内容是多态的讲解。一、多态的概念多态通俗来说，就是多种形态，具体点就是去完成某个行为，当不同的对象去完成时会产生出不同的状态。比如，在现实生活中买票这个行为，当普通人买票时，是全价买票；学生买票时，是半价买票；军人买票时是优先买票。二、多态的定义及实现 2.1 多态的构成条

19_「C++进阶」一、继承详解

C嘎嘎

「前言」面向对象三大特性是：封装、继承、多态，封装初阶的时候已经讲了，进阶开始讲解继承和多态和一些更复杂的结构，今天的篇章是讲解继承。一、继承的概念及定义 1.1 继承概念继承(inheritance)机制是面向对象程序设计使代码可以复用的最重要的手段，它允许程序员在保持原有类特性的基础上进行扩

18_【C++初阶】十三、模板进阶

C嘎嘎

「前言」之前模板初阶并没有把 C++模板讲完，因为当时没有接触 STL，下面讲解模板后半部分。一、非类型模板参数模板参数分类类型形参与非类型形参：类型形参：即出现在模板参数列表中，跟在 class 或者 typename 之类的参数类型名称非类型形参，就是用一个常量作为类(函数)模板的一个参

17_【C++初阶】十二、STL---反向迭代器的实现

C嘎嘎

「前言」文章的大致内容是反向迭代器的介绍与实现。一、反向迭代器之前的模拟实现vector、list 的时候，这些都是实现了正向迭代器，反向迭代器都没有实现，这里就要实现反向迭代器反向迭代器也是适配器（配接器）的一种，反向迭代器的实现是对正向迭代器的封装，即实现的反向迭代器能支持多种容器，给出该

16_【C++初阶】十一、STL---priority_queue（优先级队列）

C嘎嘎

「前言」文章的大致内容是 priority_queue 介绍和使用，以及模拟实现。一、priority_queue介绍 priority_queue文档介绍翻译：优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。 <

15_【C++初阶】十、STL---stack && queue 介绍及使用

C嘎嘎

「前言」文章的大致内容是 stack 和 queue 介绍和使用。一、stack介绍和使用 1.1 stack的介绍 stack的文档介绍介绍：（1）stack 是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作（2）sta