Delving into the STL: Containers and Iterators

Iterators are implemented similarly to smart pointer classes in that they overload the specific desired operators. Consult Chapter 16 for details on operator overloading. See Chapter 23 for a sample iterator implementation.

The basic iterator operations are similar to those supported by dumb pointers, so a dumb pointer is a legitimate iterator for certain containers. In fact, the vector iterator is often implemented as simply a dumb pointer. However, as a client of the containers, you need not worry about the implementation details; you can simply use the iterator abstraction.

Iterators might not be implemented internally as pointers, so this text uses the term “refers to” instead of “points to” when discussing the elements accessible via an iterator.

Chapters 22 and 23 delve into more detail about iterators and the STL algorithms that use them. This chapter simply shows you the basics of using the iterators for each container.

Only the sequential and associative containers provide iterators. The container adapters and bitmap do not support iteration over their elements.

Common Iterator Typedefs and Methods

Every container class in the STL that supports iterators provides public typedefs for its iterator types called iterator and const_iterator. That way, clients can use the container iterators without worrying about the actual types.

const_iterators provide read-only access to elements of the container.

The containers also provide a method begin() that returns an iterator referring to the first element in the container. The end() method returns a reference to the “past-the-end” value of the sequence of elements. That is, end() returns an iterator that is equal to the result of applying operator++ to an iterator referring to the last element in the sequence. Together begin() and end() provide a half-open range that includes the first element but not the last. The reason for this apparent complication is to support empty ranges (containers without any elements), in which case begin() is equal to end(). The half-open range bounded by iterators start and end is often written mathematically like this: [start,end).

The half-open range concept also applies to iterator ranges that are passed to container methods such as insert() and erase(). See the specific container descriptions in this chapter for details.

Sequential Containers

The vector, deque, and list are called the sequential containers because they store elements in a client-visible order. The best way to learn about the sequential containers is to jump in with an example of the vector, which is the container most commonly used. This section describes the vector in detail

565

Chapter 21

as an example of a sequential container, followed by briefer descriptions of the deque and the list. Once you become familiar with the sequential containers, it’s trivial to switch between them.

Vector

As described in Chapter 4, the STL vector is similar to an array: the elements are stored in contiguous memory, each in its own “slot.” You can index into the vector, as well as add new elements to the back or insert them anywhere else. Inserting and deleting elements into and from the vector generally takes linear time, though these operations actually run in amortized constant time (explained in the “Vector Memory Allocation Scheme” section) at the end of the vector. Random access of individual elements is constant complexity.

Vector Overview

The vector is defined in the <vector> header file as a class template with two type parameters: the element type to store in the vector, and an allocator type.

template <typename T, typename Allocator = allocator<T> > class vector;

The Allocator parameter specifies the type for a memory allocator object that the client can set in order to use custom memory allocation. The template parameter has a default value, which uses the element type parameter T. See Chapter 11 for details on template parameters.

The default value for the Allocator type parameter is sufficient for most applications. Programmers do not usually find it useful to customize allocators, but Chapter 23 provides more detail in case you are interested. This chapter assumes that you always use the default allocator.

Fixed-Length Vectors

The simplest way to use a vector is as a fixed-length array. The vector provides a constructor that allows you to specify the number of elements, and provides overloaded operator[] in order to access and modify those elements.

Like “real” array indexing, the vector operator[] does not provide bounds checking.

For example, here is a small program to “normalize” test scores so that the highest score is set to 100, and all other scores are adjusted accordingly. The program creates a vector of 10 doubles, reads in 10 values from the user, divides each value by the max score (times 100), and prints out the new values. For the sake of brevity, the program forsakes error checking.

#include <vector> #include <iostream> using namespace std;

int main(int argc, char** argv)

