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

我使用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();
}
}
217011 次浏览
小开

是的-有点队列类的错误特征，恕我直言。这就是我所做的:

#include <queue>
using namespace std;;


int main() {
queue <int> q1;
// stuff
q1 = queue<int>();
}
小开
最佳答案

清除标准容器的一个常用习语是交换容器的空版本:

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

它也是清除某些容器内内存的唯一方法(std::vector)

小开
主题的作者询问如何“有效地”清除队列，所以我假设他想要比线性O(队列大小)更好的复杂性。大卫·罗德里格斯， 另一次提供的方法具有相同的复杂度: 根据STL引用，operator =的复杂度为O(队列大小)。 恕我直言，这是因为队列的每个元素都是单独保留的，它不像在vector中那样分配在一个大的内存块中。因此，为了清除所有内存，我们必须分别删除每个元素。所以清除std::queue最直接的方法是一行:

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

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

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

也许你的a实现也允许你的Queue对象(这里是JobQueue)继承std::queue<Job>，而不是将Queue作为成员变量。这样你就可以在你的成员函数中直接访问c.clear()。

小开

我宁愿不依赖swap()或将队列设置为新创建的队列对象，因为队列元素没有正确地销毁。调用__abc1调用各自元素对象的析构函数。这在<int>队列中可能不是问题，但可能会对包含对象的队列产生副作用。

因此，如果你想防止可能的副作用，带__abc0的循环似乎是最有效的解决方案，至少对于包含对象的队列来说是这样。

小开

使用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
小开

显然，有两种最明显的方法来清除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;
}
小开

在c++ 11中，你可以通过这样做来清除队列:

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

假设你的m_Queue包含整数:

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

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

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

通过这种方式，你将一个空队列与你的m_Queue交换，因此m_Queue变成空队列。

小开

我这样做(使用c++ 14):

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

如果您有一个不平凡的队列类型，并且不想为其构建别名/typedef，则这种方法非常有用。不过，我总是确保对这种用法留下评论，向不知情的/维护程序员解释这并不疯狂，并代替了实际的clear()方法。

小开

另一种选择是使用一个简单的hack来获取底层容器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';
}

提交答案