株式会社エス・スリー・フォー

STL in Tools.h++

はじめに

標準C++ライブラリが提供するコンテナは、

vector (可変長配列)
list (双方向リスト)
deque (両端キュー)
set, multiset (二進木による集合)
map, multimap (二進木による辞書)

の7種です。プログラマはこれらのコンテナから目的に応じたものを選択してコーディングを行ないます。

これらコンテナ内の要素の検索に要する時間計算量は vector/list/deque では O(N)、二進木を用いた set(multiset),map(multimap) でも O(logN) です。より速いコンテナが欲しくなることもあるでしょう。

時間計算量が O(logN) より小さい(高速な)コンテナに、"ハッシュ表"があります。ハッシュ表は、それに与えるハッシュ関数とテーブルサイズを適切に選べば、検索に要する時間計算量を O(1)、すなわちほとんど瞬時に検索を実行することができます。

Tools.h++ はSTLコンテナとコンパチブルな"ハッシュ表による set/map"を独自に定義/実装しています。Tools.h++ はそれらを RWTValHashSet や RWTValHashMap 等の実装に用いていますし、プログラマが直接それらを利用することもできるようです。

Tools.h++ の STLコンテナ

Tools.h++には、

rw_slist: (単方向リスト)
rw_hashset: (要素の重複を許さない、ハッシュ表による集合)
rw_hashmultiset: (要素の重複を許す、ハッシュ表による集合)
rw_hashmap: (要素の重複を許さない、ハッシュ表による辞書)
rw_hashmultimap: (要素の重複を許す、ハッシュ表による辞書)

の5種類のSTLコンパチブルなコンテナが、ヘッダファイル:

#include <rw/stdex/slist.h> (rw_slist)
#include <rw/stdex/hashset.h> (rw_hashset)
#include <rw/stdex/hashmset.h> (rw_hashmultiset)
#include <rw/stdex/hashmap.h> (rw_hashmap)
#include <rw/stdex/hashmmap.h> (rw_hashmultimap)

に定義されています。

また、これらコンテナのイテレータはすべて ForwardIterator カテゴリに属します。したがって、rw_XXXX::iterator IT;に対し、--IT; IT--; できません。

また、operator->()が定義されていないので、IT->func(); できません。少々面倒ですが (*IT).func(); してください。

rw_slist<T,A>

テンプレート引数T,Aにはそれぞれ、

T: 要素の型
A: アロケータ

を与えます。たとえば RWCString を要素とする rw_slist は、

rw_slist<RWCString, std::allocator<RWCString> >

となります。

rw_slist();: コンストラクタ。要素数 0 の rw_slist を作ります。
rw_slist(const rw_slist& x);: コピーコンストラクタ。 xの全要素がコピーされます。
rw_slist(const_iterator begin, const_iterator end);
rw_slist(const T* begin, const T* end);: コンストラクタ。シーケンス[begin,end)がコピーされます。
rw_slist(size_type n, const T& value);: コンストラクタ。 n 個の value が要素となります。
~rw_slist();: デストラクタ。コンテナ内の全要素が棄てられます。
rw_slist& operator=(const rw_slist& x);: コピー演算子。x の全要素がコピーされます。
void swap(rw_slist& x);: *this と x の全要素を交換します。
iterator begin();
const_iterator begin() const;: 最初の要素を指すイテレータを返します。
iterator end();
const_iterator end() const;: 最後の要素(の直後)を指すイテレータを返します。
bool empty() const;: コンテナ内の要素数が 0 なら true を返します。
size_type size() const;: コンテナ内の要素数を返します。
size_type max_size() const;: コンテナ内に収容できる最大要素数を返します。
T& front();
const T& front() const;: 先頭の要素を返します。
T& back();
const T& back() const;: 末尾の要素を返します。
void push_front(const T& t);: t を先頭に挿入します。
void push_back(const T& t);: t を末尾に挿入します。
iterator insert(iterator loc, const T& val);: val を loc の位置に挿入します。
void insert(iterator loc, const_iterator first, const_iterator bound);
void insert(iterator loc, const T* first, const T* bound);: シーケンス [first,bound) を loc の位置に挿入します。
void insert(iterator loc, size_type n, const T& t);: n 個の t を loc の位置に挿入します。
void splice(iterator pos, rw_slist& donor);: donorにある全要素を pos の位置に挿入します。その結果 donor は空になります。
void splice(iterator pos, rw_slist& donor, iterator item);: donor 内の要素 *item を pos の位置に挿入します。donor から *item が削除されます。
void splice(iterator pos, rw_slist& donor,iterator begin, iterator end);: donor 内のシーケンス [begin,end) を pos の位置に挿入します。donor からシーケンス [begin,end) が削除されます。
void remove(const T& val);: valと等しい要素があれば、そのすべてをコンテナから削除します。
void unique();: 隣接する相等しい要素を削除します。
void merge(rw_slist& x);: 昇順にソートされた *this と x をマージします。その結果 x は空になります。
void reverse();: コンテナ内の要素の並びを逆転します。
void sort();: コンテナ内の要素を昇順に並び替えます。