{

566

Delving into the STL: Containers and Iterators

vector<double> doubleVector(10); // Create a vector of 10 doubles. double max;

int i;

for (i = 0; i < 10; i++) { doubleVector[i] = 0;

}

// Read the first score before the loop in order to initialize max. cout << “Enter score 1: “;

cin >> doubleVector[0]; max = doubleVector[0];

for (i = 1; i < 10; i++) {

cout << “Enter score “ << i + 1 << “: “; cin >> doubleVector[i];

if (doubleVector[i] > max) { max = doubleVector[i];

}

}

max /= 100;

for (i = 0; i < 10; i++) { doubleVector[i] /= max;

cout << doubleVector[i] << “ “;

}

cout << endl; return (0);

}

As you can see from this example, you can use a vector just as you would use an array.

The vector operator[] normally returns a reference to the element, which can be used on the left-hand side of assignment statements. If operator[] is called on a const vector object, it returns a reference to a const element, which cannot be used as the target of an assignment. See Chapter 16 for details on how this trick is implemented.

Specifying an Initial Element Value

You can specify an initial value for the elements when you create the vector like this:

#include <vector> #include <iostream> using namespace std;

int main(int argc, char** argv)

{

vector<double> doubleVector(10, 0); // Creates vector of 10 doubles of value 0 double max;

int i;

// No longer need to initialize each element: the ctor did it for you.

567

Chapter 21

// Read the first score before the loop in order to initialize max. cout << “Enter score 1: “;

cin >> doubleVector[0]; max = doubleVector[0];

for (i = 1; i < 10; i++) {

cout << “Enter score “ << i + 1 << “: “; cin >> doubleVector[i];

if (doubleVector[i] > max) { max = doubleVector[i];

}

}

max /= 100;

for (i = 0; i < 10; i++) { doubleVector[i] /= max;

cout << doubleVector[i] << “ “;

}

cout << endl; return (0);

}

Other Vector Element Access Methods

In addition to using operator[], you can access vector elements via at(), front(), and back(). at() is identical to operator[], except that it performs bounds checking, and throws an out_of_range exception if the index is out of bounds. front() and back() return the references to the first and last elements of the vector, respectively.

All vector element accesses run in constant complexity.

Dynamic-Length Vectors

The real power of the vector lies in its ability to grow dynamically. For example, consider the test score normalization program from the previous section with the additional requirement that it handle any number of test scores. Here is the new version:

int main(int argc, char** argv)

{

vector<double> doubleVector; // Create a vector with zero elements.

double max, temp; size_t i;

// Read the first score before the loop in order to initialize max. cout << “Enter score 1: “;

cin >> max; doubleVector.push_back(max);

for (i = 1; true; i++) {

cout << “Enter score “ << i + 1 << “ (-1 to stop): “;

cin >> temp;

if (temp == -1) {

568

Delving into the STL: Containers and Iterators

break;

}

doubleVector.push_back(temp);

if (temp > max) { max = temp;

}

}

max /= 100;

for (i = 0; i < doubleVector.size(); i++) { doubleVector[i] /= max;

cout << doubleVector[i] << “ “;

}

cout << endl; return (0);

}

This version of the program uses the default constructor to create a vector with zero elements. As each score is read, it’s added to the vector with the push_back() method. push_back() takes care of allocating space for the new element. Note that the last for loop uses the size() method on the vector to determine the number of elements in the container. size() returns an unsigned integer, so the type of i was changed to size_t for compatibility.

Vector Details

Now that you’ve had a taste of the power of vectors, it’s time to delve into their details.

Constructors and Destructors

The default constructor creates a vector with 0 elements.

#include <vector> using namespace std;

int main(int argc, char** argv)

{

vector<int> intVector; // Creates a vector of ints with zero elements return (0);

}

As you’ve already seen, you can specify a number of elements and, optionally, a value for those elements, like this:

#include <vector> using namespace std;

int main(int argc, char** argv)

{

vector<int> intVector(10, 100); // Creates a vector of 10 ints with value 100 return (0);

}

If you omit the default value, the new objects are zero-initialized. As described in Chapter 11, zeroinitialization constructs objects with the default constructor and initializes primitives such as int and double with 0.

569

Chapter 21

You can also create vectors of built-in classes like this:

#include <vector> #include <string> using namespace std;

int main(int argc, char** argv)

{

vector<string> stringVector(10, “hello”); return (0);

}

Finally, you can create vectors of user-defined classes:

