Thinking In C++. Volume 2: Practical Programming

In this example we’ve replaced the output sequence b in the third argument to remove_copy_if( ) with an output stream iterator, which is an instance of the ostream_iterator class template declared in the header. Output stream iterators overload their copy-assignment operators to write to their stream. This particular instance of ostream_iterator is attached to the output stream cout. Every time remove_copy_if( ) assigns an integer from the sequence a to cout through this iterator, the iterator writes the integer to cout and also automatically writes an instance of the separator string found in its second argument, which in this case contains just the newline character.

It is just as easy to write to a file instead of to cout, of course. All you have to do is provide an output file stream instead of cout:^.

//: C06:CopyIntsToFile.cpp

// Uses an output file stream iterator

#include

#include

#include

#include

using namespace std;

bool gt15(int x) {

  return 15 < x;

}

int main() {

  int a[] = {10, 20, 30};

  const size_t SIZE = sizeof a / sizeof a[0];

  ofstream outf("ints.out");

  remove_copy_if(a, a + SIZE,

  ostream_iterator(outf, "\n"), gt15);

} ///:~^.

An input stream iterator allows an algorithm to get its input sequence from an input stream. This is accomplished by having both the constructor and operator++( ) read the next element from the underlying stream and by overloading operator*( ) to yield the value previously read. Since algorithms require two pointers to delimit an input sequence, you can construct an istream_iterator in two ways, as you can see in the program that follows^.

//: C06:CopyIntsFromFile.cpp

// Uses an input stream iterator

#include

#include

#include

#include

#include "../require.h"

using namespace std;

bool gt15(int x) {

  return 15 < x;

}

int main() {

  ifstream inf("someInts.dat");

  assure(inf, "someInts.dat");

  remove_copy_if(istream_iterator(inf),

  istream_iterator(),

  ostream_iterator(cout, "\n"), gt15);

} ///:~^.

The first argument to replace_copy_if( ) in this program attaches an istream_iterator object to the input file stream containing ints. The second argument uses the default constructor of the istream_iterator class. This call constructs a special value of istream_iterator that indicates end-of-file, so that when the first iterator finally encounters the end of the physical file, it compares equal to the value istream_iterator( ), allowing the algorithm to terminate correctly. Note that this example avoids using an explicit array altogether^.

Algorithm complexity

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. Naturally, 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). Therefore, find is said to make at most a number of comparisons equal to the number of elements in the sequence^.