きままにブログ

プログラミングを主とした私のメモ帳です。寂しいのでコメントください笑

Any型の実装

Anyを実装しよう

Any型とは

何でも格納できる型を作ることを考えます。普通はそんな型は必要ないし、当然その分オーバーヘッドが生じてしまうので利用する箇所は限られるだろうけどコンテナに格納するなどして便利なことはあるにはあります。

実装方法

Step1

Any型本体を考えましょう。

class Any {
private:
public:
	template <typename T>
	Any(T const& it) : data(new ###(it)) {

	}

private:
	std::unique_ptr<###> data;
};

とりあえずコンストラクタにデータを入れてそれをどんな方でも保存できなければ要件は満たせません。さて、###にはどんな型を入れればよいのでしょうか。ここはしかたがないのでテンプレートで頑張ることにします。即ち、なんらかのクラステンプレートが必要ということです。

class Any {
private:
	template <typename T>
	class holder {
	public:
		holder(T const& it) : data(it) { }
	private:
		T data;
	};

public:
	template <typename T>
	Any(T const& it) : data(new holder<T>(it)) {

	}

private:
	std::unique_ptr<holder<###>> data;
};

Step2

さてこんどはデータの型が定まらない問題に直面しました。###はどうしたらいいのでしょうか? 複数のクラスを一つのクラスにまとめる…といえば抽象クラスが浮かびます。holderの抽象クラスplace_holderを定義して、holderはこれを継承すれば解決できそうです。

class Any {
private:
	class place_holder {
	public:
		virtual ~place_holder() { }
	};

	template <typename T>
	class holder : public place_holder {
	public:
		holder(T const& it) : data(it) { }
	private:
		T data;
	};

public:
	template <typename T>
	Any(T const& it) : data(new holder<T>(it)) {

	}

private:
	std::unique_ptr<place_holder> data;
};

それでは実際に利用してみましょう。

Any any = 100;
Any any2 = 10.5;

Step3

さて、格納した値を参照することを考えます。今現在の型が何かを知るには実行時に知るしかありません。したがって決め打ちで出力する方法が必要です。place_holderからholderにダウンキャストするにはdynamicなどが便利でしょう。即ち、メンバ関数getを定義し、holderにダウンキャストを試み、ダメであった場合はstd::bad_cast例外を投げ、大丈夫な場合は生データへの参照を返します。

template <typename T>
T& get() const {
	auto p = dynamic_cast<holder<T>*>(data.get());
	if (p == nullptr) {
		throw std::bad_cast();
	}
	return p->data;
}

Step4

再代入やコピー等を考えましょう。他のAnyオブジェクトは当然コピーできますし、任意のオブジェクトはコピーされます。同様に代入もされます。結局次のように成りました。

typeとcloneが必要なのは、typeで型情報を得る時とAnyからAnyへコピーした時にひつようだからです。

class Any {
private:
	struct place_holder {
		virtual ~place_holder() { }
		virtual std::type_info const& type() const { return typeid(nullptr); }
		virtual std::unique_ptr<place_holder> clone() const { return nullptr; }
	};

	template <typename T>
	struct holder : public place_holder {
		holder(T const& it) : data(it) { }
		template <typename ...Args>
		holder(Args ...args) : data(args) { }
		std::type_info const& type() const override { return typeid(data); }
		T data;
		std::unique_ptr<place_holder> clone() const override { return std::make_unique<holder<T>>(data); }
	};

public:
	Any() {}
	template <typename T>
	Any(T const& it) : data(new holder<T>(it)) { }
	Any(Any const& it) : data(std::make_unique<place_holder>(*it.data)) { }
	Any(Any&& it) : data(std::move(it.data)) { }
	Any& operator=(Any const& it) {
		data = it.data->clone();
		return *this;
	}
	Any& operator=(Any&& it) {
		data = std::move(it.data);
		return *this;
	}
	template <typename T>
	Any& operator=(T const& it) {
		data = std::make_unique<holder<T>(it);
		return *this;
	}

	template <typename T>
	T& get() const {
		auto p = dynamic_cast<holder<T>*>(data.get());
		if (p == nullptr) {
			throw std::bad_cast();
		}
		return p->data;
	}

	std::type_info const& type() const {
		return data->type();
	}
private:
	std::unique_ptr<place_holder> data;
};

使う場合はこうします :

Any any = C(); // construct & copy
printf("%s\n", any.type().name());
Any any2;
any2 = any; // copy
printf("%s\n", any2.type().name());
// destruct & destruct

