Стирание элементов в 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

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

Версия C++11 с использованием std::move (см. Закомментированную строку для версии C++98):

template <typename ForwardIt, typename SortedIndicesForwardIt>
inline ForwardIt remove_at(
    ForwardIt first,
    ForwardIt last,
    SortedIndicesForwardIt indices_first,
    SortedIndicesForwardIt indices_last)
{
    typedef typename std::vector<bool> flags;
    // flag elements to keep
    flags is_keep(
        static_cast<flags::size_type>(std::distance(first, last)), true);
    for(; indices_first != indices_last; ++indices_first)
        is_keep[static_cast<flags::size_type>(*indices_first)] = false;
    // move kept elements to beginning
    ForwardIt result = first;
    for(flags::const_iterator it = is_keep.begin(); first != last; ++first, ++it)
        if(*it) // keep element
            *result++ = std::move(*first); // *result++ = *first; //<= c++98
    return result;
}

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

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

std::sort(ii.begin(), ii.end()); // sort indices
vec.erase(remove_at(v.begin(), v.end(), ii.begin(), ii.end()), v.end());
//  ^     ^         
// erase-remove elements at indices

Заметки:

• индексы должны быть отсортированы
• помечает каждый элемент (сохраняется или удаляется), используя временный вектор bools
• Живой пример
• Страница Github: https://github.com/artem-ogre/remove_at

Answer 3

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

// 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 исправил ошибку, благодаря Steve Jessop, который терпеливо пытался показать мне это

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

Answer 5

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

Answer 6

Это алгоритм, основанный на Andriy Tylychko"s ответ так, что это может сделать его проще и быстрее использовать ответ, без того, чтобы забрать его на части. Это также устраняет необходимость иметь -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;
    }

    // Debug check to see if the indices are already sorted and are less than
    // size of items.
    assert(indices_begin[0] < items_size);
    assert(std::is_sorted(indices_begin, indices_end));

    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>

А Demo можно найти на сайте godbolt.org.