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

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

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

STL―標準テンプレートライブラリによるC++プログラミング 第2版

// P184 ex08-03.cpp
#include<functional>
template<typename T>
struct less_with_count : public std::binary_function<T, T, bool>{
 less_with_count(){}
 bool operator()(const T& x, const T& y){
  ++counter;
  return x < y;
 }
 static long counter;
};
template<typename T>
long less_with_count<T>::counter = 0;
#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, first 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>::counter = 0;
  sort(v.begin(), v.end(), less_with_count<int>());
  cout << "Problem size " << setw(9) << n << ",  "
   "comparisons performed: " << setw(9) << less_with_count<int>::counter
   << endl;
 }
}

出力例:

Using a function object for operation counting, first 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