第一问答网»论坛 › 中问网 › 问答 › 关联容器：map,set,multimap,multiset中的键会不会自动 ...

关联容器：map,set,multimap,multiset中的键会不会自动排序？

11 |

1 | 2013-5-14 20:00:27 | 显示全部楼层 |阅读模式

set、map底层都是用红黑树实现，红黑树是一种特殊的二叉查找树。在每次元素插入的时候会对二叉树进行动态调整，使其满足二叉查找树的特性。有关二叉查找树的特性你可以在网上找。红黑树再次基础上还能保证树的平衡性。multimap,multiset底层也是红黑树，但是再插入的时候容许重复插入。所以里面的元素可以重复。明白了二叉查找树，你自己都可以写一个lower_bound()和upper_bound()函数，其实就是利用了左子树元素比根节点元素小，右子树比根节点元素值大的特性实现的。怎么说呢，也不能算是排序吧，因为底层实现是二叉树，不像一般的线性结构。但是在使用的时候，它确实表现的像排序了一样。所以它叫做二叉排序树。...

使用道具举报

返回列表发新帖

千问

主题	0 回帖	4882万积分

论坛元老

Rank: 8 Rank: 8

积分: 48824836

回复楼主返回列表

问答

热门排行