удалить произвольный список элементов из std :: vector & lt; std :: vector & lt; T & gt; & GT;

Question

удалить произвольный список элементов из std :: vector & lt; std :: vector & lt; T & gt; & GT;

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

Я думал о создании нового вектора векторов, копировании только не удаленных строк с использованием семантики перемещения, например:

    //std::vector<std::vector<T> > values is the array to remove rows from
//std::vector<bool> toBeDeleted contains "marked for deletion" flags for each row

//Count the new number of remaining rows
unsigned int newNumRows = 0;
for(unsigned int i=0;i<numRows();i++)
{
if(!toBeDeleted[i])
{
newNumRows++;
}
}//Create a new array already sized in rows
std::vector<std::vector<T> > newValues(newNumRows);

//Move rows
for(unsigned int i=0;i<numRows();i++)
{
if(!toBeDeleted[i])
{
newValues[i] = std::move(values[i]);
}
}

//Set the new array and clear the old one efficiently
values = std::move(newValues);

Это самый эффективный способ?

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

    unsigned int newIndex = 0;
for(unsigned int oldIndex=0;oldIndex<values.size();oldIndex++)
{
if(!toBeDeleted[oldIndex])
{
if(oldIndex!=newIndex)
{
values[newIndex] = std::move(values[oldIndex]);
}

newIndex++;
}
}
values.resize(newIndex);

Спасибо!

1

c++c++11 erase-remove-idiom move-semantics vector

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

#include <algorithm>    // find, remove_if
#include <iostream>
#include <vector>

template<class T>
using M = std::vector<std::vector<T>>; // matrix

template<class T>
std::ostream& operator<<(std::ostream& os, M<T> const& m)
{
for (auto const& row : m) {
for (auto const& elem : row)
os << elem << " ";
os << "\n";
}
return os;
}

template<class T, class IdxIt>
void erase_rows(M<T>& m, IdxIt first, IdxIt last)
{
m.erase(
std::remove_if(
begin(m), end(m), [&](auto& row) {
auto const row_idx = &row - &m[0];
return std::find(first, last, row_idx) != last;
}),
end(m)
);
}

int main()
{
auto m = M<int> { { 0, 1, 2, 3 }, { 3, 4, 5, 6 }, { 6, 7, 8, 9 }, { 1, 0, 1, 0 } };
std::cout << m << "\n";

auto drop = { 1, 3 };
erase_rows(m, begin(drop), end(drop));

std::cout << m << "\n";
}

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

Заметка: потому что с C ++ 11 и далее, std::vector имеет семантику перемещения, перемешивая ряды в вашем std::vector<std::vector<T>> делается с помощью простых манипуляций с указателями, независимо от вашего типа T (было бы совсем иначе, если вы хотите колонка-удаление, хотя!).

2