有没有在STL任何数据结构，可以在O（1）或O上插入元素（log n）的，我可以写我自己的bin_search就可以了？

Question

我需要一个数据结构，可以插入在O（1）或O（log n）的元素，我可以写这样的数据构造对象对我自己的二进制搜索功能？如果没有这样的数据结构的STL，我怎么能写我自己？

Answer 1

有在具有O(1)或O(logn)插入和需要做的二进制搜索（这需要随机访问的能力）的STL容器。它的名字是std::deque，虽然它不具有任何内在的排序，所以你必须自己提供的元素顺序。

// Fill a deque with elements
std::deque<int> deq{4, 2, 3, 1, 2, 3};
// Sort it to satisfy binary search precondition
std::sort(deq.begin(), deq.end());
// Do your binary search here

Answer 2

这听起来像你想学习一些计算机科学的基础知识。我建议使用std ::向量作为基础的数据结构，这样就可以集中在较高的水平核心服务逻辑，而不是低电平底层内存处理。基于向量，就可以实现对O（log n）的插入堆。载体具有随机访问迭代器是用于访问集合分而治之算法的“中间”元素是有用的，例如二进制搜索。

Answer 3

是的，你可以使用堆数据结构，它发生在最坏情况下O（log n）的，但在平均情况下，它需要O（1）