首页 > 代码库 > stl::sort 算法的跟踪

stl::sort 算法的跟踪

  1 // basics/tracer.hpp  2 #include <iostream>  3 class SortTracer  4 {  5 private:  6     int value;                  // 用来排序的整数  7     int generation;             // 此追踪器的生成个数  8     static long n_created;      // 构造函数被调用的次数  9     static long n_destroyed;    // 析构函数被调用的次数 10     static long n_assigned;     // 赋值次数 11     static long n_compared;     // 比较次数 12     static long n_max_live;     // 同一时间最多存在几个objects 13      14     // 重新计算「同一时间最多存在几个objects」 15     static void update_max_live() 16     { 17         if (n_created - n_destroyed > n_max_live) 18         { 19             n_max_live = n_created-n_destroyed; 20         } 21     } 22 public: 23     static long creations() 24     { 25         return n_created; 26     } 27     static long destructions() 28     { 29         return n_destroyed; 30     } 31     static long assignments() 32     { 33         return n_assigned; 34     } 35     static long comparisons() 36     { 37         return n_compared; 38     } 39     static long max_live() 40     { 41         return n_max_live; 42     } 43      44 public: 45 // 构造函数 (constructor) 46     SortTracer (int v = 0)  47         :value(v),  48         generation(1) 49     { 50         ++n_created; 51         update_max_live(); 52         std::cerr << "SortTracer #" << n_created 53                   << ", created generation " << generation 54                   << " (total: " << n_created - n_destroyed 55                   << ) << std::endl; 56     } 57 // copy 构造函数(copy constructor) 58     SortTracer (SortTracer const& b) 59         : value(b.value),  60         generation(b.generation+1) 61     { 62         ++n_created; 63         update_max_live(); 64         std::cerr << "SortTracer #" << n_created 65                   << ", copied as generation " << generation 66                   << " (total: " << n_created - n_destroyed 67                   << ) << std::endl; 68     } 69  // 解构式(destructor) 70     ~SortTracer() 71     { 72         ++n_destroyed; 73         update_max_live(); 74         std::cerr << "SortTracer generation " << generation 75                   << " destroyed (total: " 76                   << n_created - n_destroyed << ) << std::endl; 77     } 78 // 赋值(assignment) 79     SortTracer& operator= (SortTracer const& b) 80     { 81         ++n_assigned; 82         std::cerr << "SortTracer assignment #" << n_assigned 83                   << " (generation " << generation 84                   << " = " << b.generation 85                   << ) << std::endl; 86         value =http://www.mamicode.com/ b.value; 87         return *this; 88     } 89     // 比较(comparison) 90     friend bool operator < (SortTracer const& a, 91                             SortTracer const& b) 92     { 93         ++n_compared; 94         std::cerr << "SortTracer comparison #" << n_compared 95                   << " (generation " << a.generation 96                   << " < " << b.generation 97                   << ) << std::endl; 98         return a.value < b.value; 99     }100     int val() const101     {102         return value;103     }104 };

 

下面的测试程序对std::sort算法进行一系列的跟踪

 1 #include "first.hpp" 2 #include <iostream> 3 #include <algorithm> 4  5 long SortTracer::n_created = 0; 6 long SortTracer::n_destroyed = 0; 7 long SortTracer::n_max_live = 0; 8 long SortTracer::n_assigned = 0; 9 long SortTracer::n_compared = 0;10 11 int main()12 {13 // 准备样本数据源14     SortTracer input[] = { 7, 3, 5, 6, 4, 2, 0, 1, 9, 8 };15 // 打印起始值16     for (int i=0; i<10; ++i)17     {18         std::cerr << input[i].val() <<  ;19     }20     std::cerr << std::endl;21 // 记录起始值22     long created_at_start = SortTracer::creations();23     long max_live_at_start = SortTracer::max_live();24     long assigned_at_start = SortTracer::assignments();25     long compared_at_start = SortTracer::comparisons();26 // 执行算法27     std::cerr << "---[ Start std::sort() ]--------------------" << std::endl;28     std::sort<>(&input[0], &input[9]+1);29     std::cerr << "---[ End std::sort() ]----------------------" << std::endl;30 // 检验结果31     for (int i=0; i<10; ++i)32     {33         std::cerr << input[i].val() <<  ;34     }35     std::cerr << std::endl << std::endl;36 // 最终报告37     std::cerr << "std::sort() of 10 SortTracer‘s"38               << " was performed by: " << std::endl39               << SortTracer::creations() - created_at_start40               << " temporary tracers" << std::endl <<  41               << "up to "42               << SortTracer::max_live()43               << " tracers at the same time ("44               << max_live_at_start << " before)" << std::endl <<  45               << SortTracer::assignments() - assigned_at_start46               << " assignments" << std::endl <<  47               << SortTracer::comparisons() - compared_at_start48               << " comparisons" << std::endl << std::endl;49 }

 

