B+-treeをC++で実装開始
ここのところ、JavaとPythonばかりでC++から離れていたので久しぶりに書いてみた。
#ifndef __MASA_TREE_HPP__ #define __MASA_TREE_HPP__ #include <vector> #include <utility> #include <queue> namespace masahase{ namespace util{ template<class I,class V> class Imap{ public: virtual size_type size() const{ return 0; } virtual bool empty() const{ return false; } virtual bool insert(const I& index,const V& value)=0; virtual void erase(const I& index)=0; virtual void clear() =0; virtual V get(I& index) const{ return NULL; } } template<class I,class V> class b_plus_tree : public Imap{ public: size_type size() const; bool empty() const; bool insert(const I& index,const V& value); void erase(const i& index); void clear(); V get(I& index) const; private: class page{ public: int value[9]; int parent; bool edge; page(); } class v_page{ public: int value[4]; int parent; int prev,next; v_page(); } std::vector<pair<I,V> > value_list; std::vector<I> index_list; std::vector<page> index_page; std::vector<v_page> value_page; std::queue<int> free_value; int insert_value_list(pair<I,V> value); int insert_index_list(I index); } } } #endif
とりあえずヘッダのみ。中身はまだ書き中。templateを今回はじめて使ってみた。使い方があっているのかどうかは怪しい。
追記:
いつものごとく勉強用のmercurialリポジトリに公開しているので、間違いを発見した場合リポジトリの最新版でも修正されていないかどうか確認したうえで、メールもしくはコメントをください。
http://www.masahase.mydns.jp/hg/lib-study/
この記事を随時更新などという手間のかかることはしないので時間がたつほどリポジトリとの差異は大きくなります。