Стирание элементов в stl :: vector с использованием индексов

Question

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

Хотя я нашел похожие посты по этой проблеме, некоторые из нихнеобходимо удалить один один элемент или несколько элементов , где идиома удаления-стирания казалась хорошим решением.В моем случае, однако, мне нужно удалить несколько элементов, и поскольку я использую индексы вместо прямых значений, remove-erase idiom не может быть применено, верно?Мой код приведен ниже, и я хотел бы знать, если это возможно сделать лучше, чем это с точки зрения эффективности?

bool find_element(const vector<int> & vMyVect, int nElem){
    return (std::find(vMyVect.begin(), vMyVect.end(), nElem)!=vMyVect.end()) ? true : false;
}

void remove_elements(){

    srand ( time(NULL) );

    int nSize = 20;
    std::vector<int> vMyValues;
    for(int i = 0; i < nSize; ++i){
            vMyValues.push_back(i);
    }

    int nRandIdx;
    std::vector<int> vMyIndexes;
    for(int i = 0; i < 6; ++i){
        nRandIdx = rand() % nSize;
        vMyIndexes.push_back(nRandIdx);
    }

    std::vector<int> vMyResult;
    for(int i=0; i < (int)vMyValues.size(); i++){
        if(!find_element(vMyIndexes,i)){
            vMyResult.push_back(vMyValues[i]);
        }
    }
}

Answer 1

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

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

... fill up the vectors ...

sort (vMyIndexes.begin(), vMyIndexes.end());

for(int i=vMyIndexes.size() - 1; i >= 0; i--){
    vMyValues.erase(vMyValues.begin() + vMyIndexes[i])
}

Answer 2

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

// fill vMyIndexes, take care about duplicated values
vMyIndexes.push_back(-1); // to handle range from 0 to the first index to remove
vMyIndexes.push_back(vMyValues.size()); // to handle range from the last index to remove and to the end of values
std::sort(vMyIndexes.begin(), vMyIndexes.end());
std::vector<int>::iterator last = vMyValues.begin();
for (size_t i = 1; i != vMyIndexes.size(); ++i) {
    size_t range_begin = vMyIndexes[i - 1] + 1;
    size_t range_end = vMyIndexes[i];
    std::copy(vMyValues.begin() + range_begin, vMyValues.begin() + range_end,   last);
    last += range_end - range_begin;
}
vMyValues.erase(last, vMyValues.end());

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

Answer 3

Стереть-удалить несколько элементов по заданным индексам

Обновление: после отзыва о производительности от @kory, я изменил алгоритм, чтобы не использовать пометки и перемещать / копировать элементы в чанках (не один за другим).

Примечания:

• индексы должны быть отсортированы и уникальны
• использует std::move (заменить на std::copy для c ++ 98):

Github Живой пример

Код:

template <class ForwardIt, class SortUniqIndsFwdIt>
inline ForwardIt remove_at(
    ForwardIt first,
    ForwardIt last,
    SortUniqIndsFwdIt ii_first,
    SortUniqIndsFwdIt ii_last)
{
    if(ii_first == ii_last) // no indices-to-remove are given
        return last;
    typedef typename std::iterator_traits<ForwardIt>::difference_type diff_t;
    typedef typename std::iterator_traits<SortUniqIndsFwdIt>::value_type ind_t;
    ForwardIt destination = first + static_cast<diff_t>(*ii_first);
    while(ii_first != ii_last)
    {
        // advance to an index after a chunk of elements-to-keep
        for(ind_t cur = *ii_first++; ii_first != ii_last; ++ii_first)
        {
            const ind_t nxt = *ii_first;
            if(nxt - cur > 1)
                break;
            cur = nxt;
        }
        // move the chunk of elements-to-keep to new destination
        const ForwardIt source_first =
            first + static_cast<diff_t>(*(ii_first - 1)) + 1;
        const ForwardIt source_last =
            ii_first != ii_last ? first + static_cast<diff_t>(*ii_first) : last;
        std::move(source_first, source_last, destination);
        // std::copy(source_first, source_last, destination) // c++98 version
        destination += source_last - source_first;
    }
    return destination;
}

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

