Sidebars

Iterators are pointer-like objects, used to cycle through the elements stored in a container.

A range is a sequence of values held in a container. The range is described by a pair of iterators, which define the beginning and end of the sequence.

When iterators are used to describe a range of values in a container, it is assumed (but not verified) that the second iterator is reachable from the first. Errors will occur if this is not true.

Because ordinary pointers have the same functionality as random access iterators, most of the generic algorithms in the standard library can be used with conventional C++ arrays, as well as with the containers provided by the standard library.

A number of the generic algorithms manipulate two parallel sequences. Frequently the second sequence is described using only a beginning iterator, rather than an iterator pair. It is assumed, but not checked, that the second sequence has at least as many elements as the first.

The function randomInteger described here is used in a number of the example programs presented in later sections.

An input stream iterator permits an input stream to be read using iterator operations. An output stream iterator similarly writes to an output stream when iterator operations are executed.

The class definitions for unary_function and binary_function can be incorporated by #including functional.

A more complex illustration of the use of a function object occurs in the radix sorting example program given as an illustration of the use of the list data type in Chapter 7. In this program references are initialized in the function object, so that during the sequence of invocations the function object can access and modify local values in the calling program.

The idea described here by the term binder is in other contexts often described by the term curry. This is not, as some people think, because it is a hot idea. Instead, it is named after the computer scientist Haskell P. Curry, who used the concept extensively in an influential book on the theory of computation in the 1930's. Curry himself attributed the idea to Moses Sch_nfinkel, leaving one to wonder why we don't instead refer to binders as "Sch_nfinkels."

Elements that are held by a vector must define a default constructor (constructor with no arguments), as well as a copy constructor. Although not used by functions in the vector class, some of the generic algorithms also require vector elements to recognize either the equivalence operator (operator ==) or the relational less-than operator (operator <).

Because it requires the ability to define a method with a template argument different from the class template, some compilers may not yet support the initialization of containers using iterators. In the mean time, while compiler technology catches up with the standard library definition, the Rogue Wave version of the standard library will support conventional pointers and vector iterators in this manner.

A vector stores values in a single large block of memory. A deque, on the other hand, employs a number of smaller blocks. This difference may be important on machines that limit the size of any single block of memory, because in such cases a deque will be able to hold much larger collections than are possible with a vector.

Even adding a single element to a vector can, in the worst case, require time proportional to the number of elements in the vector, as each element is moved to a new location. If insertions are a prominent feature of your current problem, then you should explore the possibility of using containers, such as lists or sets, which are optimized for insert operations.

Once more, it is important to remember that should reallocation occur as a result of an insertion, all references, pointers, and iterators that denoted a location in the now-deleted memory block that held the values before reallocation become invalid.

Note that count() returns its result through an argument that is passed by reference. It is important that this value be properly initialized before invoking this function.

Source for this program is found in the file sieve.cpp.

Note that if you declare a container as holding pointers, you are responsible for managing the memory for the objects pointed to. The container classes will not, for example, automatically free memory for these objects when an item is erased from the container.

Unlike a vector or deque, insertions or removals from the middle of a list will not invalidate references or pointers to other elements in the container. This property can be important if two or more iterators are being used to refer to the same container.

The searching algorithms in the standard library will always return the end of range iterator if no element matching the search condition is found. Unless the result is guaranteed to be valid, it is a good idea to check for the end of range condition.

The executable version of the widget works program is contained in file widwork.cpp on the distribution disk.

The complete radix sort program is found in the file radix.cpp in the tutorial distribution disk.

Although the abstract concept of a set does not necessarily imply an ordered collection, the set data type is always ordered. If necessary, a collection of values that cannot be ordered can be maintained in, for example, a list.

In other programming languages, a multiset is sometimes referred to as a bag.

As we noted in the earlier discussion on vectors and lists, the initialization of containers using a pair of iterators requires a mechanism that is still not widely supported by compilers. If not provided, the equivalent effect can be produced by declaring an empty set and then using the copy() generic algorithm to copy values into the set.

