とくにあぶなくないRiSKのブログ

危ないRiSKのブログだったかもしれない。本当はRiSKだけどググラビリティとか取得できるIDの都合でsscriskも使ったり。

関数オブジェクトを使ってソート時の比較回数を数える 非 static 版

STL―標準テンプレートライブラリによるC++プログラミング 第2版
main で宣言したオブジェクトを祖先とする。コピーされた関数オブジェクトは死ぬ前に祖先のオブジェクトのカウンタを加算する。最後に,祖先のカウンタを表示する。
らしいが,祖先が先に死ぬような場面では使えんだろ,これは…なぁ。

// P186 ex08-04.cpp
#include<functional>
template<typename T>
class less_with_count : public std::binary_function<T, T, bool>{
public:
 less_with_count()
  : counter(), progenitor()
 {}
 less_with_count(less_with_count<T>& x)
  : counter(), progenitor(x.progenitor ? x.progenitor : &x)
 {}
 ~less_with_count(){
  if(progenitor){
   progenitor->counter += counter;
  }
 }
 bool operator()(const T& x, const T& y){
  ++counter;
  return x < y;
 }
 long report()const{return counter;}
private:
 long counter;
 less_with_count<T>* progenitor;
};
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
int main(){
 using std::cout;
 using std::endl;
 using std::vector;
 using std::random_shuffle;
 using std::sort;
 using std::setw;
 cout << "Using a function object for operation counting, second version."
  << endl;
 const long N1 = 1000, N2 = 128000;
 for(long n = N1; n <= N2; n *= 2){
  vector<int> v;
  for(int i = 0; i < n; ++i)v.push_back(i);
  random_shuffle(v.begin(), v.end());
  less_with_count<int> comp_counter;
  sort(v.begin(), v.end(), comp_counter);
  cout << "Problem size " << setw(9) << n << ",  "
   "comparisons performed: " << setw(9) << comp_counter.report() << endl;
 }
}

出力例:

Using a function object for operation counting, second version.
Problem size      1000,  comparisons performed:     22840
Problem size      2000,  comparisons performed:     50376
Problem size      4000,  comparisons performed:    110986
Problem size      8000,  comparisons performed:    237224
Problem size     16000,  comparisons performed:    510869
Problem size     32000,  comparisons performed:   1098913
Problem size     64000,  comparisons performed:   2319373
Problem size    128000,  comparisons performed:   4968382