Подтвердить что ты не робот

Как удалить элементы из std::vector с учетом списка индексов

У меня есть вектор элементов items и вектор индексов, который следует удалить из items:

std::vector<T> items;
std::vector<size_t> indicesToDelete;

items.push_back(a);
items.push_back(b);
items.push_back(c);
items.push_back(d);
items.push_back(e);

indicesToDelete.push_back(3);
indicesToDelete.push_back(0);
indicesToDelete.push_back(1);

// given these 2 data structures, I want to remove items so it contains
// only c and e (deleting indices 3, 0, and 1)
// ???

Какой лучший способ выполнить удаление, зная, что при каждом удалении он влияет на все остальные индексы в indicesToDelete?

Несколько идей были бы следующими:

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

Похоже, я слишком задумываюсь о такой, казалось бы, тривиальной задаче. Любые лучшие идеи?

Изменить Вот решение, в основном вариант # 1, но с использованием итераторов для определения блоков для копирования результата.

template<typename T>
inline std::vector<T> erase_indices(const std::vector<T>& data, std::vector<size_t>& indicesToDelete/* can't assume copy elision, don't pass-by-value */)
{
    if(indicesToDelete.empty())
        return data;

    std::vector<T> ret;
    ret.reserve(data.size() - indicesToDelete.size());

    std::sort(indicesToDelete.begin(), indicesToDelete.end());

    // new we can assume there is at least 1 element to delete. copy blocks at a time.
    std::vector<T>::const_iterator itBlockBegin = data.begin();
    for(std::vector<size_t>::const_iterator it = indicesToDelete.begin(); it != indicesToDelete.end(); ++ it)
    {
        std::vector<T>::const_iterator itBlockEnd = data.begin() + *it;
        if(itBlockBegin != itBlockEnd)
        {
            std::copy(itBlockBegin, itBlockEnd, std::back_inserter(ret));
        }
        itBlockBegin = itBlockEnd + 1;
    }

    // copy last block.
    if(itBlockBegin != data.end())
    {
        std::copy(itBlockBegin, data.end(), std::back_inserter(ret));
    }

    return ret;
}
4b9b3361

ОТВЕТЫ

Ответ 1

Я бы пошел на 1/3, то есть: упорядочить вектор индексов, создать два итератора в вектор данных, один для чтения и один для написания. Инициализируйте итератор записи к первому элементу, который нужно удалить, и итератору чтения к одному за пределами этого. Затем на каждом шаге инкремента цикла итераторы на следующее значение (запись) и следующее значение не пропускаются (считываются) и копируют/перемещают элементы. В конце цикла вызовите erase, чтобы отбросить элементы за последним, записанные в позицию.

Кстати, это подход, реализованный в алгоритмах remove/remove_if STL с той разницей, что вы поддерживаете условие в отдельном упорядоченном векторе.

Ответ 2

std::sort() indicesToDelete в порядке убывания, а затем удалить из item в обычном цикле for. Нет необходимости корректировать индексы.

Ответ 3

Это может быть даже вариант 4:

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

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

Ответ 4

Это зависит от числа, которое вы удаляете.

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

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

Ответ 5

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

Однако, если вас не интересует относительный порядок элементов, это будет не так быстро.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <set>

using std::vector;
using std::string;
using std::remove_if;
using std::cout;
using std::endl;
using std::set;

struct predicate {
    public:
        predicate(const vector<string>::iterator & begin, const vector<size_t> & indices) {
            m_begin = begin;
            m_indices.insert(indices.begin(), indices.end());
        }

        bool operator()(string & value) {
            const int index = distance(&m_begin[0], &value);
            set<size_t>::iterator target = m_indices.find(index);
            return target != m_indices.end();
        }

    private:
        vector<string>::iterator m_begin;
        set<size_t> m_indices;
};

