C++ -- 如何高效地从STL容器中删除满足条件的元素？

Question

考虑以下代码：

struct Student
{
 int score;
}

queue<Student> stdQueue;

如果学生的分数比上一个学生低，我希望将该学生从列表中移除。如何高效地实现？

例如：

S1(100) <= S2(55) <= S3(200) <= S4(4) <= S6(1000)

获取

S1 (100) <= S3(200) <= S6(1000)

- q0987

---

单个std::queue无法实现。我怀疑这是作业？ - user2100815

@Neil：我相信用一个队列是可能的。请看我的更新答案。 - Björn Pollex

队列有意地限制了对除两端元素以外的所有元素的访问。显然，您不希望这种限制。在这种情况下，队列不是适合您的正确数据结构。您最可能需要一个双端队列。 - Benjamin Lindley

如果学生的分数低于前一个学生的分数，我想从列表中删除这些学生。但是，如果前一个学生本身也要被删除，那么“前一个学生”是什么？例如，给定 3,1,2，那么 2 的“前一个学生”是什么？是 1，这样 2 就会保留，还是 3，这样 2 就会被删除？ - MSalters

Answer 1

您可以编写自定义谓词并使用remove_if。该谓词可以是一个函数对象，始终存储前一个Student的score。类似于这样：

class ScoreLessThanPrevious {
public:
    ScoreLessThanPrevious() 
     : isFirst(true),
       previousScore(0)
    {}

    bool operator()(const Student & s) {
        if (isFirst) {
            isFirst = false;
            return false;
        }
        else {
            boolean retval = s.score < previousScore;
            previousScore = s.score;
            return retval;
        }
    }
private:
    bool isFirst;
    int previousScore;
};

正如Neil所指出的那样，使用std::queue是不可能实现的。但是如果使用像deque、list、set或vector这样具有begin()和end()函数的序列就可以实现。

如果想要使用queue来实现，可以按照以下步骤进行：

1. 从队列中删除第一个元素（使用pop）。 2. 将分数与队列中新的第一个元素进行比较（使用front访问第一个元素）。 3. 如果分数较大，则再次将元素插入到队列末尾（使用push），否则将其丢弃。 4. 再次执行1-3步，直到第一个元素再次位于队列的最前面。

为确保不重复处理任何元素，可以在循环中计数至队列的原始大小。

- Björn Pollex

---

@Neil：没错，我刚才意识到我读错了问题。这个无法使用队列实现。 - Björn Pollex

如果容器已经排序，那么大概是这样的吧？ - user2100815

你能在 std::queue 的前面插入吗？我认为一旦你从前面弹出它，只能用 push() 将其放回到后面。 - Jason

@Jason：无论哪种方式都可以。你可以在一端删除，在另一端插入。其余部分是实现细节 ;) - Björn Pollex

你能在 std::queue 的前面插入一个元素吗？我认为不行。 - user2100815

我认为问题是关于操作队列本身的 - 显然，如果你可以引入局部变量（就像你的解决方案所需），你可以做任何事情。因此，我们最终得到了一个难以理解且可能非常缓慢的算法。我纯粹讨厌这些人为制造的问题。 - user2100815

Answer 2

队列不是处理这种类型事情的正确对象。你应该使用优先队列或自定义队列包装一个链表，以允许你执行此类操作。STL的队列实现要求你只能访问前面和后面的元素，访问任何其他元素都需要删除最前面的元素和所需元素之间的所有对象。因此，为了比较对象并查看应该删除哪些对象，需要大费周折地取出一堆临时对象，然后再将它们推回去。

另一方面，优先队列已经在内部排序，因此前面和后面的对象要么是队列中最大和最小的对象，要么反之。中间的所有其他对象也会被排序。因此，当你从队列的前面弹出元素时，它们会按照递增或递减的顺序出现，具体取决于你初始化优先队列时使用的比较函数。

你可以在这里阅读有关使用优先队列的更多信息。

- Jason

---

我认为优先队列在这里并没有帮助：任务不是要提取得分最低的元素。任务是按照给定的顺序比较相邻元素的分数。 - Lambdageek

我理解你的观点，但是原帖中的问题似乎没有表明学生的顺序是否是任意的...如果顺序是任意的（即没有真正确定为什么一个学生在另一个学生之前，比如姓名等），换句话说，这只是顺序出现的方式，下一次可能会有所不同，那么为什么不使用一个可以自动排序学生的容器呢？ - Jason

Answer 3

我认为算法大致如下：

1. 获取队列的当前大小，称其为N。
2. 弹出1个元素，称其为Prev
3. 将Prev推入队列
4. 重复N-1次
   1. 弹出元素，称其为Cur
   2. 如果Cur >= Prev，则将Cur推入队列
   3. 设置Prev = Cur

基本上是遍历整个队列，但只将与前一个元素比较有利的元素推回。

- Lambdageek