Chinaunix

标题: 有这种数据结构吗？能记录key插入顺序的map。 [打印本页]

作者: tempname2 时间: 2012-05-05 22:07
标题: 有这种数据结构吗？能记录key插入顺序的map。
如题，我想让map返回所有key时保持它们插入的顺序。

作者: wolf5729 时间: 2012-05-06 09:25
据我的了解，标准库的map不支持这个功能；得结合自己的应用进行开发。

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

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

作者: folklore 时间: 2012-05-06 10:26

namespace std{
mapEx<TK,TV>:map<TK,TV>{
private:
std::vector<TK>; // Remember the insert sequence here
public:
insert(...);
remove(...);
};
}

复制代码

作者: tempname2 时间: 2012-05-06 10:30
我自己实现了，只是想知道有没有通用的数据结构有这种特性。看来是没有了，谢谢两位。

作者: OwnWaterloo 时间: 2012-05-06 13:22

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 时间: 2012-05-06 13:28
回复 2# wolf5729

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

作者: wolf5729 时间: 2012-05-07 00:37
回复 6# OwnWaterloo

谢谢你的指点。

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

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)