Почему функция erase () стоит так дорого?

Question

Рассмотрим двумерный вектор vector < vector <int> > N и предположим, что его содержимое выглядит следующим образом:

1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4

Таким образом, размер N здесь равен 4, т. Е. N.size() = 4

Теперь рассмотримследующий код:

int i = 0;
while(N != empty()){
N.erase(i);
++i;
}

Я рассчитал время только для этого фрагмента кода с различными размерами для N, и вот результаты:

Размер N равен 1000 Время выполнения: 0.230000с

Размер N равен 10000 Время выполнения: 22,900000 с

Размер N равен 20000 Время выполнения: 91,760000 с

Размер N равен 30000 Время выполнения:206.620000s

Размер N - 47895 Время выполнения: 526.540000s

Мой вопрос: почему эта функция настолько дорогая?Если это так, то операторы условного стирания во многих программах могут длиться вечно только из-за этой функции.Это тот же случай, когда я использую функцию стирания и в std::map.Есть ли альтернатива для этой функции.Другие библиотеки, такие как Boost, предлагают что-нибудь еще?

Пожалуйста, не говорите, что я могу сделать N.erase() в целом, потому что я просто пытаюсь проанализировать эту функцию.

Answer 1

Рассмотрим, что происходит, когда вы удаляете первый элемент вектора. Остальная часть вектора должна быть «сдвинута» вниз на один индекс, что предполагает его копирование. Попробуйте стереть с другого конца, и посмотрите, если это изменит (я подозреваю, что это будет ...)

Answer 2

Потому что ваш алгоритм O (n ^ 2). Каждый вызов erase заставляет vector перемещать все элементы после стертого элемента назад. Таким образом, в вашем цикле с вектором из 4 элементов первый цикл вызывает смещение 3 элементов, вторая итерация приводит к смещению 1 элемента, и после этого у вас неопределенное поведение.

Если бы у вас было 8 элементов, первая итерация переместила бы 7 элементов, следующая переместила бы 5 элементов, следующая переместила бы 3 элемента, и окончательное перечисление переместило бы 1 элемент. (И снова у вас неопределенное поведение)

Когда вы сталкиваетесь с подобными ситуациями, обычно вы должны вместо этого использовать стандартные алгоритмы (то есть std::remove, std::remove_if), так как они запускаются через контейнер один раз и превращают типичные алгоритмы O (n ^ 2) в O (n ) алгоритмы. Для получения дополнительной информации см. «Эффективный STL» Скотта Мейерса, пункт 43: «Предпочтение обращений алгоритма к явным циклам».

Answer 3

Внутренний std :: vector - это просто массив элементов.Если вы удаляете элемент посередине, все элементы после него должны быть смещены вниз.Это может быть очень дорого - тем более, если у элементов есть пользовательский operator=, который выполняет много работы!

Если вам нужно erase(), чтобы быстро, вы должны использовать std::list - при этом будет использована структура двусвязного списка, которая позволяет быстро удалять данные с середины (однако другие операции выполняются несколько медленнее).Если вам просто нужно быстро удалить из start списка, используйте std::deque - это создает связанный список массивов и предлагает большинство преимуществ скорости std::vectorпо-прежнему разрешая быстрое стирание только с начала или до конца.

Кроме того, обратите внимание, что ваш цикл усугубляет проблему - сначала вы просматриваете все элементы, равные нулю, и стираете их.Сканирование занимает O (n) время, стирание также O (n) время.Затем вы повторяете для 1 и так далее - в целом, O (n ^ 2) раз.Если вам нужно стереть несколько значений, вы должны взять итератор и самостоятельно пройти через std::list, используя вариант итератора erase().Или, если вы используете vector, вы обнаружите, что копирование в новый вектор может быть быстрее.

Что касается std::map (и std::set) - это совсем не проблема,std::map способен как удалять элементы в произвольном порядке, так и искать элементов в произвольном порядке со временем O(lg n), что вполне разумно для большинства случаев использования.Даже ваша наивная петля не должна быть слишком плохой;ручная итерация и удаление всего, что вы хотите удалить за один проход, несколько более эффективна, но не настолько, как с std::list и друзьями.

Answer 4

vector.erase будет продвигать все элементы после того, как я перешлю на 1. Это операция O (n).

Кроме того, вы передаете векторы по значению, а не по ссылке.

Ваш код также не стирает весь вектор.

Например: я = 0 стереть N [0] N = {{2, 2, 2, 2}, {3, 3, 3, 3}, {4, 4, 4, 4}}

я = 1 стереть N [1] N = {{2, 2, 2, 2}, {4, 4, 4, 4}}

я = 2 стереть N [2] ничего не происходит, потому что максимальный индекс N [1]

Наконец, я не думаю, что это правильный синтаксис для vector.erase (). Вам нужно передать итератор в начальное местоположение, чтобы стереть нужный элемент. Попробуйте это:

vector&ltvector&ltint&gt&gt vectors; // still passing by value so it'll be slow, but at least erases everything
for(int i = 0; i &lt 1000; ++i)
{
    vector&ltint&gt temp;
    for(int j = 0; j &lt 1000; ++j)
    {
        temp.push_back(i);
    }
    vectors.push_back(temp);
}

// erase starting from the beginning
while(!vectors.empty())
{
    vectors.erase(vectors.begin());
}

Вы также можете сравнить это со стиранием с конца (оно должно быть значительно быстрее, особенно при использовании значений, а не ссылок):

// just replace the while-loop at the end
while(!vectors.empty())
{
    vectors.erase(vectors.end()-1);
}

Answer 5

Как сказал Оли, удаление из первого элемента вектора означает, что элементы, следующие за ним, должны быть скопированы, чтобы массив вел себя так, как нужно.

Именно поэтому связанные списки используются для ситуаций, в которых элементы будут удаляться из случайных мест в списке - это быстрее (в больших списках), потому что нет копирования, только сбрасываются некоторые указатели узлов.

Answer 6

Вектор - это массив, который автоматически увеличивается при добавлении в него элементов.Таким образом, элементы вектора непрерывны в памяти.Это обеспечивает постоянный доступ к элементу.Поскольку они растут с конца, им также требуется амортизированное постоянное время для добавления или удаления к / с конца.

Теперь, что происходит, когда вы удаляете посередине?Ну, это означает, что все, что существует после того, как стертый элемент должен быть сдвинут назад на одну позицию.Это очень дорого.

Если вы хотите сделать много вставок / удалений в середине, используйте связанный список, такой как std :: list of std :: deque.