关于迭代器顺序的c ++ std :: map问题

Question

我是一个尝试使用地图的C++新手,所以我可以获得find()方法的恒定时间查找.

问题是,当我使用迭代器遍历地图中的元素时,元素的显示顺序与它们放置在地图中的顺序不同.

如果不维护另一个数据结构,是否有一种方法可以实现按顺序迭代,同时仍然保持恒定的时间查找能力？

请告诉我.

谢谢,jbu

编辑:感谢让我知道map :: find()不是常数时间.

Answer 1

如果不维护另一个数据结构,是否有一种方法可以实现按顺序迭代,同时仍然保持恒定的时间查找能力？

不,那是不可能的.为了获得有效的查找,容器将需要以有效查找的方式对内容进行排序.对于std :: map,这将是某种类型的排序顺序; 对于std :: unordered_map,这将是一个基于密钥哈希的顺序.

在任何一种情况下,订单都将与添加订单的顺序不同.

Answer 2

首先,std::map保证O(log n)查找时间.你可能在考虑std::tr1::unordered_map.但是,根据定义,牺牲任何顺序来获得恒定时间查找.

你必须花一些时间在它上面,但我认为你可以抨击boost::multi_index_container做你想做的事.

Answer 3

operator<项目按（默认情况下）应用于键时排序。

附言。std::map 不保证恒定时间查找。
它保证最大复杂度为 O(ln(n))