Стирание нескольких объектов из std :: vector?

Question

Вот моя проблема, допустим, у меня есть std :: vector с целыми числами.

Допустим, у него 50,90,40,90,80,60,80.

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

Спасибо

Answer 1

Я предлагаю несколько методов:

1. Быстрый метод, который не сохраняет первоначальный порядок элементов:

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

void quickDelete( int idx )
{
  vec[idx] = vec.back();
  vec.pop_back();
}

Я вижу, что это, по сути, кодированная вручную идиома стирания-удаления, на которую указал Клаим ...

2. Более медленный метод, который сохраняет первоначальный порядок элементов:

Шаг 1. Пометьте все векторные элементы, которые нужно удалить, т. Е. Специальным значением. Здесь есть O (| индексы для удаления |).

Шаг 2: Сотрите все отмеченные элементы, используя v.erase( remove (v.begin(), v.end(), special_value), v.end() );. Это имеет O (| вектор v |).

Таким образом, общее время выполнения равно O (| vector v |), при условии, что список индексов короче вектора.

3. Еще один более медленный метод, который сохраняет первоначальный порядок элементов:

Используйте предикат и удалите его, как описано в https://stackoverflow.com/a/3487742/280314. Чтобы сделать это эффективным и соблюдая требования а не «сортировка, а затем линейное стирание со смещением», моя идея состоит в том, чтобы реализовать предикат с использованием хеш-таблицы и настроить индексы, хранящиеся в хеш-таблице, по мере того, как удаление продолжается, возвращая значение true, как предложил Клайм.

Answer 2

Используя предикат и алгоритм remove_if, вы можете достичь желаемого: см. http://www.cplusplus.com/reference/algorithm/remove_if/

Не забудьте стереть элемент (см. идиома удаления-стирания ).

Ваш предикат будет просто содержать idx каждого значения, чтобы удалять и уменьшать все индексы, которые он сохраняет каждый раз, когда возвращает true.

При этом вы можете позволить себе просто удалить каждый объект с помощью remove-eraseидиома, просто сделай свою жизнь проще, делая это.

Answer 3

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

Answer 4

Я бы переместил элементы, которые вы не хотите стереть, во временный вектор, а затем заменил исходный вектор этим.

Answer 5

Будет ли это работать:

void DeleteAll(vector<int>& data, const vector<int>& deleteIndices)
{
    vector<bool> markedElements(data.size(), false);
    vector<int> tempBuffer;
    tempBuffer.reserve(data.size()-deleteIndices.size());

    for (vector<int>::const_iterator itDel = deleteIndices.begin(); itDel != deleteIndices.end(); itDel++)
        markedElements[*itDel] = true;

    for (size_t i=0; i<data.size(); i++)
    {
        if (!markedElements[i])
            tempBuffer.push_back(data[i]);
    }
    data = tempBuffer;
}

Это операция O (n), независимо от того, сколько элементов вы удаляете.Вы можете получить некоторую эффективность, переупорядочив встроенный вектор (но я думаю, что таким образом он будет более читабельным).