std::vector<int> v = /*...*/; // vector to remove elements from
std::vector<int> ii = /*...*/; // indices of elements to be removed

// prepare indices
std::sort(ii.begin(), ii.end());
ii.erase(std::unique(ii.begin(), ii.end()), ii.end());

// remove elements at indices
v.erase(remove_at(v.begin(), v.end(), ii.begin(), ii.end()), v.end());

Answer 4

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

template<typename Cont, typename It>
auto ToggleIndices(Cont &cont, It beg, It end) -> decltype(std::end(cont))
{
    int helpIndx(0);
    return std::stable_partition(std::begin(cont), std::end(cont), 
        [&](typename Cont::value_type const& val) -> bool {
            return std::find(beg, end, helpIndx++) != end;
    });
}

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

std::vector<int> v;
v.push_back(0);
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);

int ar[] = { 2, 0, 4 };
v.erase(ToggleIndices(v, std::begin(ar), std::end(ar)), v.end());

• Если операция «только по индексу» не требуется, вы можете использовать метод remove_if instedof stable_partition (O (n) против сложности O (nlogn))
• Для работы с массивами C в качестве контейнеров лямбда-функция должна быть [&] (decltype (* (std :: begin (cont))) const &val) -> bool {return std :: find (beg, end, helpIndx ++)! = end;} но тогда метод .erase () больше не является опцией

Answer 5

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

Answer 6

Это алгоритм, основанный на Andriy Tylychko 's answer , так что это может упростить и ускорить использование ответа, не разбирая его отдельно.Это также устраняет необходимость иметь -1 в начале списка индексов и число items в конце.Также некоторый отладочный код, чтобы убедиться, что indices действителен (отсортирован и допустим индекс в items).

template <typename Items_it, typename Indices_it>
auto remove_indices(
    Items_it items_begin, Items_it items_end
  , Indices_it indices_begin, Indices_it indices_end
)
{
    static_assert(
      std::is_same_v<std::random_access_iterator_tag
        , typename std::iterator_traits<Items_it>::iterator_category>
      , "Can't remove items this way unless Items_it is a random access iterator");

    size_t indices_size = std::distance(indices_begin, indices_end);
    size_t items_size = std::distance(items_begin, items_end);
    if (indices_size == 0) {
        // Nothing to erase
        return items_end;
    }

#if !defined(NDEBUG) || defined(_DEBUG)
    // Debug check to see if the indices are already sorted and are less than
    // size of items.
    assert(indices_begin[0] < items_size);
    for (int i = 1; i < indices_size; ++i) {
        assert(indices_begin[i - 1] < indices_begin[i]);
        assert(indices_begin[i] < items_size);
    }
#endif

    auto last = items_begin;
    auto shift = [&last, &items_begin](size_t range_begin, size_t range_end) {
        std::copy(items_begin + range_begin, items_begin + range_end, last);
        last += range_end - range_begin;
    };

    size_t last_index = -1;
    for (size_t i = 0; i != indices_size; ++i) {
        shift(last_index + 1, indices_begin[i]);
        last_index = indices_begin[i];
    }
    shift(last_index + 1, items_size);
    return last;
}

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

template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T>& v)
{
    for (auto i : v) {
        os << i << " ";
    }
    os << std::endl;
    return os;
}

int main()
{
    using std::begin;
    using std::end;
    std::vector<int> items = { 1, 3, 6, 8, 13, 17 };
    std::vector<int> indices = { 0, 1, 2, 3, 4 };

    std::cout << items;
    items.erase(
          remove_indices(begin(items), end(items), begin(indices), end(indices))
        , std::end(items)
    );
    std::cout << items;

    return 0;
}

Вывод:

1 3 6 8 13 17 
17 

Требуемые заголовки:

#include <iterator>
#include <vector>
#include <iostream> // only needed for output
#include <cassert>
#include <type_traits>

И Демо можно найти на godbolt.org.