2

私はstd::list例えば持っています。int 付き:9 10 8 25 70 75 30 14 80

10すべての要素を要素の後よりも少なく移動したいsome_position_number。= 5. 移動されたオブジェクトの最初の順序は重要であり、移動後の最初と同じでなければなりません。

言い換えれば、最後にsome_position_number要素を受け取る必要がfalseあり、それらの後にtrue

最初の例のように: 10 25 70 75 30 9 * 8 * 14 80

2 番目のイニシャル: 9 3 8 25 70 75 30 14 80 2 番目の結果: 10 25 70 75 30 9 * 3 * 8 14 80

3 番目のイニシャル: 25 70 75 30 14 9 3 8 80 3 番目の結果: 25 70 75 30 14 9 3 8 80(最初は既に 5 です)

4 初期: 3 4 1 2 3 9 3 8 80 4 結果: 9 3 8 80 3 4 1 2 3(このようなもの) ここでsome_position_numberは、しきい値として使用するか80 3 4 1 2 3 9 3 8、受け入れる必要があるようですが、end() と無限ループをチェックする必要があるようです?

list不必要なオブジェクトの作成と消去を避けるために、おそらく追加なしで、この最も効果的な方法を行うにはどうすればよいでしょうか? 実際のアプリでは int はありませんstd::listが、オブジェクトです。多分std::スプライス？新しい位置を見つけて std::splice ですべての要素を移動するよりも、移動する必要があるオブジェクトを何らかの方法で選択します。

4

1 に答える 1

3

それは醜いですが、機能し、すべてのイテレータの無効化状況を適切に処理すると信じています:

#include <iostream>
#include <list>

using namespace std;

list<int> l;

// prototypes for various helpers of no consequence to the question
void  init();
bool my_pred( list<int>::value_type val);
void dump_list( list<int> const& l);


typedef list<int>::iterator iter_t;

int main() 
{
    init();
    dump_list(l);

    // we want to remove elements that meet the predicate until
    // there are `some_position_number` elements that didn't meet 
    // the predicate

    int some_position_number = 5;
    list<int> tmp_list;

    iter_t i = l.begin();
    for (int count = 0; count < some_position_number && i != l.end(); ) {
        iter_t tmp(i);
        ++i;
        if (my_pred(*tmp)) {
            tmp_list.splice( tmp_list.end(), l, tmp); // remove an element
        }
        else {
            ++count;
        }
    }

    // now i points at the position we want to insert the elements we removed:

    l.splice( i, tmp_list);

    dump_list(l);
}




bool my_pred( list<int>::value_type val)
{
    return val < 10;
}

void  init()
{
    l.push_back(9);
    l.push_back(10);
    l.push_back(8);
    l.push_back(25);
    l.push_back(70);
    l.push_back(75);
    l.push_back(30);
    l.push_back(14);
    l.push_back(80);
}

void dump_list( list<int> const& l)
{
    for (list<int>::const_iterator i = l.begin(); i != l.end(); ++i) {
        cout << *i << " ";
    }

    cout << endl;
}

キーは次のとおりです。

  • i移動される可能性のある要素の範囲をウォークするために使用される反復子は、 を呼び出す前にコピーしてインクリメントする必要がありますsplice()。がsplice()呼び出されると、元のi(現在のtmp) は無効になります。
  • 移動したい要素を一時リストにスプライスします。これには 2 番目のリストが必要ですが、それでも要素のコピーは必要ありません。簿記を簡単にするために要素を別の場所に移動しているだけです。
  • 述語を満たさなかった要素の数を保持します。これにより、移動する要素をチェックしながら移動するときに、挿入ポイントを把握できます。
于 2012-05-20T21:44:25.030 に答える