c++ 循环队列是否使用STL队列?

kgsdhlau  于 2022-11-19  发布在  其他
关注(0)|答案(3)|浏览(201)

我已经在网上搜索了一段时间,但似乎找不到一个答案。
我打算用stl::queue做一些模拟,不知道stl::queue能不能做一个循环队列,据我所知stl::queue默认是线性的,不是循环的。
如果可以的话,有没有人有什么实施参考资料可以参考?

  • 谢谢-谢谢
6gpjuf90

6gpjuf901#

std::deque被非常仔细地定义为线性队列,它的设计实际上并不适合循环队列。
特别是,它将队列分成许多大小相等的块,因此,如果队列是合理平衡的(即,平均而言,数据被消耗的速度与数据被产生的速度一样快),那么通常会有块被丢弃并准备重用,因此,您可以长时间使用一个块,而堆碎片最少。
为了实现这一点,双端队列(至少在正常情况下)使用两级存储机制。也就是说,它有一个可扩展的指针数组,每个指针指向一个包含实际数据的大小相等的块。
然而,对于循环缓冲区来说,这是没有意义的,也是不必要的。对于循环缓冲区,通常在创建它时分配一个内存块,并继续使用同一个内存块,直到销毁它。在这种情况下,双端队列使用的两级存储只是为每次访问增加了一个额外的间接层,而没有完成任何有用的工作。
对于一个循环缓冲区,你可以使用一个单一的、平坦的内存块来保存你的数据,并且只在那个内存块中创建/销毁对象。

#ifndef CBUFFER_H_INC
#define CBUFFER_H_INC

template <class T>
class circular_buffer {
    T *data;
    unsigned read_pos;
    unsigned write_pos;
    unsigned in_use;
    const unsigned capacity;
public:
    circular_buffer(unsigned size) :
        data((T *)operator new(size * sizeof(T))),
        read_pos(0),
        write_pos(0),
        in_use(0),
        capacity(size)
    {}

    void push(T const &t) {
        // ensure there's room in buffer:
        if (in_use == capacity) 
            pop();

        // construct copy of object in-place into buffer
        new(&data[write_pos++]) T(t);
        // keep pointer in bounds.
        write_pos %= capacity;
        ++in_use;
    }

    // return oldest object in queue:
    T front() {
        return data[read_pos];
    }

    // remove oldest object from queue:
    void pop() { 
        // destroy the object:
        data[read_pos++].~T();

        // keep pointer in bounds.
        read_pos %= capacity;
        --in_use;
    }
  
~circular_buffer() {
    // first destroy any content
    while (in_use != 0)
        pop();

    // then release the buffer.
    operator delete(data); 
}

};

#endif
anauzrmj

anauzrmj2#

如果您可以使用The Boost Libraries,则已经存在一个boost::circular_buffer类模板,该模板实现了front()back()push_back()pop_front()成员函数,因此可以用作std::queue容器适配器的 * 底层容器 *:

#include <queue>
#include <boost/circular_buffer.hpp>
#include <cassert>

template<typename T>
using Queue = std::queue<T, boost::circular_buffer<T>>;

auto main() -> int {
   Queue<int> q(boost::circular_buffer<int>(3)); // capacity of the queue is 3

   q.push(0);
   q.push(1);
   q.push(2);
   assert(q.front() == 0);
   assert(q.back() == 2);

   q.push(3);
   assert(q.front() == 1);
   assert(q.back() == 3);

   q.pop();
   assert(q.front() == 2); 
   assert(q.back() == 3);
}
j8ag8udp

j8ag8udp3#

您可以在https://github.com/torrentg/cqueue找到循环队列的C++20实现

  • 遵守STL容器标准(分配器、迭代器等)
  • 不需要固定容量
  • 仅标题

注:我是项目维护者。

相关问题