- 论坛徽章:
- 2
|
tempname2 发表于 2012-05-05 22:07 ![]()
如题,我想让map返回所有key时保持它们插入的顺序。
题目不太准确:
1. map是指STL那个吧?
2. 顺序是指什么? begin/end?
3. 所有key —— [begin,end) 保持插入顺序? 那还不如用list……
4. 应该是所有等价的key保持插入顺序吧?
但map中等价的key是唯一的…… 应该是multimap?
如果将题目改为:二叉搜索树中序遍历中、等价key区间中的元素是否能保持插入时的相对顺序。
答案是可以的。只要插入时稍微注意就行。
不妨设中序遍历得到的是升序。
因为中序遍历是左子树、根、右子树,插入x时,与当前节点n比较:
1. x < n 插入n的左子树 —— 那么中序遍历时x在n之前
2. x > n 插入n的右子树 —— 那么中序遍历时x在n之后,这两点保证升序
3. x = n 插入n的右子树 —— 那么中序遍历时等价的两节点x、n,后插入的x出现在先插入的n之后
而STL中的multimap,C++11增加了一句话,保证对等价的key会保持插入时的相对顺序 —— 也就是说:
1. C++03很有可能就没有这样的保证……
2. 但C++03的很多实现应该是有提供这样的保证的
保险的话,只能用类似map<K,vector<V> >这样的手段…… |
|