我是一名从事高性能计算课程的小型项目的学生,因此效率是一个关键问题.
假设我有一个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)时间内从矢量中删除元素.
