映射中两个迭代器之间的距离 [英] distance between two iterators in map
问题描述
在STL的地图实现中，两个
迭代器之间的距离为it1，it2需要O（K）来计算其中K是
之间的实际距离两个迭代器。
理论上，红黑树可以在O（log K）时间内完成此任务。
任何人都知道是否有办法做这在地图<>或
如果地图<>可以继承/修改吗？
谢谢，
--j
[见 http://www.gotw.ca/resources/clcm.htm 有关的信息]
[comp.lang.c ++。moderated。第一次海报：做到这一点！ ]
John写道：在STL的地图实现中，两者之间的距离
iterators it1，it2需要O（K）来计算K是两个迭代器之间的实际距离。
你从哪里获得这些信息？
从理论上讲，红黑树可以在O（log K）时间内完成。
任何人知道是否有办法在地图中执行此操作<>或
如果地图<>可以继承/修改吗？
首先，你确定你必须修改''std :: map''吗？
其次，是的，你可以并且可以继承''std :: map''。但是，
你需要修改/继承''std :: map :: iterator''。
第三，也许你应该联系你图书馆实施者和
建议您希望他们对图书馆进行任何改进。
V
-
请通过邮件回复从我的地址删除资金
Victor Bazarov写道：
John写道：< blockquote class =post_quotes>在STL的地图实现中，两个
迭代器之间的距离为it1，it2需要O（K）来计算其中K是两个迭代器之间的实际距离。 / blockquote>
你从哪里获得这些信息？
也许来自标准[24.3.4 / 1]。
[snip}
Best
Kai-Uwe Bux
Kai-Uwe Bux写道：Victor Bazarov写道：
John写道：在STL的地图实现中，两个
迭代器之间的距离为it1，it2需要O（K）来计算K是哪个
两个迭代器之间的实际距离。
你从哪里获得这些信息？
可能来自标准[24.3.4 / 1 ]。
也许。也许不吧。 24.3.4 / 1基本上为双向迭代器设置_lowest_ standard
。虽然''std :: map'的迭代器是
''双向''类别，但没有什么能真正阻止它的真实世界
实现提供比线性更好的' 提前和
''距离''，是吗？约翰说实施......需要O（K）。
哪个实施？谁的实施？赶上我的漂移？
V
-
请在邮寄回复时从我的地址删除资金
In STL''s map implementation, the distance between two
iterators it1, it2 takes O(K) to compute where K is the
actual distance between the two iterators.
In theory, a red black tree can do this in O(log K) time.
Anyone knows if there is a way to do this in map<> or
if map<> can be inherited/modified to do this?
Thanks,
--j
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
John wrote:In STL''s map implementation, the distance between two
iterators it1, it2 takes O(K) to compute where K is the
actual distance between the two iterators.
Where did you get this information?
In theory, a red black tree can do this in O(log K) time.
Anyone knows if there is a way to do this in map<> or
if map<> can be inherited/modified to do this?
First of all, are you sure you have to modify ''std::map''?
Second, yes, you can and may inherit from ''std::map''. However,
you will then need to also modify/inherit ''std::map::iterator''.
Third, perhaps you should contact your library implementors and
suggest any improvements you want them to make to the library.
V
--
Please remove capital As from my address when replying by mail
Victor Bazarov wrote:
John wrote:In STL''s map implementation, the distance between two
iterators it1, it2 takes O(K) to compute where K is the
actual distance between the two iterators.
Where did you get this information?
Maybe from the standard [24.3.4/1].
[snip}
Best
Kai-Uwe Bux
Kai-Uwe Bux wrote:Victor Bazarov wrote:John wrote:In STL''s map implementation, the distance between two
iterators it1, it2 takes O(K) to compute where K is the
actual distance between the two iterators.
Where did you get this information?
Maybe from the standard [24.3.4/1].
Maybe. Maybe not. 24.3.4/1 essentially sets the _lowest_ standard
for bidirectional iterators. While ''std::map''s iterator is of
''bidirectional'' category, nothing really prevents its real-world
implementation from providing better than linear ''advance'' and
''distance'', does it? John says "implementation ... takes O(K)".
Which implementation? Whose implementation? Catch my drift?
V
--
Please remove capital As from my address when replying by mail
这篇关于映射中两个迭代器之间的距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
