c++ - 队列算法

Question

我正在尝试制作一个基于链表的队列以进行快速操作，现在这就是我所拥有的:

template< typename T, 
          template< typename > class Allocator = default_allocator
>
class fast_queue
 {
 public:
  typedef T element_type;
  typedef T* element_ptr;

 private:
  typedef struct e_node
  {
   element_type val;
   e_node * next;
  }node_type;
  typedef node_type * node_ptr;
  node_ptr parent;
  node_ptr child;
  int      m_size;
  typedef Allocator< node_type > allocator_type;

 public:
  fast_queue()
   : parent( 0 )
   , child( 0 )
   , m_size( 0 )
  {
  }

  ~fast_queue() {
   this->clear();
  }

  void push(element_type& i)
  {
   node_ptr n = allocator_type::alloc();
   n->val = i;
   n->next = (node_ptr)0;
   if(child) {
    child->next = n;
   } else {
    parent = n;
   }
   child = n;
   m_size++;
  }

  element_type pop()
  {
   element_type ret = parent->val;
   node_ptr p = parent;
   parent = parent->next;
   m_size--;
   allocator_type::dealloc(p);
   return ret;
  }

  inline int size() const 
  {
   return m_size;
  }

  inline bool empty() const
  {
   return (m_size == 0);
  }

  void clear() 
  {
   while(!empty()) {
    pop();
   }
   child = 0;
  }
 };

非常简单，现在我遇到的问题是 clear() 函数。似乎花费了太多时间来重新分配队列中的所有节点(7 秒)。所以问题是，什么可能是更好的算法？我试图理解 MSVC 对 std::deque 的实现，但代码太庞大了，我无法理解。

编辑:队列应该是通用的，允许任意类型的数据排队。这是我的测试代码(Windows)

DWORD time1 = timeGetTime();
fast_queue<int> queue;

for(int i = 0; i < 100000; i++) {
    queue.push(i);
}
queue.clear();
cout << "Test time: " << (int)(timeGetTime() - time1) << " milliseconds" << endl;

Answer 1

您正在构建一个链表。双端队列实现在每个分配中存储许多元素。但是，您可以为每个元素单独分配和解除分配。这就是为什么您的队列如此缓慢的原因。

除此之外，标准的队列接口(interface)表示您应该采用完整的分配器类型，而不是模板，尽管满足标准分配器要求的现实是无论如何它都必须是模板。