标准说，如果数据结构具有随机访问权限，那么std::binary_search(...)这两个相关函数std::lower_bound(...)和std::upper_bound(...)是 O(log n)。因此，鉴于此，我假设这些算法具有 O(log n) 性能std::deque（假设其内容由用户保持排序）。
但是，似乎 的内部表示std::deque很棘手（它被分成块），所以我想知道： O(log n) 搜索的要求是否适用于std::deque.
问问题
2549 次
3 回答
10
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).
That doesn't relieve you of the obligation for the deque to be sorted though.
于 2011-06-23T14:24:30.370 回答
1
是的。如果索引存在，则 deque 对索引具有恒定的时间访问权限。它以相同大小的页面组织。你有的是smth。就像一个指向页面的指针向量。如果您有 2 个页面，其中有 100 个元素，并且您想访问第 103 个元素，而不是通过 103/100 = 1 确定页面并通过 103 %100 => 3 确定页面中的索引。现在使用恒定时间访问两个向量来获取元素。
这里来自http://www.cplusplus.com/reference/stl/deque/的声明：
双端队列可以由特定的库以不同的方式实现，但在所有情况下，它们都允许通过随机访问迭代器访问各个元素，并且始终自动处理存储（根据需要扩展和收缩）。
于 2011-06-23T14:33:15.343 回答
0
只需编写一个程序来测试一下，我认为双端队列的 binary_search 实现会比向量的慢，但它的复杂度仍然是 O(logn)
于 2011-06-23T14:25:23.400 回答