首页 > 代码库 > 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 SortTracer‘s 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 算法的跟踪
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。