Implémenter un tableau circulaire en C++

Cet article décrira comment implémenter une structure de données de tableau circulaire en C++.

Implémentation de tableau d’utilisateurs pour l’implémentation de tampon circulaire en C++

Un tableau circulaire est une structure de données couramment utilisée pour implémenter une collection de données de type file d’attente. Il est également connu sous des noms alternatifs tels qu’une file d’attente circulaire ou un tampon en anneau, mais nous l’appellerons un tableau circulaire tout au long de cet article.

Le réseau circulaire a un mécanisme FIFO (First In, First Out) pour les opérations d’insertion et de suppression d’éléments. Habituellement, le tampon aura une longueur fixe. Si la capacité maximale est atteinte, le tampon peut refuser de nouvelles opérations d’insertion ou commencer à écraser les éléments les plus anciens. Cette dernière caractéristique est un choix de conception, et les avantages doivent être pris en compte pour le problème concerné.

Dans les exemples suivants, nous implémentons un tableau circulaire à l’aide d’un tableau de style C et construisons une fonction d’insertion afin que le tampon plein ne commence pas à écraser les anciennes données.

La classe CircularArray comprend 5 membres de données, dont trois de type T*, et ceux-ci sont utilisés pour stocker les adresses du premier. Les derniers éléments (head et tail respectivement). Le membre arr n’est utilisé que pour faciliter la désallocation de mémoire à l’aide de l’opérateur delete. Les deux membres de données restants sont des types intégraux qui stockent la capacité et la taille actuelle du tableau circulaire.

Le constructeur initialise automatiquement le membre size à 0, tandis que la valeur cap est acceptée comme paramètre de la fonction et par conséquent utilisée pour allouer la région mémoire requise. À ce stade, les pointeurs tail et head pointent vers le même emplacement, qui est le premier élément du tableau. N’oubliez pas, cependant, que ces pointeurs peuvent se déplacer de manière circulaire pendant la durée de vie de l’objet, nous devons donc contrôler les modifications correctes lorsque les opérations d’insertion et de suppression sont appelées.

#include <iostream>

using std::cin;
using std::cout;
using std::endl;

template <typename T>
class CircularArray {
 public:
  explicit CircularArray(const size_t elems) {
    cap = elems;
    arr = new T[elems];
    tail = head = arr;
    size = 0;
  };

  int enqueue(const T &data);
  T *dequeue();
  size_t getSize();

  ~CircularArray();

 private:
  T *arr = nullptr;
  T *head = nullptr;
  T *tail = nullptr;
  size_t cap;
  size_t size;
};

template <typename T>
CircularArray<T>::~CircularArray() {
  delete[] arr;
}

template <typename T>
int CircularArray<T>::enqueue(const T &data) {
  if (size < cap) {
    if (size == 0) {
      head = tail = arr;
      *tail = data;
      size++;
      return 0;
    }

    if (tail == &arr[cap]) {
      tail = arr;
      *tail = data;
      size++;
    } else {
      tail = tail + 1;
      *tail = data;
      size++;
    }
    return 0;
  } else {
    return -1;
  }
}

template <typename T>
T *CircularArray<T>::dequeue() {
  if (size != 0) {
    auto ret = head;

    if (head == &arr[cap]) {
      head = arr;
    } else {
      head = head + 1;
    }

    size--;
    return ret;
  } else {
    cout << "Array is empty !" << endl;
    return nullptr;
  }
}

template <typename T>
size_t CircularArray<T>::getSize() {
  return size;
}

struct MyClass {
  int num;
  double num2;
};

int main() {
  CircularArray<MyClass> m1(4);

  m1.enqueue({1, 1.1});
  m1.enqueue({1, 1.2});
  m1.enqueue({1, 1.3});
  m1.enqueue({1, 1.4});
  m1.enqueue({1, 1.5});
  m1.enqueue({1, 1.6});

  auto size = m1.getSize();
  for (size_t i = 0; i < size; ++i) {
    auto elem = m1.dequeue();
    cout << elem->num << "," << elem->num2 << endl;
  }

  return EXIT_SUCCESS;
}

Production:

1,1.1
1,1.2
1,1.3
1,1.4

Afin d’ajouter de nouveaux éléments dans le tableau circulaire, la fonction membre enqueue doit être appelée. Cette fonction prend une référence à l’objet générique et la stocke à la tail du tampon.

La fonction enqueue renvoie une valeur non nulle si l’insertion échoue, et le programmeur se charge de vérifier la valeur de retour correspondante.

En revanche, la fonction dequeue gère l’opération de suppression d’élément de la head du buffer. Il est conçu pour renvoyer le pointeur sur l’élément supprimé. Il faut vérifier le pointeur de retour avant d’y accéder (déréférencement) car il peut avoir la valeur nullptr. nullptr est renvoyé pour indiquer que le tampon est vide et qu’aucun élément ne peut être supprimé.

Pendant ce temps, on peut accéder en toute sécurité au nombre actuel d’éléments dans le tampon en utilisant la fonction getSize et utiliser la valeur renvoyée pour itérer sur la structure. Bien que l’itération ne soit pas susceptible d’être utilisée dans des scénarios du monde réel, le membre size peut être une donnée importante pour la mise en œuvre de fonctions membres supplémentaires.

#include <iostream>

using std::cin;
using std::cout;
using std::endl;

template <typename T>
class CircularArray {
 public:
  explicit CircularArray(const size_t elems) {
    cap = elems;
    arr = new T[elems];
    tail = head = arr;
    size = 0;
  };

  int enqueue(const T &data);
  T *dequeue();
  size_t getSize();

  ~CircularArray();

 private:
  T *arr = nullptr;
  T *head = nullptr;
  T *tail = nullptr;
  size_t cap;
  size_t size;
};

template <typename T>
CircularArray<T>::~CircularArray() {
  delete[] arr;
}

template <typename T>
int CircularArray<T>::enqueue(const T &data) {
  if (size < cap) {
    if (size == 0) {
      head = tail = arr;
      *tail = data;
      size++;
      return 0;
    }

    if (tail == &arr[cap]) {
      tail = arr;
      *tail = data;
      size++;
    } else {
      tail = tail + 1;
      *tail = data;
      size++;
    }
    return 0;
  } else {
    return -1;
  }
}

template <typename T>
T *CircularArray<T>::dequeue() {
  if (size != 0) {
    auto ret = head;

    if (head == &arr[cap]) {
      head = arr;
    } else {
      head = head + 1;
    }

    size--;
    return ret;
  } else {
    cout << "Array is empty !" << endl;
    return nullptr;
  }
}

template <typename T>
size_t CircularArray<T>::getSize() {
  return size;
}

struct MyClass {
  int num;
  double num2;
};

int main() {
  CircularArray<MyClass> m1(4);

  m1.dequeue();
  m1.enqueue({1, 1.9});
  auto elem = m1.dequeue();
  if (elem) cout << elem->num << "," << elem->num2 << endl;

  return EXIT_SUCCESS;
}

Production:

Array is empty !
1,1.9