Наиболее эффективный способ удаления / удаления нескольких элементов std :: vector при сохранении исходного порядка?

Question

У меня есть std::vector<int> и второй контейнер, содержащий итераторы или индексы (без ключей, я хочу постоянный доступ к элементу) для этого вектора для целей удаления.Предположим, у меня есть вектор из 1000 элементов, и я хочу стереть 200 из них.Порядок не удаляемых элементов должен быть таким же после операций удаления, как и раньше.

Еще одна вещь, которую я пропустил в первой версии моего вопроса: значения являются уникальными .Это тождества.

Как бы вы сделали это безопасным (в отношении правил stl) и эффективным способом (решение по вектору должно быть окончательным)?

Возможности или Методы Я думал о:

• Идиома erase-remove (http://en.wikipedia.org/wiki/Erase-remove_idiom): первоначально для удаления элементов, которыевыполнить условие (включая линейный поиск), но я думаю, что с диапазонами размера 1 этот метод может быть использован для уже заданных итераторов и фиктивного условия. Вопрос: является ли исходный порядок элементов сохраненным и является ли он более производительным, чемпоследний метод?
• зацикливает индексы и удаляет элементы с использованием vector.erase(vector.begin()+index+offset), сохраняя при этом индексы в контейнере для вычисления смещения. Это смещение может быть определено для каждой итерации удаления сиспользование std::lower_bound n контейнера уже удаленных элементов. Проблема: большое количество binary_searches для получения смещения и большое количество операций перемещенияиз-за случайного расположенияСортируйте их в порядке убывания в соответствии с расположением в векторе и зациклите их для окончательного удаления с помощью vector.erase.Теперь я не делаю недействительными ни один итератор, и нет никаких операций перестановки векторов, кроме самого удаления. Проблема: много сортировки

Итак, как бы вы занялись этим?Есть новые идеи?Любые рекомендации?

Спасибо за ваш вклад.

Саша

Редактировать / Обновить / Собственные результаты: Я реализовал стирание-удаление идиома, который также упоминался в KennyTM, с предикатом , основанным на поиске в boost :: dynamic_bitset , и это безумно быстро .Кроме того, я попробовал метод перемещения и усечения PigBen (также упомянутый Стивом Джессопом), который также получает доступ к битам в цикле while.Оба, кажется, одинаково быстро работают с моими данными.Я попытался удалить 100 из 1000 элементов (беззнаковые целые), сделал это 100 удаляет 1M раз, и не было никакой существенной разницы.Поскольку я думаю, что идиома erase-remove на основе stl более «естественна», я выбираю этот метод (аргумент также упоминался в KennyTM).

Answer 1

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

int last = 0;
for(int i=0; i<vec.size(); ++i, ++last)
{
   while(needs_to_be_removed(i))
      ++i;
   if(i >= vec.size()) break;

   vec[last] = vec[i];   
}

vec.resize(last);

Answer 2

В <algorithm> есть функция remove_if , которая сжимает все значения, не удаленные на передний план, поддерживая порядок.Это работает, если эти 200 элементов могут быть чисто определены значениями, а не индексом.

По сути, это идиома Erase-remove, с которой вы связаны.remove_if гарантированно выполнит O (N) сравнений (и не более O (N) копий), что будет более эффективно, чем сортировка (O (N log N)), хотя ваш последний вариант фактически не требует сортировки, еслииндексы определяются по значениям (просто копируйте в обратном направлении при копировании).

Тем не менее, использование remove_if (если вы можете) лучше, чем другие 2 варианта, потому что реализация уже написана для вас, так что меньше шансов на логическую ошибку и лучше передается what (не как ) делать.

Answer 3

Во-первых, не вызывайте erase больше раз, чем нужно, потому что для вектора он перемешивает все более поздние элементы вниз, давая всей операции & Omega; (n * m) время выполнения в худшем случае ( n размер вектора, m размер списка удаляемых индексов).

Думаю, первое, что я попробую, будет похоже на ваш текущий код:

• сортировка индексов
• создать новый вектор размером n - m
• перебирает исходный вектор, копирует indexes[0] элементы, пропускает элемент, затем копирует indexes[1] - indexes[0] - 1 элементы, пропускает элемент и т. Д.
• swap исходный вектор с новым.

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

Вы могли бы избежать второго шага, используя back_inserter, а не нажимая на вектор, хотя, вероятно, вы все равно зарезервировали бы место заранее.

[Редактировать: если подумать, зачем я что-то копирую? Вместо реализации измененного remove_copy_if, внедрите измененный remove_if и просто скопируйте в более раннюю точку в векторе. Затем erase / resize в конце. Я не буду беспокоиться о сортировке индексов O(m log m) до тех пор, пока это не станет проблемой, поскольку вряд ли она будет значительно медленнее, чем операция & Omega; (m), чтобы прочитать все значения, которые будут удалены, и сохранить их в некоторых вид контейнера. Затем использование этого контейнера в предикате для remove_if может быть или не быть O(1). Сортировка может оказаться быстрее для вероятных значений m.]

Answer 4

Вы можете скопировать все элементы вектора в список, кроме индекса во втором контейнере, а затем вернуться в вектор. Даже с вашим алгоритмом перехода от конца вектора к фронту в вашем векторе происходит много работы.

Сделайте ваш второй контейнер картой, чтобы он автоматически сортировал ваши значения.

редактирование:

Ответить на комментарий

Стоимость обслуживания карты в худшем случае такая же, как поддержание другой структуры (списка или вектора) и последующая ее сортировка. Если вы уже делаете это, вы можете оставить его на карте. Не имеет смысла жаловаться на издержки карты по сравнению с накладными расходами на сортировку списка.

Что касается производительности моего предложенного алгоритма, если m - это количество элементов, которые нужно удалить, а n - общее количество элементов, то это приводит к O (n - m).

Конечно, это в основном просто смешная попытка оптимизировать вектор.

1 - Вы не должны использовать вектор, если хотите удалить произвольный доступ. Это не то, в чем они хороши, используйте список, если это вообще возможно. И так как вы, кажется, гораздо больше интересуетесь относительным порядком, а не абсолютным индексом, мне интересно, зачем вообще нужен вектор. Если вы изложили всю проблему, возможно, существует общее решение, позволяющее использовать наиболее эффективную структуру данных для ее решения.

2 - Вместо сохранения второй структуры данных отметьте элементы, которые необходимо удалить непосредственно в их контейнере. Тривиальным способом является использование контейнера , использование контейнера > и использование char для отслеживания состояния элемента.

Если вы сделаете 1 и 2, вы полностью удалите все копии и получите намного более эффективную реализацию.

Answer 5

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

template <typename Type>
void erase_indices(
        const std::unordered_set<size_t>& indices_to_erase,
        std::vector<Type>& vec) {
    std::vector<bool> erase_index(vec.size(), false);
    for (const size_t i: indices_to_erase) {
        erase_index[i] = true;
    }
    std::vector<bool>::const_iterator it_to_erase = erase_index.cbegin();
    typename std::vector<Type>::iterator it_erase_from = std::remove_if(
        vec.begin(), vec.end(),
        [&it_to_erase](const Type&) -> bool {
          return *it_to_erase++ == true;
        }
    );
    vec.erase(it_erase_from, vec.end());
}

Это самое быстрое решение, которое пришло мне в голову.Вам нужно C ++ 11 , хотя.Пример использования для удаления элементов с индексами 2 и 5:

constexpr size_t num = 10u;
std::vector<int> vec(num);
std::iota(vec.begin(), vec.end(), 0);

std::unordered_set<size_t> indices_to_erase;
indices_to_erase.insert(2u);
indices_to_erase.insert(5u);

erase_indices(indices_to_erase, vec);

До:

0 1 2 3 4 5 6 7 8 9

После:

0 1 3 4 6 7 8 9

Редактировать: Если вы хотите быть более гибким в отношении типа контейнера, в котором хранятся индексы для удаления:

template <typename Type, typename Container>
void erase_indices(
        const Container& indices_to_erase,
        std::vector<Type>& vec) {
    typedef typename Container::value_type IndexType;
    static_assert(std::is_same<IndexType, std::size_t>::value,
        "Indices to be erased have to be of type std::size_t");
    std::vector<bool> erase_index(vec.size(), false);
    for (const IndexType idx_erase: indices_to_erase) {
        erase_index[idx_erase] = true;
    }
    std::vector<bool>::const_iterator it_to_erase = erase_index.cbegin();
    typename std::vector<Type>::iterator it_erase_from = std::remove_if(
        vec.begin(), vec.end(),
        [&it_to_erase](const Type&) -> bool {
          return *it_to_erase++ == true;
        }
    );
    vec.erase(it_erase_from, vec.end());
}

Теперь вы можете использовать любой тип контейнера из библиотеки Containers для предоставления индексов, которые будутстирается, пока value_type этого контейнера std::size_t.Использование остается прежним.

Answer 6

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

Я говорю об этом только потому, что вы, кажется, обеспокоены скоростью. Если уже выдвинутые предложения не сработают, возможно, эта идея стоит задуматься! По сути, ускорить процесс, не выполняя операцию в первую очередь.

Answer 7

Я написал функцию, основанную на ответе Бенджамина Линдли https://stackoverflow.com/a/4115582/2835054.

#include <iostream>
#include <algorithm>
#include <vector>

template <typename elementType, typename indexType>
void remove_multiple_elements_from_vector(std::vector<elementType> &vector,
std::vector<indexType> &indexes)
{
    // 1. indexType is any integer.
    // 2. elementType is any type.
    // 3. Indexes should be unique.
    // 4. The largest index inside indexes shouldn't be larger than
    //    the largetst index in the vector.
    // 5. Indexes should be sorted in ascending order
    //    (it is done inside function).
    std::sort(indexes.begin(), indexes.end());
    indexType currentIndexInIndexesVector = 0;
    indexType last = 0;
    for(indexType i=0; i<vector.size(); ++i, ++last)
    {
       while(indexes[currentIndexInIndexesVector] == i)
       {
          ++i;
          ++currentIndexInIndexesVector;
       }
       if(i >= vector.size()) break;

       vector[last] = vector[i];   
    }

    vector.resize(last);
}


int main()
{
    std::vector<int> vector = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::vector<int> indexes = {0, 10, 5};

    for (auto &vectorElement : vector)
    {
        std::cout << vectorElement << " ";
    }    
    std::cout << "\n";

    remove_multiple_elements_from_vector<int, int>(vector, indexes);

    for (auto &vectorElement : vector)
    {
        std::cout << vectorElement << " ";
    }
}