1

私は

vector<int> myVector;

そして、index削除するリストがあります：

vector<size_t> deleteIndex;

これらのインデックスを削除するには、どの戦略が最も効率的ですか?

実際には、効率的ではない解決策の 1 つとして次のようなものがあります。

//> sort deleteindex
auto deleted= 0;
for(auto i=0;i<deleteIndex.size();i++ {
   myVector.erase(myVector.begin()+deleteIndex[i]-deleted);
   deleted++;
}
4

2 に答える 2

1

ベクトルから要素を 1 つずつ消去するのは非常に非効率的です。これは、消去するたびに、すべての要素を 1 つ下にコピーしてから、1 つ小さいベクトルを再割り当てする必要があるためです。

代わりに、erase-remove イディオムを使用してください。このプロセスでは、後のアイテムを移動して以前のアイテムを置き換えることにより、アイテムを削除します (元の順序が維持されます)。アイテムが削除された後、単一の消去 (リストの最後) を実行して、n 個のアイテム (n は削除されたアイテムの数) だけ小さい新しいベクトルを再割り当てします。

サンプル実装:

template <class _FwdIt, class _FwdIt2>
_FwdIt remove_by_index(_FwdIt first, 
                       _FwdIt last,
                       _FwdIt2 sortedIndexFirst, 
                       _FwdIt2 sortedIndexLast)
{
  _FwdIt copyFrom = first;
  _FwdIt copyTo = first;
  _FwdIt2 currentIndex = sortedIndexFirst;

  size_t index = 0;
  for (; copyFrom != last; ++copyFrom, ++index)
  {
    if (currentIndex != sortedIndexLast &&
        index == *currentIndex)
    {
      // Should delete this item, so don't increment copyTo
      ++currentIndex;
      print("%d", *copyFrom);
    }
    else
    {
      // Copy the values if we're at different locations
      if (copyFrom != copyTo)
        *copyTo = *copyFrom;
      ++copyTo;
    }
  }
  return copyTo;
}

サンプル使用法:

#include <vector>
#include <algorithm>
#include <functional>

int main(int argc, char* argv[])
{
  std::vector<int> myVector;

  for (int i = 0; i < 10; ++i)
    myVector.push_back(i * 10);

  std::vector<size_t> deleteIndex;
  deleteIndex.push_back(3);
  deleteIndex.push_back(6);

  myVector.erase(
    remove_by_index(myVector.begin(), myVector.end(), deleteIndex.begin(), deleteIndex.end()), 
    myVector.end());

  for (std::vector<int>::iterator it = myVector.begin();
       it != myVector.end(); ++it)
  {
    printf("%d ", *it);
  }

  return 0;
}

要旨: https://gist.github.com/eleven41/5746079
ここでテスト: http://ideone.com/0qkDw5

于 2013-06-09T23:56:50.707 に答える
1

の並べ替えが許可されている場合はmyVector、削除するアイテムを繰り返し処理し、最後の要素と交換してポップオフすることで削除します。

順序を維持する必要がある場合は、deleteIndexコンテナーを並べ替え、単一の順序付きパスを実行して、他の要素を前方に移動して要素を削除します。

于 2013-06-09T23:43:50.110 に答える