On a previous expedition to this territory [ Love2001 ], we explored some of the basic ideas behind the STL, and how to make simple use of it effectively. This time we'll be shining a light on the associative containers, something we missed out on before. In passing, we'll see some more algorithms, some more functors, and some more ways to extend the STL and bend it to your will. So get your hats on! We're going underground...
Stalagmites & Stalactites Revisited - Containers & Iterators
A quick recap then, since we're passing through. The C++ Standard Library provides us with seven main container classes, consisting of three sequence containers, and four associative containers. On our last trip we looked a little at the sequence containers, list , vector and deque , and saw some of their common characteristics, and some of their individualities.
This time, we'll look at the associative containers, map , multimap , set and multiset , see what sets them apart from the sequences, and what distinguishes them from each other. Of course, they also have lots in common with the sequence containers, and we'll have a look at those, too.
There is one other container class we'll have a look at here as well. It's well hidden in a dark corner right at the back; even the C++ Standard seems to mention it only as an afterthought ( [ ISO1998 ], 23.1.2/1 ("Associative Containers") does not mention it at all, but it is described at the end of that section). The standard associative container called bitset is useful, after all, and we will see some common ways to put it to work.
First off, though, let's look at everyone's favourite punch-bag. Love it, or hate it, we can, I'm sure, find some use for it. A word about...
Bed Of Flint - Standard String
Much has been written on this chap of late, quite a lot of it not terribly complimentary, and the truth is, the string class has its flaws. It isn't pretty, and it doesn't always do what you'd expect, but if you're careful and treat it kindly, you'll have a friend for life.
Strings are commonly used to store information such as names, sentences and so on. Given a string such as "Steve", or "My house is on a hill" it's easy, and you are in fact encouraged to think of the string as a singular entity, rather than a sequence of characters. Hence, it is useful to think of adding strings together (one time when addition is not commutative, because "Steve" + "Love" isn't the same as "Love" + "Steve") and reading from a file:
string name; cin >> name;
It is sometimes useful to remember that a string is a sequence of characters, however. As it happens, the standard string class conforms to all the requirements of a standard Sequence container [ 1 ] . This isn't hard - you must have iterators, and a begin() - end() pair of member functions which describe the sequence [ 2 ] . This turns out to be extremely useful. In our previous visit, we looked at the standard algorithm find_if() , which in the case of a string could be used to find a single character. This is a generally useful technique for parsing a string; so is finding a partial string, a sub-sequence. Again, the C++ Standard Library provides:
string s( "My house is on a hill" );
string sub( " is" );
string::iterator p =
search( s.begin(), s.end(),
sub.begin(), sub.end() );
s = string( s.begin(), p );
cout << s << "\n";
This will print "My house" to the console.
While we're on the topic, let's have a look at one way you can use the techniques of iterators, algorithms and sequences to reduce the above code. The elements are already there; search() returns an iterator to the start of the found sub-sequence ( End if it can't find it). You can make a new string from a sequence of iterators. So how about:
s = string( s.begin(),
search( s.begin(), s.end(),
sub.begin(), sub.end() ) );
We're replacing the string s with a new string created from the range [ s.begin(). search(...) ). To the uninitiated, this expression may appear over-complicated, but then if you're not a C++ or C programmer, so does any usage of strtok() .
So, the standard string isn't strictly a part of the C++ STL. It is an extension to it, albeit a standard one, and shows how easy it is to roll your own container classes which work seamlessly with the rest of STL.
Reflections - Unique Associative Containers
On the subject of strings, how many of you have ever wanted to do this:
void function( const string & s )
{
switch( s )
{
case "Jan":
//...
case "Feb":
//...
}
}
It seems perfectly reasonable, and yet can't be done; string is a class after all, not a built-in integral type. But there must be a better way than
void function( const string & s )
{
if( s == "Jan" )
{
//...
}
else if( s == "Feb" )
{
//...
}
//...
}
Map
Well, you guessed it. If there weren't, I wouldn't be talking about it. Enter the multi-talented map container. map is a Pair Associative Container; it maps a key to a value. More than that, a map is sorted by its key, which has the fortunate effect of making it easily searchable by its key. Correspondingly, the type used for a key in a map container must be Less Than Comparable [ Austern1998 ] [ 3 ] .
A map stores two objects per element; one is the key, the other the value. So that both key and value types can be any type, built-in or user-defined, the C++ Standard Library has a helper class called pair , which is parameterised on its first and second types:
template <class _T1, class _T2>
struct pair {
pair( const _T1 & f, const _t2 & s )
: first( f ), second( s ) { }
_T1 first;
_T2 second;
}; // from [STLPort2001]
map stores elements of type pair and uses first as the key and second as the value. (The pair type is much more generally useful, as we shall see). There is also a helper function for making pairs allowing us to add items to a map like this:
map< string, int > months; months.insert( make_pair( "Jan", 1 ) ); months.insert( make_pair( "Feb", 2 ) );
Here we create a map with string as the key type and int as the value, and start adding months to the container.
There are two things to note about this piece of code. First, we've created a map and associated the value 1 with the string "Jan" and the value 2 with the string "Feb". This is straightforward enough. The second item of note is that a map is sorted on its key; printing the map "in order" demonstrates this [ 4 ] :
void print_me(const pair<string, int>
&value){
cout << value.first << ","
<< value.second << "\n";
}
// ...
for_each( months.begin(), months.end(),
print_me );
// Output:
// Feb,2
// Jan,1
Remember that the key is the string type for our map months, and so "Feb" comes before "Jan", lexically speaking. Remember also that map stores pairs of elements, so naturally its iterators will point to a pair . There is a third thing to note there: this isn't really what you'd normally do with a map . Sure we can use a map as a method of sorting elements in a container, but its best feature is that it associates elements - keys and values. Being sorted is a side-effect of map 's greatest attribute - the ability to efficiently find a value given its key.
map can be used as an associative array; it directly supports the array notation (square brackets [] in C++) to provide a key and obtain its associated value. Because our value type is a built-in integral type (which the switch statement requires) we can do the following:
void function( const string & s ) {
switch(months[ s ] ) {
case 1: // Jan
case 2: // Feb
}
}
Which is much more like our original requirement [ 5 ] .
There is a snag to this; you might ask yourself what does the map do if the element identified by s doesn't exist? We appear to have no way of knowing whether the lookup failed, because it isn't reasonable for operator[] to return an invalid value, since it cannot know what is valid. This suggests that operator[] for map never fails, which is in fact the case. If the lookup fails to locate the key provided, a new element with that key is created. The value for that key will be default constructed. operator[] actually returns a reference to the value, so you can change it using assignment:
months[ "Mar" ] = 3;
The snag is that this may not do what you expect - you may be creating a new element and not know it.
There is another method of searching a map which, in keeping with the standard algorithms, returns an iterator to the found element, or End if the item is not found. map provides its own member function for this because firstly the map contains pair s, so using the find() or find_if() algorithms would be clumsy, and partly because map itself is optimised for searching, and the algorithms don't know about this. Using the member function, you search directly for the key, and an iterator is returned:
map< string, int >::iterator p =
months.find( "Jan" );
if(p != months.end()) {
cout << p->second; // the value
}
The other useful attribute of map is that it is a Unique Associative Container, meaning that it does not store duplicate keys. If you try to insert two values with the same key, the second insertion will fail. This failure is indicated by the return value from map::insert() , which is a pair object containing a map iterator and a bool . The iterator points either to the newly inserted element, in which case the bool is true , or to the already existing element with the same key, in which case the bool is false :
pair<map<string, int>::iterator, bool>
p = months.insert( make_pair("Apr", 4));
if(! p->second) { // the insertion failed
cout << p->first->second;
// print the value associated with "Mar"
// remember an iterator points to a pair
// element
}
In practice, you won't need all this syntax. You will either want to know whether the insertion took place, or you will want to do something with value. In the first case, you can use:
if(!months.insert(
make_pair( "May", 5)->second){
// do something if insertion failed
}
and in the second, using the array syntax operator[] works fine:
months[ "Jun" ] = 6;
Whether it is less efficient to overwrite the value of an existing element or search for it first will depend upon what the value type is. As they say on the newsgroups, YMMV.
Set
The set class has similarities with map; for instance, it contains only unique elements (it's a model of Unique Associative Container), is sorted by its key and is optimised for searching. It differs in one very important way: it contains single elements, rather than pair s. It is a Simple Associative Container [ Austern1998 ], which means that its key and value types are the same thing.
In particular, this difference means you cannot use set as an associative array; it does not have an operator[] for array-like access to elements. So why have a set container at all?
Well, OK now we get into the realms of speculation (by some well-respected figures, it has to be said). The STL is not a collection of containers. It has been said that STL is merely a "specification of a library of algorithms" [ Henney2001 ], not actually a collection of anything, really. What it means is that if you write your own container, algorithm, iterator, and it conforms to the requirements that STL places on such things, then it is just as much a part of the STL as those components shipped with the C++ Standard Library.
So back to set , and its raison d'être . We need to look behind the set container, at what makes it useful, before we can see its utility. We can guess that it models the concept of Set from mathematics. In fact, that would be inaccurate; mathematical set theory really concerns the operations on sets: Union; Intersection; Difference; Contains. In fact the STL has algorithms for providing these services, and they require that the range of iterators upon which they operate is sorted. This is a key issue, which we passed over fairly quickly in our last trip. The STL algorithms don't work on containers at all, they work with iterators. The container classes can be easily seen as various convenient ways of providing iterators and iterator ranges.
set is no exception. It is a container which happily allows the STL set algorithms to work according to the expected mathematical concepts of those operations ( [ Austern1998 ]). It makes those operations efficient. For example, let's take set_intersection() as an example.
set< string > girl_names;
set< string > boy_names;
set< string > common_names;
set_intersection(
girl_names.begin(), girl_names.end(),
boy_names.begin(), boy_names.end(),
inserter(common_names,
common_names.begin()));
set_intersection() takes two input ranges, and copies its result to an output range. Here we are using a particular type of iterator adaptor, called inserter, to add new elements to an output sequence, common_names in this case. We'll be looking at inserters later in our visit.
If you're familiar at all with mathematical sets, you will know that taking the intersection of two sets results in the elements common to both. The results we might expect from this operation could be:
Sam Tracey Nicola Max Eddie Alex Hilary
The point is that set_intersection() can be used with vector , or list , provided they are sorted in advance. The set container is well suited to this operation, and the other set operations for the same reason, because it is always sorted. We could have used list as the result sequence; it allows efficient random insertion of elements, but the fact is that the intersection of two sets results in a new, possibly empty, set in mathematics. The purpose of the set algorithms in STL is to closely model the mathematical meaning of them, and the set container provides support for that goal [ Austern1998 ].
Pseudonyms
This last example demonstrates how useful typedef can be to make otherwise impenetrable code readable. It could in fact have been improved, and careful use of typedef can make code more maintainable.
In the shown code we have a multimap containing two types, author and publication . From use, we can guess that they are both string types, probably typedef s. This is in fact pretty irrelevant, and we're more interested (as maintenance programmers) in the fact that this multimap contains a mapping for authors to publications. The (supposed) typedef s of the identifiers makes our intent (as original programmers) much more clear. That's one case for typedef .
We've discussed some ways of removing the need to use container iterators directly by using the standard algorithms [ Love2001 ], but there are times, such as here, when we must use them. In doing so, we have to make the whole type, including the container and its template type(s) clear to the compiler, so it knows exactly which iterator we're after. If we'd made a typedef of the container name, not only can we shorten the code, we can make it resilient to a change in the container itself:
typedef string author; typedef string publication; typedef multimap< author, publication > index; pair< index::iterator, index::iterator > range;
The names you use will reflect the scope in which they are used. Of course, in our example, whatever index becomes, should it change, will need to have the same facilities as multimap , including count() and equal_range()
You may find that the enforced uniqueness of elements in a set , and possibly the fact it is an ordered container, useful characteristics in and of themselves, too. set is by no means limited in its use to the standard algorithms.
Refractions - Multiple Associative Containers
As we have seen, map and set both enforce the rule that elements must be unique. This often makes a great deal of sense. For example, sets in mathematics have no concept of duplicated members, and so the STL set container enforces this because it is intended to support the mathematical definition of a set.
There are two other Associative Containers which differ from set and map only in that they allow duplicate elements. They are, appropriately enough, multimap and multiset .
The set algorithms discussed in the previous section are general algorithms which work the same way for multiset as they do for set . They impose no requirement that the input sequences must be unique ranges, only that they are sorted, and multiset is a Sorted Associative Container just as set is. Another useful member of multiset is the count() function, which returns the number of items matching a given key.
multimap is useful for one-to-many relationships (associations) between a key and some values. For example, a publication will generally run articles by several authors, each of whom may submit articles to several publications. A multimap can handle this situation easily.
Both multimap and multiset have two particularly useful member functions, count() and equal_range() . The count() function returns the number of elements with a given key:
multimap< author, publication > articles;
cout << articles.count("Gordon Bennett");
equal_range() returns a pair of iterators describing all elements with a particular key:
typedef multimap< author, publication >::iterator article_ptr;
pair< article_ptr, article_ptr > range =
articles.equal_range("Arthur Dent");
for_each(range.begin(), range.end(),
print_me);
In fact, set and map have these, too, but since they store only one of each key, these functions have little utility directly.
The False Stalagmite
Finally, the most inconspicuous, quiet mannered, unobtrusive specimen provided as standard in the C++ Standard Library. bitset gives you the ability to use bitmasks without the need to understand hexadecimal numbers. OK, knowledge of hex notation is probably useful anyway, but the real utility of bitset is that it provides a much more convenient way of manipulating individual bits in a mask.
It is often useful to be able to represent a collection of flags which can be on or off, set or not set. Computers generally make extensive use of this (digital computers anyway) and provide the programmer with tools to emulate it. If you've heard the expression "it's all ones and zeros", this is where it comes from - binary representation of values.
A 32 bit number has, unsurprisingly, 32 bit locations, each of which can be a one or a zero. bitset makes it easy to set or unset any one of those values, and to test an individual bit for its state. Doing this in plain C can be tortuous - a knowledge of hexadecimal numbers makes it less painful - because you cannot address an individual bit. A byte is the smallest addressable location in C and C++ alike.
For example, to set the fifth [ 6 ] bit to one, you need to bitwise OR it with 1:
mask |= 0x10 // binary 10000
to test the same bit, you need a bitwise AND operation:
if( mask & 0x10 ){
//...
}
What bitset provides is a way to test an individual bit by its position in the mask. Thus, the equivalent forms of the above might be:
mask.set( 5 );
if( mask.test( 5 ) ) {
// ...
}
You create a bitset with a fixed number of bits, which, unlike unsigned numbers in C++, can be any size. Thus, a bitset of 50 locations is declared thus:
bitset< 50 > mask;
You can create a bitset with a starting mask by providing a number, which is the equivalent of the bare numerical bitmask. You can also use a string to represent the bitmask, which is much more convenient, because deciphering which bits are set in 0x06730 (or worse, 26416) can be difficult. The following is very useful when you are interested not in the value itself, but in which bits are set and unset:
bitset<50> mask(string
("110011100110000"));
I think you'll agree, it's much easier to see what is going on here. Note that the provided mask represents the least-significant bits; this means that the mask will be zero-filled to the left giving "0...0110011100110000".
bitset also has count() and any() member functions which return, respectively, the number of set bits and whether any bits are set in the mask.
Of course, you may actually be interested in conversions between binary and decimal representations of numbers, and bitset can be used for this, too. You can convert to an unsigned long integer using the to_ulong() member. You can also write a bitset to a stream in the usual manner. Thus, converting a decimal number to its binary representation might be done like this:
bitset< 20 > mask ( 516 ); cout << mask << "\n"; // result // 00000000001000000100
Or conversely, converting a binary number to a number like this:
bitset< 20 > mask ( string( "10110100")); cout << mask.to_ulong() << "\n"; // result // 180
Now, as to why bitset is a "false" stalagmite, it isn't really a container in the STL sense, because it has no iterators. It does have the feel of an associative array of bits, however, allowing you to do the following:
mask[ 5 ] = true;
if( mask[ 5 ] ){
// ...
}
As with map, however, this does not indicate that bitset is a Random Access container.
Summary
The associative containers' single most important difference from the sequence containers is that they are sorted. This makes it much more efficient to find a particular element by its key, or in the case of multiple associative containers, to locate the range of elements with a given key.
map and set serve specific purposes, and care should be taken when using them that you're not just shoe-horning the requirement because you want a sorted container. It is possible to sort any of the sequence containers using the standard sort() algorithm.
Remember, pair is your friend. Even though it looks like it's a library internal type to make things like map work, as you use it more, you'll think of new and interesting ways to use it more...
Finally, prefer bitset over manual bit-twiddling techniques. It supports the "traditional" bit-operators &, |, ~ and ^, along with the shift operators << and >>, but allows you to specify your intent more cleanly when you use bitmasks.
A Look In The Cauldron - More Adaptors
As we saw in a previous visit here, the adaptors are what make the STL such an interesting brew, and adding your own ingredients is not just allowed, but encouraged. We mentioned in passing an iterator adaptor called inserter. We've already seen Function Adaptors in action ( [ Love2001 ]). Here we'll look at some iterator adaptors and container adaptors to complete our investigation of the containers in STL. For this part, we reopen our boundaries to include the sequence containers once more.
Waterfalls... - Container Adaptors
There are three container adaptors provided with the C++ Standard Library:
stack queue priority_queue
In Computer Science, these are discrete data structures in their own right, each with distinct properties and behavioural characteristics. In STL, however, they are implemented in terms of the other containers, simply because they can.
Stack
Consider the operations on a stack . You, as the programmer, get access only to the top element in the container. It is a LIFO (last-in, first-out) container. You can add (push) an element, and remove (pop) that element. You cannot look at every element (without popping each one in turn), nor can you sort a stack. In this case, then, we could easily use one of the three sequence containers, and use only those operations permitted by the interface of a stack .
The stack container does this for you, and "adapts" the interface of deque , such that push() becomes deque<>::push_back() , and pop() becomes deque<>::pop_back() . The main utility in using the STL stack adaptor over using deque directly is that you are stating your intent: this program requires a stack , and is restricting its usage to that of a stack .
There is one catch to this. Normally a stack's pop() method will remove the top element of the stack and return it:
my_stack< int > s; // ... int p = s.pop();
The STL stack adaptor's pop() method returns nothing, and this may seem rather odd. Looking deeper, however, we notice that there is a method top() which returns a reference to the top element.
The reason for this is efficiency. One of the things you may need to do with a stack is to pop off a number of elements, discarding each one. Since the element is being removed, if pop() were to return it, it would have to make a copy and return it by value. If that value is then discarded, at least one copy of a possibly expensive object has been made. The alternative is to allow a copy to be made prior to its removal if that value is needed:
stack< string > s; // ... string name = s.top(); s.pop();
Queue
Again, a queue is a well-known data structure which allows first-in, first-out (FIFO) functionality. This means it operates like a double-ended stack , where you have access to the elements at either end of the container. As with stack , you cannot access the other elements. push() adds a new element to the back of the queue , pop() removes one from the front of the queue . The methods back() and front() provide references to those elements respectively, allowing you to make copies if required.
Priority Queue
priority_queue is like stack more than queue , the difference being that the top element is always the largest (it doesn't have a good four letter acronym!). Hence, push() adds a new element to the priority_queue , and pop() removes the top one, which will always be the largest, according to some comparison. The default comparison is the standard functor less<> , which by default uses operator<() for the given type, but you can provide your own comparator if required.
All of the container adaptors allow you to choose your own underlying container upon which they will be based. By default, stack and queue use deque as their implementation, and priority_queue uses vector . Any container you provide must conform to the adaptor's requirements. These are ( [ Austern1998 ]):
Table 1.
| stack | Back Insertion Sequence |
| queue | Back Insertion Sequence |
| Front Insertion Sequence | |
| priority_queue | Random Access Container |
...And Rapids - Iterator Adaptors
All of the standard algorithms work with iterators. The reason for this is generality (or more accurately, genericity). It means the algorithms can work for any container whose iterators fulfil the requirements of the algorithm.
So far, so good.
Consider then the standard algorithm copy() . In its simplest form, it takes three iterators, the first two describing the source range, and the third describing the start position (iterator) of the target. Here is a plausible example:
list< string > names;
// initialise names with suitable elements
list< string >target( names.size() );
copy( names.begin(), names.end(),
target.begin() );
Note that we must make enough space in target before copying the elements from names to it, because the default assignment for an iterator is to overwrite the previous contents. This makes perfect sense, usually. However, what we'd really like to achieve here is to make copy() perform its actions by using push_back() on the list, thereby removing the need to pre-size the target container.
Insert Iterators
We cannot change the behaviour of copy() easily, but we could easily create an iterator type that overrides the default meaning of operator=() to perform push_back() on the container.
Enter the Back Insert Iterator. It works with any Back Insertion Sequence (a container with a push_back() method, which means list , vector and deque only, in the C++ Standard Library) and works like this:
list< string > names;
// initialise names with suitable elements
list< string >target;
copy( names.begin(), names.end(),
back_inserter( target ) );
There is a corresponding Front Insert Iterator which works for containers with push_front() , which means list and deque only.
However, what happens if your target isn't a Back Insertion Sequence, or you wish to add elements to the middle of the container? Ah well, these library designers they think of everything. There is another Insert Iterator called, well, inserter. As well as the container itself, you provide an iterator to where you would like insertions to start. Thus, the following snippet is equivalent to our previous example:
list< string > names; // initialise names with suitable elements list< string >target; copy( names.begin(), names.end(), inserter( target, target.end() ) );
The difference being that inserter requires that the target container has an insert method which takes an iterator as the insertion point as well as the value to be added. This includes the Associative Containers we looked at previously. You will recall that the Associative Containers are all sorted. In their case, this insertion-point iterator is merely a hint - the position at which to start looking for an existing element. When using an inserter into a map or set , it's usually best where possible to use begin() or end() as the iterator argument to inserter.
Reverse Iterators
It sometimes makes sense to read a container backwards. It may be for the purposes of finding any subliminal messages, or perhaps reading in reverse alphabetical order. For whatever reason, there are two ways to do this.
The first and simplest method is when you are working directly with a container. Each of the standard containers provide an rbegin() and rend() method. rbegin() returns a Reverse Iterator, which is the equivalent in position of end() , except that incrementing it moves it backwards. Similarly, rend() has the equivalent position of begin() in the container.
The difficulty comes when you have an algorithm which accepts Forward Iterators, but for reasons of efficiency perhaps wants to work with Reverse Iterators. Consider a function called find_last_of() . It takes an iterator range and a value to find. You don't really wish to expose the implementation too much by requiring Reverse Iterators, but then searching the entire range from start to finish might be very inefficient. You need some way of converting a Forward Iterator into a Reverse Iterator. Once again, the C++ Standard is ahead of you, and provides an Iterator Adaptor for exactly this purpose.
reverse_iterator changes the direction of a given Bi-Directional Iterator. All of the standard containers provide Bi-Directional Iterators from their begin() and end() methods. This means you can now write find_last_of() like this:
template<typename Iterator, typename Value>
Iterator find_last_of(Iterator begin,
Iterator end, Value v ){
reverse_iterator<Iterator> rbegin(end);
reverse_iterator<Iterator> rend(begin);
reverse_iterator< Iterator > result =
find( rbegin, rend, v );
return result.base();
}
That last line which returns the base() of the Reverse Iterator is needed because a Reverse Iterator cannot just convert back to a normal one. For technical reasons. It has to do with the fact that an iterator range is a half-open range, meaning it contains the first but not the last elements [ Love2001 ], [ Josuttis1999 ]. The reversed End (one after the end) is now one before the start, which is not a valid position. Therefore, some hand-waving is needed to make it valid.
Summary
The C++ Standard Library provides you with three common data structures which use the basic containers in specialised ways. The reason for this is mainly documentation: by using a stack instead of a vector, you are making your intentions clear to any programmer reading that code. Where possible, you should follow this lead, and instead of writing your own container from scratch, consider re-using one of the standard containers, and adapting it. That way, you save yourself time and effort, at the same time as the time and effort of the poor old maintainer - which might be you. What's not to like about that?
The Iterator Adaptors give you amazing flexibility when using the standard algorithms, and when writing your own algorithms. Insert Iterators really are the last word in decoupling algorithms from data structures, which in turn has the fortunate effect of giving you the ability to use those algorithms in ways which otherwise may have required a custom function. Reusing tried and tested code is a cornerstone of software development, because if something is already tested, you (shouldn't) don't have to test it again.
Back Safe and Sound
As an end-note, I will mention a discussion I had regarding the number of lines of code required for a particular algorithm. This discussion revolved around the pros and cons of STL in particular, but was really focussed on using STL containers over C style arrays. I calculated that using only C arrays it would need 60 lines of code to perform a job that I could perform in 2 using STL. The response was that I was forgetting about the (probably more than) 58 lines in the STL code that were still required. My closing response to that was, "well, that's 58 lines of code I don't have to write - or test."
The moral of the story - write less code. Go on. You know you want to.
Acknowledgements
Thanks once again to Nigel Dickens for reading through the first drafts of this article. Thank you also to Kevlin Henney who once again sent me advance copies of yet-to-be published articles of his. Also during the writing of this, I find myself time and again referring to both [ Josuttis1999 ] and [ Austern1998 ]. They deserve more than a biblio entry. Perhaps a beer or two if we ever meet face to face...
Bibliography
[ISO1998] International Standard: Programming Language - C++, ISO/IEC 14882:1998(E), 1998
[Austern1998] Matthew H Austern, Generic Programming And The STL,Addison Wesley 1998
[Josuttis1999] Nicolai Josuttis, The C++ Standard Library - A Tutorial and Reference,Addison Wesley 1999
[Love2001] Steve Love, Are You Afraid Of The Dark?,Overload 43, 2001
[Stroustrup2000] Bjarne Stroustrup, The C++ Programming Language, Special Edition,Addison Wesley 2000
[STLPort2001] www.stlport.org , Portable and free STL implementation,
[Henney2001] Various - background
[ 1 ] std::string exposes Random Access iterators [ Josuttis1999 ], and so also meets the requirements of Reversible Container [ ISO1998 ]
[ 2 ] In addition, multiple iterations over the sequence must return the elements in the same order [ Austern1998 ]
[ 3 ] Exactly what it says; for some x and y, x < y must be well-defined.
[ 4 ] Note we've used a normal function rather than a function object here. for_each will receive a pointer to a function, which can be dereferenced (called) in the same way as a function. See [ Stroustrup2000 ] for details.
[ 5 ] Don't confuse this with Random Access as typified by vector and deque. It is merely a notational convenience in map.
[ 6 ] From the right - the first bit is the least significant bit.
