Как эффективно очистить std :: queue?

Question

Я использую std :: queue для реализации класса JobQueue. (В основном этот класс обрабатывает каждое задание в режиме FIFO). В одном сценарии я хочу очистить очередь одним выстрелом (удалить все задания из очереди). Я не вижу никакого ясного метода, доступного в классе std :: queue.

Как эффективно реализовать прозрачный метод для класса JobQueue?

У меня есть одно простое решение, возникающее в цикле, но я ищу лучшие способы.

//Clears the job queue 
void JobQueue ::clearJobs() 
{ 
    // I want to avoid pop in a loop 
    while (!m_Queue.empty()) 
    { 
     m_Queue.pop(); 
    } 
} 

Answer 1

Общий идиома для очистки стандартных контейнеров является перекачка с пустой версии контейнера:

void clear(std::queue<int> &q) 
{ 
    std::queue<int> empty; 
    std::swap(q, empty); 
} 

Это также единственный способ на самом деле очистки памяти проводится внутри некоторые контейнеры (std :: vector)

Answer 2

Да - небольшая неисправность класса очереди, ИМХО. Это то, что я делаю:

#include <queue> 
using namespace std;; 

int main() { 
    queue <int> q1; 
    // stuff 
    q1 = queue<int>(); 
} 

Answer 3

«David Rodriguez», 'anon' Автор темы спросил, как очистить очередь «эффективно», поэтому я предполагаю, что он хочет улучшить сложность, чем линейный O (размер очереди) , Методы, которые вы обслуживали, имеют одинаковую сложность: в соответствии со ссылкой stl, оператор = имеет сложность O (размер очереди). IMHO это потому, что каждый элемент очереди зарезервирован отдельно, и он не выделяется в одном большом блоке памяти, как в векторе. Чтобы очистить всю память, мы должны удалить каждый элемент отдельно. Таким образом, прямой путь, чтобы очистить stl::queue это одна строка:

while(!Q.empty()) Q.pop(); 

Answer 4

Вы можете создать класс, который наследуется из очереди и очистить основной контейнер непосредственно. Это очень эффективно.

template<class T> 
class queue_clearable : public std::queue<T> 
{ 
public: 
    void clear() 
    { 
     c.clear(); 
    } 
}; 

Может быть, ваша реализация позволяет вашей очереди объекта (здесь JobQueue) наследовать std::queue<Job> вместо того, чтобы очередь в качестве переменной-члена. Таким образом, у вас будет прямой доступ к c.clear() в ваших функциях-членах.

Answer 5

Я предпочел бы не полагаться на swap() или устанавливать очередь на вновь созданный объект очереди, потому что элементы очереди не были должным образом уничтожены. Вызов pop() вызывает деструктор для соответствующего элемента элемента. Это может быть не проблема в <int> очередях, но вполне может иметь побочные эффекты для очередей, содержащих объекты.

Поэтому петля с while(!queue.empty()) queue.pop(); представляется, к сожалению, наиболее эффективным решением, по крайней мере, для очередей, содержащих объекты, если вы хотите предотвратить возможные побочные эффекты.

Answer 6

Использование unique_ptr может быть в порядке.
Затем вы можете сбросить его, чтобы получить пустую очередь и освободить память первой очереди. Что касается сложности? Я не уверен, но думаю, что это O (1).

Возможный код:

typedef queue<int> quint; 

unique_ptr<quint> p(new quint); 

// ... 

p.reset(new quint); // the old queue has been destroyed and you start afresh with an empty queue 

Answer 7

По-видимому, существует два наиболее очевидных способов очистить std::queue: свапирования с пустым объектом и присвоение пустого объекта.

Я бы предложил использовать назначение, потому что он просто быстрее, читабельнее и недвусмысленно.

Я измерил производительность, используя следующий простой код, и я обнаружил, что замена в версии C++ 03 работает на 70-80% медленнее, чем назначение пустого объекта. Однако в C++ 11 нет никакой разницы в производительности. Во всяком случае, я бы пошел с заданием.

#include <algorithm> 
#include <ctime> 
#include <iostream> 
#include <queue> 
#include <vector> 

int main() 
{ 
    std::cout << "Started" << std::endl; 

    std::queue<int> q; 

    for (int i = 0; i < 10000; ++i) 
    { 
     q.push(i); 
    } 

    std::vector<std::queue<int> > queues(10000, q); 

    const std::clock_t begin = std::clock(); 

    for (std::vector<int>::size_type i = 0; i < queues.size(); ++i) 
    { 
     // OK in all versions 
     queues[i] = std::queue<int>(); 

     // OK since C++11 
     // std::queue<int>().swap(queues[i]); 

     // OK before C++11 but slow 
     // std::queue<int> empty; 
     // std::swap(empty, queues[i]); 
    } 

    const double elapsed = double(clock() - begin)/CLOCKS_PER_SEC; 

    std::cout << elapsed << std::endl; 

    return 0; 
} 

Answer 8

В C++ 11 вы можете очистить очередь, делая это:

std::queue<int> queue = {};