#include <vector> using namespace std;

class Element

{

public:

Element() {} ~Element() {}

};

int main(int argc, char** argv)

{

vector<Element> elementVector; return (0);

}

The vector stores copies of the objects, and its destructor calls the destructor for each of the objects. You can allocate vectors in the heap as well:

#include <vector> using namespace std;

class Element

{

public: Element() {} ~Element() {}

};

int main(int argc, char** argv)

{

vector<Element>* elementVector = new vector<Element>(10);

delete elementVector; return (0);

}

Remember to call delete when you are finished with a vector that you allocated with new!

570

Delving into the STL: Containers and Iterators

Use delete, not delete[], to free vectors. Even though the vector is implemented as an array, you are deleting only the vector object. The vector handles the underlying array itself.

Copying and Assigning Vectors

The copy constructor and assignment operator for the vector class perform deep copies of all the elements in the vector. Thus, for efficiency, you should pass vectors by reference or const reference to functions and methods. Consult Chapter 11 for the details on writing functions that take template instantiations as parameters.

In addition to normal copying and assignment, vectors provide an assign() method that allows you to remove all the current elements and add any number of new elements. This method is useful if you want to reuse a vector. Here is a trivial example:

vector<int> intVector(10, 0); // Other code . . .

intVector.assign(5, 100);

Vectors also provide a swap() method that allows you to swap the contents of two vectors. Here is a simple example:

vector<int> vectorOne(10, 0); vector<int> vectorTwo(5, 100);

vectorOne.swap(vectorTwo);

//vectorOne now has 5 elements with the value 100.

//vectorTwo now has 10 elements with the value 0.

Comparing Vectors

The STL provides the usual six overloaded comparison operators for vectors: ==, !=, <, >, <=, >=. Two vectors are equal if they have the same number of elements and all the corresponding elements in the two vectors are equal to each other. One vector is “less than” another if all elements 0 through i –1 in the first vector are equal to 0 through i - 1 in the second vector, but element i in the first is less than element i in the second.

Comparing two vectors with operator== or operator!= requires the individual elements to be comparable with operator==. Comparing two vectors with operator<, operator>, operator<=, or operator>= requires the individual elements to be comparable with operator<. If you intend to store objects of a custom class in a vector, make sure to write those operators.

Here is an example of a simple program that compares vectors of ints:

#include <vector> #include <iostream> using namespace std;

571

Chapter 21

int main(int argc, char** argv)

{

vector<int> vectorOne(10, 0); vector<int> vectorTwo(10, 0);

if (vectorOne == vectorTwo) { cout << “equal!\n”;

} else {

cout << “not equal!\n”;

}

vectorOne[3] = 50;

if (vectorOne < vectorTwo) {

cout << “vectorOne is less than vectorTwo\n”; } else {

cout << “vectorOne is not less than vectorTwo\n”;

}

return (0);

}

The output of the program is:

equal!

vectorOne is not less than vectorTwo

Vector Iterators

The section on “Iterators” at the beginning of this chapter explained the basics of container iterators. The discussion can get a bit abstract, so it’s helpful to jump in and look at a code example. Here is the test score normalization program from earlier with the for loop previously using size() replaced by a for loop using an iterator.

#include <vector> #include <iostream> using namespace std;

int main(int argc, char** argv)

{

vector<double> doubleVector; double max, temp;

int i;

// Read the first score before the loop in order to initialize max. cout << “Enter score 1: “;

cin >> max; doubleVector.push_back(max);

for (i = 1; true; i++) {

cout << “Enter score “ << i + 1 << “ (-1 to stop): “; cin >> temp;

if (temp == -1) { break;

}

doubleVector.push_back(temp);

572

Delving into the STL: Containers and Iterators

if (temp > max) { max = temp;

}

}

max /= 100;

for (vector<double>::iterator it = doubleVector.begin(); it != doubleVector.end(); ++it) {

*it /= max;

cout << *it << “ “;

}

cout << endl; return (0);

}

You see for loops like the new one in this example quite a bit in STL code. First, take a look at the for loop initialization statement:

