C ++ - How to remove an element with such a condition effective from the STL container?

Question

Given the following code,

struct Student { int score; } queue<Student> stdQueue; 

I want to remove students from the list if the student’s grade is less than the previous one. How to make it effective?

for instance

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

Get

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

Answer 1

You can write your own predicate and use remove_if . A predicate can be a functor that always stores the score previous Student . Something like that:

 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; }; 

As Neil points out, this is not possible with std::queue . However, it will work with sequences like deque , list , set or vector (all that have begin() and end() ).

If you want to do this using queue , do the following:

• Remove the first item from the queue (using pop ).
• Compare the score with the new first item in the queue (access the first item with front ).
• If the score is greater, insert the element again on the back (using push ), otherwise discard it.
• Again from 1. until you see the first item on the front panel again.

To make sure that you are not processing any element twice, you can do this in a loop that takes into account the initial size of the queue.

Answer 2

A queue is not the right object for this type of thing. You must use either a priority queue or a separate queue wrapped in a linked list that will allow you to perform such an operation. Implementing the STL queue requires that you have access only to the front and back elements, and accessing any other elements requires removing any objects between the front-most element and the element right in front of the desired element that you want from the queue. Thus, it would be quite a hassle to pull out a bunch of temporary objects and then push them back to compare the objects and see which ones need to be removed.

The priority queue, on the other hand, is already sorted internally, so the front and rear objects will be either the largest or smallest objects in the queue, or vice versa. All other intermediate objects will also be sorted. Since you drop items from the front of the queue, they will depart in ascending or decreasing order, depending on which comparison function you have initialized with the priority queue.

You can read information about using the priority queue here at cplusplus.com .

Answer 3

I think the algorithm looks something like this:

• Get the current queue size, name it N.
• pop 1 element, name it Prev
• click prev
• repeat N-1 times
  • pop element name it Cur
  • if Cur> = Prev, press Cur
  • set Prev = Cur

Basically rotate throughout the queue, but only repel elements that compare favorably with the previous one.