有这种数据结构吗？能记录key插入顺序的map。

tempname2

如题，我想让map返回所有key时保持它们插入的顺序。

wolf5729

据我的了解，标准库的map不支持这个功能；得结合自己的应用进行开发。

比如，开发一个类，数据成员有map，及deque，前者用于记录key->value，后者用于记录key的插入顺序。
或者，map的value带上一个时间戳，它的大小关系直接反映出key的插入顺序。
至于选择哪种，根据应用来。经常要获取key的插入顺序的，用前者；偶尔的，用后者。

------------------------------------
欢迎光临我的博客：www.danoking.com [DNK的生涯|IT人的故事]

folklore

1. 
   
2. namespace std{
   
3.     mapEx<TK,TV>:map<TK,TV>{
   
4.     private:
   
5.           std::vector<TK>; // Remember the insert sequence here
   
6.     public:
   
7.           insert(...);
   
8.           remove(...);
   
9.    };
   
10. }
    

复制代码

tempname2

我自己实现了，只是想知道有没有通用的数据结构有这种特性。看来是没有了，谢谢两位。

OwnWaterloo

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> >这样的手段……

OwnWaterloo

回复 2# wolf5729

翻了翻你的博客，关于CFuncAtDestruct，推荐你看看loki的scopeguard。

wolf5729

回复 6# OwnWaterloo


    谢谢你的指点。



------------------------------------
欢迎光临我的博客：www.danoking.com [DNK的博客]