vector<double>::iterator it = doubleVector.begin();

Recall that every container defines a type named iterator to represent iterators for that type of container. begin() returns an iterator of that type referring to the first element in the container. Thus, the initialization statement obtains in the variable it an iterator referring to the first element of doubleVector. Next, look at the for loop comparison:

it != doubleVector.end();

This statement simply checks if the iterator is past the end of the sequence of elements in the vector. When it reaches that point, the loop terminates. The increment statement, ++it, increments the iterator to refer to the next element in the vector.

Use preincrement instead of postincrement when possible because preincrement is at least as efficient, and usually more efficient. it++ must return a new iterator object, while ++it can simply return a reference to it. See Chapter 16 for details on implementing operator++, and Chapter 23 for details on writing iterators.

The for loop body contains these two lines:

*it /= max;

cout << *it << “ “;

As you can see, your code can both access and modify the elements over which it iterates. The first line uses * to dereference it to obtain the element to which it refers, and assigns to that element. The second line dereferences it again, but this time only to stream the element to cout.

Accessing Fields of Object Elements

If the elements of your container are objects, you can use the -> operator on iterators to call methods or access members of those objects. For example, the following small program creates a vector of 10 strings, then iterates over all of them appending a new string to the old one:

573

Chapter 21

#include <vector> #include <string> using namespace std;

int main(int argc, char** argv)

{

vector<string> stringVector(10, “hello”);

for (vector<string>::iterator it = stringVector.begin(); it != stringVector.end(); ++it) {

it->append(“ there”);

}

}

const_iterator

The normal iterator is read/write. However, if you call begin() and end() on a const object, you receive a const_iterator. The const_iterator is read-only; you cannot modify the elements. An iterator can always be converted to a const_iterator, so it’s always safe to write something like this:

vector<type>::const_iterator it = myVector.begin();

However, a const_iterator cannot be converted to an iterator. If myVector is const, the following line doesn’t compile:

vector<type>::iterator it = myVector.begin();

Thus, if you do not need to modify the elements of a vector, you should use a const_iterator. This rule will make your code more generic.

Iterator Safety

Generally, iterators are about as safe as pointers: extremely insecure. For example, you can write code like this:

vector<int> intVector;

vector<int>::iterator it = intVector.end();

*it = 10; // BUG! it doesn’t refer to a valid element.

Recall that the iterator returned by end() is past the end of the vector. Trying to dereference it is undefined, which usually means that your program will crash. However, the iterators themselves are not required to perform any verification.

Remember that end() returns an iterator past the end of the container, not the iterator referring to the last element of the container.

Another problem can occur if you use mismatched iterators. For example, the following code initializes an iterator from vectorTwo and tries to compare it to the end iterator for vectorOne. Needless to say, this loop will not do what you intended, and may never terminate.

574

Delving into the STL: Containers and Iterators

vector<int> vectorOne(10); vector<int> vectorTwo(10);

//Fill in the vectors.

//BUG! Infinite loop

for (vector<int>::iterator it = vectorTwo.begin(); it != vectorOne.end(); ++it) {

// Loop body

}

Other Iterator Operations

The vector iterator is random access, which means that you can move it backward or forward, or jump around. For example, the following code eventually changes the fifth element (index 4) in the vector to the value 4:

vector<int> intVector(10, 0);

vector<int>::iterator it = intVector.begin();

it += 5; --it; *it = 4;

Chapter 23 provides more information on the different categories of iterators.

Iterators versus Indexing

Given that you can write a for loop that uses a simple index variable and the size() method to iterate over the elements of the vector, why should you bother using iterators? That’s a valid question, for which there are three main answers:

Iterators allow you to insert and delete elements and sequences of elements at any point in the container. See the following “Adding and Removing Elements” section.

Iterators allow you to use the STL algorithms, which are discussed in Chapter 22.

Using an iterator to access each element sequentially is often more efficient than indexing the container to retrieve each element individually. This generalization is not true for vectors, but applies to lists, maps, and sets.

Adding and Removing Elements

As you have already read, you can append an element to a vector with the push_back() method. The vector provides a parallel remove method called pop_back().

