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

Question

我是一名学生，正在为高性能计算类(class)做一个小项目，因此效率是一个关键问题。

假设我有一个包含 N 个 float 的 vector ，我想删除最小的 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)

B

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 ，即在 vector::end() 之后有一些空白空间的数组，我会在 之前有一个有一些空闲空间的容器 vector::开始()。

所以问题是:在某些库(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) 时间内从 vector 中删除元素。