c++ - 使用 STL 队列的循环队列？

Question

我已经在互联网上搜索了一段时间，但似乎无法找到答案。
我打算使用 STL::queue 进行一些模拟。我想知道是否可以使用 STL::queue 创建一个循环队列？据我所知， STL::queue 是线性的，默认不是循环的？
如果这是可能的，有没有人有任何我可以引用的实现引用？
谢谢。

Answer 1

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

#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