1.1、Set容器基本概念
Set的特性是,所有元素都会根据元素的键值自动被排序。Set的元素不像map那样可以同时拥有实值和键值,set的元素即是键值又是实值。set不允许两个元素有相同的键值。
我们可以通过set的迭代器改变set元素的值吗?不行,因为set元素值就是其键值,关系到set元素的排序规则。如果任意改变set元素值,会严重破坏set组织,换句话说,set的iterator是一种const iterator。
set拥有和list某些相同的性质,当对容器中的元素插入操作或者删除操作的时候,操作之前所有的迭代器,在操作完成之后依然有效,被删除的那个元素的迭代器必然是一个例外。
1.2、Multiset容器基本概念
multiset特性及用法和set完全相同,唯一的差别在于它允许键值重复。set和multiset的底层实现是红黑树,平衡二叉树的一种。
树的简单知识:
二叉树就是任何节点最多只允许有两个字节点,分别是左节点和右节点。
二叉搜索树(TOP N 问题排序),是指二叉树中的节点按照一定的规则进行排序,使得对二叉树中元素访问更加高效。二叉搜索树的放置规则是:任何节点的元素值一定大于其左子树中的每一个节点的元素值,并且小于其右子树的值。因此从根节点一直向左走,一直到无路可走,即得到最小值,一直向右走,直到无路可走,可得到最大哦值。那么在二叉搜索树中找到最大元素和最小元素是非常简单的事情。下图为二叉搜索树:
上图我们介绍了二叉树,那么当一个二叉树的左子树和右子树不平衡的时候,那个搜索依据上图表示,搜索9所花费的时间比搜索17所花费的时间要多,由于我们的输入或者经过我们插入或删除操作,二叉树失去平衡,造成搜索效率降低。
所以我们有了一个平衡二叉树的概念,所谓的平衡不是指的完全平衡。
RB-tree(红黑树)为二叉树的一种