我已经在网上搜索了一段时间,但似乎找不到一个答案。我打算用stl::queue做一些模拟,不知道stl::queue能不能做一个循环队列,据我所知stl::queue默认是线性的,不是循环的。如果可以的话,有没有人有什么实施参考资料可以参考?
6gpjuf901#
std::deque被非常仔细地定义为线性队列,它的设计实际上并不适合循环队列。特别是,它将队列分成许多大小相等的块,因此,如果队列是合理平衡的(即,平均而言,数据被消耗的速度与数据被产生的速度一样快),那么通常会有块被丢弃并准备重用,因此,您可以长时间使用一个块,而堆碎片最少。为了实现这一点,双端队列(至少在正常情况下)使用两级存储机制。也就是说,它有一个可扩展的指针数组,每个指针指向一个包含实际数据的大小相等的块。然而,对于循环缓冲区来说,这是没有意义的,也是不必要的。对于循环缓冲区,通常在创建它时分配一个内存块,并继续使用同一个内存块,直到销毁它。在这种情况下,双端队列使用的两级存储只是为每次访问增加了一个额外的间接层,而没有完成任何有用的工作。对于一个循环缓冲区,你可以使用一个单一的、平坦的内存块来保存你的数据,并且只在那个内存块中创建/销毁对象。
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
anauzrmj2#
如果您可以使用The Boost Libraries,则已经存在一个boost::circular_buffer类模板,该模板实现了front()、back()、push_back()和pop_front()成员函数,因此可以用作std::queue容器适配器的 * 底层容器 *:
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); }
j8ag8udp3#
您可以在https://github.com/torrentg/cqueue找到循环队列的C++20实现
注:我是项目维护者。
3条答案
按热度按时间6gpjuf901#
std::deque
被非常仔细地定义为线性队列,它的设计实际上并不适合循环队列。特别是,它将队列分成许多大小相等的块,因此,如果队列是合理平衡的(即,平均而言,数据被消耗的速度与数据被产生的速度一样快),那么通常会有块被丢弃并准备重用,因此,您可以长时间使用一个块,而堆碎片最少。
为了实现这一点,双端队列(至少在正常情况下)使用两级存储机制。也就是说,它有一个可扩展的指针数组,每个指针指向一个包含实际数据的大小相等的块。
然而,对于循环缓冲区来说,这是没有意义的,也是不必要的。对于循环缓冲区,通常在创建它时分配一个内存块,并继续使用同一个内存块,直到销毁它。在这种情况下,双端队列使用的两级存储只是为每次访问增加了一个额外的间接层,而没有完成任何有用的工作。
对于一个循环缓冲区,你可以使用一个单一的、平坦的内存块来保存你的数据,并且只在那个内存块中创建/销毁对象。
anauzrmj2#
如果您可以使用The Boost Libraries,则已经存在一个
boost::circular_buffer
类模板,该模板实现了front()
、back()
、push_back()
和pop_front()
成员函数,因此可以用作std::queue
容器适配器的 * 底层容器 *:j8ag8udp3#
您可以在https://github.com/torrentg/cqueue找到循环队列的C++20实现
注:我是项目维护者。