int main() {
    vector<string> items;
    items.push_back("zeroth");
    items.push_back("first");
    items.push_back("second");
    items.push_back("third");
    items.push_back("fourth");
    items.push_back("fifth");

    vector<size_t> indicesToDelete;
    indicesToDelete.push_back(3);
    indicesToDelete.push_back(0);
    indicesToDelete.push_back(1);

    vector<string>::iterator pos = remove_if(items.begin(), items.end(), predicate(items.begin(), indicesToDelete));
    items.erase(pos, items.end());

    for (int i=0; i< items.size(); ++i)
        cout << items[i] << endl;
}

Выход для этого будет:

second
fourth
fifth

Есть немного накладных расходов на производительность, которые все еще могут быть уменьшены. В remove_if (atleast on gcc) предикат копируется по значению для каждого элемента в векторе. Это означает, что мы, возможно, каждый раз выполняем конструктор копирования на множестве m_indices. Если компилятор не может избавиться от этого, я бы рекомендовал передавать индексы в виде набора и хранить его как ссылку на константу.

Мы могли бы сделать это следующим образом:

struct predicate {
    public:
        predicate(const vector<string>::iterator & begin, const set<size_t> & indices) : m_begin(begin), m_indices(indices) {
        }

        bool operator()(string & value) {
            const int index = distance(&m_begin[0], &value);
            set<size_t>::iterator target = m_indices.find(index);
            return target != m_indices.end();
        }

    private:
        const vector<string>::iterator & m_begin;
        const set<size_t> & m_indices;
};

int main() {
    vector<string> items;
    items.push_back("zeroth");
    items.push_back("first");
    items.push_back("second");
    items.push_back("third");
    items.push_back("fourth");
    items.push_back("fifth");

    set<size_t> indicesToDelete;
    indicesToDelete.insert(3);
    indicesToDelete.insert(0);
    indicesToDelete.insert(1);

    vector<string>::iterator pos = remove_if(items.begin(), items.end(), predicate(items.begin(), indicesToDelete));
    items.erase(pos, items.end());

    for (int i=0; i< items.size(); ++i)
        cout << items[i] << endl;
}

Ответ 6

В основном ключ к проблеме - это помнить, что если вы удаляете объект с индексом i и не используете заполнитель могильника, тогда вектор должен сделать копию всех объектов после i. Это относится ко всем возможным возможностям, за исключением #1. Копирование в новый список делает одну копию независимо от того, сколько вы удаляете, что делает ее самым быстрым ответом.
И, как сказал Дэвид Родригес, сортировка списка индексов, подлежащих удалению, допускает некоторые незначительные оптимизации, но это может стоить того, если вы удаляете более 10-20 (сначала просим профиль).

Ответ 7

Вот мое решение для этой проблемы, которое хранит порядок оригинальных "элементов":

  • создать "векторную маску" и инициализировать (заполнить) его "ложными" значениями.
  • измените значения маски на "true" для всех индексов, которые вы хотите удалить.
  • перебрать все элементы "маски" и удалить из обоих векторов "элементы" и "маску" элементов с "истинными" значениями.

Вот пример кода:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<unsigned int> items(12);
    vector<unsigned int> indicesToDelete(3);
    indicesToDelete[0] = 3;
    indicesToDelete[1] = 0;
    indicesToDelete[2] = 1;
    for(int i=0; i<12; i++) items[i] = i;

    for(int i=0; i<items.size(); i++)
      cout << "items[" << i << "] = " << items[i] << endl;

    // removing indeces
    vector<bool> mask(items.size());
    vector<bool>::iterator mask_it;
    vector<unsigned int>::iterator items_it;
    for(size_t i = 0; i < mask.size(); i++)
      mask[i] = false;
    for(size_t i = 0; i < indicesToDelete.size(); i++)
      mask[indicesToDelete[i]] = true;        

    mask_it = mask.begin();
    items_it = items.begin();
    while(mask_it != mask.end()){
      if(*mask_it){
        items_it = items.erase(items_it);
        mask_it = mask.erase(mask_it);
      }
      else{
        mask_it++;
        items_it++;
      }
    }

    for(int i=0; i<items.size(); i++)
      cout << "items[" << i << "] = " << items[i] << endl;

    return 0;
}

Это не является быстрой реализацией для использования с большими наборами данных. Метод "erase()" занимает время, чтобы переставить вектор после удаления элемента.