Самый быстрый способ создать копию std :: vector минус один элемент

Question

У меня есть std :: vector [1, 2, 3, 4, 5], и я хочу получить еще один вектор, содержащий все элементы, но второй один: [1, 3, 4, 5]. Один из способов сделать это (vec1 мой входной вектор):

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

Здесь я не очень нравится стирают, который O (п) сложность, поэтому, учитывая копию массива у меня будет 2n операций. Я думал, что старый манекен будет лучше:

std::vector<int> vec2; 
for(int i=0; i<vec1.size(); ++i){ 
    if (i != 1) 
     vec2.push_back(vec1[i]); 
} 

Это амортизированное время O (n). Асимптотическое поведение одинаково, но количество операций может быть меньше.

Я должен сделать это на довольно маленьких векторах (около 100 элементов), но у меня их миллиарды. Я заметлю существенную разницу?

Как вы это сделаете?

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, копия будет просто и к тому же будет хороший номер для оптимизации компиляторов.

EDIT: как в комментариях ниже, изменение размера вектора несет некоторые дополнительные инициализации см обсуждение способов, чтобы избежать inititlization здесь: Using vector<char> as a buffer without initializing it on resize()

Answer 2

Это можно сделать с помощью существующих процедур по 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. И vector::insert, когда это делается в конце, не нужно будет перемещать элементы вокруг.

Конечно, вполне возможно, что insert делает несколько дополнительных условий, чем строго необходимо (проверять, если диапазон итераторов будет вписываться в существующие хранилища), но это маловероятно, что ряд push_back вызовов будет быстрее , И не нужно предварительно инициализировать массив, платит за себя, если размер vector значителен.

Answer 3

Это самый быстрый способ, которым я могу думать:

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); 
    } 
}