Is remove_if, а затем эффективно стирает вектор?

Question

Хотя есть несколько вопросов о remove_if + erase для vector. Я не мог найти, что такое действие такого действия. Когда я пишу:

myVector.erase(remove_if(myVector.begin(), 
         myVector.end(), 
         some_predicate), myVector.end()); 

удалить, если вернет итератор к последнему соответствующему пункту + 1 (назовем его X). Я считаю, что это произойдет в O (n).

Но как стирание будет работать?

• Если Стирание попытается удалить из X в myVector.end() будет O (N^2), так как это вызовет копирование вектора на новое место, и там будет O (п) новые выделения из кучи.
• Но если он удалит из myVector.end() в X, он может сделать это в O (n) и, что более важно, не будет выделять новую память (что-то я пытаюсь избежать).

Спасибо.

Answer 1

Рассмотрим этот вектор:

|0|1|2|3|4|5|6|7|8|9| 

Мы используем remove_if, чтобы удалить все элементы, кратные 4:

std::remove_if(v.begin(), v.end(), [](auto i){ return i != 0 && !(i%4); }); 

Это начинается итерации через вектор с помощью итератора X до тех пор, пока он не найдет элемент, где предикат возвращает true:

|0|1|2|3|4|5|6|7|8|9| 
     X 

Это первый элемент, который мы хотим удалить.

Далее он создает еще один итератор, указывающий на следующий элемент, Y = X + 1, и проверяет предикат для * Y:

|0|1|2|3|4|5|6|7|8|9| 
     X Y 

предикат является ложным, поэтому мы хотим, чтобы этот элемент, так он назначает следующий элемент к элементу, который мы хотим удалить, выполнив *X = std::move(*Y):

|0|1|2|3|5|5|6|7|8|9| 
     X Y   *X = std::move(*Y) 

Таким образом, мы имеем два итератора, X и Y, где X указывает на следующий элемент в «выход» (т.е. элементы мы не удаляем), а Y - следующий элемент для удаления.

Двигаемся как итераторы на следующую позицию, проверить предикат для Y (который является ложным снова), и сделать другое назначение:

|0|1|2|3|5|6|6|7|8|9| 
      X Y   *X = std::move(*Y) 

Затем он делает то же самое снова на следующей позиции:

|0|1|2|3|5|6|7|7|8|9| 
      X Y  *X = std::move(*Y) 

а потом она движется, но считает, что предикат истинен для Y

|0|1|2|3|5|6|7|7|8|9| 
       X Y 

S о это только увеличивает Y, который пропускает этот элемент и поэтому не копирует его в положение «выход» на X:

|0|1|2|3|5|6|7|7|8|9| 
       X Y 

предикат не относится к Y, поэтому он присваивает его X:

|0|1|2|3|5|6|7|9|8|9| 
       X Y  *X = std::move(*Y) 

Тогда приращение X и Y снова

|0|1|2|3|5|6|7|9|8|9| 
       X Y 

Теперь Y является пришедшим к концу так мы возвращаемся X (что указует на пришедший к концу выходной последовательности, то есть элементы, которые мы хотим держать).

После remove_if возвращает X мы называем v.erase(X, v.end()), поэтому вектор вызывает деструкторы для каждого элемента из X до конца:

|0|1|2|3|5|6|7|9|~|~| 
       X end 

А затем устанавливает размер поэтому вектор заканчивается на X:

|0|1|2|3|5|6|7|9| 
       end 

После этого v.capacity() >= v.size()+2, поскольку память, которая использовалась двумя конечными элементами, по-прежнему присутствует, но не используется.

Answer 2

Сложность vector::erase является well-defined:

Линейными: число обращений к деструктору Т таким же, как число элементов стертых, оператор присваивания Т называется числом раз, равных к числу элементов в векторе после стираемых элементов

Способ, которым он будет работать внутренне (то есть, как именно он собирается удалить ваши элементы), является неактуальным.

Сложность remove_if также defined и

Ровно станд :: расстояние (первый, последний) применения предиката.

Таким образом, ваш код имеет линейную сложность.

Answer 3

Почему бы не использовать подкачку «n pop»? Мы много обманывали с оптимизацией стирания в векторах и обнаружили, что это самый быстрый, поскольку он имеет сложность O(1). Единственным недостатком является то, что он не сохраняет порядок. Который в порядке - много дел. Вот метод шаблона для такой операции:

template<typename T> 
inline typename std::vector<T>::iterator unorderedErase(std::vector<T>& p_container, 
                 typename std::vector<T>::iterator p_it) 
{ 
    if (p_it != p_container.end() - 1) 
    { 
     std::swap(*p_it, p_container.back()); 
     p_container.pop_back(); 
     return p_it; 
    } 
    // else 
    p_container.pop_back(); 
    return p_container.end(); 
}