1

配列を表すベクトルのベクトルがあります。行を効率的に削除したい、つまり最小限の複雑さと割り当てで行を削除したい

次のように、移動セマンティクスを使用して、削除されていない行のみをコピーして、ベクトルの新しいベクトルを構築することを考えました。

    //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);

ありがとう！

4

1 に答える 1

2

これは、通常のerase-remove イディオム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の削除が必要な場合はまったく異なります!)。

于 2014-04-11T20:55:10.717 に答える