我有一个std::vector [1、2、3、4、5],我想得到另一个包含除第二个元素之外的所有元素的 vector :[1、3、4、5]。一种方法是(vec1是我的输入 vector ):

std::vector<int> vec2;
vec2 = vec1;
vec2.erase(vec2.begin()+1)

在这里,我不太喜欢O(n)复杂度的擦除,因此考虑数组的副本,我将进行2n次操作。我以为旧的虚拟方法会更好:
std::vector<int> vec2;
for(int i=0; i<vec1.size(); ++i){
    if (i != 1)
        vec2.push_back(vec1[i]);
}

这是分摊的O(n)时间。渐近行为相同,但操作次数可能更少。

我必须在相当小的 vector (大约100个元素)上执行此操作,但是我有数十亿个 vector 。我会注意到明显的不同吗?

你会怎么做?

最佳答案

关于复杂性,您无法寻求比O(n)更好的方法,因为无论如何您都必须复制n个元素。但是出于某种微优化的目的,您可以:

  • 保留先验大小,如
  • 注释中所示
  • 通过执行2个连续副本而不检查以下内容来避免在循环内检查条件:
    std::vector<int> vec1 = { 1,2,3,4,5 };
    std::vector<int> vec2(vec1.size()-1);
    
    constexpr int i = 1; // let i be the position you want to skip
    
    std::copy(vec1.cbegin(), vec1.cbegin() + i, vec2.begin());
    std::copy(vec1.cbegin() + i+1, vec1.cend(), vec2.begin()+i);
    

  • 因为没有if语句或std::copy-if,所以副本将很简单,而且为编译器优化提供了良好的空间。

    编辑:如下面的注释所示,调整 vector 的大小会引起一些初始化的额外问题,请参见此处避免初始化的方法的讨论:Using vector<char> as a buffer without initializing it on resize()

    09-09 20:02
    查看更多