Использовать вектор индексов, чтобы стереть эти индексы другого вектора

У меня есть два вектора, один вектор индексов другого вектора, который я хотел бы стереть. В настоящее время я делаю следующее:

#include <vector>
#include <iostream>
#include <string>

int main() {
        std::vector<std::string> my_vec;
        my_vec.push_back("one");
        my_vec.push_back("two");
        my_vec.push_back("three");
        my_vec.push_back("four");
        my_vec.push_back("five");
        my_vec.push_back("six");

        std::vector<int> remove_these;
        remove_these.push_back(0);
        remove_these.push_back(3);

        // remove the 1st and 4th elements
        my_vec.erase(my_vec.begin() + remove_these[1]);
        my_vec.erase(my_vec.begin() + remove_these[0]);

        my_vec.erase(remove_these.begin(), remove_these.end());

        for (std::vector<std::string>::iterator it = my_vec.begin(); it != my_vec.end(); ++it)
                std::cout << *it << std::endl;

        return 0;
}

Но я думаю, что это не элегантно и неэффективно. Кроме того, я думаю, что я должен быть осторожен, чтобы отсортировать remove_these Vector и начинайте с конца (поэтому я стираю индекс 3 перед индексом 0). Я хотел бы иметь одну команду стирания, что-то вроде

my_vec.erase(remove_these.begin(), remove_these.end());

Но, конечно, это не сработает, потому что my_vec.erase() ожидает, что итераторы ссылаются на один и тот же вектор.

Источник

3 ответа

Решение

В вашей ситуации я думаю, что есть две проблемы, которые стоит принять во внимание:

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

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

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

Я лично пошел бы на простой цикл, но C++ предлагает много способов для достижения аналогичного результата. Вот версия цикла:

    std::vector<bool> remove_these(my_vec.size(), false):
    remove_these[0] = remove_these[4] = true;

    std::vector<std::string> my_result;
    my_result.reserve(my_vec.size() - 2);

    for (int i = 0; i < remove_these.size(); ++i)
        if (!remove_these[i])
             my_result.push_back(my_vec[i]);

Обратите внимание на использование reserve чтобы избежать множественных перераспределений при заполнении вектора.

Теперь все, что нужно сделать, это обернуть вышеупомянутый код в функцию, которая предварительно преобразует вектор int в вектор bool:

template <typename IT>
void erase(std::vector<std::string> &my_vec, IT begin, IT end){
    std::vector<std::string> res;
    std::vector<bool> r(my_vec.size(), false);
    res.reserve(my_vec.size() - (end - begin));
    for (IT it = begin; it != end; ++it)
        r[*it] = true;
    for (int i = 0; i < r.size(); ++i)
        if (!r[i])
            res.push_back(my_vec[i]);
    my_vec = res;
}

Это было бы это. Временная сложность алгоритма составляет около O (N + M), где N и M - размеры my_vec а также remove_these, В качестве альтернативы можно заменить второй цикл remove_if,

На самом деле, если stl предоставляет функцию для итерации по последовательности, такой как remove_if и вызвать функцию предиката, принимающую в качестве параметра ключ и значение этого итератора, мы могли бы использовать его, передав его my_vec обратные итераторы и лямбда для проверки, находится ли данный ключ в remove_these, но сложность по времени будет немного выше, чем решение выше.

Источник

Известная идиома для удаления элементов из стандартной последовательности - идиома стирания / удаления. Вы сначала позвоните remove алгоритм, который будет перемещать все элементы, которые вы хотите сохранить в начале последовательности, то вы erase удаленные элементы в конце вашей последовательности. В C++11 это выглядит так:

std::vector< std::string > strings;
strings.erase(
    std::remove_if(
        strings.begin(), strings.end()
      , []( std::string const& s ) -> bool
        {
            return /*whether to remove this item or not*/;
        }
    )
  , strings.end()
);
Источник 
    std::sort(remove_these.begin(), remove_these.end());

    int counter = 0;
    auto end = std::remove_if(my_vec.begin(), my_vec.end(),
                             [&](const std::string&) mutable {
        return std::binary_search(remove_these.begin(), remove_these.end(), counter++);
    });
    my_vec.erase(end, my_vec.end());

Это использует remove_if с лямбда-функцией, которая возвращает true, если индекс текущего элемента (отслеживается переменной counter) находится в векторе remove_these, Этот вектор отсортирован так, что binary_search может быть использован, как оптимизация. Если список элементов для удаления невелик, может быть быстрее не сортировать его и просто использовать его в лямбда-выражении:

        return std::find(remove_these.begin(), remove_these.end(), counter++) != remove_these.end();
Источник
Другие вопросы по тегам