pop_back() does not return the element that it removed. If you want the element you must first retrieve it with back().

You can also insert elements at any point in the vector with the insert() method. insert() adds one or more elements to a position specified by an iterator, shifting all subsequent elements down to make

575

Chapter 21

room for the new ones. There are three different overloaded forms of insert(): one that inserts a single element, one that inserts n copies of a single element, and one that inserts elements from an iterator range. Recall that the iterator range is half-open, such that it includes the element referred to by the starting iterator but not the one referred to by the ending iterator.

push_back() and insert() take const references to elements, allocate memory as needed to store the new elements, and store copies of the element arguments.

You can similarly remove elements from any point in the vector with erase(). There are two forms of erase(): single element and range specified by an iterator. You can remove all elements with clear().

Here is a small program that demonstrates the methods for adding and removing elements. It uses a helper function printVector() that prints the contents of the vector to cout, but whose implementation is not shown here because it uses algorithms covered in the next two chapters.

int main(int argc, char** argv)

{

vector<int> vectorOne, vectorTwo; int i;

vectorOne.push_back(1); vectorOne.push_back(2); vectorOne.push_back(3); vectorOne.push_back(5);

//Oops, we forgot to add 4. Insert it in the correct place. vectorOne.insert(vectorOne.begin() + 3, 4);

//Add elements 6 through 10 to vectorTwo.

for (i = 6; i <= 10; i++) { vectorTwo.push_back(i);

}

printVector(vectorOne);

printVector(vectorTwo);

// Add all the elements from vectorTwo to the end of vectorOne. vectorOne.insert(vectorOne.end(), vectorTwo.begin(), vectorTwo.end());

printVector(vectorOne);

//Clear vectorTwo entirely. vectorTwo.clear();

//And add 10 copies of the value 100. vectorTwo.insert(vectorTwo.begin(), 10, 100);

//Decide we only want 9 elements. vectorTwo.pop_back();

//Now erase the numbers 2 through 5 in vectorOne. vectorOne.erase(vectorOne.begin() + 1, vectorOne.begin() + 5);

576

Delving into the STL: Containers and Iterators

printVector(vectorOne);

printVector(vectorTwo);

return (0);

}

The output of the program is:

1	2	3	4	5
6 7 8			9 10
1	2 3		4	5	6		7	8	9 10
1	6	7	8	9	10
100 100				100		100 100				100 100 100	100

Recall that iterator pairs represent a half-open range, and insert() adds elements before the element referred to by the iterator position. Thus, you can insert the entire contents of vectorTwo into the end of vectorOne, like this:

vectorOne.insert(vectorOne.end(), vectorTwo.begin(), vectorTwo.end());

Methods such as insert() and erase() that take a vector range as arguments assume that the beginning and ending iterators refer to elements in the same container, and that the end iterator refers to an element at or past the begin iterator. The methods will not work correctly if these preconditions are not met!

Algorithmic Complexity and Iterator Invalidation

Inserting or erasing elements in a vector causes all subsequent elements to shift up or down to make room for, or fill in the holes left by, the affected elements. Thus, these operations take linear complexity. Furthermore, all iterators referring to the insertion or removal point or subsequent positions are invalid following the action. The iterators are not “magically” moved to keep up with the elements that are shifted up or down in the vector.

Also keep in mind that an internal vector reallocation can cause invalidation of all iterators referring to elements in the vector, not just those referring to elements past the point of insertion or deletion. See the next section for details.

The Vector Memory Allocation Scheme

The vector allocates memory automatically to store the elements that you insert. Recall that the vector requirements dictate that the elements must be in contiguous memory, like in C-style arrays. Because it’s impossible to request to add memory to the end of a current chunk of memory, every time the vector allocates more memory it must allocate a new, larger, chunk in a separate memory location and copy all the elements to the new chunk. This process is time-consuming, so the vector implementations attempt to avoid it by allocating more space than needed when they have to perform a reallocation. That way, they can avoid reallocating memory every time you insert an element.

