//Revised from
//STL Tutorial and Reference Guide C++ Programming with the Standard Template L
ibrary, 2nd Edition
//by David R. Musser (Author), Atul Saini (Author)
//# Publisher: Addison-Wesley Pub (Sd) (March 1996)
//# Language: English
//# ISBN-10: 0201633981
//# ISBN-13: 978-0201633986
#include
#include
#include
#include
#include
#include
using namespace std;
template
class less_with_count : public binary_function {
public:
less_with_count() : counter(0), progenitor(0) { }
// Copy constructor:
less_with_count(less_with_count& x) : counter(0),
progenitor(x.progenitor ? x.progenitor : &x) { }
bool operator()(const T& x, const T& y) {
++counter;
return x < y;
}
long report() const { return counter; }
~less_with_count() { // Destructor
if (progenitor) {
progenitor->counter += counter;
}
}
private:
long counter;
less_with_count* progenitor;
};
int main()
{
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 vector1;
for (int k = 0; k < N; ++k)
vector1.push_back(k);
random_shuffle(vector1.begin(), vector1.end());
less_with_count comp_counter;
sort(vector1.begin(), vector1.end(), comp_counter);
cout << "Problem size " << setw(9) << N
<< ", comparisons performed: "
<< setw(9) << comp_counter.report() << endl;
}
return 0;
}
Using a function object for operation counting, second version.
Problem size 1000, comparisons performed: 11846
Problem size 2000, comparisons performed: 26397
Problem size 4000, comparisons performed: 56776
Problem size 8000, comparisons performed: 125715
Problem size 16000, comparisons performed: 271505
Problem size 32000, comparisons performed: 596740
Problem size 64000, comparisons performed: 1235889
Problem size 128000, comparisons performed: 2727581