问题描述
标准说 std :: binary_search（...）和两个相关的函数 std :: lower_bound（...） / code>和 std :: upper_bound（...）都是O（log n）。因此，假定这些算法在 std :: deque （假设其内容由用户保持排序）上具有O（log n）性能。
The standard says that std::binary_search(...) and the two related functions std::lower_bound(...) and std::upper_bound(...) are O(log n) if the data structure has random access. So, given that, I presume that these algorithms have O(log n) performance on std::deque (assuming its contents are kept sorted by the user).
但是，看来 std :: deque 的内部表示是棘手的（它被分成块），所以我是想知道： std :: deque 是否满足O（log n）搜索的要求。
However, it seems that the internal representation of std::deque is tricky (it's broken into chunks), so I was wondering: does the requirement of O(log n) search hold for std::deque.
推荐答案
是，它仍然适用于 deque ，因为容器需要在常量时间提供对任何元素的访问$ c> vector ）。
Yes it still holds for deque because the container is required to provide access to any element in constant time (just a slightly higher constant than vector).
这并不能免除您 deque 可以排序。
That doesn't relieve you of the obligation for the deque to be sorted though.
这篇关于二叉搜索是否具有deque C ++数据结构的对数性能？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！