One obvious question at this point is why you, as a client of the vector, care how it manages its memory internally. You might think that the principle of abstraction should allow you to disregard the internals of the vector memory allocation scheme. Unfortunately, there are two reasons why you need to understand how it works:

577

Chapter 21

1.Efficiency. The vector allocation scheme can guarantee that element insert runs in amortized constant time: most of the time the operation is constant, but once in a while (if it requires a reallocation), it’s linear. If you are worried about efficiency you can control when the vector performs reallocations.

2.Iterator invalidations. A reallocation invalidates all iterators referring to elements in the vector.

Thus, the vector interface allows you to query and control the vector reallocations. If you don’t control the reallocations explicitly, you should assume that all insertions cause a reallocation and thus invalidate all iterators.

Size and Capacity

The vector provides two methods for obtaining information about its size: size() and capacity(). size() returns the number of elements in the vector, while capacity() returns the number of elements that it can hold without a reallocation. Thus, the number of elements that you can insert without causing a reallocation is capacity() – size().

You can query whether a vector is empty with the empty() method. A vector can be empty but have nonzero capacity.

Reserving Capacity

If you don’t care about efficiency or iterator invalidations, there is never a need to control the vector memory allocation explicitly. However, if you want to make your program as efficient as possible, or want to guarantee that iterators will not be invalidated, you can force the vector to preallocate enough space to hold all of its elements. Of course, you need to know how many elements it will hold, which is sometimes impossible to predict.

One way to preallocate space is to call reserve(). That method allocates enough memory to hold the specified number of elements. The next section shows an example of the reserve() method in action.

Reserving space for elements changes the capacity, but not the size. That is, it doesn’t actually create elements. Don’t access elements past the vector size.

Another way to preallocate space is to specify, in the constructor, how many elements you want the vector to store. This method actually creates a vector of that size (and probably of that capacity).

Vector Example: A Round-Robin Class

A common problem in computer science is distributing requests among a finite list of resources. For example, a network load balancer distributes incoming network connections among the various hosts that can service the request. Ideally, each of the hosts would be kept equally busy. One of the simplest algorithmic solutions to this problem is round-robin scheduling, in which the resources are used or processed in order. When the last resource has been used, the scheduler starts over again at the beginning. For example, in the case of a network load balancer with three hosts, the first request would go the first host, the second to the second host, the third to the third host, and the fourth back to the first host. The cycle would continue in this way indefinitely.

578

Delving into the STL: Containers and Iterators

Suppose that you decide to write a generic round-robin scheduling class that can be used with any type of resource. The class should support adding and removing resources, which occurs infrequently, and should support cycling through the resources in order to obtain the next one. You could use the STL vector directly, but it’s often helpful to write a wrapper class that provides more directly the functionality you need for your specific application. The following example shows a RoundRobin class template with comments explaining the code. First, here is the class definition:

#include <stdexcept> #include <vector> using std::vector;

//

//Class template RoundRobin

//Provides simple round-robin semantics for a list of elements.

//Clients add elements to the end of the list with add().

//getNext() returns the next element in the list, starting with the first,

//and cycling back to the first when the end of the list is reached.

//

// remove() removes the element matching the argument.

//

template <typename T> class RoundRobin

{

public:

//

//Client can give a hint as to the number of expected elements for

//increased efficiency.

//

RoundRobin(int numExpected = 0); ~RoundRobin();

//

//Appends elem to the end of the list. May be called

//between calls to getNext().

//

void add(const T& elem);

//

//Removes the first (and only the first) element

//in the list that is equal (with operator==) to elem.

//May be called between calls to getNext().

//

void remove(const T& elem);

//

//Returns the next element in the list, starting from 0 and continuously

//cycling, taking into account elements that are added or removed.

//

T& getNext() throw(std::out_of_range); protected:

vector<T> mElems;

typename std::vector<T>::iterator mCurElem;

579

Chapter 21

private:

// Prevent assignment and pass-by-reference. RoundRobin(const RoundRobin& src); RoundRobin& operator=(const RoundRobin& rhs);

};

