C++でコラッツ逆展開

しつこくコラッツ。
せっかく std::set があるので C++ でもコラッツ逆展開を書いてみた:

typedef long long num_t;
typedef pair< num_t, num_t >  nums_t;

num_t collatz( num_t n )
{
  num_t done = 3;
  set< nums_t > waits;
  waits.insert( nums_t(8,4) );
  nums_t max(0,0);
  while( done < n ){
    nums_t a = *waits.begin();
    waits.erase( waits.begin() );
    if ( a.first<= n ){
      ++done;
      if ( max.second < a.second )
        max = a;
    }
    waits.insert( nums_t( a.first*2, a.second+1 ) );
    if ( 3==(a.first-1)%6 )
      waits.insert( nums_t( (a.first-1)/3, a.second+1 ) );
  }
  return max.first;
}

当たり前だが、ruby より断然速く*1、collatz(20000)でも10秒で終わる。すごい。
コンパイラだから速いということもあるが、配列に対する挿入と std::set に対する挿入では速さが違うということもおおいに効いていると思う。
collatz(10000)を計算し終えた時点での、waits.size() は 二百万以上。配列で持ってしまうと、挿入のコストが高すぎる。かといって list にすると二分探索が遅くなるので、木にするのがいいんだが、木は手で書くのがかなり大変。私は書ける自信がない。
というわけで、ruby にも std::set のような、自動的にソートされるコンテナがあった方がいいと思う。
それとももうあるのかな。

*1:実行速度は rubyで逆展開 ＜ C++で逆展開C++ ＜ rubyで普通に計算 の順。いくら C++ でも、無駄がとてつもなく多いアルゴリズムなので、ruby で普通に計算したものの方が圧倒的に速い