1 // (C) Copyright Herve Bronnimann 2004.
2 // Use, modification and distribution are subject to the
3 // Boost Software License, Version 1.0. (See accompanying file
4 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
5
6 #include <utility>
7 #include <functional>
8 #include <algorithm>
9 #include <numeric>
10 #include <iterator>
11 #include <vector>
12 #include <list>
13 #include <set>
14 #include <iostream>
15 // What's the proper BOOST_ flag for <iomanip.h> vs <ios>
16 #include <iomanip>
17
18 #include <boost/timer.hpp>
19 #include <boost/algorithm/minmax.hpp>
20
21 template <class T1, class T2>
tie(std::pair<T1,T2> p,T1 & min,T2 & max)22 void tie(std::pair<T1, T2> p, T1& min, T2& max)
23 {
24 min = p.first; max = p.second;
25 }
26
27 template <class Value>
28 struct less_count : std::less<Value> {
less_countless_count29 less_count(less_count<Value> const& lc) : _M_counter(lc._M_counter) {}
less_countless_count30 less_count(int& counter) : _M_counter(counter) {}
operator ()less_count31 bool operator()(Value const& a, Value const& b) const {
32 ++_M_counter;
33 return std::less<Value>::operator()(a,b);
34 }
resetless_count35 void reset() {
36 _M_counter = 0;
37 }
38 private:
39 int& _M_counter;
40 };
41
opt_min_count(int n)42 inline int opt_min_count(int n) {
43 return (n==0) ? 0 : n-1;
44 }
opt_minmax_count(int n)45 inline int opt_minmax_count(int n) {
46 if (n < 2) return 0;
47 if (n == 2) return 1;
48 return (n%2 == 0) ? 3*(n/2)-1 : 3*(n/2)+1;
49 }
opt_boost_minmax_count(int n)50 inline int opt_boost_minmax_count(int n) {
51 if (n < 2) return 0;
52 if (n == 2) return 1;
53 return (n%2 == 0) ? 3*(n/2)-2 : 3*(n/2);
54 }
55
56 int repeats = 10;
57
58 #define TIMER( n, cmd , cmdname ) \
59 t.restart(); \
60 for (int i=0; i<repeats; ++i) { cmd ; } \
61 std::cout << " " << std::setprecision(4) \
62 << (double)n*repeats/t.elapsed()/1.0E6 \
63 << "M items/sec " << cmdname << "\n"
64
65 #define CTIMER( n, cmd , cmdname, count, opt ) \
66 t.restart(); lc.reset(); \
67 for (int i=0; i<repeats; ++i) { cmd ; } \
68 std::cout << " " << std::setprecision(4) \
69 << (double)n*repeats/t.elapsed()/1.0E6 \
70 << "M items/sec " << cmdname \
71 << " ("<< (count)/repeats << " vs " << opt << ")\n"
72
73 template <class CIterator>
test_minmax_element(CIterator first,CIterator last,int n,char * name)74 void test_minmax_element(CIterator first, CIterator last, int n, char* name)
75 {
76 typedef typename std::iterator_traits<CIterator>::value_type vtype;
77 boost::timer t;
78
79 std::cout << " ON " << name << " WITH OPERATOR<()\n";
80 TIMER( n, std::min_element(first, last),
81 "std::min_element" << name << "");
82 TIMER( n, std::max_element(first, last),
83 "std::max_element" << name << "");
84 TIMER( n, boost::first_min_element(first, last),
85 "boost::first_min_element" << name << "");
86 TIMER( n, boost::last_min_element(first, last),
87 "boost::last_min_element" << name << " ");
88 TIMER( n, boost::first_max_element(first, last),
89 "boost::first_max_element" << name << "");
90 TIMER( n, boost::last_max_element(first, last),
91 "boost::last_max_element" << name << " ");
92 TIMER( n, boost::minmax_element(first, last),
93 "boost::minmax_element" << name << " ");
94 TIMER( n, boost::first_min_last_max_element(first, last),
95 "boost::first_min_last_max_element" << name << "");
96 TIMER( n, boost::last_min_first_max_element(first, last),
97 "boost::last_min_first_max_element" << name << "");
98 TIMER( n, boost::last_min_last_max_element(first, last),
99 "boost::last_min_last_max_element" << name << " ");
100
101 #define pred std::bind2nd( std::greater<vtype>(), vtype(10) )
102 TIMER( n, boost::min_element_if(first, last, pred),
103 "boost::min_element_if" << name << "");
104 TIMER( n, boost::max_element_if(first, last, pred),
105 "boost::max_element_if" << name << "");
106 TIMER( n, std::min_element(boost::make_filter_iterator(first, last, pred),
107 boost::make_filter_iterator(last, last, pred)),
108 "std::min_element_with_filter_iterator" << name << "");
109 TIMER( n, std::max_element(boost::make_filter_iterator(first, last, pred),
110 boost::make_filter_iterator(last, last, pred)),
111 "std::max_element_if_with_filter_iterator" << name << "");
112 #undef pred
113
114 int counter = 0;
115 less_count<vtype> lc(counter);
116 std::cout << " ON " << name << " WITH LESS<> AND COUNTING COMPARISONS\n";
117 CTIMER( n, std::min_element(first, last, lc),
118 "std::min_element" << name << " ",
119 counter, opt_min_count(n) );
120 CTIMER( n, std::max_element(first, last, lc),
121 "std::max_element" << name << " ",
122 counter, opt_min_count(n) );
123 CTIMER( n, boost::first_min_element(first, last, lc),
124 "boost::first_min_element" << name << "",
125 counter, opt_min_count(n) );
126 CTIMER( n, boost::last_min_element(first, last, lc),
127 "boost::last_max_element" << name << " ",
128 counter, opt_min_count(n) );
129 CTIMER( n, boost::first_max_element(first, last, lc),
130 "boost::first_min_element" << name << "",
131 counter, opt_min_count(n) );
132 CTIMER( n, boost::last_max_element(first, last, lc),
133 "boost::last_max_element" << name << " ",
134 counter, opt_min_count(n) );
135 CTIMER( n, boost::minmax_element(first, last, lc),
136 "boost::minmax_element" << name << " ",
137 counter, opt_minmax_count(n) );
138 CTIMER( n, boost::first_min_last_max_element(first, last, lc),
139 "boost::first_min_last_max_element" << name << "",
140 counter, opt_boost_minmax_count(n) );
141 CTIMER( n, boost::last_min_first_max_element(first, last, lc),
142 "boost::last_min_first_max_element" << name << "",
143 counter, opt_boost_minmax_count(n) );
144 CTIMER( n, boost::last_min_last_max_element(first, last, lc),
145 "boost::last_min_last_max_element" << name << " ",
146 counter, opt_minmax_count(n) );
147 }
148
149 template <class Container, class Iterator, class Value>
test_container(Iterator first,Iterator last,int n,char * name)150 void test_container(Iterator first, Iterator last, int n, char* name)
151 {
152 Container c(first, last);
153 typename Container::iterator fit(c.begin()), lit(c.end());
154 test_minmax_element(fit, lit, n, name);
155 }
156
157 template <class Iterator>
test_range(Iterator first,Iterator last,int n)158 void test_range(Iterator first, Iterator last, int n)
159 {
160 typedef typename std::iterator_traits<Iterator>::value_type Value;
161 // Test various containers with these values
162 test_container< std::vector<Value>, Iterator, Value >(first, last, n, "<vector>");
163 #ifndef ONLY_VECTOR
164 test_container< std::list<Value>, Iterator, Value >(first, last, n, "<list> ");
165 test_container< std::multiset<Value>, Iterator, Value >(first, last, n, "<set> ");
166 #endif
167 }
168
169 template <class Value>
test(int n)170 void test(int n)
171 {
172 // Populate test vector with identical values
173 std::cout << "IDENTICAL VALUES... \n";
174 std::vector<Value> test_vector(n, Value(1));
175 typename std::vector<Value>::iterator first( test_vector.begin() );
176 typename std::vector<Value>::iterator last( test_vector.end() );
177 test_range(first, last, n);
178
179 // Populate test vector with two values
180 std::cout << "TWO DISTINCT VALUES...\n";
181 typename std::vector<Value>::iterator middle( first + n/2 );
182 std::fill(middle, last, Value(2));
183 test_range(first, last, n);
184
185 // Populate test vector with increasing values
186 std::cout << "INCREASING VALUES... \n";
187 std::fill(first, last, Value(1));
188 std::accumulate(first, last, Value(0));
189 test_range(first, last, n);
190
191 // Populate test vector with decreasing values
192 std::cout << "DECREASING VALUES... \n";
193 std::reverse(first, last);
194 test_range(first, last, n);
195
196 // Populate test vector with random values
197 std::cout << "RANDOM VALUES... \n";
198 std::random_shuffle(first, last);
199 test_range(first, last, n);
200 }
201
202 int
main(char argc,char ** argv)203 main(char argc, char** argv)
204 {
205 int n = 100;
206 if (argc > 1) n = atoi(argv[1]);
207 if (argc > 2) repeats = atoi(argv[2]);
208
209 test<int>(n);
210
211 return 0;
212 }
213