Optional

以前作ったOptionalにちょっと機能を付け足しました :

  • operator()(Arg...)にて再配置newによって再構築可能としました。これにより不要なコピーのオーバーヘッドがなくなります。
  • コンストラクタとデストラクタが同数呼び出されるように修正しました。コンストラクタとデストラクタによるリソース管理ができるようになりました。(後述)
  • 代入演算子の戻り値が参照でない問題を修正しました。

実装

#pragma once

#include <new>
#include <type_traits>
#include <functional>

namespace mytools {
class None {};

template <typename T>
class Optional {
public:
	Optional() : data_pointer(nullptr) {}
	Optional(T const& it) : data_pointer(new(&data) T(it)) { }
	Optional(None const& it) : data_pointer(nullptr) { }
	Optional(Optional<T> const& it) : data_pointer(new(&data) T(*it) ) { }
	template <typename ...Args>
	Optional(Args ...args) : data_pointer(new(&data) T(args...)) {}

	~Optional() {
		if (data_pointer != nullptr) {
			data_pointer->~T();
		}
	}

	Optional<T>& operator=(T const& it) {
		if (data_pointer != nullptr) {
			data_pointer->~();
		}
		data_pointer = new(&data) T(it);
		return *this;
	}
	Optional<T>& operator=(Optional<T> const& it) {
		if (data_pointer != nullptr) {
			data_pointer->~();
		}
		data_pointer = new(&data) T(*it);
		return *this;
	}
	Optional<T>& operator=(None const& it) {
		if (data_pointer != nullptr) {
			data_pointer->~();
		}
		return *this;
	}
	bool operator==(Optional<T> const& it) const {
		return data_pointer == it.data_pointer;
	}
	bool operator!=(Optional<T> const& it) const {
		return data_pointer != it.data_pointer;
	}
	T& operator*() const {
		return *data_pointer;
	}
	T* operator->() const {
		return data_pointer;
	}

	template <typename ...Args>
	Optional<T>& operator()(Args ...args) {
		if (data_pointer != nullptr) {
			data_pointer->~T();
		}
		data_pointer = new(&data) T(args...);
		return *this;
	}

	operator bool() const {
		return data_pointer != nullptr;
	}
private:
	mutable T* data_pointer;
	typename std::aligned_storage<sizeof(T), __alignof(T)>::type data;
};
}

Optionalによるリソース管理例

Optionalは通常、無効値を表すのに使えますがそれだけではありません。例えば次のような処理で困ったことはないでしょうか。

{
	C c; // どうしてもここで初期化したい
}

// ここでは使えない…

もちろん可能なかぎりこのようなことはないようにすべきですが、こう書いたほうが分かりやすかったり効率が良かったりする場合もあります。こんなときOptionalなら、スタックにメモリを確保しつつあとでplacement-newすることで再構築可能です。

Optional<C> c; // == None

{
	c(); // 再構築
}

// ここでも使える!

このようにスコープを自由に調整できる利点もあるわけです。これを遅延初期化といいます。

古い日記に言及, メソッドチェーン

C++ ですらできる(でもメモリリークします)。

#include <iostream>

class Foo {
public:
  void method()
  {
    std::cout << "hello!\n";
  }
};

int main(int, char*[])
{
  new Foo()->method();
  return 0;
}

いやいや、C++でのメソッドチェーンとは次のような書き方をします。

class C {
public:
	C(int n) : n(n) { }

	C methodA() { // 非constなメンバ関数A
		++n;
		return *this;
	}

	C methodB() { // 非constなメンバ関数B
		n *= 2;
		return *this;
	}

	void show() const { // 表示する
		printf("n=%d\n", n);
	}

private:
	int n;
};

における、

C(10).methodA().methodB().show();

なにかとnewしないと行けないみたいな思い込みがあるのは変な解説が多すぎる(た)からですね。特にJavaからC++を勉強した人とかにありがち。newなんて使いませんから!!

簡易メモリアロケータのunique_ptrを返す実装

#pragma once

#include <vector>
#include <memory>

namespace mytools {
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:
	template <typename T>
	class Deleter {
	public:
		FixedVector<T>* self;
		using pointer = T*;
		Deleter(FixedVector<T>* self) : self(self) {}

		void operator()(pointer p) {
			self->free(p);
		}
	};

	using unique = std::unique_ptr<T, Deleter<T>>;

	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;
	}

	template <typename ...Args>
	unique make_unique(Args ...args) {
		return unique(make(args...), Deleter<T>(this));
	}

	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;
};
}

について、ベンチマークを取ったところ:

mytools::FixedVector<S> fv;
	{
		WindowsTimer wt;
		wt.start();
		for (int i = 0; i < 10000000; ++i) {
			auto p = fv.make();
			fv.free(p);
		}
		wt.stop();
		printf("MAKE %lf\n", static_cast<double>(wt));

		wt.start();
		for (int i = 0; i < 10000000; ++i) {
			decltype(fv)::unique p = fv.make_unique();
		}
		wt.stop();
		printf("MAKE_UNIQUE %lf\n", static_cast<double>(wt));

		wt.start();
		for (int i = 0; i < 10000000; ++i) {
			auto p = new S();
			delete p;
		}
		wt.stop();
		printf("delete %lf\n", static_cast<double>(wt));

		wt.start();
		for (int i = 0; i < 10000000; ++i) {
			auto p = std::make_unique<S>();
		}
		wt.stop();
		printf("unique %lf\n", static_cast<double>(wt));
	}
MAKE 0.024968
MAKE_UNIQUE 0.096462
delete 0.597430
unique 0.539340

という結果になりました。やはりカスタムデリータに管理元クラスのポインタを持たせているためにだいぶ遅くなってしまっているみたいです。そもそもカスタムデリータが遅いのか?

C++AMP

お久し振りです。しばらくプログラムを書いていなかったのですが、VisualStudio 2015 RCも出たことでC++を書いています。今回はC++AMPを触ってみました。

特定の行列のなかの部分行列にアクセスし、GPUで演算を行うものをC++AMPを使って書いたものです。処理速度はともかく、とても簡素な記述でGPUに対して処理できるのでとても便利ですね。

#include <iostream>
#include <amp.h>

int main() {
	using namespace concurrency;

	array_view<int, 2> av(3, 3);
	
	parallel_for_each(av.extent,
					  [av](index<2> i) restrict(amp) {
		av[i] += (i[0] + 1) * 10 + (i[1] + 1);
	});

	auto av_sub = av.section(index<2>(1, 0), extent<2>(2, 2));

	parallel_for_each(av_sub.extent,
					  [av_sub](index<2> i) restrict(amp) {
		av_sub[i] += 100;
	});

	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			std::cout << av(i, j) << "\t";
		}
		std::cout << std::endl;
	}

	std::getchar();
	return 0;
}

ダイクストラ法

なんか大変微妙な実装になってしまったが、有向・無向グラフを実装した。正直、使うごとに自分で定義してアルゴリズムも書き直したほうがいい気がするのでこれ以上は改良しないで色々グラフを堪能していこうと思います。

  • 使用例
#include <cstdio>

#include "Graph.h"

int main() {
	Graph<int, int> g;

	auto v1 = g.createVertex(1);
	auto v2 = g.createVertex(2);
	auto v3 = g.createVertex(3);
	auto v4 = g.createVertex(4);
	auto v5 = g.createVertex(5);

	g.createEdge(v1, v2, 12);
	g.createEdge(v1, v3, 10);
	g.createEdge(v1, v4, 1);
	g.createEdge(v2, v3, 2);
	g.createEdge(v2, v5, 1);
	g.createEdge(v3, v4, 20);
	g.createEdge(v4, v5, 1);

	g.solveByDijkstra(0, INT_MAX);

	g.show();

	getchar();
	return 0;
}
  • Graph.h
#pragma once

#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include "Vertex.h"
#include "Edge.h"

template <typename Data, typename CostType>
class Graph {
public:
	Graph() : vertex_size(0), edge_size(0) {

	}

	Vertex<Data> createVertex(const Data& data) {
		vertex_list.emplace_back(data, vertex_size++);
		return vertex_list.back();
	}

	void createEdge(const Vertex<Data>& from, const Vertex<Data>& to, const CostType& cost) {
		edge_list.emplace_back(from, to, cost, edge_size++);
		auto edge_id = edge_list.back().id;
		edge_list.emplace_back(to, from, cost, edge_size++);
		auto reverse_edge_id = edge_list.back().id;

		auto& v_from = vertex_list[from.id];
		auto& v_to = vertex_list[to.id];

		v_from.edge_id_list.emplace_back(edge_id);
		v_to.edge_id_list.emplace_back(reverse_edge_id);
	}