最终运行结果:

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 comparison #1 (generation 1 < 1)SortTracer #11, copied as generation 2 (total: 11)SortTracer assignment #1 (generation 1 = 1)SortTracer assignment #2 (generation 1 = 2)SortTracer generation 2 destroyed (total: 10)SortTracer comparison #2 (generation 1 < 1)SortTracer #12, copied as generation 2 (total: 11)SortTracer comparison #3 (generation 2 < 1)SortTracer assignment #3 (generation 1 = 1)SortTracer comparison #4 (generation 2 < 1)SortTracer assignment #4 (generation 1 = 2)SortTracer generation 2 destroyed (total: 10)SortTracer comparison #5 (generation 1 < 1)SortTracer #13, copied as generation 2 (total: 11)SortTracer comparison #6 (generation 2 < 1)SortTracer assignment #5 (generation 1 = 1)SortTracer comparison #7 (generation 2 < 1)SortTracer assignment #6 (generation 1 = 2)SortTracer generation 2 destroyed (total: 10)SortTracer comparison #8 (generation 1 < 1)SortTracer #14, copied as generation 2 (total: 11)SortTracer comparison #9 (generation 2 < 1)SortTracer assignment #7 (generation 1 = 1)SortTracer comparison #10 (generation 2 < 1)SortTracer assignment #8 (generation 1 = 1)SortTracer comparison #11 (generation 2 < 1)SortTracer assignment #9 (generation 1 = 1)SortTracer comparison #12 (generation 2 < 1)SortTracer assignment #10 (generation 1 = 2)SortTracer generation 2 destroyed (total: 10)SortTracer comparison #13 (generation 1 < 1)SortTracer #15, copied as generation 2 (total: 11)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 comparison #14 (generation 1 < 1)SortTracer #16, copied as generation 2 (total: 11)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 comparison #15 (generation 1 < 1)SortTracer #17, copied as generation 2 (total: 11)SortTracer comparison #16 (generation 2 < 1)SortTracer assignment #24 (generation 1 = 1)SortTracer comparison #17 (generation 2 < 1)SortTracer assignment #25 (generation 1 = 1)SortTracer comparison #18 (generation 2 < 1)SortTracer assignment #26 (generation 1 = 1)SortTracer comparison #19 (generation 2 < 1)SortTracer assignment #27 (generation 1 = 1)SortTracer comparison #20 (generation 2 < 1)SortTracer assignment #28 (generation 1 = 1)SortTracer comparison #21 (generation 2 < 1)SortTracer assignment #29 (generation 1 = 1)SortTracer comparison #22 (generation 2 < 1)SortTracer assignment #30 (generation 1 = 2)SortTracer generation 2 destroyed (total: 10)SortTracer comparison #23 (generation 1 < 1)SortTracer #18, copied as generation 2 (total: 11)SortTracer comparison #24 (generation 2 < 1)SortTracer assignment #31 (generation 1 = 2)SortTracer generation 2 destroyed (total: 10)SortTracer comparison #25 (generation 1 < 1)SortTracer #19, copied as generation 2 (total: 11)SortTracer comparison #26 (generation 2 < 1)SortTracer assignment #32 (generation 1 = 1)SortTracer comparison #27 (generation 2 < 1)SortTracer assignment #33 (generation 1 = 2)SortTracer generation 2 destroyed (total: 10)---[ End std::sort() ]----------------------0 1 2 3 4 5 6 7 8 9 std::sort() of 10 SortTracers was performed by: 9 temporary tracers up to 11 tracers at the same time (10 before) 33 assignments 27 comparisonsSortTracer 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)

 

stl::sort 算法的跟踪