2

我有std::list例如。带整数：9 10 8 25 70 75 30 14 80

我想在元素10之后移动所有元素，some_position_number例如。= 5. 移动对象的初始顺序很重要，必须与移动后的初始顺序相同。

换句话说，最后需要接收它们之后的some_position_number元素falsetrue

就像第一个例子一样：10 25 70 75 30 9 * 8 * 14 80

第二个首字母：9 3 8 25 70 75 30 14 80 第二个结果：10 25 70 75 30 9 * 3 * 8 14 80

第三个首字母：25 70 75 30 14 9 3 8 80 第三个结果：（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的以避免不必要的对象创建和擦除？std::list因为在真正的应用程序中， , 但对象没有整数。也许 std::splice？以某种方式选择需要移动的对象，而不是找到新位置并将每个元素 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）无效。
  • 我们将要移动的元素拼接到一个临时列表中。虽然这需要第二个列表，但它仍然不涉及元素的副本——我们只是将它们移动到其他地方以方便记账。
  • 保留不满足谓词的元素的计数 - 这让我们在移动时找出插入点，检查要移动的元素。
于 2012-05-20T21:44:25.030 回答