rw_hashset<T,Hash,EQ,A>

テンプレート引数T,Hash,EQ,Aにはそれぞれ、

T: 要素の型
Hash: ハッシュ関数オブジェクト
EQ: 同値判定オブジェクト
A: アロケータ

を与えます。

関数オブジェクト Hash は const T& を引数とし、unsigned long を返す operator() を定義します。EQ は std::equal_to を使えばいいでしょう。

たとえば RWCString を要素とする rw_hashset は、

struct str_hash {
  unsigned long operator()(const RWCString& x) const {
    return x.hash();
  }
};

rw_hashset<RWCString, str_hash, std::equal_to<RWCString> std::allocator<RWCString> >

となります。

rw_hashset(size_type sz = 1024, const Hash& h = Hash(), const EQ& eq = EQ());: コンストラクタ。引数 sz にはハッシュテーブルの大きさを与えます。これが小さいとスピードが落ちます。
rw_hashset(const typename value_type* first, const typename value_type* bound, size_type sz = 1024, const Hash& h = Hash(), const EQ& eq = EQ() );
rw_hashset(const_iterator first,const_iterator bound, size_type sz = 1024, const Hash& h = Hash(), const EQ& eq = EQ());: コンストラクタ。シーケンス[first,bound)が要素となります。
~rw_hashset() {}: デストラクタ。全要素が棄てられます。
rw_hashset& operator=(const rw_hashset& t);: コピー演算子。t の全要素がコピーされます。
bool operator==(const rw_hashset& t) const;: 等値演算子。*this と t の要素数が等しく、かつ *this の全要素が t にも存在するとき true を返します。
iterator begin() const;: 先頭の要素を指すイテレータを返します。
iterator end() const;: 末尾の要素(の直後)を指すイテレータを返します。
bool empty() const;: コンテナが空であれば true を返します。
size_type size() const;: コンテナ内の要素数を返します。
size_type count(const_reference key) const;: key と等しい要素の数を返します。
iterator find(const_reference key) const;: key と等しい要素を指すイテレータを返します。
iterator lower_bound(const_reference key) const;: key と等しいか大きい最初の要素を指すイテレータを返します。
iterator upper_bound(const_reference key) const;: key と等しい要素の次に位置する要素を指すイテレータを返します。
std::pair<iterator,iterator> equal_range(const_reference key) const;: lower_bound/upper_bound の結果の組を返します。
size_type capacity() const;: ハッシュテーブルの大きさを返します。
float fill_ratio() const;: size()/capacity() を返します。
void resize(size_type s);: ハッシュテーブルの大きさを s に設定します。size() に比例した処理時間を要します。
void swap(rw_hashset& t);: *this と t の全要素を交換します。
std::pair<iterator,bool> insert(const_reference k);: k をコンテナに挿入します。
size_type insert(const value_type* first, const value_type* bound);
size_type insert(const_iterator first, const_iterator bound);: シーケンス [first,bound) をコンテナに挿入し、挿入された要素数を返します。
iterator insert(iterator , const_reference k);: k をコンテナに挿入します。第 1 引数は無視されます。
size_type erase(const_reference t);: t と等しい要素を削除します。
iterator erase(iterator it);: it が指す要素を削除します。
iterator erase(iterator it, iterator bound);: シーケンス [it,bound) を削除します。
void clear();: 全要素を削除します。

rw_hashmultiset<T,Hash,EQ,A>

相等しい要素の重複を許す事を除いて、rw_hashset と同じです。

rw_hashmap<Key,T,Hash,EQ,A>

テンプレート引数Key,T,Hash,EQ,Aにはそれぞれ、

Key: キーの型
T: 要素の型
Hash: ハッシュ関数オブジェクト
EQ: 同値判定オブジェクト
A: アロケータ

を与えます。

関数オブジェクト Hash は const Key& を引数とし、unsigned long を返す operator()を定義します。EQはstd::equal_toを使えばいいでしょう。

たとえば RWCString を Key, int を T とする rw_hashmap は、

struct str_hash {
  unsigned long operator()(const RWCString& x) const {
    return x.hash();
  }
};

rw_hashmap<RWCString, int, strhash, std::equal_to<RWCString>, 
   std::allocator<std::pair<const RWCString,int> > >

となります。rw_hashmap<Key,T,Hash,EQ,A> に格納される要素の型(value_type)はstd::pair<const Key,T> >です。

