C++ で循環配列を実装する
この記事では、C++ で循環配列データ構造を実装する方法について説明します。
C++ での循環バッファ実装のためのユーザー配列実装
循環配列は、キューのようなデータのコレクションを実装するために一般的に使用されるデータ構造です。循環キューやリングバッファなどの別名でも知られていますが、この記事では循環配列と呼びます。
循環配列には、要素の挿入および削除操作のための FIFO（先入れ先出し）メカニズムがあります。通常、バッファの長さは固定されています。最大容量に達すると、バッファは新しい挿入操作を拒否するか、最も古い要素の上書きを開始する場合があります。後者の機能は設計上の選択であり、目前のそれぞれの問題について利点を考慮する必要があります。
次の例では、C スタイルの配列を使用して循環配列を実装し、バッファ全体が古いデータの上書きを開始しないように挿入関数を作成します。
CircularArray クラスには 5つのデータメンバーが含まれ、そのうち 3つは T*タイプであり、これらは最初のアドレスを格納するために使用されます。最後の要素（それぞれ head と tail）。arr メンバーは、delete 演算子を使用してメモリの割り当て解除を容易にするためにのみ使用されます。残りの 2つのデータ型は、循環配列の容量と現在のサイズを格納する整数型です。
コンストラクターは、size メンバーを 0 に自動的に初期化しますが、cap 値は関数パラメーターとして受け入れられ、その結果、必要なメモリー領域を割り当てるために使用されます。この時点で、tail と head の両方のポインターが同じ場所を指しています。これは配列の最初の要素です。ただし、これらのポインタはオブジェクトの存続期間中に循環的に移動する可能性があるため、挿入および削除操作が呼び出されたときに正しい変更を制御する必要があることに注意してください。
#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;
}
出力：
1,1.1
1,1.2
1,1.3
1,1.4
循環配列に新しい要素を追加するには、enqueue メンバー関数を呼び出す必要があります。この関数は、汎用オブジェクトへの参照を取得し、それをバッファの tail に格納します。
挿入が失敗した場合、enqueue 関数はゼロ以外の値を返し、プログラマーは対応する戻り値をチェックする責任があります。
一方、dequeue 関数は、バッファの head からの要素の削除操作を処理します。削除された要素へのポインタを返すように設計されています。リターンポインタには nullptr 値がある可能性があるため、アクセス（逆参照）する前にリターンポインタを確認する必要があります。nullptr は、バッファが空であり、要素を削除できないことを示すために返されます。
一方、getSize 関数を使用してバッファ内の現在の要素数に安全にアクセスし、戻り値を使用して構造を反復処理できます。反復が実際のシナリオで使用される可能性は低いですが、size メンバーは、追加のメンバー関数を実装するための重要なデータになる可能性があります。
#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;
}
出力：
Array is empty !
1,1.9
