動的確保しないリスト

[みけCAT]

・データの新規作成と削除がO(1)でできる
・イテレータによる処理ができる
・要素を作成するたびに動的確保することはない
という条件を満たす処理を行うクラスを作ってみました。
シューティング　：　リストと配列で書いたものの再投稿です。

クラス本体(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

使用例(data_supplier.cpp)

コード:

#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などでも大丈夫なはずです。
データの初期化は、コンストラクタではなく生成したデータのポインタが指す先にアクセスすることで行ってください。

使用・改造など自由です。