亲宝软件园·资讯

展开

STL中的Set和Map

少年π 人气:1

STL中的Set和Map

先来看一段网络上的文字描述:

上图是一段关于STL中Set集合的描述,同样的,也近似适合Map的描述。上述文字中,描述了最为重要的特征:

Set和Map,底层调用了红黑树的结构,并且实现的是一种自动平衡二叉搜索树。

  • Set

平衡二叉搜索树(Set)

如上图,STL中Set实现的本质是平衡二叉搜索树,且树中没有相同的元素,每一个节点表示Set中的一个元素,Set中只有键,也就是上述图中每个节点的值,就是Set的每个元素,因此Set中没有重复元素,当向Set中执行insert(插入)时,树会自动调整结构(对于红黑树而言,会实现节点的旋转),以保证树结构的平衡性。当执行多次向节点中插入同一个键值时,比如insert(5),insert(5),则只会执行第一次的insert操作。后续的插入,并不会执行,因为Set结构的树中无重复元素。

另一个点在于,Set中被插入的键不能被修改,也就是通过迭代器修改键值是不被允许的。因为键值一旦被修改,就意味着树的结构遭到了破坏,而这在最坏的情况意味着:整棵二叉树遭到了破坏,甚至需要重构整棵二叉树。即使在红黑树中,并没有这样的操作。因为红黑树的最为显著的特征为:局部调整。即对于Set而言,其iterator属于const-iterator。

另外一个需要被注意的点在于:

我们使用迭代器来访问容器是一件很平常的事情,上述代码是一段使用极其平常的代码,其作用是遍历Set中所有的元素。注意循环的终止条件是:!=,而不是:<。我们通常习惯了小于的小法:

即:

但这样的写法是错误的。

  • Map

下面来看Map,Map的结构形成机理和Set几乎是一模一样的,而Map的结构如下:

"挂件"平衡二叉搜索树(Map)

Map的结构如上图:可见,同Set相比,Map只是多了一个"挂件",也就是常说的Map是由:键—值对构成的。键充当了索引,值则记录了一些其他内容。而对于Set而言,只有键。或许我们用下面这个表来描述更为合适:

键—值对

索引序号

名字

1

张三

2

李四

3

王五

左边的索引号就是键,右边的名字就是值,所以说Map实际上是一种极为普遍简单的概念。这种关系就像字典一样。

而关于Map的其他性质,和Set是极其类似的。比如:没有相同的元素,当然对于Map而言,没有相同的元素是只没有两个元素键相同。执行两个insert,仍然会只有键值对存在树中,只是第二次执行的insert会修改第一次的 键-值对中的值。

同样的,Map中的键是不能被修改的,因为同样会导致"重建树"这个问题,但是很明显的是,值明显是可以修改的,就像我们可以把上述索引序号为"3"的"王五"修改为"赵六";但我们不能将索引号3修改为4,(我们只能将3删除,再添加4,这是可以的)。当然是用迭代器访问时,其也只能用!=,而不是<。

加载全部内容

相关教程
猜你喜欢
用户评论