Question

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

lower_bound(k)返回指向键不小于k的第一个元素的迭代器；假设为iter1;
upper_bound(k)返回指向键大于k的第一个元素的迭代器；假设为iter2;
不排序的话，iter2会指向iter1之前的元素吧？ 这样迭代的话，iter1++能达到iter2的值？ 求解惑！

Answer 1

set、map底层都是用红黑树实现，红黑树是一种特殊的二叉查找树。在每次元素插入的时候会对二叉树进行动态调整，使其满足二叉查找树的特性。有关二叉查找树的特性你可以在网上找。红黑树再次基础上还能保证树的平衡性。

multimap,multiset底层也是红黑树，但是再插入的时候容许重复插入。所以里面的元素可以重复。

明白了二叉查找树，你自己都可以写一个lower_bound()和upper_bound()函数，其实就是利用了左子树元素比根节点元素小，右子树比根节点元素值大的特性实现的。

怎么说呢，也不能算是排序吧，因为底层实现是二叉树，不像一般的线性结构。但是在使用的时候，它确实表现的像排序了一样。所以它叫做二叉排序树。