・イテレータによる処理ができる
・要素を作成するたびに動的確保することはない
という条件を満たす処理を行うクラスを作ってみました。
シューティング : リストと配列で書いたものの再投稿です。
クラス本体(data_supplier.h)
#ifndef DATA_SUPPLIER_H_GUARD_A32E1860_7166_4BE8_A0D6_50080331A49F
#define DATA_SUPPLIER_H_GUARD_A32E1860_7166_4BE8_A0D6_50080331A49F
#include <iterator>
template<typename T>
class data_supplier {
private:
// データの最大数
size_t max_num;
T *data; // データ本体
// データを格納する領域の情報
struct data_link_t {
T *data;
data_link_t *prev; // 前のデータ領域
data_link_t *next; // 次のデータ領域
} *data_link;
// 先頭と末尾のデータの位置
data_link_t *head;
data_link_t *tail;
// データの空き位置を管理するキュー(リングバッファ)
data_link_t **empty_queue;
size_t empty_start, empty_end, empty_count;
// コピー・代入を許可しない
data_supplier(const data_supplier<T>& d) {}
data_supplier<T>& operator=(const data_supplier<T>& d) const {
return *this;
}
// キューの操作
bool is_queue_empty() const {return empty_count == 0;}
bool is_queue_full() const {return empty_count == max_num;}
data_link_t *dequeue() {
if (is_queue_empty()) return 0;
data_link_t *ret = empty_queue[empty_start];
empty_start = (empty_start + 1) % max_num;
empty_count--;
return ret;
}
void enqueue(data_link_t *v) {
if (is_queue_full()) return;
empty_queue[empty_end] = v;
empty_end = (empty_end + 1) % max_num;
empty_count++;
}
public:
// イテレータの定義
class iterator : public std::iterator<std::input_iterator_tag, T*> {
friend class data_supplier;
private:
// 参照先のデータの情報
data_supplier::data_link_t *data;
data_supplier::data_link_t data_end;
// 勝手にイテレータを作られないようにする
iterator(){}
iterator(data_link_t* d, data_link_t* prev = NULL) {
data = d;
data_end.prev = prev;
}
public:
// コピーコンストラクタ
iterator(const data_supplier& d) {
data = d.data;
data_end = d.data_end;
}
// 進める
iterator& operator++() {
if (data->next == NULL) {
data_end.data = NULL;
data_end.prev = data;
data_end.next = NULL;
data = &data_end;
} else {
data = data->next;
}
return *this;
}
iterator operator++(int) {
iterator bak = *this;
++(*this);
return bak;
}
// データを取得する
T* operator*() const {
return data->data;
}
// 比較する
bool operator==(const iterator& it) const {
data_link_t* d = data;
data_link_t* itd = it.data;
if (d == &data_end) d = NULL;
if (itd == &it.data_end) itd = NULL;
return d == itd;
}
bool operator!=(const iterator& it) const {
return !(*this == it);
}
};
// 先頭要素のイテレータを返す
iterator begin() const {
return iterator(head);
}
// 末尾のイテレータを返す
iterator end() const {
return iterator(NULL, tail);
}
// 初期化
data_supplier(size_t max = 1) {
max_num = max;
// 領域の確保
data = new T[max];
data_link = new data_link_t[max];
head = NULL;
tail = NULL;
for (size_t i = 0; i < max_num; i++) {
data_link[i].data = &data[i];
}
// キューの初期化
empty_queue = new data_link_t*[max];
empty_start = 0;
empty_end = 0;
empty_count = max_num;
for (size_t i = 0; i < max_num; i++) {
empty_queue[i] = &data_link[i];
}
}
// 開放
~data_supplier() {
delete[] data;
delete[] data_link;
delete[] empty_queue;
}
// 全消し
void clear() {
head = NULL;
tail = NULL;
empty_start = 0;
empty_end = 0;
empty_count = max_num;
for (size_t i = 0; i < max_num; i++) {
empty_queue[i] = &data_link[i];
}
}
// 新しいデータの追加
T* create_new_data() {
if (is_queue_empty()) {
return NULL;
} else {
// 次のデータ領域を取得する
data_link_t *next_data = dequeue();
// リストの先頭に追加する
if (head == NULL) {
head = next_data;
head->prev = NULL;
head->next = NULL;
tail = head;
} else {
data_link_t *old_head = head;
head = next_data;
head->prev = NULL;
head->next = old_head;
old_head->prev = head;
}
return next_data->data;
}
}
// データの削除
iterator delete_data(const iterator& it) {
if (it == end()) return it;
data_link_t *prev = it.data->prev;
data_link_t *next = it.data->next;
if (prev != NULL) prev->next = next; else head = next;
if (next != NULL) next->prev = prev;
enqueue(it.data);
return iterator(next);
}
};
#endif
#include <cstdio>
#include "data_supplier.h"
int main(void) {
data_supplier<int> ds(10);
for(;;) {
int query = 0;
puts("1: 追加、2: 削除、 3: インクリメント");
puts("4: 閲覧、5: リセット、6: 終了");
fputs(">", stdout);
if(scanf("%d", &query) != 1) return 1;
switch (query) {
case 1: {
fputs("数値>", stdout);
if (scanf("%d", &query) != 1) return 1;
int *next = ds.create_new_data();
if (next == NULL) {
puts("容量不足です");
} else {
*next = query;
puts("セットしました");
}
break;
}
case 2: {
fputs("数値>", stdout);
if (scanf("%d", &query) != 1) return 1;
for (data_supplier<int>::iterator it = ds.begin();
it != ds.end();) {
printf("%d : ", **it);
if (**it == query) {
puts("YES");
it = ds.delete_data(it);
} else {
puts("NO");
++it;
}
}
break;
}
case 3: {
for (data_supplier<int>::iterator it = ds.begin();
it != ds.end(); ++it) (**it)++;
puts("インクリメントしました");
break;
}
case 4: {
for (data_supplier<int>::iterator it = ds.begin();
it != ds.end(); ++it) printf("%d\n", **it);
break;
}
case 5:
ds.clear();
puts("リセットしました");
break;
case 6:
return 0;
default:
puts("コマンドが不正です");
break;
}
}
return 0;
}
・変数宣言
data_supplier<管理する型名> 変数名(最大要素数);
・新しいデータの生成
create_new_data() // 新しいデータのポインタが返る
・先頭イテレータの取得
begin()
・末尾イテレータの取得
end()
・データの削除
delete_data(削除するデータを指すイテレータ) // 次の要素を指すイテレータが返る
・データの全消し(初期化)
clear()
管理するデータはコンストラクタやデストラクタでの処理が必要ないもの(C言語的な「構造体」など)にしてください。
clearすることで前のデータの影響を受けない、std::vectorなどでも大丈夫なはずです。
データの初期化は、コンストラクタではなく生成したデータのポインタが指す先にアクセスすることで行ってください。
使用・改造など自由です。