Удаление группы элементов по их индексу?

Question

Удаление группы элементов по их индексу?

у меня есть

vector<int> myVector;

И у меня есть список index удалить:

vector<size_t> deleteIndex;

Какая стратегия будет наиболее эффективной для удаления этих индексов?

На самом деле одно неэффективное решение было бы:

//> sort deleteindex
auto deleted= 0;
for(auto i=0;i<deleteIndex.size();i++ {
myVector.erase(myVector.begin()+deleteIndex[i]-deleted);
deleted++;
}

1

c++remove-if vector

Решение

Другие решения

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

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

1

Источник

Accepted Answer

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

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

Пример реализации:

template <class _FwdIt, class _FwdIt2>
_FwdIt remove_by_index(_FwdIt first,
_FwdIt last,
_FwdIt2 sortedIndexFirst,
_FwdIt2 sortedIndexLast)
{
_FwdIt copyFrom = first;
_FwdIt copyTo = first;
_FwdIt2 currentIndex = sortedIndexFirst;

size_t index = 0;
for (; copyFrom != last; ++copyFrom, ++index)
{
if (currentIndex != sortedIndexLast &&
index == *currentIndex)
{
// Should delete this item, so don't increment copyTo
++currentIndex;
print("%d", *copyFrom);
}
else
{
// Copy the values if we're at different locations
if (copyFrom != copyTo)
*copyTo = *copyFrom;
++copyTo;
}
}
return copyTo;
}

Пример использования:

#include <vector>
#include <algorithm>
#include <functional>

int main(int argc, char* argv[])
{
std::vector<int> myVector;

for (int i = 0; i < 10; ++i)
myVector.push_back(i * 10);

std::vector<size_t> deleteIndex;
deleteIndex.push_back(3);
deleteIndex.push_back(6);

myVector.erase(
remove_by_index(myVector.begin(), myVector.end(), deleteIndex.begin(), deleteIndex.end()),
myVector.end());

for (std::vector<int>::iterator it = myVector.begin();
it != myVector.end(); ++it)
{
printf("%d ", *it);
}

return 0;
}

Суть: https://gist.github.com/eleven41/5746079
Проверьте здесь: http://ideone.com/0qkDw5

1