| Thinking in C++ Vol 2 - Practical Programming |
|
Prev |
Home |
Next |
Using a software library is a matter of trust. You trust the
implementers to not only provide correct functionality, but you also hope that
the functions execute as efficiently as possible. It s better to write your own
loops than to use algorithms that degrade performance.
To guarantee quality library implementations, the C++
Standard not only specifies what an algorithm should do, but how fast it should
do it and sometimes how much space it should use. Any algorithm that does not
meet the performance requirements does not conform to the standard. The measure
of an algorithm s operational efficiency is called its complexity.
When possible, the standard specifies the exact number of
operation counts an algorithm should use. The count_if( ) algorithm, for example, returns the number of elements in a sequence satisfying a given
predicate. The following call to count_if( ), if applied to a
sequence of integers similar to the examples earlier in this chapter, yields
the number of integer elements that are greater than 15:
size_t n = count_if(a, a + SIZE, gt15);
Since count_if( ) must look at every element
exactly once, it is specified to make a number of comparisons exactly equal to
the number of elements in the sequence. The copy( ) algorithm has
the same specification.
Other algorithms can be specified to take at most a
certain number of operations. The find( ) algorithm searches through a sequence in order until it encounters an element equal to its third
argument:
int* p = find(a, a + SIZE, 20);
It stops as soon as the element is found and returns a pointer
to that first occurrence. If it doesn t find one, it returns a pointer one
position past the end of the sequence (a+SIZE in this example). So find()
makes at most a number of comparisons equal to the number of elements in the
sequence.
Sometimes the number of operations an algorithm takes cannot
be measured with such precision. In such cases, the standard specifies the
algorithm s asymptotic complexity, which is a measure of how the
algorithm behaves with large sequences compared to well-known formulas. A good
example is the sort( ) algorithm, which the standard says takes
approximately n log n comparisons on average (n is the number
of elements in the sequence). Such
complexity measures give a feel for the cost of an algorithm and at least
give a meaningful basis for comparing algorithms. As you ll see in the next
chapter, the find( ) member function for the set container
has logarithmic complexity, which means that the cost of searching for an
element in a set will, for large sets, be proportional to the logarithm
of the number of elements. This is much smaller than the number of elements for
large n, so it is always better to search a set by using its find( )
member function rather than by using the generic find( ) algorithm.
| Thinking in C++ Vol 2 - Practical Programming |
|
Prev |
Home |
Next |
