最快的方式来创建一个std :: vector的副本减一个元素

我有一个std :: vector [1,2,3,4,5]，我想获得另一个包含所有元素的矢量，但第二个一：[1，3，4，5]。其中一个办法就是（VEC 1是我的输入向量）：最快的方式来创建一个std :: 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）时间。渐近行为是相同的，但操作次数可能更小。

我必须对相当小的矢量（大约100个元素）执行此操作，但我拥有数十亿个元素。我会注意到一个重要的区别？

你会怎么做？

来源

2016-12-03 user3091275

电话储备。至于你是否会注意到它的差异，很好地描述它，这是获得可靠答案的唯一方法。 – Borgleader

也许你应该重新考虑你的算法，如果你不需要，不要复制。另外检查插入（） –

你可以反向迭代你的矢量，并删除最后一个元素，所以你不必复制。或者您可以跟踪应该是第一个元素的索引并从中迭代到结束。有很多方法可以避免复制。 –

关于复杂性，无论如何你都不得不复制n个元素，所以你不能比O（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，该副本将是直接的，而且会有不错的空间编译器优化。

编辑：在下面的意见，调整矢量招致一些额外的初始化，看到的方式来避免这里的inititlization讨论：Using vector<char> as a buffer without initializing it on resize()

来源

2016-12-03 19:54:56

“*创建时保留*”不保留;它*初始化*这些值。这是一个O（n）过程。如果你想保留，你应该叫* reserve *。 –

@NicolBolas我说无论如何这个过程都是O（n）。然而你是正确的，初始化器将被调用。保留或我的意思是，创建时调整大小已知很难（仍然可行）与std :: vector（请参阅http://stackoverflow.com/questions/15219984/using-vectorchar-as-a-buffer-without-initializing -IT上调整大小）。 –

这可以使用的std::vector现有的程序来完成。鉴于i，这是你想跳过（这是vec范围内）的位置：

template<typename T> 
vector<T> skip_copy(const vector<T> &vec, size_t i) 
{ 
    vector<T> ret; 
    ret.reserve(vec.size() - 1); 
    ret.insert(ret.end(), vec.begin(), vec.begin() + i); 
    ret.insert(ret.end(), vec.begin() + i + 1, vec.end()); 
    return ret; 
}

通过保留空间，我们避免ret任何不必要的内存分配。最后完成时，不需要转移元素。

当然，insert可能会比严格要求的做一些额外的条件（检查迭代器的范围是否适合现有的存储），但是一系列的调用不可能更快。如果vector的大小很大，则无需预先初始化该阵列即可支付自己的费用。

来源

2016-12-03 20:41:55

这是我能想到的最快的方法：第一

std::vector<int> vec1{1, 2, 3, 4, 5}; 

// Do not call the constructor with the known size here. That would allocate 
// AND initialize a lot of data that will be overwritten later anyway. 
std::vector<int> vec2; 

// Instead, use it on 'reserve' since it only allocates the memory and 
// leaves it uninitialized. The vector is still considered empty, but its 
// underlying capacity will be big enough to be filled with new data 
// without any unnecessary initializations and reallocations occuring (as long 
// as you don't exceed the capacity) 
vec2.reserve(vec1.size() - 1); 

// Nothing expensive should be going on behind the scenes now, just fill it up 
for(auto it = vec1.begin(), skip = vec1.begin() + 1 ; it != vec1.end() ; ++it) { 
    if(it != skip) { 
     vec2.push_back(*it); 
    } 
}

来源

2016-12-03 20:45:21 zee01

最快的方式来创建一个std :: vector的副本减一个元素

回答

相关问题