Lesson of 16 February 2011¶
Sorting example
File sortC++.cc
1// to compile on unix/OSX use
2// g++ -I. sortC++.cc TimeMeter.cc
3//
4
5// include header for C++ I/O
6// search stdio.h in standard C/C++ include directory e.g. /usr/include
7#include <iostream> // for the definition of cin, cout, ...
8#include <iomanip> // for manipulator setw, setprecision ...
9
10// include header for STL vector and algorithm
11#include <vector>
12#include <algorithm>
13
14// if in windows use a portable version of stdint.h
15#ifdef _WIN32
16 #include "pstdint.h" // for uint64_t
17#else
18 #include <stdint.h> // for uint64_t
19#endif
20
21#include <cstdlib> // near equivalent to <stdlib.h> for exit, rand, ...
22#include <cmath> // near equivalent to <math.h> for sin, cos, log, ..
23
24#include "TimeMeter.hh" // class computing elapsed time
25
26using namespace std ;
27
28// general random numer generator
29template <typename U>
30inline
31U random() { return rand() ; }
32
33// specialization for uint32_t (32 bit integer)
34template <>
35inline
36uint32_t random<uint32_t>() {
37 return uint32_t(rand()) ^ (uint32_t(rand())<<16) ;
38}
39
40// specialization for uint64_t (64 bit integer)
41template <>
42inline
43uint64_t random<uint64_t>() {
44 return uint64_t(rand()) ^
45 (uint64_t(rand())<<16) ^
46 (uint64_t(rand())<<32) ^
47 (uint64_t(rand())<<48) ;
48}
49
50template <typename T>
51static
52void
53bubbleSort( vector<T> & v ) {
54 // passed by reference, any modifation of v is also on the caller
55 for ( unsigned i = 0 ; i < v.size()-1 ; ++i )
56 for ( unsigned j = i+1 ; j < v.size() ; ++j )
57 if ( v[i] > v[j] )
58 swap( v[i], v[j] ) ;
59
60}
61
62typedef uint64_t INTEGER ; // make an alias for uint64_t
63
64int
65main() {
66
67 vector<double> elapsed ; // define a vector containing saved elapsed time
68 vector<double> elapsed1 ; // define a vector containing saved elapsed time
69 vector<unsigned> sizevec ; // define a vector containing saved sizes
70 vector<INTEGER> A ; // a working vector with number to be oredered
71 TimeMeter tm ; // tm is an instance of a class TimeMeter for timing
72
73 elapsed . clear() ;
74 sizevec . clear() ; // vector are emptied and reduced of size 0
75 for ( unsigned sz = 100 ; sz <= 10000 ; sz *= 2 ) {
76 A . clear() ; // empty the vector, size is 0
77 A . reserve( sz ) ; // reserve memory for sz elements
78 for ( unsigned j = 0 ; j < sz ; ++j )
79 A . push_back( random<INTEGER>() ) ;
80 // setw(6) reserve 6 character for the next output
81 // flush : write immediately to the standard output (empty the buffer)
82 cout << "sorting (STL) " << setw(6) << sz << " numbers..." << flush ;
83 tm . start() ; // start time computation
84 sort( A . begin(), A . end() ) ; // STL ruotine to sort a vector
85 double e = tm . milliseconds() ;
86 elapsed . push_back( e ) ;
87 sizevec . push_back( sz ) ;
88 cout << "done in " << setprecision(4) << e << "ms\n" ;
89
90 A . clear() ; // empty the vector, size is 0
91 for ( unsigned j = 0 ; j < sz ; ++j )
92 A . push_back( random<INTEGER>() ) ;
93
94 cout << "sorting (BUBBLE) " << setw(6) << sz << " numbers..." << flush ;
95 tm . start() ; // start time computation
96 bubbleSort( A ) ; // Simple routine to sort a vector
97 e = tm . milliseconds() ;
98 elapsed1 . push_back( e ) ;
99 cout << "done in " << setprecision(4) << e << "ms\n" ;
100
101 }
102
103 cout << "\n\n\n" ;
104 for ( unsigned i = 0 ; i < sizevec . size() ; ++i ) {
105 double e = elapsed[i] ;
106 double e1 = elapsed1[i] ;
107 unsigned sz = sizevec[i] ;
108 cout << "n = " << setw(6) << sz
109 << " elapsed " << setw(8) << setprecision(4) << e << "ms"
110 << " elapsed/(n*log(n)) = " << setw(10) << 100000*e/(sz*log(sz))
111 << " elapsed1 " << setw(8) << setprecision(4) << e1 << "ms"
112 << " elapsed1/(n^2) = " << setw(10) << 100000*e1/(sz*sz)
113 << " elapsed1/elapsed = " << setw(10) << e1/e
114 << '\n' ;
115 }
116 return 0 ; // return is a statement for returning value to the caller
117}
A cross-platform, free implementation of ``stdint.h`` from Paul Hsieh
File pstdint.h
1/* A portable stdint.h
2 ****************************************************************************
3 * BSD License:
4 ****************************************************************************
5 *
6 * Copyright (c) 2005-2007 Paul Hsieh
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 *
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. The name of the author may not be used to endorse or promote products
19 * derived from this software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
22 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
23 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
24 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
25 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
26 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
30 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 *
32 ****************************************************************************
33 *
34 * Version 0.1.11
35 *
36 * The ANSI C standard committee, for the C99 standard, specified the
37 * inclusion of a new standard include file called stdint.h. This is
38 * a very useful and long desired include file which contains several
39 * very precise definitions for integer scalar types that is
40 * critically important for making portable several classes of
41 * applications including cryptography, hashing, variable length
42 * integer libraries and so on. But for most developers its likely
43 * useful just for programming sanity.
44 *
45 * The problem is that most compiler vendors have decided not to
46 * implement the C99 standard, and the next C++ language standard
47 * (which has a lot more mindshare these days) will be a long time in
48 * coming and its unknown whether or not it will include stdint.h or
49 * how much adoption it will have. Either way, it will be a long time
50 * before all compilers come with a stdint.h and it also does nothing
51 * for the extremely large number of compilers available today which
52 * do not include this file, or anything comparable to it.
53 *
54 * So that's what this file is all about. Its an attempt to build a
55 * single universal include file that works on as many platforms as
56 * possible to deliver what stdint.h is supposed to. A few things
57 * that should be noted about this file:
58 *
59 * 1) It is not guaranteed to be portable and/or present an identical
60 * interface on all platforms. The extreme variability of the
61 * ANSI C standard makes this an impossibility right from the
62 * very get go. Its really only meant to be useful for the vast
63 * majority of platforms that possess the capability of
64 * implementing usefully and precisely defined, standard sized
65 * integer scalars. Systems which are not intrinsically 2s
66 * complement may produce invalid constants.
67 *
68 * 2) There is an unavoidable use of non-reserved symbols.
69 *
70 * 3) Other standard include files are invoked.
71 *
72 * 4) This file may come in conflict with future platforms that do
73 * include stdint.h. The hope is that one or the other can be
74 * used with no real difference.
75 *
76 * 5) In the current verison, if your platform can't represent
77 * int32_t, int16_t and int8_t, it just dumps out with a compiler
78 * error.
79 *
80 * 6) 64 bit integers may or may not be defined. Test for their
81 * presence with the test: #ifdef INT64_MAX or #ifdef UINT64_MAX.
82 * Note that this is different from the C99 specification which
83 * requires the existence of 64 bit support in the compiler. If
84 * this is not defined for your platform, yet it is capable of
85 * dealing with 64 bits then it is because this file has not yet
86 * been extended to cover all of your system's capabilities.
87 *
88 * 7) (u)intptr_t may or may not be defined. Test for its presence
89 * with the test: #ifdef PTRDIFF_MAX. If this is not defined
90 * for your platform, then it is because this file has not yet
91 * been extended to cover all of your system's capabilities, not
92 * because its optional.
93 *
94 * 8) The following might not been defined even if your platform is
95 * capable of defining it:
96 *
97 * WCHAR_MIN
98 * WCHAR_MAX
99 * (u)int64_t
100 * PTRDIFF_MIN
101 * PTRDIFF_MAX
102 * (u)intptr_t
103 *
104 * 9) The following have not been defined:
105 *
106 * WINT_MIN
107 * WINT_MAX
108 *
109 * 10) The criteria for defining (u)int_least(*)_t isn't clear,
110 * except for systems which don't have a type that precisely
111 * defined 8, 16, or 32 bit types (which this include file does
112 * not support anyways). Default definitions have been given.
113 *
114 * 11) The criteria for defining (u)int_fast(*)_t isn't something I
115 * would trust to any particular compiler vendor or the ANSI C
116 * committee. It is well known that "compatible systems" are
117 * commonly created that have very different performance
118 * characteristics from the systems they are compatible with,
119 * especially those whose vendors make both the compiler and the
120 * system. Default definitions have been given, but its strongly
121 * recommended that users never use these definitions for any
122 * reason (they do *NOT* deliver any serious guarantee of
123 * improved performance -- not in this file, nor any vendor's
124 * stdint.h).
125 *
126 * 12) The following macros:
127 *
128 * PRINTF_INTMAX_MODIFIER
129 * PRINTF_INT64_MODIFIER
130 * PRINTF_INT32_MODIFIER
131 * PRINTF_INT16_MODIFIER
132 * PRINTF_LEAST64_MODIFIER
133 * PRINTF_LEAST32_MODIFIER
134 * PRINTF_LEAST16_MODIFIER
135 * PRINTF_INTPTR_MODIFIER
136 *
137 * are strings which have been defined as the modifiers required
138 * for the "d", "u" and "x" printf formats to correctly output
139 * (u)intmax_t, (u)int64_t, (u)int32_t, (u)int16_t, (u)least64_t,
140 * (u)least32_t, (u)least16_t and (u)intptr_t types respectively.
141 * PRINTF_INTPTR_MODIFIER is not defined for some systems which
142 * provide their own stdint.h. PRINTF_INT64_MODIFIER is not
143 * defined if INT64_MAX is not defined. These are an extension
144 * beyond what C99 specifies must be in stdint.h.
145 *
146 * In addition, the following macros are defined:
147 *
148 * PRINTF_INTMAX_HEX_WIDTH
149 * PRINTF_INT64_HEX_WIDTH
150 * PRINTF_INT32_HEX_WIDTH
151 * PRINTF_INT16_HEX_WIDTH
152 * PRINTF_INT8_HEX_WIDTH
153 * PRINTF_INTMAX_DEC_WIDTH
154 * PRINTF_INT64_DEC_WIDTH
155 * PRINTF_INT32_DEC_WIDTH
156 * PRINTF_INT16_DEC_WIDTH
157 * PRINTF_INT8_DEC_WIDTH
158 *
159 * Which specifies the maximum number of characters required to
160 * print the number of that type in either hexadecimal or decimal.
161 * These are an extension beyond what C99 specifies must be in
162 * stdint.h.
163 *
164 * Compilers tested (all with 0 warnings at their highest respective
165 * settings): Borland Turbo C 2.0, WATCOM C/C++ 11.0 (16 bits and 32
166 * bits), Microsoft Visual C++ 6.0 (32 bit), Microsoft Visual Studio
167 * .net (VC7), Intel C++ 4.0, GNU gcc v3.3.3
168 *
169 * This file should be considered a work in progress. Suggestions for
170 * improvements, especially those which increase coverage are strongly
171 * encouraged.
172 *
173 * Acknowledgements
174 *
175 * The following people have made significant contributions to the
176 * development and testing of this file:
177 *
178 * Chris Howie
179 * John Steele Scott
180 * Dave Thorup
181 *
182 */
183
184#include <stddef.h>
185#include <limits.h>
186#include <signal.h>
187
188/*
189 * For gcc with _STDINT_H, fill in the PRINTF_INT*_MODIFIER macros, and
190 * do nothing else. On the Mac OS X version of gcc this is _STDINT_H_.
191 */
192
193#if ((defined(__STDC__) && __STDC__ && __STDC_VERSION__ >= 199901L) || (defined (__WATCOMC__) && (defined (_STDINT_H_INCLUDED) || __WATCOMC__ >= 1250)) || (defined(__GNUC__) && (defined(_STDINT_H) || defined(_STDINT_H_)) )) && !defined (_PSTDINT_H_INCLUDED)
194#include <stdint.h>
195#define _PSTDINT_H_INCLUDED
196# ifndef PRINTF_INT64_MODIFIER
197# define PRINTF_INT64_MODIFIER "ll"
198# endif
199# ifndef PRINTF_INT32_MODIFIER
200# define PRINTF_INT32_MODIFIER "l"
201# endif
202# ifndef PRINTF_INT16_MODIFIER
203# define PRINTF_INT16_MODIFIER "h"
204# endif
205# ifndef PRINTF_INTMAX_MODIFIER
206# define PRINTF_INTMAX_MODIFIER PRINTF_INT64_MODIFIER
207# endif
208# ifndef PRINTF_INT64_HEX_WIDTH
209# define PRINTF_INT64_HEX_WIDTH "16"
210# endif
211# ifndef PRINTF_INT32_HEX_WIDTH
212# define PRINTF_INT32_HEX_WIDTH "8"
213# endif
214# ifndef PRINTF_INT16_HEX_WIDTH
215# define PRINTF_INT16_HEX_WIDTH "4"
216# endif
217# ifndef PRINTF_INT8_HEX_WIDTH
218# define PRINTF_INT8_HEX_WIDTH "2"
219# endif
220# ifndef PRINTF_INT64_DEC_WIDTH
221# define PRINTF_INT64_DEC_WIDTH "20"
222# endif
223# ifndef PRINTF_INT32_DEC_WIDTH
224# define PRINTF_INT32_DEC_WIDTH "10"
225# endif
226# ifndef PRINTF_INT16_DEC_WIDTH
227# define PRINTF_INT16_DEC_WIDTH "5"
228# endif
229# ifndef PRINTF_INT8_DEC_WIDTH
230# define PRINTF_INT8_DEC_WIDTH "3"
231# endif
232# ifndef PRINTF_INTMAX_HEX_WIDTH
233# define PRINTF_INTMAX_HEX_WIDTH PRINTF_INT64_HEX_WIDTH
234# endif
235# ifndef PRINTF_INTMAX_DEC_WIDTH
236# define PRINTF_INTMAX_DEC_WIDTH PRINTF_INT64_DEC_WIDTH
237# endif
238
239/*
240 * Something really weird is going on with Open Watcom. Just pull some of
241 * these duplicated definitions from Open Watcom's stdint.h file for now.
242 */
243
244# if defined (__WATCOMC__) && __WATCOMC__ >= 1250
245# if !defined (INT64_C)
246# define INT64_C(x) (x + (INT64_MAX - INT64_MAX))
247# endif
248# if !defined (UINT64_C)
249# define UINT64_C(x) (x + (UINT64_MAX - UINT64_MAX))
250# endif
251# if !defined (INT32_C)
252# define INT32_C(x) (x + (INT32_MAX - INT32_MAX))
253# endif
254# if !defined (UINT32_C)
255# define UINT32_C(x) (x + (UINT32_MAX - UINT32_MAX))
256# endif
257# if !defined (INT16_C)
258# define INT16_C(x) (x)
259# endif
260# if !defined (UINT16_C)
261# define UINT16_C(x) (x)
262# endif
263# if !defined (INT8_C)
264# define INT8_C(x) (x)
265# endif
266# if !defined (UINT8_C)
267# define UINT8_C(x) (x)
268# endif
269# if !defined (UINT64_MAX)
270# define UINT64_MAX 18446744073709551615ULL
271# endif
272# if !defined (INT64_MAX)
273# define INT64_MAX 9223372036854775807LL
274# endif
275# if !defined (UINT32_MAX)
276# define UINT32_MAX 4294967295UL
277# endif
278# if !defined (INT32_MAX)
279# define INT32_MAX 2147483647L
280# endif
281# if !defined (INTMAX_MAX)
282# define INTMAX_MAX INT64_MAX
283# endif
284# if !defined (INTMAX_MIN)
285# define INTMAX_MIN INT64_MIN
286# endif
287# endif
288#endif
289
290#ifndef _PSTDINT_H_INCLUDED
291#define _PSTDINT_H_INCLUDED
292
293#ifndef SIZE_MAX
294# define SIZE_MAX (~(size_t)0)
295#endif
296
297/*
298 * Deduce the type assignments from limits.h under the assumption that
299 * integer sizes in bits are powers of 2, and follow the ANSI
300 * definitions.
301 */
302
303#ifndef UINT8_MAX
304# define UINT8_MAX 0xff
305#endif
306#ifndef uint8_t
307# if (UCHAR_MAX == UINT8_MAX) || defined (S_SPLINT_S)
308 typedef unsigned char uint8_t;
309# define UINT8_C(v) ((uint8_t) v)
310# else
311# error "Platform not supported"
312# endif
313#endif
314
315#ifndef INT8_MAX
316# define INT8_MAX 0x7f
317#endif
318#ifndef INT8_MIN
319# define INT8_MIN INT8_C(0x80)
320#endif
321#ifndef int8_t
322# if (SCHAR_MAX == INT8_MAX) || defined (S_SPLINT_S)
323 typedef signed char int8_t;
324# define INT8_C(v) ((int8_t) v)
325# else
326# error "Platform not supported"
327# endif
328#endif
329
330#ifndef UINT16_MAX
331# define UINT16_MAX 0xffff
332#endif
333#ifndef uint16_t
334#if (UINT_MAX == UINT16_MAX) || defined (S_SPLINT_S)
335 typedef unsigned int uint16_t;
336# ifndef PRINTF_INT16_MODIFIER
337# define PRINTF_INT16_MODIFIER ""
338# endif
339# define UINT16_C(v) ((uint16_t) (v))
340#elif (USHRT_MAX == UINT16_MAX)
341 typedef unsigned short uint16_t;
342# define UINT16_C(v) ((uint16_t) (v))
343# ifndef PRINTF_INT16_MODIFIER
344# define PRINTF_INT16_MODIFIER "h"
345# endif
346#else
347#error "Platform not supported"
348#endif
349#endif
350
351#ifndef INT16_MAX
352# define INT16_MAX 0x7fff
353#endif
354#ifndef INT16_MIN
355# define INT16_MIN INT16_C(0x8000)
356#endif
357#ifndef int16_t
358#if (INT_MAX == INT16_MAX) || defined (S_SPLINT_S)
359 typedef signed int int16_t;
360# define INT16_C(v) ((int16_t) (v))
361# ifndef PRINTF_INT16_MODIFIER
362# define PRINTF_INT16_MODIFIER ""
363# endif
364#elif (SHRT_MAX == INT16_MAX)
365 typedef signed short int16_t;
366# define INT16_C(v) ((int16_t) (v))
367# ifndef PRINTF_INT16_MODIFIER
368# define PRINTF_INT16_MODIFIER "h"
369# endif
370#else
371#error "Platform not supported"
372#endif
373#endif
374
375#ifndef UINT32_MAX
376# define UINT32_MAX (0xffffffffUL)
377#endif
378#ifndef uint32_t
379#if (ULONG_MAX == UINT32_MAX) || defined (S_SPLINT_S)
380 typedef unsigned long uint32_t;
381# define UINT32_C(v) v ## UL
382# ifndef PRINTF_INT32_MODIFIER
383# define PRINTF_INT32_MODIFIER "l"
384# endif
385#elif (UINT_MAX == UINT32_MAX)
386 typedef unsigned int uint32_t;
387# ifndef PRINTF_INT32_MODIFIER
388# define PRINTF_INT32_MODIFIER ""
389# endif
390# define UINT32_C(v) v ## U
391#elif (USHRT_MAX == UINT32_MAX)
392 typedef unsigned short uint32_t;
393# define UINT32_C(v) ((unsigned short) (v))
394# ifndef PRINTF_INT32_MODIFIER
395# define PRINTF_INT32_MODIFIER ""
396# endif
397#else
398#error "Platform not supported"
399#endif
400#endif
401
402#ifndef INT32_MAX
403# define INT32_MAX (0x7fffffffL)
404#endif
405#ifndef INT32_MIN
406# define INT32_MIN INT32_C(0x80000000)
407#endif
408#ifndef int32_t
409#if (LONG_MAX == INT32_MAX) || defined (S_SPLINT_S)
410 typedef signed long int32_t;
411# define INT32_C(v) v ## L
412# ifndef PRINTF_INT32_MODIFIER
413# define PRINTF_INT32_MODIFIER "l"
414# endif
415#elif (INT_MAX == INT32_MAX)
416 typedef signed int int32_t;
417# define INT32_C(v) v
418# ifndef PRINTF_INT32_MODIFIER
419# define PRINTF_INT32_MODIFIER ""
420# endif
421#elif (SHRT_MAX == INT32_MAX)
422 typedef signed short int32_t;
423# define INT32_C(v) ((short) (v))
424# ifndef PRINTF_INT32_MODIFIER
425# define PRINTF_INT32_MODIFIER ""
426# endif
427#else
428#error "Platform not supported"
429#endif
430#endif
431
432/*
433 * The macro stdint_int64_defined is temporarily used to record
434 * whether or not 64 integer support is available. It must be
435 * defined for any 64 integer extensions for new platforms that are
436 * added.
437 */
438
439#undef stdint_int64_defined
440#if (defined(__STDC__) && defined(__STDC_VERSION__)) || defined (S_SPLINT_S)
441# if (__STDC__ && __STDC_VERSION >= 199901L) || defined (S_SPLINT_S)
442# define stdint_int64_defined
443 typedef long long int64_t;
444 typedef unsigned long long uint64_t;
445# define UINT64_C(v) v ## ULL
446# define INT64_C(v) v ## LL
447# ifndef PRINTF_INT64_MODIFIER
448# define PRINTF_INT64_MODIFIER "ll"
449# endif
450# endif
451#endif
452
453#if !defined (stdint_int64_defined)
454# if defined(__GNUC__)
455# define stdint_int64_defined
456 __extension__ typedef long long int64_t;
457 __extension__ typedef unsigned long long uint64_t;
458# define UINT64_C(v) v ## ULL
459# define INT64_C(v) v ## LL
460# ifndef PRINTF_INT64_MODIFIER
461# define PRINTF_INT64_MODIFIER "ll"
462# endif
463# elif defined(__MWERKS__) || defined (__SUNPRO_C) || defined (__SUNPRO_CC) || defined (__APPLE_CC__) || defined (_LONG_LONG) || defined (_CRAYC) || defined (S_SPLINT_S)
464# define stdint_int64_defined
465 typedef long long int64_t;
466 typedef unsigned long long uint64_t;
467# define UINT64_C(v) v ## ULL
468# define INT64_C(v) v ## LL
469# ifndef PRINTF_INT64_MODIFIER
470# define PRINTF_INT64_MODIFIER "ll"
471# endif
472# elif (defined(__WATCOMC__) && defined(__WATCOM_INT64__)) || (defined(_MSC_VER) && _INTEGRAL_MAX_BITS >= 64) || (defined (__BORLANDC__) && __BORLANDC__ > 0x460) || defined (__alpha) || defined (__DECC)
473# define stdint_int64_defined
474 typedef __int64 int64_t;
475 typedef unsigned __int64 uint64_t;
476# define UINT64_C(v) v ## UI64
477# define INT64_C(v) v ## I64
478# ifndef PRINTF_INT64_MODIFIER
479# define PRINTF_INT64_MODIFIER "I64"
480# endif
481# endif
482#endif
483
484#if !defined (LONG_LONG_MAX) && defined (INT64_C)
485# define LONG_LONG_MAX INT64_C (9223372036854775807)
486#endif
487#ifndef ULONG_LONG_MAX
488# define ULONG_LONG_MAX UINT64_C (18446744073709551615)
489#endif
490
491#if !defined (INT64_MAX) && defined (INT64_C)
492# define INT64_MAX INT64_C (9223372036854775807)
493#endif
494#if !defined (INT64_MIN) && defined (INT64_C)
495# define INT64_MIN INT64_C (-9223372036854775808)
496#endif
497#if !defined (UINT64_MAX) && defined (INT64_C)
498# define UINT64_MAX UINT64_C (18446744073709551615)
499#endif
500
501/*
502 * Width of hexadecimal for number field.
503 */
504
505#ifndef PRINTF_INT64_HEX_WIDTH
506# define PRINTF_INT64_HEX_WIDTH "16"
507#endif
508#ifndef PRINTF_INT32_HEX_WIDTH
509# define PRINTF_INT32_HEX_WIDTH "8"
510#endif
511#ifndef PRINTF_INT16_HEX_WIDTH
512# define PRINTF_INT16_HEX_WIDTH "4"
513#endif
514#ifndef PRINTF_INT8_HEX_WIDTH
515# define PRINTF_INT8_HEX_WIDTH "2"
516#endif
517
518#ifndef PRINTF_INT64_DEC_WIDTH
519# define PRINTF_INT64_DEC_WIDTH "20"
520#endif
521#ifndef PRINTF_INT32_DEC_WIDTH
522# define PRINTF_INT32_DEC_WIDTH "10"
523#endif
524#ifndef PRINTF_INT16_DEC_WIDTH
525# define PRINTF_INT16_DEC_WIDTH "5"
526#endif
527#ifndef PRINTF_INT8_DEC_WIDTH
528# define PRINTF_INT8_DEC_WIDTH "3"
529#endif
530
531/*
532 * Ok, lets not worry about 128 bit integers for now. Moore's law says
533 * we don't need to worry about that until about 2040 at which point
534 * we'll have bigger things to worry about.
535 */
536
537#ifdef stdint_int64_defined
538 typedef int64_t intmax_t;
539 typedef uint64_t uintmax_t;
540# define INTMAX_MAX INT64_MAX
541# define INTMAX_MIN INT64_MIN
542# define UINTMAX_MAX UINT64_MAX
543# define UINTMAX_C(v) UINT64_C(v)
544# define INTMAX_C(v) INT64_C(v)
545# ifndef PRINTF_INTMAX_MODIFIER
546# define PRINTF_INTMAX_MODIFIER PRINTF_INT64_MODIFIER
547# endif
548# ifndef PRINTF_INTMAX_HEX_WIDTH
549# define PRINTF_INTMAX_HEX_WIDTH PRINTF_INT64_HEX_WIDTH
550# endif
551# ifndef PRINTF_INTMAX_DEC_WIDTH
552# define PRINTF_INTMAX_DEC_WIDTH PRINTF_INT64_DEC_WIDTH
553# endif
554#else
555 typedef int32_t intmax_t;
556 typedef uint32_t uintmax_t;
557# define INTMAX_MAX INT32_MAX
558# define UINTMAX_MAX UINT32_MAX
559# define UINTMAX_C(v) UINT32_C(v)
560# define INTMAX_C(v) INT32_C(v)
561# ifndef PRINTF_INTMAX_MODIFIER
562# define PRINTF_INTMAX_MODIFIER PRINTF_INT32_MODIFIER
563# endif
564# ifndef PRINTF_INTMAX_HEX_WIDTH
565# define PRINTF_INTMAX_HEX_WIDTH PRINTF_INT32_HEX_WIDTH
566# endif
567# ifndef PRINTF_INTMAX_DEC_WIDTH
568# define PRINTF_INTMAX_DEC_WIDTH PRINTF_INT32_DEC_WIDTH
569# endif
570#endif
571
572/*
573 * Because this file currently only supports platforms which have
574 * precise powers of 2 as bit sizes for the default integers, the
575 * least definitions are all trivial. Its possible that a future
576 * version of this file could have different definitions.
577 */
578
579#ifndef stdint_least_defined
580 typedef int8_t int_least8_t;
581 typedef uint8_t uint_least8_t;
582 typedef int16_t int_least16_t;
583 typedef uint16_t uint_least16_t;
584 typedef int32_t int_least32_t;
585 typedef uint32_t uint_least32_t;
586# define PRINTF_LEAST32_MODIFIER PRINTF_INT32_MODIFIER
587# define PRINTF_LEAST16_MODIFIER PRINTF_INT16_MODIFIER
588# define UINT_LEAST8_MAX UINT8_MAX
589# define INT_LEAST8_MAX INT8_MAX
590# define UINT_LEAST16_MAX UINT16_MAX
591# define INT_LEAST16_MAX INT16_MAX
592# define UINT_LEAST32_MAX UINT32_MAX
593# define INT_LEAST32_MAX INT32_MAX
594# define INT_LEAST8_MIN INT8_MIN
595# define INT_LEAST16_MIN INT16_MIN
596# define INT_LEAST32_MIN INT32_MIN
597# ifdef stdint_int64_defined
598 typedef int64_t int_least64_t;
599 typedef uint64_t uint_least64_t;
600# define PRINTF_LEAST64_MODIFIER PRINTF_INT64_MODIFIER
601# define UINT_LEAST64_MAX UINT64_MAX
602# define INT_LEAST64_MAX INT64_MAX
603# define INT_LEAST64_MIN INT64_MIN
604# endif
605#endif
606#undef stdint_least_defined
607
608/*
609 * The ANSI C committee pretending to know or specify anything about
610 * performance is the epitome of misguided arrogance. The mandate of
611 * this file is to *ONLY* ever support that absolute minimum
612 * definition of the fast integer types, for compatibility purposes.
613 * No extensions, and no attempt to suggest what may or may not be a
614 * faster integer type will ever be made in this file. Developers are
615 * warned to stay away from these types when using this or any other
616 * stdint.h.
617 */
618
619typedef int_least8_t int_fast8_t;
620typedef uint_least8_t uint_fast8_t;
621typedef int_least16_t int_fast16_t;
622typedef uint_least16_t uint_fast16_t;
623typedef int_least32_t int_fast32_t;
624typedef uint_least32_t uint_fast32_t;
625#define UINT_FAST8_MAX UINT_LEAST8_MAX
626#define INT_FAST8_MAX INT_LEAST8_MAX
627#define UINT_FAST16_MAX UINT_LEAST16_MAX
628#define INT_FAST16_MAX INT_LEAST16_MAX
629#define UINT_FAST32_MAX UINT_LEAST32_MAX
630#define INT_FAST32_MAX INT_LEAST32_MAX
631#define INT_FAST8_MIN INT_LEAST8_MIN
632#define INT_FAST16_MIN INT_LEAST16_MIN
633#define INT_FAST32_MIN INT_LEAST32_MIN
634#ifdef stdint_int64_defined
635 typedef int_least64_t int_fast64_t;
636 typedef uint_least64_t uint_fast64_t;
637# define UINT_FAST64_MAX UINT_LEAST64_MAX
638# define INT_FAST64_MAX INT_LEAST64_MAX
639# define INT_FAST64_MIN INT_LEAST64_MIN
640#endif
641
642#undef stdint_int64_defined
643
644/*
645 * Whatever piecemeal, per compiler thing we can do about the wchar_t
646 * type limits.
647 */
648
649#if defined(__WATCOMC__) || defined(_MSC_VER) || defined (__GNUC__)
650# include <wchar.h>
651# ifndef WCHAR_MIN
652# define WCHAR_MIN 0
653# endif
654# ifndef WCHAR_MAX
655# define WCHAR_MAX ((wchar_t)-1)
656# endif
657#endif
658
659/*
660 * Whatever piecemeal, per compiler/platform thing we can do about the
661 * (u)intptr_t types and limits.
662 */
663
664#if defined (_MSC_VER) && defined (_UINTPTR_T_DEFINED)
665# define STDINT_H_UINTPTR_T_DEFINED
666#endif
667
668#ifndef STDINT_H_UINTPTR_T_DEFINED
669# if defined (__alpha__) || defined (__ia64__) || defined (__x86_64__) || defined (_WIN64)
670# define stdint_intptr_bits 64
671# elif defined (__WATCOMC__) || defined (__TURBOC__)
672# if defined(__TINY__) || defined(__SMALL__) || defined(__MEDIUM__)
673# define stdint_intptr_bits 16
674# else
675# define stdint_intptr_bits 32
676# endif
677# elif defined (__i386__) || defined (_WIN32) || defined (WIN32)
678# define stdint_intptr_bits 32
679# elif defined (__INTEL_COMPILER)
680/* TODO -- what will Intel do about x86-64? */
681# endif
682
683# ifdef stdint_intptr_bits
684# define stdint_intptr_glue3_i(a,b,c) a##b##c
685# define stdint_intptr_glue3(a,b,c) stdint_intptr_glue3_i(a,b,c)
686# ifndef PRINTF_INTPTR_MODIFIER
687# define PRINTF_INTPTR_MODIFIER stdint_intptr_glue3(PRINTF_INT,stdint_intptr_bits,_MODIFIER)
688# endif
689# ifndef PTRDIFF_MAX
690# define PTRDIFF_MAX stdint_intptr_glue3(INT,stdint_intptr_bits,_MAX)
691# endif
692# ifndef PTRDIFF_MIN
693# define PTRDIFF_MIN stdint_intptr_glue3(INT,stdint_intptr_bits,_MIN)
694# endif
695# ifndef UINTPTR_MAX
696# define UINTPTR_MAX stdint_intptr_glue3(UINT,stdint_intptr_bits,_MAX)
697# endif
698# ifndef INTPTR_MAX
699# define INTPTR_MAX stdint_intptr_glue3(INT,stdint_intptr_bits,_MAX)
700# endif
701# ifndef INTPTR_MIN
702# define INTPTR_MIN stdint_intptr_glue3(INT,stdint_intptr_bits,_MIN)
703# endif
704# ifndef INTPTR_C
705# define INTPTR_C(x) stdint_intptr_glue3(INT,stdint_intptr_bits,_C)(x)
706# endif
707# ifndef UINTPTR_C
708# define UINTPTR_C(x) stdint_intptr_glue3(UINT,stdint_intptr_bits,_C)(x)
709# endif
710 typedef stdint_intptr_glue3(uint,stdint_intptr_bits,_t) uintptr_t;
711 typedef stdint_intptr_glue3( int,stdint_intptr_bits,_t) intptr_t;
712# else
713/* TODO -- This following is likely wrong for some platforms, and does
714 nothing for the definition of uintptr_t. */
715 typedef ptrdiff_t intptr_t;
716# endif
717# define STDINT_H_UINTPTR_T_DEFINED
718#endif
719
720/*
721 * Assumes sig_atomic_t is signed and we have a 2s complement machine.
722 */
723
724#ifndef SIG_ATOMIC_MAX
725# define SIG_ATOMIC_MAX ((((sig_atomic_t) 1) << (sizeof (sig_atomic_t)*CHAR_BIT-1)) - 1)
726#endif
727
728#endif
729
730#if defined (__TEST_PSTDINT_FOR_CORRECTNESS)
731
732/*
733 * Please compile with the maximum warning settings to make sure macros are not
734 * defined more than once.
735 */
736
737#include <stdlib.h>
738#include <stdio.h>
739#include <string.h>
740
741#define glue3_aux(x,y,z) x ## y ## z
742#define glue3(x,y,z) glue3_aux(x,y,z)
743
744#define DECLU(bits) glue3(uint,bits,_t) glue3(u,bits,=) glue3(UINT,bits,_C) (0);
745#define DECLI(bits) glue3(int,bits,_t) glue3(i,bits,=) glue3(INT,bits,_C) (0);
746
747#define DECL(us,bits) glue3(DECL,us,) (bits)
748
749#define TESTUMAX(bits) glue3(u,bits,=) glue3(~,u,bits); if (glue3(UINT,bits,_MAX) glue3(!=,u,bits)) printf ("Something wrong with UINT%d_MAX\n", bits)
750
751int main () {
752 DECL(I,8)
753 DECL(U,8)
754 DECL(I,16)
755 DECL(U,16)
756 DECL(I,32)
757 DECL(U,32)
758#ifdef INT64_MAX
759 DECL(I,64)
760 DECL(U,64)
761#endif
762 intmax_t imax = INTMAX_C(0);
763 uintmax_t umax = UINTMAX_C(0);
764 char str0[256], str1[256];
765
766 sprintf (str0, "%d %x\n", 0, ~0);
767
768 sprintf (str1, "%d %x\n", i8, ~0);
769 if (0 != strcmp (str0, str1)) printf ("Something wrong with i8 : %s\n", str1);
770 sprintf (str1, "%u %x\n", u8, ~0);
771 if (0 != strcmp (str0, str1)) printf ("Something wrong with u8 : %s\n", str1);
772 sprintf (str1, "%d %x\n", i16, ~0);
773 if (0 != strcmp (str0, str1)) printf ("Something wrong with i16 : %s\n", str1);
774 sprintf (str1, "%u %x\n", u16, ~0);
775 if (0 != strcmp (str0, str1)) printf ("Something wrong with u16 : %s\n", str1);
776 sprintf (str1, "%" PRINTF_INT32_MODIFIER "d %x\n", i32, ~0);
777 if (0 != strcmp (str0, str1)) printf ("Something wrong with i32 : %s\n", str1);
778 sprintf (str1, "%" PRINTF_INT32_MODIFIER "u %x\n", u32, ~0);
779 if (0 != strcmp (str0, str1)) printf ("Something wrong with u32 : %s\n", str1);
780#ifdef INT64_MAX
781 sprintf (str1, "%" PRINTF_INT64_MODIFIER "d %x\n", i64, ~0);
782 if (0 != strcmp (str0, str1)) printf ("Something wrong with i64 : %s\n", str1);
783#endif
784 sprintf (str1, "%" PRINTF_INTMAX_MODIFIER "d %x\n", imax, ~0);
785 if (0 != strcmp (str0, str1)) printf ("Something wrong with imax : %s\n", str1);
786 sprintf (str1, "%" PRINTF_INTMAX_MODIFIER "u %x\n", umax, ~0);
787 if (0 != strcmp (str0, str1)) printf ("Something wrong with umax : %s\n", str1);
788
789 TESTUMAX(8);
790 TESTUMAX(16);
791 TESTUMAX(32);
792#ifdef INT64_MAX
793 TESTUMAX(64);
794#endif
795
796 return EXIT_SUCCESS;
797}
798
799#endif
Compare STL sort with C qsort
File sortCompare.cc
1// to compile on unix/OSX use
2// g++ -I. sortCompare.cc TimeMeter.cc
3//
4
5// include header for C++ I/O
6// search stdio.h in standard C/C++ include directory e.g. /usr/include
7#include <iostream> // for the definition of cin, cout, ...
8#include <iomanip> // for manipulator setw, setprecision ...
9
10// include header for STL vector and algorithm
11#include <vector>
12#include <algorithm>
13
14// if in windows use a portable version of stdint.h
15#ifdef _WIN32
16 #include "pstdint.h" // for uint64_t
17#else
18 #include <stdint.h> // for uint64_t
19#endif
20
21#include <stdlib.h> // for qsort
22
23#include <cstdlib> // near equivalent to <stdlib.h> for exit, rand, ...
24#include <cmath> // near equivalent to <math.h> for sin, cos, log, ..
25
26#include "TimeMeter.hh" // class computing elapsed time
27
28using namespace std ;
29
30// general random numer generator
31template <typename U>
32inline
33U random() { return rand() ; }
34
35// specialization for uint32_t (32 bit integer)
36template <>
37inline
38uint32_t random<uint32_t>() {
39 return uint32_t(rand()) ^ (uint32_t(rand())<<16) ;
40}
41
42// specialization for uint64_t (64 bit integer)
43template <>
44inline
45uint64_t random<uint64_t>() {
46 return uint64_t(rand()) ^
47 (uint64_t(rand())<<16) ^
48 (uint64_t(rand())<<32) ^
49 (uint64_t(rand())<<48) ;
50}
51
52
53typedef uint64_t INTEGER ; // make an alias for uint64_t
54
55int
56C_comparator( void const * a, void const * b ) {
57 INTEGER const & A = *(static_cast<INTEGER const *>(a)) ;
58 INTEGER const & B = *(static_cast<INTEGER const *>(b)) ;
59 if ( A < B ) return -1 ;
60 if ( A > B ) return +1 ;
61 return 0 ;
62}
63
64int
65main() {
66
67 vector<double> elapsed ; // define a vector containing saved elapsed time
68 vector<double> elapsed1 ; // define a vector containing saved elapsed time
69 vector<unsigned> sizevec ; // define a vector containing saved sizes
70 vector<INTEGER> A, B ; // a working vector with number to be oredered
71 TimeMeter tm ; // tm is an instance of a class TimeMeter for timing
72
73 elapsed . clear() ;
74 sizevec . clear() ; // vector are emptied and reduced of size 0
75 for ( unsigned sz = 1000 ; sz <= 1000000 ; sz *= 2 ) {
76 A . clear() ; // empty the vector, size is 0
77 A . reserve( sz ) ; // reserve memory for sz elements
78 for ( unsigned j = 0 ; j < sz ; ++j ) A . push_back( random<INTEGER>() ) ;
79
80 // make a copy of vector A
81 B . resize(A . size()) ;
82 copy( A.begin(), A.end(), B.begin() ) ;
83
84 cout << "sorting " << setw(6) << sz << flush ;
85
86 // setw(6) reserve 6 character for the next output
87 // flush : write immediately to the standard output (empty the buffer)
88 tm . start() ; // start time computation
89 sort( A . begin(), A . end() ) ; // STL ruotine to sort a vector
90 double e = tm . milliseconds() ;
91 elapsed . push_back( e ) ;
92 sizevec . push_back( sz ) ;
93 cout << " STL: " << setprecision(4) << setw(6) << e << "ms " ;
94
95 // using qsort
96 tm . start() ; // start time computation
97 qsort( &B.front(), B.size(), sizeof(B[0]), C_comparator ) ;
98 e = tm . milliseconds() ;
99 elapsed1 . push_back( e ) ;
100 cout << " qsort: " << setprecision(4) << setw(6) << e << "ms\n" ;
101
102 }
103
104 cout << "\n\n\n" ;
105 for ( unsigned i = 0 ; i < sizevec . size() ; ++i ) {
106 double e = elapsed[i] ;
107 double e1 = elapsed1[i] ;
108 unsigned sz = sizevec[i] ;
109 cout << "n = " << setw(6) << sz
110 << " elapsed " << setw(8) << setprecision(4) << e << "ms"
111 << " elapsed/(n*log(n)) = " << setw(10) << 100000*e/(sz*log(sz))
112 << " elapsed1 " << setw(8) << setprecision(4) << e1 << "ms"
113 << " elapsed1/(n*log(n)) = " << setw(10) << 100000*e1/(sz*log(sz))
114 << " elapsed1/elapsed = " << setw(10) << e1/e
115 << '\n' ;
116 }
117 return 0 ; // return is a statement for returning value to the caller
118}
119
120/*
121Results with various optimization options
122
123g++ -O0 -I. sortCompare.cc TimeMeter.cc
124
125sorting 1000 STL: 0.194ms qsort: 0.132ms
126sorting 2000 STL: 0.448ms qsort: 0.276ms
127sorting 4000 STL: 0.943ms qsort: 0.679ms
128sorting 8000 STL: 2.022ms qsort: 1.288ms
129sorting 16000 STL: 4.66ms qsort: 2.761ms
130sorting 32000 STL: 13.11ms qsort: 6.587ms
131sorting 64000 STL: 18.91ms qsort: 13.21ms
132sorting 128000 STL: 45.3ms qsort: 26.46ms
133sorting 256000 STL: 90.34ms qsort: 57.22ms
134sorting 512000 STL: 187.6ms qsort: 126.4ms
135
136g++ -O1 -I. sortCompare.cc TimeMeter.cc
137
138sorting 1000 STL: 0.044ms qsort: 0.097ms
139sorting 2000 STL: 0.093ms qsort: 0.221ms
140sorting 4000 STL: 0.2ms qsort: 0.497ms
141sorting 8000 STL: 0.49ms qsort: 0.922ms
142sorting 16000 STL: 1.237ms qsort: 2.168ms
143sorting 32000 STL: 1.999ms qsort: 4.228ms
144sorting 64000 STL: 5.265ms qsort: 10.21ms
145sorting 128000 STL: 8.86ms qsort: 19.68ms
146sorting 256000 STL: 18.47ms qsort: 44.15ms
147sorting 512000 STL: 45.12ms qsort: 88.37ms
148
149g++ -O2 -I. sortCompare.cc TimeMeter.cc
150
151sorting 1000 STL: 0.042ms qsort: 0.096ms
152sorting 2000 STL: 0.09ms qsort: 0.2ms
153sorting 4000 STL: 0.192ms qsort: 0.427ms
154sorting 8000 STL: 0.408ms qsort: 0.93ms
155sorting 16000 STL: 0.997ms qsort: 2.145ms
156sorting 32000 STL: 1.864ms qsort: 4.203ms
157sorting 64000 STL: 4.076ms qsort: 14.47ms
158sorting 128000 STL: 8.562ms qsort: 20.16ms
159sorting 256000 STL: 18.13ms qsort: 41.41ms
160sorting 512000 STL: 42.95ms qsort: 85.43ms
161
162g++ -O3 -I. sortCompare.cc TimeMeter.cc
163
164sorting 1000 STL: 0.042ms qsort: 0.096ms
165sorting 2000 STL: 0.087ms qsort: 0.209ms
166sorting 4000 STL: 0.256ms qsort: 0.429ms
167sorting 8000 STL: 0.406ms qsort: 0.912ms
168sorting 16000 STL: 0.872ms qsort: 1.962ms
169sorting 32000 STL: 1.89ms qsort: 5.299ms
170sorting 64000 STL: 4.61ms qsort: 9.939ms
171sorting 128000 STL: 8.526ms qsort: 19.9ms
172sorting 256000 STL: 19.01ms qsort: 43.14ms
173sorting 512000 STL: 40.74ms qsort: 84.79ms
174
175*/