最近在看STL源码剖析,然后也刷了一下关于使用容器的一些题,发现一个关于multimap的一个问题想不通,大家都知道multimap是允许有重复键值,底层是通过红黑树来实现的,对于一个全是重复元素的multimap使用find函数查找,为什么find函数总能返回插入顺序中的第一个key值?
测试代码如下:
void main()
{
multimap test;
multimap::iterator pt;
for (int i = 0; i < 5; i++) //插入5个key为1的键值对,然后用second记录i,代表插入的顺序;
test.insert(make_pair(1,i));
for (int i = 0; i < 5; i++)
{
pt = test.find(1); //输出每次查找到的1的插入顺序;
cout << (*pt).second << " ";
test.erase(pt);
}
}
我想在建立这个红黑树的时候,根据STL中的insert_equal()函数,遇“大”则往左,遇“小于或等于”则往右,所以每次都插入1的时候应该都是往右插入,这时肯定会遇到不符合红黑树性质的情况,就得调整红黑树,得到最后的红黑树,在find查找时,根据二叉搜索树的方式,找到满足条件的第一个节点为什么就一定能保证是插入时的第一个呢???