	void createEdgeTo(const Vertex<Data>& from, const Vertex<Data>& to, const CostType& cost) {
		edge_list.emplace_back(from, to, cost, edge_size++);
		auto edge_id = edge_list.back().id;

		auto& v_from = vertex_list[from.id];
		v_from.edge_id_list.emplace_back(edge_id);
	}

	void solveByDijkstra(int start, const CostType max_cost) {
		// 初期化
		std::vector<CostType> d(vertex_size);
		std::vector<int> prev(vertex_size);
		std::fill(d.begin(), d.end(), max_cost);
		std::vector<bool> is_use(vertex_size);

		std::fill(is_use.begin(), is_use.end(), false);

		struct queue_data {
			int id;
			CostType cost;
		};

		struct queue_func {
			int operator()(const queue_data& ia, const queue_data& ib) {
				return ia.cost > ib.cost;
			}
		};

		auto queue = std::priority_queue<queue_data, std::vector<queue_data>, queue_func>(queue_func());

		queue.push(queue_data { 0, 0 } );
		d[start] = 0;

		// 実行
		while(!queue.empty()) {
			const queue_data qd = queue.top();
			const int u_id = qd.id;
			is_use[u_id] = false;
			queue.pop();

			for(const auto e_id : vertex_list[u_id].edge_id_list) {
				const auto edge = edge_list[e_id];
				const CostType cost = d[u_id] + edge.cost;
				if(d[edge.to_id] > cost) {
					d[edge.to_id] = cost;
					prev[edge.to_id] = u_id;

					if(!is_use[edge.to_id]) {
						queue.push(queue_data{ edge.to_id, cost });
						is_use[edge.to_id] = true;
					}
				}
			}
		}

		for(size_t i = 0; i < prev.size(); ++i) {
			printf("%d%d\n", vertex_list[prev[i]].data, vertex_list[i].data);
		}
	}

	void show() {
		printf("=== Vertex ===\n"); 
		for(Vertex<Data>& it : vertex_list) {
			printf("%d: %d\n", it.id, it.data);
		}
		printf("=== Edge ===\n");
		for(Edge<CostType>& it : edge_list) {
			printf("%d: %d (%d%d)\n", it.id, it.cost, it.from_id, it.to_id);
		}
	}
private:
	std::vector<Vertex<Data>> vertex_list;
	std::vector<Edge<CostType>> edge_list;
	int vertex_size;
	int edge_size;
};
  • Edge.h
#pragma once

template <typename Data, typename CostType>
class Graph;

template <typename Data>
class Vertex;

template <typename CostType>
class Edge {
	template <typename Data, typename CostType>
	friend class Graph; 
	template <typename T>
	friend class Vertex;
	
public:
	template <typename T>
	Edge(const Vertex<T>& from, const Vertex<T>& to, const CostType& cost, int id) : from_id(from.id), to_id(to.id), cost(cost), id(id) { }
private:
	CostType cost;
	int id;
	int from_id;
	int to_id;
};
  • Vertex.h
#pragma once

#include <vector>

template <typename Data, typename CostType>
class Graph;

template <typename Data>
class Edge;

template <typename Data>
class Vertex {
	template <typename Data, typename CostType>
	friend class Graph;
	friend Edge<Data>;
	
public:
	Vertex(const Data& data, int id) : data(data), edge_id_list(0), id(id) { }

private:
	Data data;
	int id;
	std::vector<int> edge_id_list;
	static int max_id;
};

template <typename Data>
int Vertex<Data>::max_id = 0;

C++17予定らしいawait

C#では便利なawaitがありますが、C++にも導入予定らしいです。これでマルチスレッド周りがより便利になりますね。VC++ 2013Nov CTPより、VisualStudioでもインテリセンスはキキませんがコンパイルができるので色々遊べます。ジェネリックラムダとかconstexprとか無制限unionとか普通に使いたいですね。

#include <cstdio>

#include <ppltasks.h>
#include <pplawait.h>

concurrency::task<void> func() __resumable {
	Sleep(100);
}

// __awaitを使う関数は__resumableがついていないとダメ
concurrency::task<void> execute_func() __resumable {
	printf("start of func\n");
	__await func(); // ここでfuncの終了を待ち合わせる
	printf("end of func\n");
}

int main() {
	printf("start of main\n");
	auto task = execute_func(); // 関数の実行が終わらなくても
	printf("wait in main\n"); // ここで実行される
	task.wait(); // execute_funcの終了を待つ
	printf("join at main\n");
	getchar();
	return 0;
}