самый быстрый способ удалить элементы из нескольких std :: vectors - PullRequest
Новая
       7

самый быстрый способ удалить элементы из нескольких std :: vectors

0 голосов
/ 26 февраля 2019

У меня есть три std::vectors, каждый из которых содержит разные типы данных.

Что мне нужно сделать, это удалить один и тот же элемент индекса из каждого, в зависимости от значения этого индексированного элемента в первом.

В приведенном ниже коде, если значение localMap_points[i].m_counter больше 30, я стираю элемент с индексом [i] из всех трех векторов.(localMap_desc содержит 8 элементов для других векторов один, следовательно, к этому добавляется x 8)

Это работает отлично, но медленно.Есть ли более быстрый способ сделать это?

У меня есть: 

for (int i = 0; i < localMap_points.size(); i++)
{
    if (localMap_points[i].m_counter > 30)
    {
        localMap_kp.erase(localMap_kp.begin() + i, localMap_kp.begin() + i + 1); // Deleting from n element to n element
        localMap_desc.erase(localMap_desc.begin() + (i * 8), localMap_desc.begin() + (i * 8) + 8); // Deleting from n element to n element X 8
        localMap_points.erase(localMap_points.begin() + i, localMap_points.begin() + i + 1); // Deleting from n element to n element

    }

}

Ответы [ 3 ]

0 голосов
/ 26 февраля 2019

Узким местом производительности здесь является макет памяти std::vector, возможно, вместе со свойствами специальных функций-членов / существованием векторных элементов.Если вы удалите один элемент в середине, все элементы от этой позиции до конца должны быть перемещены, чтобы приспособиться к элементу перед удаленным.Это делается с помощью

  • одна копия конструкции на элемент, если нет движущегося ctor или если ctor движения не помечен noexcept
  • одна конструкция перемещения на элемент в противном случае.

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

Во-вторых, обязательно используйте erase-removeидиома здесь.Следуя этой схеме, переупорядочение в терминах вызовов подкачки выполняется в первую очередь, перед любыми вызовами на удаление.Для n элементов, подлежащих удалению, это n вызовы подкачки.Затем у вас будет тривиальный вызов std::vector::erase, так как все элементы уже на месте, как и должно быть.Чтобы эта процедура была максимально быстрой, вы можете рассмотреть возможность предоставления функции swap для пользовательских типов.

0 голосов
/ 26 февраля 2019

Вот пример того, как вы можете применить идиому erase-remove для трех векторов одновременно.

Алгоритм в O ( N ), т.е. требуетодин проход по векторам. 

template<typename T1, typename T2, typename T3, typename P>
void erase3(T1& v1, T2& v2, T3& v3, P predicate) {
    auto first1 = begin(v1);
    auto first2 = begin(v2);
    auto first3 = begin(v3);
    while (first1 != end(v1) && !predicate(*first1)) {
        ++first1; ++first2; ++first3;
    }
    if (first1 != end(v1)) {
        auto it1 = first1; auto it2 = first2; auto it3 = first3;
        while (++it1 != end(v1)) {
            ++it2;
            ++it3;
            if (!predicate(*it1)) {
                *first1++ = std::move(*it1);
                *first2++ = std::move(*it2);
                *first3++ = std::move(*it3);
            }
        }
        v1.erase(first1, end(v1));
        v2.erase(first2, end(v2));
        v3.erase(first3, end(v3));
    }
}

int main()
{
    std::vector<int> v1 = { 1,2,3,4,5 }, v2 = { 11,12,13,14,15 }, v3 = { 21,22,23,24,25 };

    erase3(v1, v2, v3, [](int a) { return a == 3 || a == 4; });

}

Это работает, перемещая все оставшиеся элементы в начало векторов, а затем обрезая выдвинутые элементы с конца.

0 голосов
/ 26 февраля 2019

Используйте более правильную структуру данных.векторы не предназначены для быстрого внутреннего удаления и вставки (они O(n)), списки могут быть лучшим выбором, если вам не нужен индексированный доступ (вставка / удаление * постоянное время O(1) ==).В зависимости от ваших потребностей, вы можете использовать вспомогательную структуру, но это невозможно без дополнительной информации.

--- Добавление другой мысли (хотя кто-то уже предлагал это).

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

Это будет O(1).

---Мысли вслух.

Еще один прием - использовать очередь с приоритетами .Это структура данных, которая переупорядочивается на основе «веса» одного поля, в вашем приложении это будет поле counter.они могут вставлять в O(log n) и удалять сверху O(1).Так что было бы довольно быстро удалить предметы с более высоким counter, потому что они всегда находятся сверху.

...