如何有效地清除 std::queue ？

Question

我正在使用 std::queue 来实现 JobQueue 类。 （基本上这个类以先进先出的方式处理每个作业）。 在一种情况下，我想一次性清除队列（从队列中删除所有作业）。 我在 std::queue 类中没有看到任何明确的方法可用。

如何有效地实现 JobQueue 类的clear方法？

我有一个简单的循环弹出解决方案，但我正在寻找更好的方法。

//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

在 C++11 中，您可以通过执行以下操作来清除队列：

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

Answer 4

该主题的作者询问如何“有效”地清除队列，因此我假设他想要比线性O（队列大小）更好的复杂性。 由 David Rodriguez、 提供的方法anon 具有相同的复杂性：
根据 STL 参考，operator = 的复杂度为 O(queue size)。
恕我直言，这是因为队列的每个元素都是单独保留的，并且它没有像向量一样分配在一个大内存块中。 因此，要清除所有内存，我们必须分别删除每个元素。 因此，清除 std::queue 的最直接方法是一行：

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

Answer 5

显然，有两种最明显的方法可以清除 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 6

您可以创建一个继承自队列的类并直接清除底层容器。 这是非常有效的。

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

也许您的实现还允许您的 Queue 对象（此处为 JobQueue）继承 std::queue而不是将队列作为成员变量。 这样您就可以在成员函数中直接访问c.clear()。

Answer 7

假设您的 m_Queue 包含整数：

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

否则，如果它包含指向 Job 对象的指针，则：

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

这样您就可以将空队列与您的 m_Queue 交换，因此 m_Queue 变空。

Answer 8

我这样做（使用 C++14）：

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

如果您有一个不平凡的队列类型，并且不想为其构建别名/typedef，则这种方法很有用。 不过，我总是确保围绕此用法留下评论，以向毫无戒心的/维护程序员解释这并不疯狂，并且是代替实际的 clear() 方法完成的。

Answer 9

我不想依赖 swap() 或将队列设置为新创建的队列对象，因为队列元素没有正确销毁。 调用 pop() 会调用相应元素对象的析构函数。 这在 队列中可能不是问题，但很可能会对包含对象的队列产生副作用。

因此，如果您想防止可能的副作用，则使用 while(!queue.empty())queue.pop(); 的循环似乎是最有效的解决方案，至少对于包含对象的队列而言是如此。

Answer 10

使用 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 11

另一种选择是使用简单的 hack 来获取底层容器 std::queue::c 并对其调用 clear 。 根据标准，该成员必须存在于 std::queue 中，但不幸的是 受保护。 这里的黑客取自这个答案。

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

Answer 12

交换并不比“=”更有效。 。

template <class T> void swap (T& a, T& b)
{
  T c(std::move(a)); a=std::move(b); b=std::move(c);
}

交换只需使用 std::move 即可。 但对于空队列，std::move 是没有用的。

我的队列=空队列； 或 my_queue = std::move(empty_queue);