簡易メモリアロケータ―ちゃん

概要

いわゆるリスト構造を1つ1つ繋ぐのではなく、複数個をまとめて繋いでいく形のリンクリストを際発明しただけのものです。freeもできて、そのポインタを後で再利用していきます。例外周りが適当です。

有用な点は、どれだけメモリ確保しても元のデータのポインタは変わらない点、使わなくなったらfreeして次のmake時に再利用される点です。freeは実際にはメモリを開放するわけではないので、全体のデータがいらなくなったときはfv自体を開放する(= デストラクタを呼び出す)必要があります。

これは制作中の『繋げてたまともシールオンライン』の中でも使ってます。

テストコード

#include <iostream>
#include "fixed_vector.h"

int main() {
	FixedVector<int> fv;

	auto p = fv.make();
	*p = 10;

	std::cout << p << ":" << *p << std::endl;

	fv.free(p);

	auto p2 = fv.make();
	*p2 = 100;

	std::cout << p2 << ":" << *p2 << std::endl;


	std::cin.get();
	return 0;
}

実行例:

00291FC8:10
00291FC8:100

実装

#pragma once

#include <vector>

template <typename T>
class FixedVector {
	template <typename T>
	struct Storage {
		Storage(size_t size) : buffer(new T[size]), next(nullptr) { }
		~Storage() {
			delete[] buffer; delete next;
		}
		T* buffer;
		Storage<T>* next;
	};

public:
	FixedVector(size_t size = 10) : size(size), free_list_size(size), position(0), free_top(0) {
		storage = new Storage<T>(size);
		last_storage = storage;
		free_list.resize(free_list_size);
		popAndPush(&storage->buffer[0]);
	}

	FixedVector(const FixedVector<T>& it) { }

	FixedVector(FixedVector<T>&& it) { }

	template <typename ...Args>
	T* make(Args ...args) {
		T* ret = getTop();

		new(ret)T(args...);

		if(free_top > 0) {
			pop();
		}
		else {
			++position;

			if(position >= size) {
				makeStorage();
			}

			popAndPush(&last_storage->buffer[position]);
		}

		return ret;
	}

	void free(T* it) {
		push(it);
	}

	void sfree(T*& it) {
		if(it == nullptr) {
			throw std::exception();
		}
		push(it);
		it = nullptr;
	}

	~FixedVector() {
		delete storage;
	}

private:
	T* getTop() {
		return free_list[free_top];
	}

	void pop() {
		--free_top;
	}

	void popAndPush(T* it) {
		free_list[free_top] = it;
	}

	void push(T* it) {
		++free_top;
		if(free_top >= free_list_size) {
			free_list_size += size;
			free_list.resize(free_list_size);
		}
		free_list[free_top] = it;
	}

	void makeStorage() {
		last_storage = new Storage<T>(size);
		storage->next = last_storage;
		position = 0;
	}

	Storage<T>* storage;
	Storage<T>* last_storage;
	std::vector<T*> free_list;
	size_t size;
	size_t free_top;
	size_t position;
	size_t free_list_size;
};