Zirkuläre Array in C++ implementieren

Jinku Hu 12 Oktober 2023

C++ C++ Data Structure

In diesem Artikel wird beschrieben, wie Sie eine zirkuläre Array-Datenstruktur in C++ implementieren.

User-Array-Implementierung für Circular Buffer-Implementierung in C++

Ein kreisförmiges Array ist eine Datenstruktur, die üblicherweise verwendet wird, um eine warteschlangenartige Sammlung von Daten zu implementieren. Es ist auch mit alternativen Namen wie einer zirkulären Warteschlange oder einem Ringpuffer bekannt, aber wir werden es in diesem Artikel als zirkuläres Array bezeichnen.

Das kreisförmige Array hat einen FIFO-Mechanismus (First In, First Out) zum Einfügen und Entfernen von Elementen. Normalerweise hat der Puffer eine feste Länge. Wenn die maximale Kapazität erreicht ist, kann der Puffer neue Einfügeoperationen verweigern oder mit dem Überschreiben der ältesten Elemente beginnen. Letzteres Merkmal ist eine Designentscheidung, und die Vorteile sollten für das jeweilige Problem berücksichtigt werden.

In den folgenden Beispielen implementieren wir ein kreisförmiges Array mit einem Array im C-Stil und konstruieren eine Einfügefunktion, damit der volle Puffer nicht beginnt, alte Daten zu überschreiben.

Die Klasse CircularArray umfasst 5 Datenelemente, von denen drei den Typ T* haben, und diese werden verwendet, um die Adressen für den ersten zu speichern. Die letzten Elemente (head bzw. tail). arr Member wird nur verwendet, um die Speicherfreigabe mit dem Operator delete zu erleichtern. Die verbleibenden zwei Datenmember sind ganzzahlige Typen, die die Kapazität und die aktuelle Größe des kreisförmigen Arrays speichern.

Der Konstruktor initialisiert das Member size automatisch auf 0, während der Wert cap als Funktionsparameter akzeptiert und somit zur Zuweisung des benötigten Speicherbereichs verwendet wird. An diesem Punkt zeigen sowohl die Zeiger tail als auch head auf dieselbe Position, die das erste Element im Array ist. Denken Sie jedoch daran, dass sich diese Zeiger während der Lebensdauer des Objekts kreisförmig bewegen können, sodass wir beim Aufrufen von Einfüge- und Entfernungsvorgängen die richtigen Änderungen kontrollieren müssen.

#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;
}

Ausgabe:

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

Um neue Elemente in das zirkuläre Array hinzuzufügen, sollte die Memberfunktion enqueue aufgerufen werden. Diese Funktion nimmt eine Referenz auf das generische Objekt und speichert sie am tail des Puffers.

Die Funktion enqueue liefert einen Wert ungleich Null zurück, wenn das Einfügen nicht erfolgreich ist, und der Programmierer ist dafür verantwortlich, den entsprechenden Rückgabewert zu überprüfen.

Andererseits übernimmt die Funktion dequeue die Entfernung der Elemente aus dem head des Puffers. Es soll den Zeiger auf das entfernte Element zurückgeben. Vor dem Zugriff (Dereferenzieren) muss der Return-Pointer überprüft werden, da er den Wert nullptr haben kann. nullptr wird zurückgegeben, um anzuzeigen, dass der Puffer leer ist und keine Elemente entfernt werden können.

Währenddessen kann man mit der Funktion getSize sicher auf die aktuelle Anzahl von Elementen im Puffer zugreifen und den zurückgegebenen Wert verwenden, um über die Struktur zu iterieren. Obwohl die Iteration in realen Szenarien wahrscheinlich nicht verwendet wird, kann das Element size wichtige Daten für die Implementierung zusätzlicher Elementfunktionen sein.

#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;
}

Ausgabe:

Array is empty !
1,1.9

Autor: Jinku Hu

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn Facebook

User-Array-Implementierung für Circular Buffer-Implementierung in C++

Verwandter Artikel - C++ Data Structure