Qt: делаем кольцевой буфер

В библиотеке Tulip, как и в stl, есть практически все нужные контейнеры для реализации типовых динамических структур данных. Конечно, иногда приходится изменять или расширять функционал контейнера, и самый естественный путь сделать это - написать класс-потомок, модифицирующий или дополняющий базовый функционал класса-родителя.

В качестве примера сделаем из стандартной очереди QQueue кольцевой буфер CQueue, отличающийся тем, что ёмкость очереди ограничена заданным натуральным значением count. Если при добавлении элементов предельная ёмкость превышена, из буфера удаляется самый старый элемент.

Чтобы решение было достаточно универсальным, реализуем шаблон класса CQueue, полный исходник с комментариями - ниже:

#include <QCoreApplication>
#include <QQueue>
#include <QDebug>
#include <iostream>
using namespace std;

//Кольцевой буфер на основе стандартной очереди
template <class T>
class CQueue : public QQueue <T> {
 //как наследоваться от стандартного контейнера
 //для любого типа данных T
 private:
  int count; //предельный размер
 public:
  inline CQueue (int cnt) : QQueue<T>(),count(cnt) {
   //конструктор
  }
  inline void enqueue (const T &t) {
   //перегрузка метода постановки в очередь
   if (count==QQueue<T>::count()) {
    QQueue<T>::dequeue();
    //удалить старейший элемент по заполнении
   }
   QQueue<T>::enqueue(t);
  }
};

int main() {
 const int size=5; //размер буфера
 CQueue <int> q(size);
 for (int i=0; i<2*size; i++) q.enqueue(i+1);
  //заносим в буфер вдвое больше элементов,
  //чем он вмещает
 qDebug() << "Size=" << q.size();
 for (int i=0; i<size; i++) qDebug() << q.dequeue();
  //осталась только последняя половина элементов
 cin.sync(); cin.get(); return 0;
}

Как видно из кода, нам пришлось модифицировать только конструктор и метод постановки в очередь родительского класса.

P.S. Показанный ниже шаблон кольцевого буфера пригодился мне при "ручном" решении задачи, аналогичной поставленной в статье, поэтому добавлю листинг сюда.

Конструктору основного класса queue должны быть переданы размерность буфера _cnt (больше единицы) и значение _unacceptable типа T, которое будет возвращаться при невозможности получить элемент (например, при попытке извлечь значение из уже пустого буфера или получить значение по недопустимой позиции в буфере).

Показана работа с буфером из целых чисел и буфером из объектов демо-класса Data.

В классе должны быть определены конструктор по умолчанию и оператор new. Оператор << определён просто для удобства вывода объектов класса в консоль.

Проверено в актуальных сборках "Студии" 2019/2022.

#include <iostream>
#include <cstdlib>
using namespace std;

//Основной шаблон
template <class T> class queue {
 size_t cnt, head, tail, len;
 T* data;
 T unacceptable;
 size_t next(size_t pos) {
  return (pos + 1) % cnt;
 }
public:
 queue(size_t _cnt, T _unacceptable) {
  if (_cnt > 1) {
   cnt = _cnt; data = new T[cnt];
  }
  else {
   cnt = 0; data = nullptr;
  }
  unacceptable = _unacceptable;
  head = cnt - 1;
  tail = len = 0;
 }
 ~queue() { if (data) delete[] data; }
 bool empty () { return len == 0; }
 bool full() { return len == cnt; }
 size_t length () { return len; }
 T get() {
  if (!empty()) {
   T t = data[tail];
   tail = next(tail);
   len--;
   return t;
  }
  return unacceptable;
 }
 void put(const T& t) {
  if (data) {
   head = next (head);
   data[head] = t;
   if (full()) tail = next(tail);
   else len++;
  }
 }
 T at(int i) {
  if (data) {
   if (i > -1 && i < cnt) return data[i];
   else return unacceptable;
  }
  return unacceptable;
 }
};

//Просто класс для демонстрации
class Data {
 int n;
public:
 Data(int _n = 0) { n = _n; }
 void* operator new (size_t n) {
  return new Data [n];
 }
 friend ostream& operator << (ostream& out, Data d) {
  return out << d.n;
 }
};

