前回 の続き。
作った immutable_string_impl を用いて基本的な部分を実装してみます。
と、その前に、 immutable_string_impl の設計を、少し見直します。
せっかく immutable なので、ハッシュ値を予め計算しておくことで、比較の高速化を図りたいのです。
また、名前に関しても、もう一段階 impl を噛ませたい都合から immutable_string_buffer と改名します。
では早速、見てみましょう。
// とりあえず char のみ #include <cassert> #include <boost/compressed_pair.hpp> namespace gintenlib { namespace intrusive_hook_ // ADL 回避用名前空間 { // 普通の delete 演算子を呼び出す deleter // http://gintenlib.sourceforge.jp/gintenlib/deleter.hpp struct deleter { typedef void result_type; template<typename T> void operator()( T* p ) const { delete p; } }; // struct deleter // 本体 template<typename Derived, typename Deleter = deleter> class intrusive_hook { typedef intrusive_hook this_type; protected: // 型定義 typedef int counter_type; typedef Deleter deleter; // デフォルトコンストラクタ intrusive_hook() : pair_( 0, deleter() ) {} // コピーコンストラクタ（コピーしない） intrusive_hook( this_type const& ) : pair_( 0, deleter() ) {} // 削除子指定 intrusive_hook( Deleter const& d ) : pair_( 0, d ) {} // 初期カウント指定 intrusive_hook( counter_type initial_count ) : pair_( initial_count, deleter() ) {} // 初期カウント指定＆削除子指定 intrusive_hook( counter_type initial_count, Deleter const& d ) : pair_( initial_count, d ) {} // operator=（何もしない） this_type& operator=( const this_type& ) { return *this; } // メンバアクセス counter_type use_count() const { return count_(); } deleter& get_deleter() { return deleter_(); } deleter const& get_deleter() const { return deleter_(); } private: // メンバ typedef boost::compressed_pair<counter_type, deleter> pair_type; mutable pair_type pair_; // 補助関数 counter_type& count_() const { return pair_.first(); } deleter& deleter_() const { return pair_.second(); } // Derived からのメンバアクセス static counter_type& get_count( Derived const& x ) { return static_cast<this_type const&>(x).count_(); } static deleter const& get_deleter( Derived const& x ) { return static_cast<this_type const&>(x).get_deleter(); } // カウントの増減 // ADLによって呼び出される friend void intrusive_ptr_add_ref( Derived const* p ) { using namespace std; assert( p != 0 ); counter_type& count = get_count(*p); assert( count >= 0 ); ++count; } friend void intrusive_ptr_release( Derived const* p ) { using namespace std; assert( p != 0 ); counter_type& count = get_count(*p); assert( count > 0 ); if( --count == 0 ) { // p の破棄処理の途中で deleter が削除されると困るのでコピーする deleter d = get_deleter(*p); // 削除本体 d(p); } } // カウントチェック（ boost::intrusive_ptr では使われない） friend void intrusive_ptr_use_count( Derived const* p ) { using namespace std; assert( p != 0 ); counter_type const count = get_count(*p); assert( count >= 0 ); return count; } }; // intrusive_hook<Derived, Deleter> } // namespace intrusive_hook_ // 単純に gintenlib:: で使えるようにする using namespace intrusive_hook_; // さらに部品を作る // 可変領域に対するデリータ struct variable_region_deleter { typedef void result_type; template<typename T> void operator()( T* p ) const { // デストラクタをまず呼び出す p->~T(); // 領域を解放する void const* const vp = p; delete [] static_cast<char const*>(vp); } }; // variable_region_deleter // 固定長バッファの初期化 // http://gintenlib.sourceforge.jp/gintenlib/assign.hpp template<typename FwdIter, typename InIter> InIter assign( FwdIter const& begin, FwdIter const& end, InIter src ) { for( FwdIter it = begin; it != end; ++it, ++src ) { *it = *src; } return src; } } // namespace gintenlib #include <cstring> #include <boost/intrusive_ptr.hpp> #include <boost/functional/hash.hpp> namespace gintenlib { // 本題 class immutable_string_buffer : public intrusive_hook<immutable_string_buffer, variable_region_deleter> { typedef immutable_string_buffer this_type; typedef intrusive_hook<immutable_string_buffer, variable_region_deleter> base_; public: typedef boost::intrusive_ptr<this_type const> pointer; // バッファ取得 std::size_t size() const { return buf_size; } char const* c_str() const { return buf; } // ハッシュ値取得 std::size_t hash_value() const { return hashed; } // オブジェクト製作 // 領域サイズとイテレータから製作 template<typename Iter> static pointer create( std::size_t size, Iter const& src ) { // intrusive_ptr に格納しておけば、例外が投げられてもリークしない boost::intrusive_ptr<this_type> const p = create_(size); // バッファを初期化する gintenlib::assign( &p->buf[0], &p->buf[size], src ); // NULL終端 p->buf[size] = 0; // ハッシュ値を計算する p->hashed = boost::hash_range( &p->buf[0], &p->buf[size] ); return p; } // より一般的な方。イテレータ対から製作 template<typename Iter> static pointer create( Iter const& begin, Iter const& end ) { return create( std::distance( begin, end ), begin ); } // 空文字列 static pointer create() { static pointer const p = create_(0); return p; } private: // メンバ std::size_t hashed; // ハッシュ値 std::size_t const buf_size; // 領域長は固定 char buf[1]; // 外部からの構築禁止 explicit immutable_string_buffer( std::size_t size ) // never throws : hashed(0), buf_size( size ) {} // 指定された削除子以外からの破棄を禁止 friend class variable_region_deleter; ~immutable_string_buffer() throw () {} // 未初期化状態のオブジェクトを製作 static boost::intrusive_ptr<this_type> create_( std::size_t size ) { // 領域を確保し void* const vp = ::new char[ sizeof(this_type) + size ]; // placement new でオブジェクトを構築する return boost::intrusive_ptr<this_type>( ::new (vp) this_type(size) ); } }; // immutable_string_buffer } // namespace gintenlib
前半は細かい部品です。殆どは前回作ったので問題ないでしょう。
gintenlib::assign に関しても、動作は非常に分かりやすいはずです。
本題の immutable_string_buffer ですが、ハッシュ値を計算する都合上、
非 const のオブジェクトを外部からアクセス出来ないように工夫してみました。
それと例外安全関係の配慮を少しして、これでバッファは（ひとまず）完成。
そうしたら今度は、そのバッファをラップして扱い易くしたクラスを作ります。
これは、直接 intrusive_ptr
普通のクラスのように扱えた方が見通しもいいですし、後から小細工もしやすいからです。
後から小細工する、というのは、具体的には flyweight デザインパターンを仕込みます。乞うご期待。
namespace gintenlib // 実装用クラス // flyweight デザインパターンを使うために分離する class immutable_string_impl { typedef immutable_string_impl this_type; typedef immutable_string_buffer buffer; public: immutable_string_impl() : p( buffer::create() ) {} template<typename Iter> immutable_string_impl( Iter const& begin, Iter const& end ) : p( buffer::create( begin, end ) ) {} template<typename Iter> immutable_string_impl( std::size_t n, Iter const& it ) : p( buffer::create( n, it ) ) {} // 基本情報 std::size_t size() const { return p->size(); } char const* c_str() const { return p->c_str(); } // swap 関連 void swap( this_type& other ){ p.swap( other.p ); } friend void swap( this_type& one, this_type& another ){ return one.swap( another ); } // ハッシュ値関連 std::size_t hash_value() const { return p->hash_value(); } friend std::size_t hash_value( this_type const& t ){ return t.hash_value(); } // 等値比較関連 friend bool operator==( this_type const& lhs, this_type const& rhs ) { if( lhs.hash_value() == rhs.hash_value() ) { if( lhs.size() == rhs.size() ) { return std::strcmp( lhs.c_str(), rhs.c_str() ) == 0; } } return false; } private: boost::intrusive_ptr<buffer const> p; }; // immutable_string_impl } namespace gintenlib
特に問題はないでしょう。
最後に、この実装クラスを使って、インターフェイスを整えた immutable_string を作ります。
#include <string> #include <iterator> #include <iostream> #include <boost/operators.hpp> namespace gintenlib { // 本体 class immutable_string : boost::totally_ordered<immutable_string>, boost::totally_ordered<immutable_string, std::string>, boost::totally_ordered<immutable_string, char const*> { typedef immutable_string this_type; typedef immutable_string_impl impl_type; public: // 型定義 typedef char value_type; typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; typedef char const& reference; typedef char const& const_reference; typedef char const* pointer; typedef char const* const_pointer; typedef char const* iterator; typedef char const* const_iterator; typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<iterator> const_reverse_iterator; // 構築 immutable_string() {} immutable_string( char const* p ) : impl( std::strlen(p), p ) {} immutable_string( std::string const& str ) : impl( str.size(), str.begin() ) {} // range から構築 template<typename Iter> immutable_string( Iter const& begin, Iter const& end ) : impl( begin, end ) {} // swap void swap( this_type& other ) { impl.swap( other.impl ); } friend void swap( this_type& one, this_type& another ) { one.swap( another ); } // 文字列取得 char const* c_str() const { return impl.c_str(); } std::string str() const { return std::string( c_str(), size() ); } friend std::string to_string( this_type const& x ) { return x.str(); } // 文字列長 size_type size() const { return impl.size(); } size_type length() const { return size(); } bool empty() const { return size() == 0; } // イテレータアクセス const_iterator begin() const { return c_str(); } const_iterator end() const { return c_str() + size(); } const_reverse_iterator rbegin() const { return const_reverse_iterator( end() ); } const_reverse_iterator rend() const { return const_reverse_iterator( begin() ); } // hash std::size_t hash_value() const { return impl.hash_value(); } friend std::size_t hash_value( this_type const& x ) { return x.hash_value(); } // ストリーム出力 friend std::ostream& operator<<( std::ostream& lhs, this_type const& rhs ) { lhs.write( rhs.c_str(), rhs.size() ); return lhs; } friend std::istream& operator>>( std::istream& lhs, this_type& rhs ) { std::string buffer; lhs >> buffer; this_type( buffer ).swap( rhs ); return lhs; } // 比較 // 等値比較 friend bool operator==( this_type const& lhs, this_type const& rhs ) { return lhs.impl == rhs.impl; } friend bool operator==( this_type const& lhs, char const* rhs ) { return std::strcmp( lhs.c_str(), rhs ) == 0; } friend bool operator==( this_type const& lhs, std::string const& rhs ) { return lhs.c_str() == rhs; } // 辞書順比較 friend bool operator<( this_type const& lhs, this_type const& rhs ) { return std::strcmp( lhs.c_str(), rhs.c_str() ) < 0; } friend bool operator<( this_type const& lhs, char const* rhs ) { return std::strcmp( lhs.c_str(), rhs ) < 0; } friend bool operator>( this_type const& lhs, char const* rhs ) { return std::strcmp( lhs.c_str(), rhs ) > 0; } friend bool operator<( this_type const& lhs, std::string const& rhs ) { return lhs.c_str() < rhs; } friend bool operator>( this_type const& lhs, std::string const& rhs ) { return lhs.c_str() > rhs; } // 残りは Boost.Operators で自動生成 private: impl_type impl; }; } // namespace gintenlib
こんな感じ。定義したメンバは最小限ですが、特に不便はないでしょう。
きちんと iterator 関連や begin(), end() さえ定義しておけば、
Boost.StringAlgo の恩恵にあやかれる筈ですので、メンバ変数は多い必要は特にありません。
また演算子多重定義は面倒なので、 Boost.Operators を使っています。基本ですね。
では早速、テストしてみましょう。
#include <algorithm> #include <boost/lambda/lambda.hpp> int main() { using namespace std; using boost::lambda::_1; // 入力を得る gintenlib::immutable_string s1; cin >> s1; // サイズを得る cout << s1.size() << endl; // ハッシュ値を得る cout << hash_value(s1) << endl; // 反転して出力してみる for_each( s1.rbegin(), s1.rend(), cout << _1 ); cout << endl; }
>./a.out >hoge 4 1213632650 egoh
上手くいったようです。
次回は文字列連結を出来るようにしつつ、 std::string との速度比較をやってみようと思います。
