C++ 创建固定大小的队列

Question

在C++ 中，如何创建一个简单的固定大小队列？

我在 Java 和 Python 中做过多次，但我正在寻找一种基于 C++ 的方法。

我需要一个只有 2 个元素的简单 FIFO 队列才能使用push和pop实用程序：我已经知道我可以实现我自己的类来执行这种限制，但我的问题旨在知道是否存在任何可用的解决这个问题。

或者是否有可能用数组完成相同的任务？那也行。

Answer 1

您可以从 queue 继承，然后重新实现 push 方法。这是一个基本的例子。

#include <queue>
#include <deque>
#include <iostream>

template <typename T, int MaxLen, typename Container=std::deque<T>>
class FixedQueue : public std::queue<T, Container> {
public:
    void push(const T& value) {
        if (this->size() == MaxLen) {
           this->c.pop_front();
        }
        std::queue<T, Container>::push(value);
    }
};

int main() {
    FixedQueue<int, 3> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);
    q.push(6);
    q.push(7);

    while (q.size() > 0)
    {
        std::cout << q.front() << std::endl;
        q.pop();
    }
}

这将打印

$ g++ fixedqueue.cpp -std=c++17 -o fixedqueue && ./fixedqueue
5
6
7

Answer 2

在 C++ 中，如何创建一个简单的固定大小队列？

首先，我认为您真正想要的是一个固定容量的队列，即队列的大小本身受限于队列的容量，但大小可能会有所不同。例如，如果队列为空，则大小最初可以为零，并在将元素插入队列时增加到队列的容量。

使用boost::circular_buffer

Boost 库具有实现容器 ( ) 的库Boost.CircularBuffer。该容器适合用作固定容量的 FIFO。boost::circular_bufferboost/circular_buffer.hpp

与 不同的是std::vector，无论您向容器中插入多少元素，其boost::circular_buffer容量都保持不变。也就是说，幕后不会发生重新分配：如果boost::circular_buffer的大小达到其容量，则插入新元素只会覆盖现有元素。

您可以boost::circular_buffer在构造时指定 的容量：

boost::circular_buffer<int> cb(2);

cb的容量为2，并且其初始大小为零，因为容器是空的。它的大小永远不会超过它的容量。但是，您可以显式更改容器的容量，例如，通过调用circular_buffer::set_capacity().

通过使用push_back()和pop_front()成员函数，您可以将其用作boost::circular_bufferFIFO。例子：

#include <boost/circular_buffer.hpp>
#include <iostream>

void print(const boost::circular_buffer<int>& cb) {
   std::cout << "size: " << cb.size() << ", capacity: " << cb.capacity() << '\n';

   for (auto const& elem: cb)
      std::cout << elem << ' ';
   std::cout << '\n';
}

auto main() -> int {
   // empty: size is zero
   boost::circular_buffer<int> cb(3);
   print(q);

   cb.push_back(0);
   print(cb);

   cb.push_back(1);
   print(cb);

   cb.push_back(2);  
   print(cb);

   // overwrites the oldest element: 0
   cb.push_back(3);
   print(cb);

   // overwrites the oldest element: 1
   cb.push_back(4);
   print(cb);

   cb.pop_front();
   print(cb);

   cb.pop_front();
   print(cb);

   // empty again
   cb.pop_front();
   print(cb);
}

输出：

size: 0, capacity: 3

size: 1, capacity: 3
0
size: 2, capacity: 3
0 1
size: 3, capacity: 3
0 1 2
size: 3, capacity: 3
1 2 3
size: 3, capacity: 3
2 3 4
size: 2, capacity: 3
3 4
size: 1, capacity: 3
4
size: 0, capacity: 3

std::queue与使用boost::circular_buffer

std::queue是一个容器适配器，其底层容器std::deque默认为。但是，您可以使用boost::circular_bufferasstd::queue的底层容器，因为它实现了、 和front()成员back()函数：push_back()pop_front()

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

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

auto main() -> int {
   FixedCapacityQueue<int> fixedCapQueue(boost::circular_buffer<int>(3));

   fixedCapQueue.push(0);
   fixedCapQueue.push(1);
   fixedCapQueue.push(2);
   fixedCapQueue.push(3); // overwrites the 0
   assert(fixedCapQueue.front() == 1);

   fixedCapQueue.pop(); // pops the 1
   assert(fixedCapQueue.front() == 2); 
}