C++ - 如何从STL容器有效的条件删除元素？

考虑下面的代码，C++ - 如何从STL容器有效的条件删除元素？

struct Student 
{ 
int score; 
} 

queue<Student> stdQueue;

我想从列表中删除的学生，如果学生的成绩是低于前一个。如何做到这一点高效？

例如

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

获取

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

来源

2011-05-19 q0987

不可能只有一个std ::队列。我怀疑这是作业吗？ – 2011-05-19 20:15:26

@尼尔：我相信这可能只有一个队列。看到我更新的答案。 – 2011-05-19 20:26:44

队列有意限制访问除了末尾的元素之外的每个元素。显然，你不需要这个限制。在这种情况下，队列不适合你。你很可能想要一个双簧管。 – 2011-05-19 21:31:05

你可以写一个自定义的断言和使用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; 
};

正如尼尔指出的，这是不可能的std::queue。然而，它将使用如deque，list,set或vector（任何具有begin()和end()）的序列。

如果你想用一个queue做到这一点，像这样做：

从队列中取出第一个元素（使用pop）。
将分数与队列中新的第一个元素进行比较（使用front访问第一个元素）。
如果得分较高，请将元素再次插入后面（使用push），否则将其丢弃。
再次从1开始，直到您再次获得前面的第一个元素。

要确保你不处理任何元素两次，你可以在一个循环，计数到队列的原始尺寸做到这一点。

来源

2011-05-19 20:14:54

队列是适配器 – 2011-05-19 20:18:15

@尼尔：对，我刚刚意识到我误解了这个问题。这是不可能的一个队列。 – 2011-05-19 20:19:36

如果容器被分类，大概？ – 2011-05-19 20:26:25

队列不是这种类型的东西的正确对象。您应该使用优先级队列或自定义队列来封装链接列表，以便您可以执行此类操作。 STL的队列实现要求您只访问前面和后面的元素，并且访问任何其他元素需要在队列中所需的所需元素之前移除最前面元素和元素之间的任何对象。因此，将一堆临时对象拉出来，然后再将它们推回去，以便比较对象并查看哪些对象应该被移除，会有相当大的麻烦。

另一方面，优先级队列已经内部排序，所以前端和后端对象可能是队列中最大和最小的对象，反之亦然。所有其他对象之间也将被排序。因此，当您将元素从队列的前面弹出时，它们将以递增或递减的顺序出现，具体取决于您已将优先级队列初始化的比较函数。

您可以阅读使用优先级队列here at cplusplus.com。

来源

2011-05-19 20:17:18 Jason

我不认为优先队列在这里会有所帮助：任务不是取出得分最低的元素。任务是按给定的顺序比较adjactent元素的分数。 – Lambdageek 2011-05-19 20:29:02

我明白了你的观点，但是OP的问题似乎并没有表明学生的顺序是否是任意的？如果顺序是任意的（即，没有什么能确定*为什么*一个学生先于另一个学生，就像一个名字等......换句话说，这就是排序出来的方式，下次可能会有所不同），那么为什么不使用容器来自动排序学生呢？ – Jason 2011-05-19 20:32:45

我认为该算法是类似以下内容：

获取队列的当前大小，称之为N.
弹出1个元素，把它上一个
推上一个
重复N-1次
1. 流行元素，称之为Cur
2. 如果Cur> = Prev，推动Cur
3. 套装prev =姜黄素

基本上通过整个队列旋转，但只有推回，与前述一个媲美的元素。

来源

2011-05-19 20:33:27 Lambdageek

C++ - 如何从STL容器有效的条件删除元素？

回答

相关问题