|
| |
| 5.22.5.Sort Tracer |
|
|
/* The following code example is taken from the book
* "C++ Templates - The Complete Guide"
* by David Vandevoorde and Nicolai M. Josuttis, Addison-Wesley, 2002
*
* (C) Copyright David Vandevoorde and Nicolai M. Josuttis 2002.
* Permission to copy, use, modify, sell and distribute this software
* is granted provided this copyright notice appears in all copies.
* This software is provided "as is" without express or implied
* warranty, and with no claim as to its suitability for any purpose.
*/
#include <iostream>
#include <algorithm>
#include <iostream>
class SortTracer {
private:
int value; // integer value to be sorted
int generation; // generation of this tracer
static long n_created; // number of constructor calls
static long n_destroyed; // number of destructor calls
static long n_assigned; // number of assignments
static long n_compared; // number of comparisons
static long n_max_live; // maximum of existing objects
// recompute maximum of existing objects
static void update_max_live() {
if (n_created-n_destroyed > n_max_live) {
n_max_live = n_created-n_destroyed;
}
}
public:
static long creations() {
return n_created;
}
static long destructions() {
return n_destroyed;
}
static long assignments() {
return n_assigned;
}
static long comparisons() {
return n_compared;
}
static long max_live() {
return n_max_live;
}
public:
// constructor
SortTracer (int v = 0) : value(v), generation(1) {
++n_created;
update_max_live();
std::cerr << "SortTracer #" << n_created
<< ", created generation " << generation
<< " (total: " << n_created - n_destroyed
<< ")\n";
}
// copy constructor
SortTracer (SortTracer const& b)
: value(b.value), generation(b.generation+1) {
++n_created;
update_max_live();
std::cerr << "SortTracer #" << n_created
<< ", copied as generation " << generation
<< " (total: " << n_created - n_destroyed
<< ")\n";
}
// destructor
~SortTracer() {
++n_destroyed;
update_max_live();
std::cerr << "SortTracer generation " << generation
<< " destroyed (total: "
<< n_created - n_destroyed << ")\n";
}
// assignment
SortTracer& operator= (SortTracer const& b) {
++n_assigned;
std::cerr << "SortTracer assignment #" << n_assigned
<< " (generation " << generation
<< " = " << b.generation
<< ")\n";
value = b.value;
return *this;
}
// comparison
friend bool operator < (SortTracer const& a,
SortTracer const& b) {
++n_compared;
std::cerr << "SortTracer comparison #" << n_compared
<< " (generation " << a.generation
<< " < " << b.generation
<< ")\n";
return a.value < b.value;
}
int val() const {
return value;
}
};
long SortTracer::n_created = 0;
long SortTracer::n_destroyed = 0;
long SortTracer::n_max_live = 0;
long SortTracer::n_assigned = 0;
long SortTracer::n_compared = 0;
int main()
{
// prepare sample input:
SortTracer input[] = { 7, 3, 5, 6, 4, 2, 0, 1, 9, 8 };
// print initial values:
for (int i=0; i<10; ++i) {
std::cerr << input[i].val() << ' ';
}
std::cerr << std::endl;
// remember initial conditions:
long created_at_start = SortTracer::creations();
long max_live_at_start = SortTracer::max_live();
long assigned_at_start = SortTracer::assignments();
long compared_at_start = SortTracer::comparisons();
// execute algorithm:
std::cerr << "---[ Start std::sort() ]--------------------\n";
std::sort<>(&input[0], &input[9]+1);
std::cerr << "---[ End std::sort() ]----------------------\n";
// verify result:
for (int i=0; i<10; ++i) {
std::cerr << input[i].val() << ' ';
}
std::cerr << "\n\n";
// final report:
std::cerr << "std::sort() of 10 SortTracer's"
<< " was performed by:\n "
<< SortTracer::creations() - created_at_start
<< " temporary tracers\n "
<< "up to "
<< SortTracer::max_live()
<< " tracers at the same time ("
<< max_live_at_start << " before)\n "
<< SortTracer::assignments() - assigned_at_start
<< " assignments\n "
<< SortTracer::comparisons() - compared_at_start
<< " comparisons\n\n";
}
|
|
SortTracer #1, created generation 1 (total: 1)
SortTracer #2, created generation 1 (total: 2)
SortTracer #3, created generation 1 (total: 3)
SortTracer #4, created generation 1 (total: 4)
SortTracer #5, created generation 1 (total: 5)
SortTracer #6, created generation 1 (total: 6)
SortTracer #7, created generation 1 (total: 7)
SortTracer #8, created generation 1 (total: 8)
SortTracer #9, created generation 1 (total: 9)
SortTracer #10, created generation 1 (total: 10)
7 3 5 6 4 2 0 1 9 8
---[ Start std::sort() ]--------------------
SortTracer #11, copied as generation 2 (total: 11)
SortTracer comparison #1 (generation 2 < 1)
SortTracer assignment #1 (generation 1 = 1)
SortTracer assignment #2 (generation 1 = 2)
SortTracer generation 2 destroyed (total: 10)
SortTracer #12, copied as generation 2 (total: 11)
SortTracer comparison #2 (generation 2 < 1)
SortTracer #13, copied as generation 3 (total: 12)
SortTracer comparison #3 (generation 3 < 1)
SortTracer assignment #3 (generation 1 = 1)
SortTracer comparison #4 (generation 3 < 1)
SortTracer assignment #4 (generation 1 = 3)
SortTracer generation 3 destroyed (total: 11)
SortTracer generation 2 destroyed (total: 10)
SortTracer #14, copied as generation 2 (total: 11)
SortTracer comparison #5 (generation 2 < 1)
SortTracer #15, copied as generation 3 (total: 12)
SortTracer comparison #6 (generation 3 < 1)
SortTracer assignment #5 (generation 1 = 1)
SortTracer comparison #7 (generation 3 < 1)
SortTracer assignment #6 (generation 1 = 3)
SortTracer generation 3 destroyed (total: 11)
SortTracer generation 2 destroyed (total: 10)
SortTracer #16, copied as generation 2 (total: 11)
SortTracer comparison #8 (generation 2 < 1)
SortTracer #17, copied as generation 3 (total: 12)
SortTracer comparison #9 (generation 3 < 1)
SortTracer assignment #7 (generation 1 = 1)
SortTracer comparison #10 (generation 3 < 1)
SortTracer assignment #8 (generation 1 = 1)
SortTracer comparison #11 (generation 3 < 1)
SortTracer assignment #9 (generation 1 = 1)
SortTracer comparison #12 (generation 3 < 1)
SortTracer assignment #10 (generation 1 = 3)
SortTracer generation 3 destroyed (total: 11)
SortTracer generation 2 destroyed (total: 10)
SortTracer #18, copied as generation 2 (total: 11)
SortTracer comparison #13 (generation 2 < 1)
SortTracer assignment #11 (generation 1 = 1)
SortTracer assignment #12 (generation 1 = 1)
SortTracer assignment #13 (generation 1 = 1)
SortTracer assignment #14 (generation 1 = 1)
SortTracer assignment #15 (generation 1 = 1)
SortTracer assignment #16 (generation 1 = 2)
SortTracer generation 2 destroyed (total: 10)
SortTracer #19, copied as generation 2 (total: 11)
SortTracer comparison #14 (generation 2 < 1)
SortTracer assignment #17 (generation 1 = 1)
SortTracer assignment #18 (generation 1 = 1)
SortTracer assignment #19 (generation 1 = 1)
SortTracer assignment #20 (generation 1 = 1)
SortTracer assignment #21 (generation 1 = 1)
SortTracer assignment #22 (generation 1 = 1)
SortTracer assignment #23 (generation 1 = 2)
SortTracer generation 2 destroyed (total: 10)
SortTracer #20, copied as generation 2 (total: 11)
SortTracer comparison #15 (generation 2 < 1)
SortTracer #21, copied as generation 3 (total: 12)
SortTracer comparison #16 (generation 3 < 1)
SortTracer assignment #24 (generation 1 = 1)
SortTracer comparison #17 (generation 3 < 1)
SortTracer assignment #25 (generation 1 = 1)
SortTracer comparison #18 (generation 3 < 1)
SortTracer assignment #26 (generation 1 = 1)
SortTracer comparison #19 (generation 3 < 1)
SortTracer assignment #27 (generation 1 = 1)
SortTracer comparison #20 (generation 3 < 1)
SortTracer assignment #28 (generation 1 = 1)
SortTracer comparison #21 (generation 3 < 1)
SortTracer assignment #29 (generation 1 = 1)
SortTracer comparison #22 (generation 3 < 1)
SortTracer assignment #30 (generation 1 = 3)
SortTracer generation 3 destroyed (total: 11)
SortTracer generation 2 destroyed (total: 10)
SortTracer #22, copied as generation 2 (total: 11)
SortTracer comparison #23 (generation 2 < 1)
SortTracer #23, copied as generation 3 (total: 12)
SortTracer comparison #24 (generation 3 < 1)
SortTracer assignment #31 (generation 1 = 3)
SortTracer generation 3 destroyed (total: 11)
SortTracer generation 2 destroyed (total: 10)
SortTracer #24, copied as generation 2 (total: 11)
SortTracer comparison #25 (generation 2 < 1)
SortTracer #25, copied as generation 3 (total: 12)
SortTracer comparison #26 (generation 3 < 1)
SortTracer assignment #32 (generation 1 = 1)
SortTracer comparison #27 (generation 3 < 1)
SortTracer assignment #33 (generation 1 = 3)
SortTracer generation 3 destroyed (total: 11)
SortTracer generation 2 destroyed (total: 10)
---[ End std::sort() ]----------------------
0 1 2 3 4 5 6 7 8 9
std::sort() of 10 SortTracer's was performed by:
15 temporary tracers
up to 12 tracers at the same time (10 before)
33 assignments
27 comparisons
SortTracer generation 1 destroyed (total: 9)
SortTracer generation 1 destroyed (total: 8)
SortTracer generation 1 destroyed (total: 7)
SortTracer generation 1 destroyed (total: 6)
SortTracer generation 1 destroyed (total: 5)
SortTracer generation 1 destroyed (total: 4)
SortTracer generation 1 destroyed (total: 3)
SortTracer generation 1 destroyed (total: 2)
SortTracer generation 1 destroyed (total: 1)
SortTracer generation 1 destroyed (total: 0) |
|