The Articles - Elegant C++

Problem
std::mapより高速なコンテナはありませんか？

Solution
std::mapは十分速いコンテナですが、より速いハッシュコンテナが存在します。

代表的なハッシュコンテナ(の実装)としては次のようなものがあります。
・次期C++標準unordered_map
・SGI系hash_map
・GoogleCode sparse_hash_map
・GoogleCode dense_hash_map

これらのハッシュコンテナについて、std::mapと処理速度の比較を行ってみました。

評価には次のコードを使用しました。
今回は、std::stringをキーとして100万個の要素を追加し、200万個の検索を行いますので、検索の半分は存在しないキーでの検索になります。
コンパイラはgcc version 4.1.2で、最適化オプションは-O1を使用し、timeコマンドで処理時間を測定しました。
また、hash関数はstd::tr1::hashを用いました。

#include <iostream>
#include <sstream>
#include <map>
#include <ext/hash_map>
#include <tr1/unordered_map>
#include <google/sparse_hash_map>
#include <google/dense_hash_map>

inline std::string toString(int n)
{
  std::stringstream stm;
  stm << n;
  return stm.str();
}

int main()
{
#if 1
  std::map<std::string, int> data;
#endif
#if 0
  std::tr1::unordered_map<std::string, int> data;
#endif
#if 0
  __gnu_cxx::hash_map<std::string, int, std::tr1::hash<std::string> > data;
#endif
#if 0
  google::sparse_hash_map<std::string, int, std::tr1::hash<std::string> > data;
#endif
#if 0
  google::dense_hash_map<std::string, int, std::tr1::hash<std::string> > data;
  data.set_empty_key("");
#endif
  
  for (int n = 0; n < 1000000; ++n) {
    data[toString(n)] = n;
  }
  
  for (int n = 0; n < 2000000; ++n) {
    data.find(toString(n));
  }
  
  return 0;
}

処理時間順の測定結果は次のとおりです。

google::dense_hash_map
real    0m4.717s
user    0m4.572s
sys     0m0.124s

__gnu_cxx::hash_map
real    0m4.741s
user    0m4.648s
sys     0m0.088s

std::tr1::unordered_map
real    0m4.924s
user    0m4.800s
sys     0m0.104s

std::map
real    0m7.549s
user    0m7.416s
sys     0m0.116s

google::sparse_hash_map
real    0m10.863s
user    0m10.713s
sys     0m0.120s

最も速かったのはdense_hash_mapでした。さすがはGoogleといったところでしょうか。
最も遅かったのはsparse_hash_mapでしたが、sparse_hash_mapは消費メモリを抑えることを目的に処理速度を犠牲にしたハッシュコンテナなので、当然の結果と言えます。

最後に、ハッシュに限ったことではありませんが、ライブラリの処理速度は実装に依存します。
使用の際には、自分の処理系で、プロファイリングを行うことをお薦めします。

関連記事
・ハッシュコンテナ
・ハッシュコンテナ - Part2
・ハッシュコンテナ - Part3

Problem
shared_ptrとは、どのようなもなのでしょうか？

Solution
shared_ptrとは、C++の次期バージョンC++0xに含まれるスマートポインタで、そのオリジナルはboostのboost::shared_ptrです。
その働きはポインタをラップし、参照カウントがゼロになったときにポインタを自動的にdeleteします。

#include <iostream>
#include <tr1/memory>

class Object {
public:
  Object() { std::cout << "    Object::Object()" << std::endl; }
  ~Object() { std::cout << "    Object::~Object()" << std::endl; }
};

void func()
{
  std::cout << "  func() begin" << std::endl;
  std::tr1::shared_ptr<Object> ptr(new Object);
  std::cout << "  func() end" << std::endl;
}

int main()
{
  std::cout << "main() begin" << std::endl;
  func();
  std::cout << "main() end" << std::endl;
  return 0;
}

実行結果

main() begin
  func() begin
    Object::Object()
  func() end
    Object::~Object()
main() end

加えて、deleterを指定することが可能です。

#include <iostream>
#include <tr1/memory>

class Object {
public:
  Object() { std::cout << "    Object::Object()" << std::endl; }
  ~Object() { std::cout << "    Object::~Object()" << std::endl; }
};

template<class T>
struct log_deleter {
  void operator()(T* x) const
  {
    std::cout << "log_deleter: " << x << std::endl;
    delete x;
  }
};

void func()
{
  std::cout << "  func() begin" << std::endl;
  std::tr1::shared_ptr<Object> ptr(new Object, log_deleter<Object>());
  std::cout << "  func() end" << std::endl;
}

int main()
{
  std::cout << "main() begin" << std::endl;
  func();
  std::cout << "main() end" << std::endl;
  return 0;
}

実行結果

main() begin
  func() begin
    Object::Object()
  func() end
log_deleter: 0x804b008
    Object::~Object()
main() end

他の特徴として、ポインタの型に柔軟性があります。
例えば、通常、基底クラスのポインタ型を用いて派生クラスのポインタをdeleteする場合、仮想デストラクタが必要になります。
しかし、shared_ptrを使用する場合は、仮想デストラクタを必要としません。

#include <iostream>
#include <tr1/memory>

class Object {
public:
  Object() { std::cout << "    Object::Object()" << std::endl; }
  ~Object() { std::cout << "    Object::~Object()" << std::endl; }
};

class DerivedObject : public Object {
public:
  DerivedObject() { std::cout << "    DerivedObject::DerivedObject()" << std::endl; }
  ~DerivedObject() { std::cout << "    DerivedObject::~DerivedObject()" << std::endl; }
};

void func()
{
  std::cout << "  func() begin" << std::endl;
  std::tr1::shared_ptr<Object> ptr(new DerivedObject);
  std::cout << "  func() end" << std::endl;
}

int main()
{
  std::cout << "main() begin" << std::endl;
  func();
  std::cout << "main() end" << std::endl;
  return 0;
}

実行結果

main() begin
  func() begin
    Object::Object()
    DerivedObject::DerivedObject()
  func() end
    DerivedObject::~DerivedObject()
    Object::~Object()
main() end

また、型を指定せずvoidとすることも可能で、この場合でも正しくdeleteされます。
ただし、ポインタを使用する際はキャストが必要になります。

#include <iostream>
#include <tr1/memory>

class Object {
public:
  Object() { std::cout << "    Object::Object()" << std::endl; }
  ~Object() { std::cout << "    Object::~Object()" << std::endl; }
};

class DerivedObject : public Object {
public:
  DerivedObject() { std::cout << "    DerivedObject::DerivedObject()" << std::endl; }
  ~DerivedObject() { std::cout << "    DerivedObject::~DerivedObject()" << std::endl; }
};

void func()
{
  std::cout << "  func() begin" << std::endl;
  std::tr1::shared_ptr<Object> ptr(new DerivedObject);
  std::cout << "  func() end" << std::endl;
}

int main()
{
  std::cout << "main() begin" << std::endl;
  func();
  std::cout << "main() end" << std::endl;
  return 0;
}

実行結果

main() begin
  func() begin
    Object::Object()
    DerivedObject::DerivedObject()
  func() end
    DerivedObject::~DerivedObject()
    Object::~Object()
main() end

更に詳細が知りたい場合は、boost::shared_ptrに関するドキュメントが参考になります。Notesを参照してください。

Notes
1. shared_ptr class template
2. shared_ptr class template(日本語)