If you want to use the pair data type without using maps, you should include the header file named utility.

Unlike a vector or deque, the insertion or removal of values from a set does not invalidate iterators or references to other elements in the collection.

This program can be found in the file spell.cpp in the tutorial distribution.

In other programming languages, a map-like data structure is sometimes referred to as a dictionary, a table, or an associative array.

See the discussion of insertion in Chapter 8 for a description of the pair data type.

Unlike a vector or deque, the insertion or removal of elements from a map does not invalidate iterators which may be referencing other portions of the container.

The complete example program is included in the file tutorial tele.cpp in the distribution.

The executable version of this program is found in the file graph.cpp on the tutorial distribution disk.

An executable version of the concordance program is found on the tutorial distribution file under the name concord.cpp.

A stack is sometimes referred to as a LIFO structure, and a queue is called a FIFO structure. The abbreviation LIFO stands for Last In, First Out. This means the first entry removed from a stack is the last entry that was inserted. The term FIFO, on the other hand, is short for First In, First Out. This means the first element removed from a queue is the first element that was inserted into the queue.

Note that on most compilers it is important to leave a space between the two right angle brackets in the declaration of a stack; otherwise they are interpreted by the compiler as a right shift operator.

This program is found in the file calc.cpp in the distribution package.

A more robust program would check to see if the stack was empty before attempting to perform the pop() operation.

The complete version of the bank teller simulation program is found in file teller.cpp on the distribution disk.

The term priority queue is a misnomer, in that the data structure is not a queue, in the sense that we used the term in Chapter 10, since it does not return elements in a strict first-in, first-out sequence. Nevertheless, the name is now firmly associated with this particular data type.

As we noted in earlier sections, support for initializing containers using a pair of iterators requires a feature that is not yet widely supported by compilers. While we document this form of constructor, it may not yet be available on your system.

Information on Heaps. Details of the algorithms used in manipulating heaps will not be discussed here, however such information is readily available in almost any textbook on data structures.

We describe the priority queue as a structure for quickly discovering the largest element in a sequence. If, instead, your problem requires the discovery of the smallest element, there are various possibilities. One is to supply the inverse operator as either a template argument or the optional comparison function argument to the constructor. If you are defining the comparison argument as a function, as in the example problem, another solution is to simply invert the comparison test.

Other example programs in this tutorial have all used containers to store values. In this example the container will maintain pointers to values, not the values them-selves. Note that a consequence of this is that the programmer is then responsible for managing the memory for the objects being manipulated.

The complete event simulation is found in the file icecream.cpp on the distribution disk.

In the remainder of this section we will refer to the string data type, however all the operations we will introduce are equally applicable to wide strings.

Remember, the ability to initialize a container using a pair of iterators requires the ability to declare a template member function using template arguments independent of those used to declare the container. At present not all compilers support this feature.

Note that the contents of an iterator are not guaranteed to be valid after any operation that might force a reallocation of the internal string buffer, such as an append or an insertion.

Although the function is accessible, users will seldom invoke the member function compare() directly. Instead, comparisons of strings are usually performed using the conventional comparison operators, which in turn make use of the function compare().

The split function can be found in the concordance program in file concord.cpp.

The sample programs described in this section can be found in the file alg1.cpp.

The initialization algorithms all overwrite every element in a container. The difference between the algorithms is the source for the values used in initialization. The fill() algorithm repeats a single value, the copy() algorithm reads values from a second container, and the generate() algorithm invokes a function for each new value.

The result returned by the copy() function is a pointer to the end of the copied sequence. To make a catenation of values, the result of one copy() operation can be used as a starting iterator in a subsequent copy().

In the copy_backwards algorithm, note that it is the order of transfer, and not the elements themselves that is "backwards"; the relative placement of moved values in the target is the same as in the source.