rw_hashmap(size_type sz = 1024, const Hash& h = Hash(), const EQ& eq = EQ());: コンストラクタ。引数 sz にはハッシュテーブルの大きさを与えます。これが小さいとスピードが落ちます。
rw_hashmap(const value_type* first, const value_type* bound, size_type sz = 1024, const Hash& h = Hash(), const EQ& eq = EQ());
rw_hashmap(const_iterator first, const_iterator bound,size_type sz = 1024, const Hash& h = Hash(), const EQ& eq = EQ());: コンストラクタ。シーケンス [first,bound) が要素となります。
rw_hashmap(const rw_hashmap& t);: コピー演算子。t の全要素がコピーされます。
rw_hashmap& operator=(const rw_hashmap& t);: コピー演算子。t の全要素がコピーされます。
~rw_hashmap() {}: デストラクタ。全要素が棄てられます。
bool operator==(const rw_hashmap& t) const;: 等値演算子。*this と t の要素数が等しく、かつ *this の全要素が t にも存在するとき true を返します。
T& operator[](const key_type& k);: key と等しい要素を探し、それに対応する T の参照を返します。key と等しい要素が見つからないときは新たな T() を生成して、その参照を返します。
iterator begin();
const_iterator begin() const;: 先頭の要素を指すイテレータを返します。
iterator end();
const_iterator end() const;: 末尾の要素(の直後)を指すイテレータを返します。
bool empty() const;: コンテナが空であれば true を返します。
bool equal_by_keys(const rw_hashmap& t) const;: ( T に対する比較をせず、) Key の等値のみに着目して *this と t を比較し、同じであれば true を返します。
size_type size() const;: コンテナ内の要素数を返します。
size_type count(const key_type& k) const;: key と等しい要素の数を返します。
const_iterator find(const key_type& k) const;
iterator find(const key_type& k);: key と等しい要素を指すイテレータを返します。
iterator lower_bound(const key_type& k);
const_iterator lower_bound(const key_type& k) const;: key と等しい課大きい最初の要素を指すイテレータを返します。
iterator upper_bound(const key_type& k);
const_iterator upper_bound(const key_type& k) const;: key と等しい要素の次に位置する要素を指すイテレータを返します。
std::pair<iterator,iterator> equal_range(const key_type& k);
std::pair<const_iterator,const_iterator> equal_range(const key_type& k) const;: lower_bound/upper_bound の結果の組を返します。
size_type capacity() const;: ハッシュテーブルの大きさを返します。
float fill_ratio() const;: size()/capacity() を返します。
void resize(size_t n);: ハッシュテーブルの大きさを s に設定します。size() に比例した処理時間を要します。
void swap(rw_hashmap& t);: *this と t の全要素を交換します。
std::pair<iterator,bool> insert(const value_type& pr);: pr をコンテナに挿入します。
iterator insert(iterator ,const value_type& pr);: pr をコンテナに挿入します。第 1 引数は無視されます。
size_type insert(const value_type* first, const value_type* bound);
size_type insert(const_iterator first, const_iterator bound);: シーケンス [first,bound) をコンテナに挿入し、挿入された要素数を返します。
size_type erase(const key_type& k);: k と等しい要素を削除し、削除した数を返します。
iterator erase(iterator it);: it が指す要素を削除します。
iterator erase(iterator it, iterator bound);: シーケンス [it,bound) を削除します。
void clear();: 全要素を削除します。

rw_hashmultimap<Key,T,Hash,EQ,A>

相等しい要素の重複を許す事を除いて、rw_hashmap と同じです。(メンバ関数 V& operator[](const key_type& k); はありません。)

setとrw_hashsetの速度比較

それでは実際に set と rwq_hashset との処理速度を比較してみましょう。テストプログラムを以下に示します。

#include <windows.h>
#include <iostream>
#include <set>

#include <rw/stdex/hashset.h>
#include <rw/cstring.h>

struct strhash {
  unsigned long operator()(const RWCString& x) const {
    return x.hash();
  }
};

RWCString* table = 0;
const int N = 10000;

void init_table() {
  if ( table ) return;
  table = new RWCString[N]; 
  char buf[8];
  for ( int i = 0; i < N; ++i ) { 
    sprintf(buf, "%d", i);
    table[i] = buf;
  }
}

/*
 * N 個の RWCString をコンテナに挿入/削除する。
 * 10回繰り返して、所要時間を算出する。
 */
template<class Container>
long time_trial(Container& c) {
  int i;
  init_table();
  long t = GetTickCount();
  for ( int x = 0; x < 10; ++x ) {
    for ( i = 0; i < N; ++i )
      c.insert(table[i]);
    for ( i = 0; i < N; ++i )
      c.erase(table[i]);
  }
  return GetTickCount() - t;  
}

int main() {
  std::set<RWCString> s;
  rw_hashset<RWCString,strhash,std::equal_to<RWCString>,std::allocator<RWCString> > hs(N+N);

  cout << "rw_hashset : " << time_trial(hs) << "[ms]" << endl;
  cout << "set        : " << time_trial(s)  << "[ms]" << endl;

  return 0;
}

僕のマシンでの実測値は、rw_hashset : 1532[ms] , set : 3425[ms] でした。rw_hashset が setより約2倍高速という結果となりました。これは set に対する要素の挿入/削除の際に要素の比較が logN 回行われるのに対し、rw_hashset では要素の比較がほとんど行なわれないことによるものです。比較が低コスト(高速)な要素、たとえば int などではこの速度差は小さく、あるいは逆転することもあるでしょう。

επιστημη 2006-04-05