c++ - 创建 std::vector 减去一个元素的拷贝的最快方法

Question

我有一个 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 。我会注意到显着差异吗？

你会怎么做？

Answer 1

关于复杂性，您无法找到比 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()