A number of algorithms operate on two parallel sequences. In most cases the second sequence is identified using only a starting iterator, not a starting and ending iterator pair. It is assumed, but never verified, that the second sequence is at least as large as the first. Errors will occur if this condition is not satisfied.

The example functions described in this section can be found in the file alg2.cpp.

The searching algorithms in the standard library all return the end-of-sequence iterator if no value is found that matches the search condition. As it is generally illegal to dereference the end-of-sequence value, it is important to check for this condition before proceeding to use the result of a search.

These algorithms perform a linear sequential search through the associated structures. The set and map data structures, which are ordered, provide their own find() member functions, which are more efficient. Because of this, the generic find() algorithm should not be used with set and map.

In the worst case, the number of comparisons performed by the algorithm search() is the product of the number of elements in the two sequences. Except in rare cases, however, this worst case behavior is highly unlikely.

The maximum and minimum algorithms can be used with all the data types provided by the standard library. However, for the ordered data types, set and map, the maximum or minimum values are more easily accessed as the first or last elements in the structure.

The example functions described in this section can be found in the file alg3.cpp.

While there is a unique stable_ partition() for any sequence, the partition() algorithm can return any number of values. The following, for example, are all legal partitions of the example problem.

2 4 6 8 10 1 3 5 7 9

10 8 6 4 2 5 7 9 3 1

2 6 4 8 10 3 5 7 9 1

6 4 2 10 8 5 3 7 9 1.

Permutations can be ordered, with the smallest permutation being the one in which values are listed smallest to largest, and the largest being the sequence that lists values largest to smallest. Consider, for example, the permutations of the integers 1 2 3. The six permutations of these values are, in order:

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

Notice that in the first permutation the values are all ascending, while in the last permutation they are all descending.

The algorithms in this section set up a sequence so that the desired elements are moved to the front. The remaining values are not actually removed, but the starting location for these values is returned, making it possible to remove these values by means of a subsequent call on erase(). Remember, the remove algorithms do not actually remove the unwanted elements.

The example functions described in this section can be found in the file alg4.cpp.

The example functions described in this section can be found in the file alg5.cpp.

Note that the count() algorithms do not return the sum as a function result, but instead simply add to the last argument in their parameter list, which is passed by reference. This means successive calls on these functions can be used to produce a cumulative sum. This also means that you must initialize the variable passed to this last argument location prior to calling one of these algorithms.

By substituting another function for the binary predicate, the equal and mismatch algorithms can be put to a variety of different uses. Use the equal() algorithm if you want a pairwise test that returns a boolean result. Use the mismatch() algorithm if you want to discover the location of elements that fail the test.

The example functions described in this section can be found in the file alg6.cpp.

The function passed as the third argument is not permitted to make any modifications to the sequence, so it can only achieve any result by means of a side effect, such as printing, assigning a value to a global or static variable, or invoking another function that produces a side effect. If the argument function returns any result, it is ignored.

The example programs described in this section have been combined and are included in the file alg7.cpp in the tutorial distribution. As we did in Chapter 13, we will generally omit output statements from the descriptions of the programs provided here, although they are included in the executable versions.

Yet another sorting algorithm is provided by the heap operations, to be described in Chapter 14 (Heap Operations).

Note that an ordered collection is a heap, but a heap need not necessarily be an ordered collection. In fact, a heap can be constructed in a sequence much more quickly than the sequence can be sorted.

This program can be found in the file exceptn.cpp in your code distribution.

You can find this program in the file autoptr.cpp in the turorial distribution.

Note that, with the exception of the member functions real() and imag(), most operations on complex numbers are performed using ordinary functions, not member functions.

This program is found in the file complx.cpp in the distribution.

For reasons of compatibility, the numeric_limits mechanism is used as an addition to the symbolic constants used in older C++ libraries, rather than a strict replacement. Thus both mechanisms will, for the present, exist in parallel. However, as the numeric_limits technique is more uniform and extensible, it should be expected that over time the older symbolic constants will become outmoded.