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)

Answer 1

Вы можете написать собственный предикат и использовать remove_if.Предикат может быть функтором, который всегда хранит score предыдущего Student.Примерно так:

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 сделайте это следующим образом:

1. Удалите первый элемент из очереди (используя pop).
2. Сравните результат с новым первым элементом вочередь (доступ к первому элементу, используя front).
3. Если счет больше, вставьте элемент снова в конец (используя push), в противном случае отмените его.
4. Снова из1. пока у вас снова не появится первый элемент спереди.

Чтобы убедиться, что вы не обрабатываете ни один элемент дважды, вы можете сделать это в цикле, который подсчитывает исходный размер очереди.

Answer 2

Я думаю, что алгоритм выглядит примерно так:

1. Получите текущий размер очереди, назовите его N.
2. pop 1 element, назовите его Prev
3. push Prev
4. повторение N-1 раз
   1. элемент pop, назовите его Cur
   2. , если Cur> = Prev, нажмите Cur
   3. set Prev= Cur

В основном вращаются по всей очереди, но отталкивают только те элементы, которые выгодно отличаются от предыдущей.

Answer 3

Очередь не подходит для этого типа вещей. Вы должны использовать либо приоритетную очередь, либо пользовательскую очередь, заключающую в себе связанный список, который позволит вам выполнить такую ​​операцию. Реализация очереди STL требует, чтобы вы имели доступ только к передним и задним элементам, а доступ к любым другим элементам требует удаления любых объектов между самым передним элементом и элементом прямо перед желаемым элементом, который вы хотите из очереди. Так что было бы довольно хлопотно вытащить кучу временных объектов, а затем толкнуть их обратно, чтобы сравнить объекты и посмотреть, какие из них следует удалить.

Очередь приоритетов с другой стороны уже отсортирована внутри, поэтому передние и задние объекты будут либо самыми большими, либо самыми маленькими объектами в очереди, или наоборот. Все остальные промежуточные объекты также будут отсортированы. Поэтому, когда вы вытаскиваете элементы из передней части очереди, они будут появляться в возрастающем или убывающем порядке, в зависимости от того, с какой функцией сравнения вы инициализировали очередь с приоритетами.

Вы можете прочитать об использовании приоритетной очереди здесь, на cplusplus.com .