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

发布时间：2020-12-16 03:28:55 所属栏目：百科来源：网络整理

导读：我是一名从事高性能计算课程的小型项目的学生,因此效率是一个关键问题. 假设我有一个N浮点数的向量,我想删除最小的n个元素和最大的n个元素.有两种简单的方法可以做到这一点：一个 sort in ascending order // O(NlogN)remove the last n elements // O(1)in

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

假设我有一个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)？

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

解决方法

您是否考虑过将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)时间内从矢量中删除元素.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!