C++创建固定大小队列

Question

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

我已经在Java和Python中多次完成了此操作，但现在寻求一种基于C++的方式。

我需要一个仅具有2个元素的简单FIFO队列，以使用push和pop这些工具：我已经知道我可以实现自己的类来执行此类限制，但我的问题是想知道是否存在任何已经可用的解决方案。

或者也许可以使用数组来完成同样的任务吗？那也可以。

- Employee

---

您需要实现所需的有限容器并使用 std::queue 适配器。 - 273K

@S.M. 谢谢，您能否再详细解释一下这个问题？ - Employee

你必须在你的容器中实现至少 push_back，pop_front 和 size 方法，并在 std::queue 中使用它。 - 273K

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

- solinent

---

这里的c是什么？ - Kumar Roshan Mehta

@KumarRoshanMehta 我觉得那是个打字错误，应该是 this->pop_front(); 应该可以运行。 - undefined

Answer 2

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

首先，我认为你实际上想要的是一个固定容量队列，即队列的大小将被限制在队列的容量内，但大小可能会变化。例如，如果队列为空，则大小可以最初为零，并随着向队列插入元素而增加到队列的容量。

---

使用 boost::circular_buffer

Boost库提供了Boost.CircularBuffer库，实现了boost::circular_buffer容器（boost/circular_buffer.hpp）。该容器适用于固定容量的FIFO。

与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_buffer用作FIFO。例如：

#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

---

使用boost::circular_buffer和std::queue

std::queue是一个容器适配器，默认情况下其底层容器为std::deque。但是，您可以使用boost::circular_buffer作为std::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); 
}

- ローウ

---

这个解决方案的问题在于boost::circular_buffer<T>会覆盖最旧的元素。然而，作者没有指定这样的要求，所以这仍然是一个好的答案。 - Tihran

@Tihran 是的。循环缓冲区非常适用于旧元素相对于新元素失去相关性的用例，例如日志记录。当插入到满队列时，其他策略可能是(1) 忽略要插入的新元素和(2) 覆盖最新的元素。不过，这两种策略都可以轻松地使用std::queue实现。关于(2)：back()返回对最新元素的引用。 - JFMR

Answer 3

使用自定义循环容器。在线示例在这里：https://ideone.com/0nEBZa

#include <array>
#include <iostream>
#include <queue>

template <typename T, size_t N = 2>
class CyclicArray {
 public:
  typedef typename std::array<T, N>::value_type value_type;
  typedef typename std::array<T, N>::reference reference;
  typedef typename std::array<T, N>::const_reference const_reference;
  typedef typename std::array<T, N>::size_type size_type;

  ~CyclicArray() {
    while (size())
      pop_front();
  }

  void push_back(const T& v) {
    if (size_ + 1 > N)
      throw;
    new (&array_[(front_ + size_) % N]) T(v);
    ++size_;
  }

  void pop_front() {
    if (size_ < 1)
      throw;
    front().~T();
    ++front_;
    --size_;
    if (front_ >= N)
      front_ = 0;
  }

  const_reference front() const {
    return *reinterpret_cast<const T*>(&array_[front_]);
  }

  reference front() {
    return *reinterpret_cast<T*>(&array_[front_]);
  }

  size_type size() const {
    return size_;
  }

 private:
  size_type front_ = 0;
  size_type size_ = 0;
  std::array<char[sizeof(T)], N> array_;
};

int main() {
    std::queue<int, CyclicArray<int, 2>> queue;
    queue.push(1);
    queue.push(2);
    queue.pop();
    queue.push(3);
    int f = queue.front();
    queue.pop();
    std::cout << f << std::endl;
    f = queue.front();
    queue.pop();
    std::cout << f << std::endl;
    return 0;
}

输出

2
3

- 273K