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

Ответ 1

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

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

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

Ответ 2

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

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

Ответ 3

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

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

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

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

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

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

Ответ 4

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

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

изменить:

Чтобы ответить на комментарий

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

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

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

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

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

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

Ответ 5

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

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

Ответ 6

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

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

Это самое быстрое решение, которое пришло мне в голову. Вам нужно С++ 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

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

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

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

Ответ 7

Я написал функцию на основе ответа Бенджамина Линдли fooobar.com/info/319397/....

#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 << " ";
    }
}