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

166

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

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

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

//Clears the job queue
void JobQueue ::clearJobs()
 {
  // I want to avoid pop in a loop
    while (!m_Queue.empty())
    {
        m_Queue.pop();
    }
}
Aj.
источник
3
Примечание dequeподдерживает ясно
бобобо

Ответы:

257

Распространенная идиома для очистки стандартных контейнеров - это замена пустой версией контейнера:

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

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

Дэвид Родригес - дрибеи
источник
41
А еще лучше std::queue<int>().swap(q). С идиом copy и swap все это должно быть эквивалентно q = std::queue<int>().
Александр С.
12
Хотя std::queue<int>().swap(q)это эквивалентно приведенному выше коду, оно q = std::queue<int>()не обязательно должно быть эквивалентным. Поскольку при назначении выделенной памяти нет передачи прав собственности, некоторые контейнеры (например, вектор) могут просто вызывать деструкторы ранее удерживаемых элементов и устанавливать размер (или эквивалентную операцию с сохраненными указателями) без фактического освобождения памяти.
Дэвид Родригес - dribeas
6
queueне имеет swap(other)метода, поэтому queue<int>().swap(q)не компилируется. Я думаю, что вы должны использовать общий swap(a, b).
Дастин Босвелл
3
@ ThorbjørnLindeijer: В C ++ 03 вы правы, в C ++ 11 очереди имеют подкачку как функцию-член, и, кроме того, существует перегрузка свободной функции, которая поменяет две очереди одного типа.
Дэвид Родригес - dribeas
10
@ ThorbjørnLindeijer: с точки зрения пользователей исходной очереди, эти элементы не существуют. Вы правы в том, что они будут уничтожены один за другим, а стоимость будет линейной, но они не доступны никому, кроме локальной функции. В многопоточной среде вы должны заблокировать, поменять временную очередь на прежнюю, разблокировать (для обеспечения одновременного доступа) и позволить обмененной очереди умереть. Таким образом, вы можете переместить стоимость уничтожения за пределы критической секции.
Дэвид Родригес - dribeas
46

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

#include <queue>
using namespace std;;

int main() {
    queue <int> q1;
    // stuff
    q1 = queue<int>();  
}
Марк Рэнсом
источник
8
@Naszta Пожалуйста, опишите, как swapэто «более эффективно»
Бобобобо
@bobobobo:q1.swap(queue<int>());
Наста
12
q1=queue<int>();и короче, и четче (вы на самом деле не пытаетесь .swap, вы пытаетесь .clear).
Бобобобо
28
С новым C ++ q1 = {}достаточно
Николай Богдюк
2
Синтаксис @Ari (2) в list_initialization и (10) в operator_assignment . По умолчанию queue<T>конструктора соответствует пустому списку аргументов {}и неявно, так это называется, а затем q1.operator=(queue<T>&&)уничтожает вновь созданныйqueue
Николай Bogdiuk
26

Автор темы спросил, как очистить очередь «эффективно», поэтому я предполагаю, что он хочет лучшей сложности, чем линейный O (размер очереди) . Методы , обслуживаемый Дэвид Родригес , Anon имеют одинаковую сложность: в соответствии со справочной STL, operator =имеет сложность O (очередь размера) . ИМХО, это потому, что каждый элемент очереди зарезервирован отдельно и не размещается в одном большом блоке памяти, как в векторе. Таким образом, чтобы очистить всю память, мы должны удалить каждый элемент отдельно. Таким образом, самый простой способ очистить std::queueэто одна строка:

while(!Q.empty()) Q.pop();
Janis
источник
5
Вы не можете просто посмотреть на сложность операции, если вы работаете с реальными данными. Я бы взял O(n^2)алгоритм над O(n)алгоритмом, если бы константы линейной операции делали его медленнее, чем квадратичный для всех n < 2^64, если у меня не было веской причины полагать, что мне пришлось искать в адресном пространстве IPv6 или какой-то другой конкретной проблеме. Производительность на самом деле важнее для меня, чем производительность на пределе.
Дэвид Стоун
2
Это лучший ответ, чем принятый ответ, потому что внутренняя очередь делает это в любом случае при уничтожении. Таким образом, принятый ответ - O (n) плюс он делает дополнительные распределения и инициализации для совершенно новой очереди.
Шиталь Шах
Помните, что O (n) означает меньше или равно n сложности. Так что, да, в некоторых случаях, например в очереди <vector <int >>, потребуется уничтожить каждый элемент 1 на 1, что в любом случае будет медленным, но в очереди <int> память фактически выделяется в одном большом блоке, и поэтому ему не нужно уничтожать внутренние элементы, и поэтому деструктор очереди может использовать одну эффективную операцию free (), которая почти наверняка займет меньше O (n) времени.
Бенджамин
15

Очевидно, есть два наиболее очевидных способа очистки 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;
}
Тим
источник
8

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

std::queue<int> queue;
// ...
queue = {};
kolage
источник
4

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

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

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

typ1232
источник
9
Контейнеры STL не предназначены для наследования. В этом случае вы, вероятно, в порядке, потому что вы не добавляете никаких дополнительных переменных-членов, но в целом это не очень хорошая вещь.
bstamour
2

Предполагая, что ваш m_Queueсодержит целые числа:

std::queue<int>().swap(m_Queue)

В противном случае, если он содержит, например, указатели на Jobобъекты, то:

std::queue<Job*>().swap(m_Queue)

Таким образом, вы меняете пустую очередь на свою m_Queue, таким образом, m_Queueстановитесь пустыми.

Даниэль Ласло Ковач
источник
1

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

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

Marste
источник
3
swap()или присваивание вызывает деструктор в теперь не существующей очереди, который вызывает деструкторы всех объектов в очереди. Теперь, если в вашей очереди есть объекты, которые на самом деле являются указателями, это другая проблема - но простое pop()тоже вам там не поможет.
Jhfrontz
Почему к сожалению? Это элегантно и просто.
OS2
1

Я делаю это (используя C ++ 14):

std::queue<int> myqueue;
myqueue = decltype(myqueue){};

Этот способ полезен, если у вас нетривиальный тип очереди, для которого вы не хотите создавать псевдоним / typedef. Тем не менее, я всегда оставляю комментарий об этом использовании, чтобы объяснить ничего не подозревающим программистам, что это не сумасшествие и сделано вместо реального clear()метода.

void.pointer
источник
Почему вы явно указываете тип в операторе присваивания? Я предполагаю, что это myqueue = { };будет работать просто отлично.
Джоэл Боденманн
0

Использование 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
Ронни
источник
Если вы решите очистить очередь, удалив ее, это нормально, но вопрос не в этом, и я не понимаю, почему поступает
unique_ptr
0

Другой вариант - использовать простой хак, чтобы получить базовый контейнер std::queue::cи вызвать clearего. Этот участник должен присутствовать в std::queueсоответствии со стандартом, но к сожалению protected. Взлом здесь был взят из этого ответа .

#include <queue>

template<class ADAPTER>
typename ADAPTER::container_type& get_container(ADAPTER& a)
{
    struct hack : ADAPTER
    {
        static typename ADAPTER::container_type& get(ADAPTER& a)
        {
            return a .* &hack::c;
        }
    };
    return hack::get(a);
}

template<typename T, typename C>
void clear(std::queue<T,C>& q)
{
    get_container(q).clear();
}

#include <iostream>
int main()
{
    std::queue<int> q;
    q.push(3);
    q.push(5);
    std::cout << q.size() << '\n';
    clear(q);
    std::cout << q.size() << '\n';
}
Руслан
источник