動的確保しないリスト

みんなが作った便利な関数やサンプルを共有するコミュニティです。
[url]http://www.activebasic.com/forum/viewforum.php?f=2]ActiveBasicの「実践コードモジュール」[/url]的な感じでやりましょう。
フォーラム(掲示板)ルール
・投稿するコードはできるだけ一つ、もしくは一つの関数を補助する複数の関数の形式にするか、
それだけをコンパイルして動くソースコード一式の形にしてください。
記事には説明だけを書き、コードは添付ファイルにしてもかまいません。
・使い方などの説明も書いてください。
環境に依存するコードの場合は、対象の環境も書いてください。
・使用条件(ライセンスなど)も書いていただけるとありがたいです。
・C言語、もしくはC++推奨ですが、他の言語でもかまいません。
・コードは正しくcodeタグで囲みましょう。
・一つのスレッドで一つのサンプルが基本です。
関連するサンプルの場合はまとめてもかまいません。
・投稿したサンプルを修正する場合には、スレッドの返信の形で投稿してください。
(新しいスレッドにしないでください。記事の編集でもかまいません)
返信
アバター
みけCAT
記事: 6190
登録日時: 8年前
住所: 千葉県
連絡を取る:

動的確保しないリスト

#1

投稿記事 by みけCAT » 4年前

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

使用・改造など自由です。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

返信

“サンプルを共有するコミュニティ” へ戻る