"There are only two hard things in Computer Science: cache invalidation and naming things" — Phil Karlton
среда, 19 января 2011 г.
Как правильно удалять элементы из вектора
Существует множество вариантов удаления элементов из вектора и лишь один из правильный.
Стефан Т. Лававей (Stephan T.Lavavej) рассказывает об этом варианте во второй части видео-лекций по STL, который также известен как идиома erase/remove и описан в книге Скотта Мейерса "Эффективное использование STL".
Предположим, у нас есть заполненный вектор из int и необходимо удалить элемент 23. Можно написать цикл, который проходит по всем элементам, проверяет каждый из них на равенство 23 и удаляет поэлементно, а можно обойтись одной строчкой:
Функция std::remove из стандартной библиотеки вовсе не удаляет объекты, а лишь сдвигает все элементы, не равные 23, в начало и возвращает итератор на конец новой последовательности. Функция же erase вектора удалит все элементы, начиная с итератора, возвращенного функцией std::remove, и до конца вектора.
Такой код не только компактен, он также сокращает количество вызовов функции.
Тоже самое относится к удалению по условию с использованием предиката.
Или тоже самое с использованием лямбды (C++0x):
Использовать циклы для удаления можно в случае, если необходимо сделать какие-либо дополнительные действия при удалении. Но при этом следует помнить, что при удалении элемента из вектора все итераторы, ссылающиеся на удаляемый элемент и после него, становятся недействительными. К счастью, функция erase вектора возвращает действительный итератор на следующий после удаленного элемент. Выглядит это примерно следующим образом:
Более подробно об этом и об использовании STL в целом найдете в книге "Эффективное использование STL" Скотта Майерса.
Как удалить элемент из std:: vector<> по индексу? (7)
Если вы работаете с большими векторами (размером> 100 000) и хотите удалить множество элементов, я бы рекомендовал сделать что-то вроде этого:
Код принимает каждое число в vec, которое не может быть разделено на 3 и копирует его в vec2. Затем он копирует vec2 в vec. Это довольно быстро. Для обработки 20 000 000 элементов этот алгоритм занимает всего 0,8 с!
Я сделал то же самое с методом стирания, и требуется много и много времени:
У меня есть std :: vector , и я хочу удалить n-й элемент. Как я могу это сделать?
Если у вас есть неупорядоченный вектор, вы можете воспользоваться тем фактом, что он неупорядочен и использует то, что я видел у Дэна Хиггинса в CPPCON
Поскольку порядок списка не имеет значения, просто возьмите последний элемент в списке и скопируйте его поверх элемента, который хотите удалить, затем нажмите и удалите последний элемент.
Метод стирания на std :: vector перегружен, поэтому, вероятно, более понятный вызов
когда вы хотите удалить только один элемент.
Предыдущие ответы предполагают, что у вас всегда есть подписанный индекс. К сожалению, std::vector использует параметр size_type для индексирования и difference_type для арифметики итератора, поэтому они не работают вместе, если вы включили «-Wconversion» и друзей. Это еще один способ ответить на вопрос, имея возможность обрабатывать как подписанные, так и неподписанные:
Чтобы удалить один элемент, вы можете сделать следующее:
Или, чтобы удалить сразу несколько элементов:
Чтобы удалить элемент, используйте следующий способ:
Подскажите, как корректно пройтись по вектору и удалить некоторые его элементы.
Т.е., корректно ли выполнять такие действия?
Или возникнут проблемы с итератором после удаления первого элемента?
Прочитал комментарии, всем спасибо за помощь
Пересмотрел код и понял, что не совсем полно поставил задачу:
Если воспользоваться советом @Harry, то тогда код можно же преобразовать к такому:
4 ответа 4
? Как по мне — понятнее и никаких проблем с итераторами. Вероятно, еще и быстрее, чем убирать по одному элементу.
Если перепишете check так, чтоб работал наоборот — то и лямбда-выражение (или bind ) не потребуется.
Если уж позарез нужен цикл — то воспользуйтесь тем, что erase возвращает итератор на элемент, следующий за удаленным:
Но учтите, что тут сложность — квадратичная, в отличие от remove_if (спасибо @pavel).
