Стирание нескольких объектов от станд.:: вектор?
Вот моя проблема, позволяет, говорят, что у меня есть станд.:: вектор с ints в нем.
скажем, это имеет 50,90,40,90,80,60,80.
Я знаю, что должен удалить вторые, пятые и третьи элементы. Я не обязательно всегда знаю порядок элементов удалить, ни сколько. Проблема путем стирания элемента, это изменяет индекс других элементов. Поэтому, как я мог стереть их и компенсировать индексное изменение. (сортирующий затем линейно стирающийся со смещением не опция),
Спасибо
5 ответов
Предлагаю несколько методов:
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 (| вектор v |), если список индексов короче вектора.
3. Другой более медленный метод, который сохраняет исходный порядок элементов:
Используйте предикат и удалите if, как описано в https://stackoverflow.com/a/3487742/280314 . Чтобы сделать это эффективным и соблюдая требования а не «сортировка, а затем линейное стирание со смещением», моя идея состоит в том, чтобы реализовать предикат с использованием хеш-таблицы и настроить индексы, хранящиеся в хеш-таблице, по мере того, как удаление продолжается при возврате истины, как предложил Клаим.
Используя предикат и алгоритм remove_if, вы можете добиться желаемого: см. http: //www.cplusplus.com / reference / algorithm / remove_if /
Не забудьте стереть элемент (см. идиома удаления-стирания ).
Ваш предикат будет просто удерживать idx каждого значения, чтобы удалять и уменьшать все сохраняемые индексы каждый раз, когда он возвращает true.
Тем не менее, если вы можете позволить себе просто удалить каждый объект с помощью идиомы удаления-стирания, просто сделайте свою жизнь проще, сделав это.
Я бы переместил элементы, которые вы не хотите стирать, во временный вектор, а затем заменил бы им исходный вектор.
Стирайте элементы в обратном порядке. Другими словами, сначала стирается самый высокий индекс, затем следующий и т.д. Вы не аннулируете предыдущие итераторы или индексы, поэтому можно просто использовать очевидный подход, состоящий из нескольких вызовов стирания.
Будет ли это работать:
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), независимо от того, сколько элементов вы удаляете. Вы можете получить некоторую эффективность, переупорядочив вектор в строке (но я думаю, что так он будет более читабельным).