是否有任何类似数组的数据结构可以在两侧增大？

Question

我是一名从事高性能计算课程的小型项目的学生,因此效率是一个关键问题.

假设我有一个N浮点数的向量,我想删除最小的n个元素和最大的n个元素.有两种简单的方法可以做到这一点:

一个

sort in ascending order    // O(NlogN)
remove the last n elements // O(1)
invert elements order      // O(N)
remove the last n elements // O(1)

乙

sort in ascending order     // O(NlogN)
remove the last n elements  // O(1)
remove the first n elements // O(N)

在A中反转元素顺序需要交换所有元素,而在B中删除前n个元素需要移动所有其他元素以占据留空的位置.使用std :: remove会产生同样的问题.

如果我可以免费删除前n个元素,那么解决方案B会更便宜.这应该很容易实现,如果不是有一个向量,即一个带有一些空白空间的数组vector::end(),我之前也会有一个带有一些空闲空间的容器vector::begin().

所以问题是:在某些库(STL,Boost)中是否存在类似数组(即连续内存,没有链表),允许在数组的两侧插入/删除O(1)？

如果没有,您是否认为有更好的解决方案而不是创建这样的数据结构？

Answer 1

您是否考虑过使用std::partition自定义仿函数,如下例所示:

#include <iostream>
#include <vector>
#include <algorithm>

template<typename T>
class greaterLess {
    T low;
    T up;
  public:
    greaterLess(T const &l, T const &u) : low(l), up(u) {}
    bool operator()(T const &e) { return !(e < low || e > up); }
};

int main()
{
    std::vector<double> v{2.0, 1.2, 3.2, 0.3, 5.9, 6.0, 4.3};
    auto it = std::partition(v.begin(), v.end(), greaterLess<double>(2.0, 5.0));
    v.erase(it, v.end());

    for(auto i : v) std::cout << i << " ";
    std::cout << std::endl;

    return 0;
}

这样你就可以O(N)及时擦除矢量中的元素.