int main(void) {
 //Кольцевой буфер n целых чисел
 const int n = 5;
 queue <int> d(n,0);
 for (int i = 1; i <= 2*n; i++) d.put(i);
 cout << "After adding of " << 2*n << " int item(s) in buffer from " 
  << n << " position(s)" << endl;
 for (int i = 0; i < n; i++) cout << d.at(i) << ' ';
 cout << endl << "Getting of " << n << " item(s):" << endl;
 for (int i = 0; i < n; i++) cout << d.get() << ' ';
 cout << endl << "After retrieving of " << n << " items length = " << 
  d.length() << endl;
 d.put(11);
 d.put(12);
 cout << "Put 2 items, 11 and 12" << endl;
 cout << "Get 1 item: " << d.get() << endl;
 cout << "Length = " << d.length() << endl;

 //Буфер из m объектов класса Data
 Data a(1),b(2),c(3);
 const int m = 2;
 Data bad(-1);
 queue <Data> d2(m, bad);
 d2.put(a); d2.put(b); d2.put(c);
 cout << endl << "Put 3 Data items, 1, 2 and 3 " << 
  "in buffer from 2 positions" << endl;
 for (int i = 0; i < m; i++) cout << d2.at(i) << ' ';
 cout << endl << "Length of d2 = " << d2.length() << endl;
 cout << "Get item " << d2.get() << endl;
 cout << "Length of d2 = " << d2.length() << endl;
 cout << "Get item " << d2.get() << endl;
 cout << "Length of d2 = " << d2.length() << endl;
 d2.put(11);
 cout << "Put 1 item, 11" << endl;
 cout << "Length of d2 = " << d2.length() << endl;
 cout << "Trying to extract another 2 elements" << endl;
 Data t = d2.get();
 t = d2.get();
 cout << "Last result is " << t <<  endl;
 cout << "Length of d2 = " << d2.length() << endl;

 return 0;
}

Вывод этого кода в консоль:

After adding of 10 int item(s) in buffer from 5 position(s)
6 7 8 9 10
Getting of 5 item(s):
6 7 8 9 10
After retrieving of 5 items length = 0
Put 2 items, 11 and 12
Get 1 item: 11
Length = 1

Put 3 Data items, 1, 2 and 3 in buffer from 2 positions
3 2
Length of d2 = 2
Get item 2
Length of d2 = 1
Get item 3
Length of d2 = 0
Put 1 item, 11
Length of d2 = 1
Trying to extract another 2 elements
Last result is -1
Length of d2 = 0

Разумеется, на основе стандартной очереди queue из STL мы тоже могли сделать кольцевой буфер с меньшими усилиями, как и для Qt в начале статьи.

Здесь мы тоже создаём класс-наследник от стандартной очереди и модифицируем только метод постановки в очередь с учётом ограниченного размера буфера.

#include <iostream>
#include <queue>
using namespace std;

//Кольцевой буфер на основе стандартной очереди
template <class T> class cqueue : public queue <T> {
 //как наследоваться от стандартного контейнера для любого типа данных T
private:
 int count; //предельный размер
public:
 cqueue(int cnt) : queue<T>(), count(cnt) {
  //конструктор
 }
 void push(const T& t) { //перегрузка метода постановки в очередь
  if (count == queue<T>::size()) {
   queue<T>::pop(); //удалить старейший элемент по заполнении
  }
  queue<T>::push(t);
 }
};

int main() {
 const int size = 5; //размер буфера
 cqueue <int> q(size);
 for (int i = 0; i < 2 * size; i++) {
  q.push(i + 1);
  //заносим в буфер вдвое больше элементов, чем он вмещает
 }
 cout << "Size=" << q.size() << endl;
 for (int i = 0; i < size; i++) { //осталась только последняя половина элементов
  cout << q.front() << ' ';
  q.pop();
 }
 //буфер пуст, добавим ещё 2 элемента и проверим размер:
 q.push(11);
 q.push(12);
 cout << endl << "Size=" << q.size() << endl;
 return 0;
}

/*
Вывод этого кода в консоль:

Size=5
6 7 8 9 10
Size=2
*/

25.03.2016, 14:40 [9149 просмотров]