As you can see, the public interface is straightforward: only three methods plus the constructor and destructor. The resources are stored in the vector mElems. mCurElem is an iterator that always refers to the next element in mElems that should be used in the round-robin scheme. Note the use of the typename keyword in front of the line declaring mCurElem. So far, you’ve only seen that keyword used to specify template parameters, but there is another use for it. You must specify typename explicitly whenever you access a type based on one or more template parameters. In this case, the template parameter T is used to access the iterator type. Thus, you must specify typename. This is another example of arcane C++ syntax.

The implementation of the RoundRobin class follows. Note the use of reserve() in the constructor, and the extensive use of the iterator in add(), remove(), and getNext(). The trickiest aspect is keeping mCurElem valid and referring to the correct element following add() or remove().

template <typename T> RoundRobin<T>::RoundRobin(int numExpected)

{

//If the client gave a guideline, reserve that much space. mElems.reserve(numExpected);

//Initialize mCurElem even though it isn’t used until

//there’s at least one element.

mCurElem = mElems.begin();

}

template <typename T> RoundRobin<T>::~RoundRobin()

{

// Nothing to do here--the vector will delete all the elements

}

//

// Always add the new element at the end.

//

template <typename T>

void RoundRobin<T>::add(const T& elem)

{

//

//Even though we add the element at the end,

//the vector could reallocate and invalidate the iterator.

//Take advantage of the random access iterator features to save our

//spot.

//

int pos = mCurElem - mElems.begin();

//Add the element. mElems.push_back(elem);

//If it’s the first element, initialize the iterator to the beginning.

580

Delving into the STL: Containers and Iterators

if (mElems.size() == 1) { mCurElem = mElems.begin();

}else {

//Set it back to our spot.

mCurElem = mElems.begin() + pos;

}

}

template <typename T>

void RoundRobin<T>::remove(const T& elem)

{

for (typename std::vector<T>::iterator it = mElems.begin(); it != mElems.end(); ++it) {

if (*it == elem) {

//

//Removing an element will invalidate our mCurElem iterator if

//it refers to an element past the point of the removal.

//Take advantage of the random access features of the iterator

//to track the position of the current element after the removal.

int newPos;

//If the current iterator is before or at the one we’re removing,

//the new position is the same as before.

if (mCurElem <= it) {

newPos = mCurElem - mElems.begin();

}else {

//Otherwise, it’s one less than before. newPos = mCurElem - mElems.begin() - 1;

}

//Erase the element (and ignore the return value). mElems.erase(it);

//Now reset our iterator.

mCurElem = mElems.begin() + newPos;

//If we were pointing to the last element and it was removed,

//we need to loop back to the first.

if (mCurElem == mElems.end()) { mCurElem = mElems.begin();

}

return;

}

}

}

template <typename T>

T& RoundRobin<T>::getNext()throw(std::out_of_range)

{

//First, make sure there are any elements. if (mElems.empty()) {

throw std::out_of_range(“No elements in the list”);

}

//Retrieve a reference to return.

T& retVal = *mCurElem;

581

Chapter 21

//Increment the iterator modulo the number of elements. ++mCurElem;

if (mCurElem == mElems.end()) { mCurElem = mElems.begin();

}

//Return the reference.

return (retVal);

}

Here’s a simple implementation of a load balancer that uses the RoundRobin class template. The actual networking code is omitted because networking is operating system specific.

#include “RoundRobin.h”

//

//Forward declaration for NetworkRequest

//Implementation details omitted

//

class NetworkRequest;

//

//Simple Host class that serves as a proxy for a physical machine.

//Implementation details omitted.

//

class Host

{

public:

//

//Implementation of processRequest would forward

//the request to the network host represented by the

//object. Omitted here.

//

void processRequest(NetworkRequest& request) {}

};

//

//Simple load balancer that distributes incoming requests

//to its hosts using a round-robin scheme

//

class LoadBalancer

{

public:

//

// Constructor takes a vector of hosts.

//

LoadBalancer(const vector<Host>& hosts); ~LoadBalancer() {}

//

//Ship the incoming request to the next host using

//a round-robin scheduling algorithm.

//

void distributeRequest(NetworkRequest& request);

582