Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |
The STL has a predefined set of iterators that can be quite
handy. For example, you ve already seen the reverse_iterator objects produced by calling rbegin( ) and rend( ) for all the basic containers.
The insertion iterators are necessary because some of
the STL algorithms copy( ), for example use the assignment operator=
to place objects in the destination container. This is a problem when you re
using the algorithm to fill the container rather than to overwrite items
that are already in the destination container that is, when the space isn t
already there. What the insert iterators do is change the implementation of operator=
so that instead of doing an assignment, it calls a push or insert function
for that container, thus causing it to allocate new space. The constructors for
both back_insert_iterator and front_insert_iterator take a basic sequence container object (vector, deque or list) as their argument and produce an
iterator that calls push_back( ) or push_front( ), respectively, to perform assignment. The helper functions back_inserter( ) and front_inserter( ) produce these insert-iterator objects with a
little less typing. Since all the basic sequence containers support push_back( ),
you will probably find yourself using back_inserter( ) with some
regularity.
An insert_iterator lets you insert elements in the middle of the sequence, again replacing the meaning of operator=, but this time
by automatically calling insert( ) instead of one of the push functions. The insert( ) member function requires an iterator indicating the
place to insert before, so the insert_iterator requires this iterator in
addition to the container object. The shorthand function inserter( ) produces the same object.
The following example shows the use of the different types
of inserters:
//: C07:Inserters.cpp
// Different types of iterator inserters.
#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <iterator>
using namespace std;
int a[] = { 1, 3, 5, 7, 11, 13, 17, 19, 23 };
template<class Cont> void
frontInsertion(Cont& ci) {
copy(a, a + sizeof(a)/sizeof(Cont::value_type),
front_inserter(ci));
copy(ci.begin(), ci.end(),
ostream_iterator<typename Cont::value_type>(
cout, " "));
cout << endl;
}
template<class Cont> void backInsertion(Cont&
ci) {
copy(a, a + sizeof(a)/sizeof(Cont::value_type),
back_inserter(ci));
copy(ci.begin(), ci.end(),
ostream_iterator<typename Cont::value_type>(
cout, " "));
cout << endl;
}
template<class Cont> void midInsertion(Cont&
ci) {
typename Cont::iterator it = ci.begin();
++it; ++it; ++it;
copy(a, a + sizeof(a)/(sizeof(Cont::value_type) * 2),
inserter(ci, it));
copy(ci.begin(), ci.end(),
ostream_iterator<typename Cont::value_type>(
cout, " "));
cout << endl;
}
int main() {
deque<int> di;
list<int> li;
vector<int> vi;
// Can't use a front_inserter() with vector
frontInsertion(di);
frontInsertion(li);
di.clear();
li.clear();
backInsertion(vi);
backInsertion(di);
backInsertion(li);
midInsertion(vi);
midInsertion(di);
midInsertion(li);
} ///:~
Since vector does not support push_front( ),
it cannot produce a front_insert_iterator. However, you can see that vector
does support the other two types of insertions (even though, as you shall see
later, insert( ) is not an efficient operation for vector).
Note the use of the nested type Cont::value_type instead of hard-coding int.
More on stream iterators
We introduced the use of the stream iterators ostream_iterator (an output iterator) and istream_iterator (an input iterator) in conjunction with copy( ) in the previous chapter. Remember that an output stream
doesn t have any concept of an end, since you can always just keep writing
more elements. However, an input stream eventually terminates (for example,
when you reach the end of a file), so you need a way to represent that. An istream_iterator
has two constructors, one that takes an istream and produces the
iterator you actually read from, and the other which is the default constructor
and produces an object that is the past-the-end sentinel. In the following
program this object is named end:
//: C07:StreamIt.cpp
// Iterators for istreams and ostreams.
#include <fstream>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
#include "../require.h"
using namespace std;
int main() {
ifstream in("StreamIt.cpp");
assure(in, "StreamIt.cpp");
istream_iterator<string> begin(in), end;
ostream_iterator<string> out(cout,
"\n");
vector<string> vs;
copy(begin, end, back_inserter(vs));
copy(vs.begin(), vs.end(), out);
*out++ = vs[0];
*out++ = "That's all, folks!";
} ///:~
When in runs out of input (in this case when the end
of the file is reached), init becomes equivalent to end, and the copy( )
terminates.
Because out is an ostream_iterator<string>, you can simply assign any string object to the dereferenced iterator using operator=,
and that string will be placed on the output stream, as seen in the two assignments
to out. Because out is defined with a newline as its second
argument, these assignments also insert a newline along with each assignment.
Although it is possible to create an istream_iterator<char>
and ostream_iterator<char>, these actually parse the input
and thus will, for example, automatically eat whitespace (spaces, tabs, and
newlines), which is not desirable if you want to manipulate an exact
representation of an istream. Instead, you can use the special iterators
istreambuf_iterator and ostreambuf_iterator, which are designed strictly to move characters. Although
these are templates, they are meant to be used with template arguments of
either char or wchar_t. The
following example lets you compare the behavior of the stream iterators with
the streambuf iterators:
//: C07:StreambufIterator.cpp
// istreambuf_iterator & ostreambuf_iterator.
#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
#include "../require.h"
using namespace std;
int main() {
ifstream in("StreambufIterator.cpp");
assure(in, "StreambufIterator.cpp");
// Exact representation of stream:
istreambuf_iterator<char> isb(in), end;
ostreambuf_iterator<char> osb(cout);
while(isb != end)
*osb++ = *isb++; // Copy 'in' to cout
cout << endl;
ifstream in2("StreambufIterator.cpp");
// Strips white space:
istream_iterator<char> is(in2), end2;
ostream_iterator<char> os(cout);
while(is != end2)
*os++ = *is++;
cout << endl;
} ///:~
The stream iterators use the parsing defined by istream::operator>>,
which is probably not what you want if you are parsing characters directly it s
fairly rare that you want all the whitespace stripped out of your character
stream. You ll virtually always want to use a streambuf iterator when using
characters and streams, rather than a stream iterator. In addition, istream::operator>>
adds significant overhead for each operation, so it is only appropriate for
higher-level operations such as parsing numbers.
Manipulating raw storage
The raw_storage_iterator is defined in <memory> and is an output iterator. It is provided to enable algorithms to store their results
in uninitialized memory. The interface is quite simple: the constructor takes
an output iterator that is pointing to the raw memory (typically a pointer),
and the operator= assigns an object into that raw memory. The template
parameters are the type of the output iterator pointing to the raw storage and
the type of object that will be stored. Here s an example that creates Noisy
objects, which print trace statements for their construction, assignment, and
destruction (we ll show the Noisy class definition later):
//: C07:RawStorageIterator.cpp {-bor}
// Demonstrate the raw_storage_iterator.
//{L} Noisy
#include <iostream>
#include <iterator>
#include <algorithm>
#include "Noisy.h"
using namespace std;
int main() {
const int QUANTITY = 10;
// Create raw storage and cast to desired type:
Noisy* np = reinterpret_cast<Noisy*>(
new char[QUANTITY * sizeof(Noisy)]);
raw_storage_iterator<Noisy*, Noisy> rsi(np);
for(int i = 0; i < QUANTITY; i++)
*rsi++ = Noisy(); // Place objects in storage
cout << endl;
copy(np, np + QUANTITY,
ostream_iterator<Noisy>(cout, "
"));
cout << endl;
// Explicit destructor call for cleanup:
for(int j = 0; j < QUANTITY; j++)
(&np[j])->~Noisy();
// Release raw storage:
delete reinterpret_cast<char*>(np);
} ///:~
To make the raw_storage_iterator template happy, the
raw storage must be of the same type as the objects you re creating. That s why
the pointer from the new array of char is cast to a Noisy*. The
assignment operator forces the objects into the raw storage using the
copy-constructor. Note that the explicit destructor call must be made for proper cleanup, and this also allows the objects to be deleted one at a time
during container manipulation. The expression delete np would be invalid
anyway since the static type of a pointer in a delete expression must be
the same as the type assigned to in the new expression.
Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |