11

要素を効率的に前面に移動できる std::list のような std コンテナーを探しています。

a-b-c-d-e

"b" を前に移動:

a-c-d-e-b

std コンテナにはそのような機能はありません。そのため、 remove と push_front 関数を組み合わせる必要があると思いますが、より良いアイデアを見つけることができる人はいますか?

少し早いですがお礼を。

4

2 に答える 2

17

では、線形の複雑さを持つ をstd::vector使用できますstd::rotate

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

std::vector<int> v = { 0, 1, 2, 3, 4 };

int main()
{
   std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ",")); 
   std::cout << "\n";

   // swap ranges [1, 2) and [2, 5)
   auto it = std::next(v.begin(), 1); // O(1)
   auto rb = std::next(it);
   auto re = v.end();
   std::rotate(it, rb, re); // O(N)

   std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ","));   
   std::cout << "\n";
}

では、（イテレータを指定すると）一定の複雑さを持つstd::listメンバー関数を使用できますsplice

#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>

std::list<int> v = { 0, 1, 2, 3, 4 };

int main()
{
   std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ",")); 
   std::cout << "\n";

   auto it = std::next(v.begin(), 1); // O(N)
   auto rb = std::next(it);
   auto re = v.end();   
   v.splice(it, v, rb, re); // O(1)

   std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ","));
   std::cout << "\n";   
}

注: 最後の要素はback、STL コンテナーでは慣習的に として示され、最初の要素は として示されfrontます。の場合std::vector、特定の要素へのイテレータの取得は一定時間であり、スワッピングは線形時間です。の場合std::list、イテレータの取得は線形時間ですが、同じリストへのスプライシングは定数時間です。ただし、 Stroustrup によるこのベンチマークが示すように、vector のはるかに優れたメモリ キャッシュ動作も重要です。

更新:いくつかのコメンターは、単純に要素を交換することに言及しました:これは、に変換する場合にのみ適用さa-b-c-d-eれa-e-c-d-bます。その場合は、std::iter_swapお好きな容器でお使いください。を に変換するにはa-b-c-d-e、またはa-c-d-e-bを使用します。std::rotatelist::splice

于 2013-01-29T09:51:41.777 に答える
15

他の要素の順序を維持する必要がない場合、最も簡単な解決策は、必要な要素をコンテナー内の最初の要素と交換することです。これは、すべてのコンテナで効率的です。

それ以外の場合は、使用できる操作をstd::list提供します。splice次のようなものだと思います：

void
moveToFront( 
    std::list<MyType>& list,
    std::list<MyType>::iterator element )
{
    if ( element != list.begin() ) {
        list.splice( list.begin(), list, element, std::next( element ) );
    }
}

これは、2、3 のポインター操作だけで終わり、 コピーはありません。一方、std::list一般的には非常に遅くなる可能性があります (局所性が低いため)。を使用して単純な実装に対して非常に慎重に測定しstd::vector、それが世界的に勝利したことを確認します. ここですべてのコピーを削除しても、前面に移動したい要素を見つけるために反復するのに 10 倍のコストがかかる場合、うまくいかない可能性があります。(これの多くMyTypeは、コピーのコストとサイズによって異なります。sizeof(MyType)ページのサイズに近い場合、またはアクセスMyTypeが間接的に割り当てられた多くのオブジェクトにアクセスすることになる場合、局所性の引数は保持されません。)

明らかな/std::vectorではなく、eraseinsert

void
moveToFront( 
    std::vector<MyType>& list,
    std::vector<MyType>::iterator element )
{
    MyType tmp( *element );
    std::copy_backwards( list.begin(), std::prev( element ), element );
    *list.begin() = tmp;
}

これにより、 （後続の要素をすべてコピーする）パターン（erase後続の要素insertもすべてコピーします。これは、最初に挿入しているため、すべての要素を意味します）よりもコピーが少なくなります。

于 2013-01-29T10:30:58.733 に答える