Programming with the Standard Library - Advanced Programming - C++ All-in-One For Dummies (2009)

C++ All-in-One For Dummies (2009)

Book IV

Advanced Programming

Chapter 6: Programming with the Standard Library

In This Chapter

Architecting the Standard C++ Library

Storing data in vector or map

Containing data with a list or set

Stacking and queuing

Copying containers

When you get around in the world of C++ programming (a fun world indeed!), you’re going to encounter two different libraries that people use to make their lives easier. That is, after all, the ultimate point of computers — to make our lives easier, right? These two libraries are

♦ Standard C++ Library

♦ Standard Template Library (STL)

Some people say, “We use STL.” Others say, “We use the Standard C++ Library.” In this case, library means a set of classes that you can use in your programs. These libraries include handy classes, such as string and vector (which is like an array in that it’s a list in which you can store objects).

The difference between the Standard C++ Library and STL is that STL came first. STL was used by so many developers that the American National Standards Institute (ANSI) decided to standardize it. The result is the similar Standard C++ Library that is part of the official ANSI standard and now part of most modern C++ compilers (including CodeBlocks, Microsoft Visual C++, Borland C++ Builder, MinGW, Cygwin, and Dev-C++). We use the Standard C++ Library in this chapter. Because we know that this is C++, we just call it the Standard Library.

The concepts that we present here apply to STL, so if you’re using STL, you can use this chapter.

Architecting the Standard Library

When people start using the Standard C++ Library, they often ask: Where’s the source code? We see the header files, but where are the .cpp files? This question has an easy answer: There are no .cpp files! ANSI architected the Standard C++ Library for ease of use and reliability.

The classes contain their functions inside the class definitions; there are no forward declarations. You don’t add source files to your project or linking in compiled libraries. Just add an include line for the libraries you want.

Containing Your Classes

Computers need a place to store things, so the Standard Library includes containers in which you can put things. The classes for containing things are called container classes. These classes are templates. When you create an instance of a container class, you specify what class it holds.

image When you specify the class in a container, you are saying that the container will contain instances of your specified class or of classes derived from your specified class. You must decide whether the container will hold instances of the class, pointers to the instances, or references to the instances.

Storing in a vector

Listing 6-1 is an example of a container class. This particular container is a datatype called a vector, and it works much like an array.

Listing 6-1: Using Vectors as Examples of Container Classes

#include <iostream>

#include <vector>

using namespace std;

int main()

{

vector<string> names;

names.push_back(“Tom”);

names.push_back(“Dick”);

names.push_back(“Harry”);

names.push_back(“April”);

names.push_back(“May”);

names.push_back(“June”);

cout << names[0] << endl;

cout << names[5] << endl;

return 0;

}

Now, note how we used vector. First, it’s a template! That means it’s going to have a template parameter! And what is the template parameter? Why, you guessed it. (Or you looked at the code.) The template parameter is the type that the template will hold. Thus, the following declares a vector that holds strings:

vector<string> names;

Note also the header files that we included. Among them, we included <vector> (with no .h after the filename). In general, you include the header file that matches the name of the container you are using. Thus, if there were such a thing as a container called rimbucklebock, you would type #include <rimbucklebock>. Or, if there were such thing as a container called set (which there is), you would type #include <set>.

imageAt this point, you may be wondering, what’s the advantage to using a vector instead of a regular, plain old, no-frills array? The advantage is that, when you declare the vector instance, you don’t need to know up front how many items will be going in it. With an array, you need to know the size when you declare it.

A vector is the closest thing the Standard Library has to an array. In fact, a vector is very much like an array, except (being a class template) you get all the goodies that go with a class, such as member functions that operate on vector.

Here are some things you can do with vector:

♦ Add items to the end of it

♦ Access its members by using bracket notation

♦ Iterate through it, either from beginning to end or from end back to beginning

Listing 6-2 is another example of a vector. In this one, we set up several vectors, and you can see that each one holds a different type, which we specified in the template parameter.

Listing 6-2: Containing the Type You Specify in Classes

#include <iostream>

#include <vector>

using namespace std;

class Employee

{

public:

string Name;

string FireDate;

int GoofoffDays;

Employee(string aname, string afiredate,

int agoofdays) : Name(aname), FireDate(afiredate),

GoofoffDays(agoofdays) {}

};

int main()

{

// A vector that holds strings

vector<string> MyAliases;

MyAliases.push_back(string(“Bud The Sailor”));

MyAliases.push_back(string(“Rick Fixit”));

MyAliases.push_back(string(“Bobalou Billow”));

cout << MyAliases[0] << endl;

cout << MyAliases[1] << endl;

cout << MyAliases[2] << endl;

// A vector that holds integers

vector<int> LuckyNumbers;

LuckyNumbers.push_back(13);

LuckyNumbers.push_back(26);

LuckyNumbers.push_back(52);

cout << LuckyNumbers[0] << endl;

cout << LuckyNumbers[1] << endl;

cout << LuckyNumbers[2] << endl;

// A vector that holds Employee instances

vector<Employee> GreatWorkers;

GreatWorkers.push_back(Employee(“George Washington”,”123100”, 50));

GreatWorkers.push_back(Employee(“Thomas Jefferson”,”052002”, 40));

cout << GreatWorkers[0].Name << endl;

cout << GreatWorkers[1].Name << endl;

return 0;

}

After you compile and run this program, you see the following output from the cout statements:

Bud The Sailor

Rick Fixit

Bobalou Billow

13

26

52

George Washington

Thomas Jefferson

Mapping your data

Listing 6-3 is an example of a type of container called map. map works much like vector, except for one main difference: Whereas you look up items in vector by putting a number inside brackets as in this

cout << names[0] << endl;

with map, you can use any class or type you want for the index, not just numbers. This feature lets you associate objects. Take a gander at Listing 6-3 to see where we’re coming from.

Listing 6-3: Associating Objects with map

#include <iostream>

#include <map>

using namespace std;

int main()

{

map<string, string> marriages;

marriages[“Tom”] = “Suzy”;

marriages[“Harry”] = “Harriet”;

cout << marriages[“Tom”] << endl;

cout << marriages[“Harry”] << endl;

return 0;

}

First, you can see that to use map, we declare a variable of class map, supplying to the template the types of first the keys and then the values:

map<string, string> marriages;

Then we store something in map by putting a key inside brackets and setting it equal to a value:

marriages[“Tom”] = “Suzy”;

And to retrieve that particular item, we grab it based on the key:

cout << marriages[“Tom”] << endl;

And voilà! We get back the item stored in map for that particular key. Think of map like an array, except the indices, which are called keys, can be any object, not just a string.

image Even though the keys can be any type or class, you must specify the type or class you’re using when you set up map. And after you do that, you can use only that type for the particular map. Thus, if you say the keys will be strings, you cannot then use an integer for a key, as inmarriages[3] = “Suzy”;.

Containing instances, pointers, or references

One of the most common discussions you encounter when people start talking about how to use the container templates is whether to put instances in the containers, pointers, or references. For example, which of these should you type:

vector<MyClass>

vector<MyClass *>

vector<MyClass &>

In other words, do you want your container to store the actual instance (whatever that might mean), a reference to the actual instance, or a pointer to the instance?

To explore this idea, have a look at Listing 6-4. Here, we’re trying out the different ways of storing things in map: instances, pointers, and references.

Listing 6-4: Making Decisions: Oh, What to Store?

#include <iostream>

#include <map>

using namespace std;

class StoreMe

{

public:

int Item;

};

bool operator < (const StoreMe & first,

const StoreMe & second)

{

return first.Item < second.Item;

}

int main()

{

// First try storing the instances

map<StoreMe, StoreMe> instances;

StoreMe key1 = {10}; // braces notation!

StoreMe value1 = {20};

StoreMe key2 = {30};

StoreMe value2 = {40};

instances[key1] = value1;

instances[key2] = value2;

value1.Item = 12345;

cout << instances[key1].Item << endl;

instances[key1].Item = 34567;

cout << instances[key1].Item << endl;

// Next try storing pointers to the instances

map<StoreMe*, StoreMe*> pointers;

StoreMe key10 = {10};

StoreMe value10 = {20};

StoreMe key11 = {30};

StoreMe value11 = {40};

pointers[&key10] = &value10;

pointers[&key11] = &value11;

value10.Item = 12345;

cout << (*pointers[&key10]).Item << endl;

// Finally try storing references to the instances.

// (I commented it out because it will

// get an error. See the text!)

// map<StoreMe&, StoreMe&> pointers;

return 0;

}

First, note that to create the instances of StoreMe, we used the braces notation. You can do that when you have no constructors. So the line

StoreMe key1 = {10};

creates an instance of StoreMe and puts 10 in the Item member variable.

Also note that we commented out the single line

// map<StoreMe&, StoreMe&> pointers;

This is where we attempt to declare a map that holds references. But the line gets a compiler error. When you type this listing, you can try uncommenting the commented line and see the error message. We get several error messages as a result of this line, the main one was

error: conflicting declaration ‘std::map<StoreMe&, StoreMe&,

std::less<StoreMe&>, std::allocator<std::pair<StoreMe&, StoreMe&> > > pointers’

Apparently references are out of the question. But why is that?

Here’s why: It turns out map is making a copy of everything you put in it. How do we know this? By the output. Here’s what you see when you type this program (and recomment out the line that you uncommented out so that it’s a recommented-decommented line).

20

34567

12345

Aha! Tricky. Tricky indeed! But now we need to determine what this output means. For the first line, we stored a pair in map for key1 and value1:

instances[key1] = value1;

And then we changed the Item member variable in value1:

value1.Item = 12345;

Next we retrieved the value from the pair in map and printed the Item member:

cout << instances[key1].Item << endl;

When we did, we saw 20, not 12345. That means the value stored in map is a copy, not the original. We changed the Item member of the original to 12345, but the copy still had the previous value of 20.

But then, we did this:

instances[key1].Item = 34567;

The hope here was that this action would change the Item member of the value stored in map. And so we printed the value again:

cout << instances[key1].Item << endl;

And this time it did indeed change. We saw 34567. Excellent! Where there’s a will, there’s a way, and where there’s a value, there’s a change. (Or something like that.)

And now that we’ve figured out that map is storing copies of what we put in it, the idea of storing a pointer should be pretty clear: If we have a pointer variable and then we make a copy of it, although we have a separate pointer variable now, the original and the copy both point to the same thing. And that’s the idea behind the second part of Listing 6-4. We created map like this:

map<StoreMe*, StoreMe*> pointers;

Now this map stores pointer variables. Remember that a pointer variable just holds a number that represents an address. If two separate pointer variables hold the same number, it means they point to the same thing. Furthermore, because this map is holding pointers, really it’s holding numbers, not instances — something to think about.

And so we next set up some instances and then made one association:

pointers[&key10] = &value10;

Note the ampersand (&) — we’re storing the addresses in map. Then we changed the Item member of one the value objects:

value10.Item = 12345;

And this time, when we printed it by using this carefully parenthesized line

cout << (*pointers[&key10]).Item << endl;

We see this

12345

And once again . . . aha! This time the change stuck. Why is that? Because even though map holds a copy, it’s holding a copy of a pointer. And that pointer happens to point to the original value10 object. So when we changed the Item member of value10, map picked up the change.map itself didn’t change, but map is pointing to that value.

image From all this discussion about the containers holding copies, you can come to the following conclusion. Because map holds copies, you can remember these two rules about deleting your original objects:

♦ The container holds instances: If you’re putting instances in map, you can delete the original instances after they’re in map. This is okay because map has its own copies of the instances.

♦ The container holds pointers: If you’re putting pointers in map, you don’t want to delete the original instances because the pointers in map still point to these instances.

So which method is best? It’s up to you. But here are a couple of things to consider:

♦ Keeping instances around: If you don’t want to keep instances lying around, you can put the instances in the container, and it will make copies.

♦ Copyability: Are your classes copyable? Some classes, such as classes filled with pointers to other classes or classes that are enormous, don’t copy well. In that case, you may want to put pointers in the container.

Comparing instances

When you work with classes that contain other classes (such as vector), you need to provide the class with a way to compare two things. For us humans, having the superbrains that we do, comparing is easy. But it’s not that easy for a computer. For example, suppose you have two pointers to string objects. The first points to a string containing abc. The second points to another string containing abc. Are these two pointers the same?

Well, that depends on how you look at it. If you mean do they point to the same sequence of characters, then, yes, they are the same. But if you mean do they point to the same object, then maybe or maybe not. Look at this code:

string *pointer1 = new string(“abc”);

string *pointer2 = new string(“abc”);

Are pointer1 and pointer2 equal? Again, it depends on how you look at it. If you mean do they point to strings that are equivalent, then, yes, they are equal in that sense. If you mean do they point to the same object, then, no, they are not equal in that sense. Now look at this code:

string *pointer3 = new string(“abc”);

string *pointer4 = pointer3;

These two pointers point to the same object. So in that sense, they are equal. And because they point to the same object, they also point to the same string of characters. So, again, in that sense, they are equal.

As you can see, you have two kinds of comparisons when dealing with objects:

♦ You are comparing two objects and determining whether they are identical, even though they’re separate objects. If the two objects are separate but identical, you would say that they are equal.

♦ You are comparing two objects and determining if they are the same object. This can happen if you have two pointers and they both point to the same object. In that case, you say that they are equal.

So why do you need to know this besides to drive people batty? (“You say your car and our cars are the same, but in fact, they are different: One is yours, and the others are ours!”) You need to know this distinction because when you create a container class that holds instances of your object, often the class needs to know how to compare objects. This is particularly true in the case of map, which holds pairs of items, and you locate the items based on the first of the pair (called the key). When you tell map to find an item based on a key, map must search through its list of pairs until it finds one such that the key in the pair is equal to the one you passed in to the search.

Well, that’s all fine and dandy; but now, how can the computer know whether two objects are identical? That is, suppose that you are doing your comparison based on whether two separate objects are identical. How does the computer compare the two objects to determine if they are, in fact, identical?

And because we like to get people thinking, how about this: What if you have a list of objects, and you want to keep them in a sorted order? How does the computer determine a sort order?

Here’s an example. We create a class called Employee. That’s a standard example that you see in lots of books, but in this case it makes for a good example, for once. Now our Employee class contains these member variables: FirstName, LastName, andSocialSecurityNumber.

Next, we have a Salary class that contains payroll information for an employee. This class has member variables MonthlySalary and Deductions. (Yes, in real life, you would probably have more member variables, but this is good enough for now.)

Next, we have a map instance, where each key,value pair contains an Employee instance for the key and a Salary instance for the value. So the big question is this: If we want to look up an employee, we would make an instance of Employee and fill in the FirstName, LastName, and SocialSecurityNumber member variables. We would then retrieve the value based on this key. But we can think of two issues here:

♦ We would create an instance and allow map to find the key that matches the instance. Is map looking for the exact same instance or one identical to it?

♦ If map is looking for an instance identical to the object we filled in, what happens if the employee changed his or her name (such as during a marriage). Can you cause map to still find the right key if map has one name and the search object has another? Most likely. In such cases, you would want the value to match only based on the SocialSecurityNumber, without worrying about the others. So in that case, can you tell map to treat the two objects as identical?

Here’s how to resolve these two issues: If you’re dealing with your own classes, in addition to setting up a container class, you also provide a function that compares two instances of your own class. Your comparison function can determine whether two classes are equal, if the first is less than the second, or if the first is greater than the second.

image At first, how less than and greater than can apply to things like an Employee class may not seem apparent. But the idea behind less than and greater than is to give the container class a way to determine a sort order. If you have a list class holding Employee instances, for example, and you tell the list to keep them in a sorted order, how does the list know how to sort them? By using the notion of less than and greater than. The list can determine if one is greater than another and can group them in a sorted order. But if you’re dealing with anEmployee class, you would choose how to sort them: Should an Employee instance with a social security number of 111-11-1111 be less than 999-99-9999? Or should they be sorted based on name, so that the person with social security number 111-11-1111 but the name Zoë Zusseldörf come after the person with social security number 999-99-9999 but the name Aaron Aackman? Well, the answer is this: It’s your decision. And after you decide how you want them sorted, you would create a function that determines if one is less than, equal to, or greater than the other. If you want the list to sort by name, you would make your function look strictly at the names. (And will it look at last name, first name, or both? That’s your decision.) But if you want your list to sort by social security number, you would write your function to compare the social security numbers.

Listing 6-5 shows an example of a map class, along with a comparison function that determines whether two keys are equal.

Listing 6-5: Containing Instances and Needing Functions That Compare Them

#include <iostream>

#include <map>

using namespace std;

class Employee

{

public:

string Nickname;

string SocialSecurityNumber;

Employee(string anickname, string asocial) :

Nickname(anickname),

SocialSecurityNumber(asocial) {}

Employee() : Nickname(“”), SocialSecurityNumber(“”) {}

};

class Salary

{

public:

int AnnualRipoff;

int IRSDeductionsCheat;

Salary(int aannual, int adeductions) :

AnnualRipoff(aannual),

IRSDeductionsCheat(adeductions) {}

Salary() : AnnualRipoff(0), IRSDeductionsCheat(0) {}

};

bool operator < (const Employee& first, const Employee& second)

{

return first.Nickname < second.Nickname;

}

int main()

{

map<Employee, Salary> employees;

Employee emp1(“sparky”, “123-22-8572”);

Salary sal1(135000, 18);

employees[emp1] = sal1;

Employee emp2(“buzz”, “234-33-5784”);

Salary sal2(150000, 23);

employees[emp2] = sal2;

// Now test it out!

Employee emptest(“sparky”, “”);

cout << employees[emptest].AnnualRipoff << endl;

return 0;

}

When you run this program, you will see the AnnualRipoff member of the Salary value, where the key is an Employee with the name sparky:

135000

Now notice a couple things about this code. First, to locate the salary for Sparky, we didn’t need the Employee instance for Sparky. Instead, we created an instance of Employee and set up the Nickname member without worrying about the SocialSecurityNumber member. Then we retrieved the value by using the bracket notation for map:

cout << employees[emptest].AnnualRipoff << endl;

Now why did this work? Because the map code uses our less-than function that we provided. And in that function, we compared only the Nickname members, not the SocialSecurityNumber member. We could, however, change things around a bit. Instead of comparing theNickname members, we could compare the SocialSecurityNumber members. We could change the less-than function like so:

bool operator < (const Employee& first,

const Employee& second)

{

return first.SocialSecurityNumber <

second.SocialSecurityNumber;

}

And then we can locate Sparky’s salary based on his social security number:

Employee emptest(“”, “123-22-8572”);

cout << employees[emptest].AnnualRipoff << endl;

image Wait! This can’t be right! How can the computer locate the item with the matching key if all you’re giving it is a less-than comparison? Good question. Here’s how: Suppose you want to find out if two numbers, say 5 and 5, are equal. (We know, they are equal, but bear with us.) But suppose the only comparison you have available is less-than. How can you determine if they are equal? You first see if the first is less than the second: Is 5 less than 5? Nope. Then you see if the second is less than the first: Is the second 5 less than the first 5? Nope. And because neither is less than the other, they must be equal! Aha! And that’s how the code for the various containers matches objects: It calls your less-than function twice, the second time flip-flopping the order of the parameters; and if your function returns false both times, the computer determines that they are equal. That approach makes life easier because you need to provide only a single comparison function! Yay!

Iterating through a container

When your house is full of things, sometimes being able to climb over it all so you can look down on it and see what all is there is nice. Containers in the Standard Library are the same way: If you have a container filled with things, being able to climb through it would be nice.

To climb through a container, you use an iterator. And iterator works with a container to let you step one-by-one through the container, seeing what all is in it.

Each container class contains an embedded type called iterator. To create an iterator instance, then, you need to use the fully qualified name. For example, if you have a map that holds integers and strings as in map<int, string>, you would create an iterator instance like this:

map<string, int>::iterator loopy

Although loopy is an instance of iterator, some serious typedefing is going on, and, in fact, loopy is a pointer to an item stored inside the container.

Less<MyClass> is more

When we create a class that we will be using in a container, we prefer to write our own overloaded less-than function. The containers in the Standard Library work as follows: When you create a class based on a container template, you provide the types that the container holds, and you also provide a class (or struct) that includes a less-than member function. However, this class doesn’t have a function called <. Instead, it’s called (), and it takes two parameters, one for each of the two items you’re comparing. The container class then calls this function to compare instances.

Well that’s all great, but why haven’t we seen this in action? The reason is the containers have default template parameters. If you don’t supply this magical less-than class, the container supplies one for you. What does it supply? It supplies a class based on a template called less. This template is simple; it includes a single member function that returns the Boolean value

x < y

For most basic types, that’s fine. The compiler can easily use that if, for example, you’re working with integers. But what if you’re working with one of your own classes? The compiler doesn’t understand the < operator unless you provide your own < operator function, as we did everywhere else in this chapter. However, because the container takes a class in its parameter that defaults to the class less, you can put together your own class and use that instead of writing your own < operator function. Here’s a sample:

class MyLess

{

public:

bool operator()(const MyClass &x,

const MyClass &y) const

{

return x.Name < y.Name;

}

};

Then when you create, for example, a map, you would pass this class as a third parameter, rather than relying on the default:

map<MyClass, MyClass, MyLess> mymap;

And, of course, then you don’t need your own less-than function.

Now, you want to initialize loopy to point to the first item in the container. And you can do this by calling the container’s begin member function and storing the results in loopy. Then loopy will point to the first item in the container. You can access the item by dereferencingloopy; then when you’re finished, you can move to the next item by incrementing loopy like this:

loopy++;

That’s pretty easy. And you can tell whether you’re finished by checking to see whether loopy points to the end of the items. To do this, you call the container’s end member function and compare loopy to the results of end. If it’s equal, you’re done.

The following few lines of code do these steps:

vector<string>::iterator vectorloop = Words.begin();

while (vectorloop != Words.end())

{

cout << *vectorloop << endl;

vectorloop++;

}

You can see the type we used for the iterator, in this case called vectorloop. And you can see that we initialized it by calling begin. We dereferenced it to get to the data itself, and then incremented vectorloop to get to the next item. And in the while loop we testedvectorloop against the results of end to see if we’re all done.

image Many people seem to forget how to use iterators. We suggest keeping the code in Listing 6-6 handy somewhere. (Print it and hang it on the wall, or save a copy in a directory on your hard drive where you can find it quickly, or maybe print it on really big paper and paste it to the front windshield of your car.) Then if you forget how to put together a simple iterator, you can easily find the answer.

Listing 6-6: Iterating

#include <iostream>

#include <map>

#include <vector>

using namespace std;

int main()

{

// Iterating through a map

map<string, int> NumberWords;

NumberWords[“ten”] = 10;

NumberWords[“twenty”] = 20;

NumberWords[“thirty”] = 30;

map<string, int>::iterator loopy = NumberWords.begin();

while (loopy != NumberWords.end())

{

cout << loopy->first << “ “;

cout << loopy->second << endl;

loopy++;

}

// Iterating through a vector

vector<string> Words;

Words.push_back(“hello”);

Words.push_back(“there”);

Words.push_back(“ladies”);

Words.push_back(“and”);

Words.push_back(“aliens”);

vector<string>::iterator vectorloop = Words.begin();

while (vectorloop != Words.end())

{

cout << *vectorloop << endl;

vectorloop++;

}

return 0;

}

image When you create a vector, it allocates some space for the data you put in it. But after all that space gets filled up and vector is stuffed to the brim, vector will resize itself, adding more space. But in doing so, it uses the old memory-shuffle trick where it first allocates a bigger chunk of memory; then it copies the existing data into the beginning of that bigger chunk of memory, and finally it frees the original chunk of memory. Now if you use the various iterator functions to home in on a certain item in vector (giving you a pointer to the item) and you save that pointer, then after vector reallocates itself, that pointer will no longer be valid! It will point to somewhere in the original memory block that’s no longer being used. So be careful.

For example, suppose you have the following code to set up a vector

vector<int> test;

test.push_back(1);

test.push_back(2);

test.push_back(3);

and then you use an iterator to get to the beginning; from there you go to the second item in vector; then you print the address of the second item:

vector<int>::iterator i1 = test.begin();

i1++;

cout << i1 << endl;

Then you decide to add a whole bunch of items:

for (int loop = 0; loop < 5000; loop++)

{

test.push_back(loop);

}

And now, if you once again use an iterator to get to the second item and then print the address like so

vector<int>::iterator i2 = test.begin();

i2++;

cout << i2 << endl;

you will likely see a different number than you previously did. If so, it means vector reallocated itself, and that means the original pointer is no longer valid.

A map of pairs in your hand

When you iterate through map, you get back not just the value of each item nor the key of each item. Instead, you get back a pair of things — the key and the value together. These live inside an instance of a class called Pair. (Although, really, it’s a template.) This pair instance has two member variables, first and second. The first member refers to the key in the pair, and the second member refers to the value in the pair. When you iterate through map, the iterator points to an instance of Pair, so you can grab the key by looking at first and the value by looking at second. But be careful, because Pair is the internal storage bin inside map. You’re not looking at copies; you’re looking at the actual data in map. If you change the data as in this

while (loopy != NumberWords.end())

{

loopy->second = loopy->second * 2;

loopy++;

}

you will be changing the value stored in map — not a copy of it. So use caution!

The Great Container Showdown

In the sections that follow, we give a rundown of the containers available in the Standard Library. Different containers have different places in life. Some are tall, some are short — wait a minute, that’s not right. They each have a different purpose, and in the following sections we show you where you can use each of them.

Associating and storing with a set

First things first. set is not a set. If you have any background in mathematics, you’ve likely come across the notion of a set. And in math, a set doesn’t have an order to it. It’s a group of items stored in, well, a set.

In the Standard Library, set has an order to it. However, like a math set, set doesn’t allow duplicates. If you try to put an item in set that’s already there, set will ignore your attempt to do so.

Listing 6-7 shows you how to use set.

Listing 6-7: Using set to Look up Items

#include <iostream>

#include <set>

using namespace std;

class Employee

{

public:

string Nickname;

string SocialSecurityNumber;

Employee(string anickname, string asocial) :

Nickname(anickname),

SocialSecurityNumber(asocial) {}

Employee() : Nickname(“”), SocialSecurityNumber(“”) {}

};

bool operator < (const Employee& first,

const Employee& second)

{

return first.SocialSecurityNumber <

second.SocialSecurityNumber;

}

ostream& operator << (ostream &out, const Employee &emp)

{

cout << “(“ << emp.Nickname;

cout << “,” << emp.SocialSecurityNumber;

cout << “)”;

return out;

}

int main()

{

set<Employee> employees;

Employee emp1(“sparky”, “123-22-8572”);

employees.insert(emp1);

Employee emp2(“buzz”, “234-33-5784”);

employees.insert(emp2);

Employee emp3(“coollie”, “123-22-8572”);

employees.insert(emp3);

Employee emp4(“sputz”, “199-19-0000”);

employees.insert(emp4);

// List the items

set<Employee>::iterator iter = employees.begin();

while (iter != employees.end())

{

cout << *iter << endl;

iter++;

}

// Find an item

cout << “Finding...” << endl;

Employee findemp(“”, “123-22-8572”);

iter = employees.find(findemp);

cout << *iter << endl;

return 0;

}

In Listing 6-7, we included an Employee class, along with a less-than function. The less-than function compares the SocialSecurityNumber member of two Employee instances. This results in two things:

♦ Ordering: The items in set will be ordered according to social security number. This is not true with all containers, but it is the way a set works.

♦ Duplicates: If we try to add two employees with matching SocialSecurityNumber members (but the other members can be different), the second addition won’t take. The set will ignore it.

You can see in this listing that we tried to add two employees with the same SocialSecurityNumber members:

Employee emp1(“sparky”, “123-22-8572”);

employees.insert(emp1);

and

Employee emp3(“coollie”, “123-22-8572”);

employees.insert(emp3);

Later, when we print all the items in set, we see only the one for “sparky”, not the one for “coollie”. set ignored the second employee.

Finding an item in set is interesting. Look at how we did it: We created an instance of Employee, and we filled in only the SocialSecurityNumber member, because that’s the only member that the less-than function looks at. Then we called find. But what did we get back? If you look at the function header, you will see that the find function returns an iterator. But that seems silly. Why an iterator? We’re not iterating, by cracky!

The reason we get back an iterator is because the iterator type is really a typedef for a pointer to an item inside set. Oh, okay; that makes sense then: When we call find, we get back a pointer to an item in set, even if its typename is iterator. And so to access the item, we dereference the pointer.

imageIn Listing 6-7, we did something handy: We created a function that lets us use our Employee instance with cout. We did this by overloading the insertion function. This function’s header looks like this:

ostream& operator << (ostream &out, const Employee &emp) {

The first parameter represents cout, and the second is the item we’re couting. And so, inside this function, we write to cout the individual members of the Employee. Not a problem.

Unionizing and intersecting sets

Everybody has an opinion on unionizing, but fortunately, we’re not talking about workers’ unions in this section. Instead, we’re talking about sets and how you can combine two sets to get the union, or you can find the common elements to get the intersection.

When you #include <set>, you automatically get a couple of handy functions for finding the union and intersection of some sets.

Showdown: maps versus sets

And for the first showdown, we’d like to offer you a philosophical (yet practical!) discussion on the difference between map and set. map lets you store information based on a key, through which you can retrieve a value. Elsewhere in this chapter, we use an example where the key is anEmployee instance and the value is a Salary instance. But with set, you can achieve something similar: In Listing 6-7, we could have had a single class containing both Employee and Salary information. And you can see in Listing 6-7 that we were able to look up the Employeeinstance based on nothing but a social security number. So in this sense, we created a map where the key is a social security number and the value is the rest of the employee information. Tricky, no? The fact is, you can often accomplish associations with set, as you can with map. But the advantage to set is that you need to store only one instance for each item, whereas with map, you must have two instances, both a key and a value. But the advantage to map is that you can use the nice bracket notation. The choice is yours.

image set does not allow duplicates. A union of two sets is a set that consists of all the elements of the two sets combined, but without any duplicates. The intersection is also itself a set, and therefore it has no duplicates.

Listing 6-8 shows how you can find the intersection and union of two sets.

Listing 6-8: Finding an Intersection and a Union Is Easy!

#include <iostream>

#include <set>

using namespace std;

void DumpClass(set<string> *myset)

{

set<string>::iterator iter = myset->begin();

while (iter != myset->end())

{

cout << *iter << endl;

iter++;

}

}

int main()

{

set<string> EnglishClass;

set<string> HistoryClass;

EnglishClass.insert(“Zeus”);

EnglishClass.insert(“Magellan”);

EnglishClass.insert(“Vulcan”);

EnglishClass.insert(“Ulysses”);

EnglishClass.insert(“Columbus”);

HistoryClass.insert(“Vulcan”);

HistoryClass.insert(“Ulysses”);

HistoryClass.insert(“Ra”);

HistoryClass.insert(“Odin”);

set<string> Union;

set<string> Intersection;

insert_iterator<set<string> >

IntersectIterate(Intersection, Intersection.begin());

insert_iterator<set<string> >

UnionIterate(Union, Union.begin());

set_intersection(EnglishClass.begin(),

EnglishClass.end(),

HistoryClass.begin(), HistoryClass.end(),

IntersectIterate);

cout << “===Intersection===” << endl;

DumpClass(&Intersection);

set_union(EnglishClass.begin(),

EnglishClass.end(),

HistoryClass.begin(), HistoryClass.end(),

UnionIterate);

cout << endl << “===Union===” << endl;

DumpClass(&Union);

return 0;

}

When you run the code in Listing 6-8, you see this output:

===Intersection===

Ulysses

Vulcan

===Union===

Columbus

Magellan

Odin

Ra

Ulysses

Vulcan

Zeus

But as you can see, something a little bizarre is in the code. Specifically, this part isn’t exactly simple:

insert_iterator<set<string> >

IntersectIterate(Intersection, Intersection.begin());

This is used in the call to set_intersection. First, recognize that this crazy code is a variable declaration. The first line is the type of the variable, a template called insert_iterator. The template parameter is the type of set, in this case set<string>.

The next line is the instance name, IntersectIterate, and the constructor requires two things: the set that will hold the intersection (called Intersection) and an iterator pointing to the beginning of the Intersection set (even though set is empty).

The variable that these two lines create is an iterator, and it is basically a helper object through which some function that needs to insert multiple items into a list can use. In this case, the function is set_intersection. Now the set_intersection function doesn’t take as parameters the sets directly; instead, it takes the beginning and ending iterators of the two sets, along with the IntsersectIterate thingamabob declared earlier. And you can see in Listing 6-8 that those are the five items we passed to the set_intersection function.

Then after calling the set_intersection function, the Intersection object will contain the intersection of the two sets.

The set_union function works precisely the same way, except it figures out the union of the two sets, not the intersection.

image To use the set_intersection and set_union functions, you need to #include <algorithm>. This is one of the header files in the Standard C++ Library.

imageIf you find the code in Listing 6-8 particularly ugly, a slightly easier way to call set_intersection where you don’t need to directly create an instance of insert_iterator is available. It turns out there’s a function that will do it for you. To use this function, you can remove the declaration for IntersectIterate and UnionIterate, and then instead call set_intersection like this:

set_intersection(EnglishClass.begin(),

EnglishClass.end(),

HistoryClass.begin(), HistoryClass.end(),

inserter(Intersection, Intersection.begin()));

The fourth line simply calls a function called inserter, which creates an instance of insert_iterator for you. Then you can do the same for set_union:

set_union(EnglishClass.begin(),

EnglishClass.end(),

HistoryClass.begin(), HistoryClass.end(),

inserter(Union, Union.begin()));

Listing with list

A list is a simple container similar to an array, except you can’t access the members of list by using a bracket notation as you can in vector or an array. You don’t use list when you don’t need access to only one item in the list; you use it when you plan to traverse through the list, item-by-item.

To add items to a list, use the list’s push_front member function or its push_back member function. The push_front function inserts the item in the beginning of the list, in front of all the others that are presently in the list. If you use push_front several times in a row, the items will be in the reverse order from which you put them in. The push_back function adds the item to the end of the list. So if you put items in a list by using push_back, their order will be the same as the order in which you added them.

You can also insert an item before an existing item if you have a pointer to the item inside the list.

image For operations where you need a pointer to an item in the list, you need to use an iterator. An iterator is simply a typedef for a pointer to an item in the list; however, it points to the item in the list, not the original item you added to the list. Remember, the containers hold copies. Thus, if you do an insert into a list and point to an original item, that item won’t be a member of the list, and the insert won’t work.

imageAlthough the list template includes an insert function, this function has only very special uses. To use insert, you must have a pointer to an item in the list — that is, you need to have an iterator. But how do you get this pointer? By traversing the list. It has no findfunction, and so really the only time you would use the insert function is if you’re already working your way through the list. But if you do need to do an insert and you’re willing to use iterators to move through the list to find the location where you want to put the new item,insert will do the job.

In Listing 6-9, we demonstrate lists by using a duck metaphor. (They’re all in a row.) In this example, we create a list, add our ducks to it, and then reverse it. Next, we create a second list and splice its members into the first list.

Listing 6-9: Handling Items in a List Template

#include <iostream>

#include <list>

using namespace std;

class Duck

{

public:

string name;

int weight;

int length;

};

ostream& operator << (ostream &out, const Duck &duck)

{

cout << “(“ << duck.name;

cout << “,” << duck.weight;

cout << “,” << duck.length;

cout << “)”;

return out;

}

void DumpDucks(list<Duck> *mylist)

{

list<Duck>::iterator iter = mylist->begin();

while (iter != mylist->end())

{

cout << *iter << endl;

iter++;

}

}

list<Duck>::iterator MoveToPosition(list<Duck> *mylist, int pos)

{

list<Duck>::iterator res = mylist->begin();

for (int loop = 1; loop <= pos; loop++)

{

res++;

}

return res;

}

int main()

{

list<Duck> Inarow;

// Push some at the beginning

Duck d1 = {“Jim”, 20, 15}; // Braces notation!

Inarow.push_front(d1);

Duck d2 = {“Sally”, 15, 12};

Inarow.push_front(d2);

// Push some at the end

Duck d3 = {“Squakie”, 18, 25};

Inarow.push_front(d3);

Duck d4 = {“Trumpeter”, 19, 26};

Inarow.push_front(d4);

Duck d5 = {“Sneeky”, 12, 13};

Inarow.push_front(d5);

// Display the ducks

cout << “===========” << endl;

DumpDucks(&Inarow);

// Reverse

Inarow.reverse();

cout << “===========” << endl;

DumpDucks(&Inarow);

// Splice

// Need another list for this

list<Duck> extras;

Duck d6 = {“Grumpy”, 8, 8};

extras.push_back(d6);

Duck d7 = {“Sleepy”, 8, 8};

extras.push_back(d7);

Duck d8 = {“Ornery”, 8, 8};

extras.push_back(d8);

Duck d9 = {“Goofy”, 8, 8};

extras.push_back(d9);

cout << “===========” << endl;

cout << “extras:” << endl;

DumpDucks(&extras);

list<Duck>::iterator first =

MoveToPosition(&extras, 1);

list<Duck>::iterator last =

MoveToPosition(&extras, 3);

list<Duck>::iterator into =

MoveToPosition(&Inarow, 2);

Inarow.splice(into, extras, first, last);

cout << “===========” << endl;

cout << “extras after splice:” << endl;

DumpDucks(&extras);

cout << “===========” << endl;

cout << “Inarow after splice:” << endl;

DumpDucks(&Inarow);

return 0;

}

We made a function, MoveToPosition, that moves to a position in the list. This may seem counterproductive because the list template doesn’t allow random access. But we needed three iterators to perform the splice: The start and end position of the second list (the one we’re splicing members from) and the position in the first list where we want to put the spliced members. For that, we needed an iterator, which MoveToPosition finds for us.

image The function we created, MoveToPosition, is a template function. But when we called the function, we didn’t provide the typename in angle brackets. The compiler can figure out which class version we need; the compiler knows that it can look at what we pass into the function as a parameter and use its type to decide the template parameter. (Without the template type in the function parameter, the compiler can’t figure it out.) Here’s the program output:

===========

(Sneeky,12,13)

(Trumpeter,19,26)

(Squakie,18,25)

(Sally,15,12)

(Jim,20,15)

===========

(Jim,20,15)

(Sally,15,12)

(Squakie,18,25)

(Trumpeter,19,26)

(Sneeky,12,13)

===========

extras:

(Grumpy,8,8)

(Sleepy,8,8)

(Ornery,8,8)

(Goofy,8,8)

===========

extras after splice:

(Grumpy,8,8)

(Goofy,8,8)

===========

Inarow after splice:

(Jim,20,15)

(Sally,15,12)

(Sleepy,8,8)

(Ornery,8,8)

(Squakie,18,25)

(Trumpeter,19,26)

(Sneeky,12,13)

Showdown: lists versus vectors

With a list, you do not have random access to the list, which is a fancy-schmancy way of saying that you can’t drop into the middle of the list and look at whatever item is stored there as you can with a vector. If you want to look at the items in the list, you must either start at the beginning or the end and work your way through it one by one. But with a vector, you can refer to any element by using brackets, as in MyVector[3}. This may seem like a disadvantage for the list, but the ANSI document claims that “many algorithms only need sequential access anyway.” We suppose that there are times when you don’t need to drop into the middle of an array, and then a list might do. But lists have definite advantages. The list template allows you to splice together multiple lists, and it has good support for sorting the list, for splicing members out of one list and into another, and for merging multiple lists.

You can see the elements that were inside the two lists before and after the splice; the ducks moved from one list to another.

image When you specify the positions for the splice operation, the splice includes the start position up to but not including the ending position. Listing 6-9 shows this: We spliced from position 1 to 3 in the second list (extras). But we got the ducks from positions 1 and 2 because the code spliced position 1 up to but not including 3 — which is 2.

Stacking the deque

A deque (pronounced “deck”) container is a sequential list of items like vector and list. Like vectors and unlike lists, deques allow bracket notation for random access. Unlike vector, deque lets you insert items at the beginning and pop items off the beginning. To create a deque that holds integers, do something like this:

deque<int> mydek;

mydek.push_front(10);

mydek.push_front(20);

mydek.push_front(30);

mydek.push_back(40);

mydek.push_back(50);

mydek.push_back(60);

Then you can loop through the deque, accessing its members with a bracket, as if it’s an array:

int loop;

for (loop = 0; loop < mydek.size(); loop++)

{

cout << mydek[loop] << endl;

}

You can also grab items off the front or back of the deque. Here’s an example from the front:

while (mydek.size() > 0)

{

cout << mydek.front() << endl;

mydek.pop_front();

}

Two functions show up here, front and pop_front. The front function returns a reference to the item at the front of the deque. The pop_front function removes the item that’s at the front of the deque.

Waiting in line with stacks and queues

Two common programming data structures are in the Standard Library:

♦ Stack: With a stack, you put items one-by-one on top of it, and you only take items one-by-one off the top of it. You can add several items, one after the other, before taking an item off the top. This process is sometimes called a First In Last Out (FILO) algorithm.

♦ Queue: A queue is like waiting in line at the post office (and some people call such a line a queue). The line gets longer and longer as people arrive, and the new people each go to the back of the line. But people leave only by the front of the line. The queue data structure is like that: You add data at the back of the queue, and take data off one-by-one at the front of the queue. Like the stack, the queue also has an alternate name: it’s a First In First Out (FIFO) algorithm.

To use the Standard Library to make a stack, you can use a deque, a list, or a vector as the underlying storage bin. Then you declare the stack, as in the following example:

stack<int, vector<int> > MyStack;

Or you can optionally use the default, which is queue:

stack<int> MyStack;

For a queue, you can’t use vector because vectors don’t include operations for dealing with a front. So, for that situation, you can use either deque or list. For example, here’s a line of code that uses list:

queue<int, list<int> > MyQueue;

Or here’s a line of code that uses deque by default:

queue<int> MyQueue;

Showdown: deques versus vectors

If you go online to any discussion board and use a search phrase like C++ deque vector, you will see a lot of discussion, arguments, and confusion between when to use deque and when to use vector. To know which to use when, you need to understand the differences between the two. Under the hood, vector usually stores all its data in a regular old array, making it easy to directly access the members. But that also means that, to insert items, vector must slide everything over to make room for the inserted items. deque, however, does not use the contiguousapproach that vector does. Inserting is then easier for it because it doesn’t need to shuffle things around. Also, deque doesn’t have to regrow itself if it runs out of space, whereas vector does. And finally, deque includes a push_front member function that allows you to easily add an item at the beginning. The vector template does not include this member.

You normally perform three operations with a stack and a queue:

♦ push: When you add an item to a stack or queue, you push the item. This puts the item on top of the stack or at the back of the queue.

♦ peek: When you look at the top item of the stack or the front of the queue, you peek. The peek operation doesn’t remove the item, however.

♦ pop: When you remove an item from a stack or from the front of the queue, you pop it off. For some libraries, this gives you the item. For the Standard Library, it removes the item. To use an item off the top or front of the stack or queue, first you peek at it and then you pop it off.

In the Standard Library, for peeking at the front of a queue, you call the front member function. For a stack, you call the top member function.

For pushing and popping, the Standard Library uses these terms. The queue and stack each include a push function and a pop function. Listing 6-10 demonstrates both a stack and a queue.

Listing 6-10: Creating a Stack and a Queue

#include <iostream>

#include <stack>

#include <queue>

using namespace std;

void StackDemo()

{

cout << “===Stack Demo===” << endl;

stack<int, vector<int> > MyStack;

// Remember the space between the > >

MyStack.push(5);

MyStack.push(10);

MyStack.push(15);

MyStack.push(20);

cout << MyStack.top() << endl;

MyStack.pop();

cout << MyStack.top() << endl;

MyStack.pop();

MyStack.push(40);

cout << MyStack.top() << endl;

MyStack.pop();

}

void QueueDemo()

{

cout << “===Queue Demo===” << endl;

queue<int> MyQueue;

// No container specified in the queue, so it

// uses deque by default. The same goes for stack.

MyQueue.push(5);

MyQueue.push(10);

MyQueue.push(15);

cout << MyQueue.front() << endl;

MyQueue.pop();

cout << MyQueue.front() << endl;

MyQueue.pop();

MyQueue.push(40);

cout << MyQueue.front() << endl;

MyQueue.pop();

}

int main()

{

StackDemo();

QueueDemo();

return 0;

}

image When you specify a container to use inside the stack or queue, remember to put a space between the closing angle brackets. Otherwise, the compiler reads it as a single insertion operator, >>, and gets confused.

Copying Containers

Structures are easy to copy when class libraries are well designed. The Standard C++ Library is that well designed. Each container class contains both a copy constructor and an equal operator. To copy a container, you either set one equal to the other or pass the first container into the constructor of the second (which copies the first into the second). Listing 6-11 shows this.

Listing 6-11: Copying Containers Couldn’t Be Easier

#include <iostream>

#include <map>

using namespace std;

class Scrumptious

{

public:

string Dessert;

};

bool operator < (const Scrumptious & first,

const Scrumptious & second)

{

return first.Dessert < second.Dessert;

}

class Nutrition

{

public:

int VitaminC;

int Potassium;

};

int main()

{

map<Scrumptious, Nutrition> ItsGoodForMe;

Scrumptious ap = {“Apple Pie”}; // Braces notation!

Nutrition apn = {7249, 9722};

Scrumptious ic = {“Ice Cream”};

Nutrition icn = {2459, 19754};

Scrumptious cc = {“Chocolate Cake”};

Nutrition ccn = {9653, 24905};

Scrumptious ms = {“Milk Shake”};

Nutrition msn = {46022, 5425};

ItsGoodForMe[ap] = apn;

ItsGoodForMe[ic] = icn;

ItsGoodForMe[cc] = ccn;

ItsGoodForMe[ms] = msn;

map<Scrumptious,Nutrition> Duplicate = ItsGoodForMe;

map<Scrumptious,Nutrition> AnotherDuplicate(ItsGoodForMe);

ItsGoodForMe[ap].Potassium = 20;

cout << ItsGoodForMe[ap].Potassium << endl;

cout << Duplicate[ap].Potassium << endl;

cout << AnotherDuplicate[ap].Potassium << endl;

return 0;

}

You can see in this listing that we created two classes, Scrumptious and Nutrition. We then created a map called ItsGoodForMe that associates Scrumptious instances with Nutrition instances.

We copied map twice, using both an equals sign and a copy constructor:

map<Scrumptious,Nutrition> Duplicate = ItsGoodForMe;

map<Scrumptious,Nutrition> AnotherDuplicate(ItsGoodForMe);

And that was it! We then changed one of the elements in the original map, to see what would happen. Then we printed that element, as well as the corresponding element in the two copies. Here’s the output:

20

9722

9722

Yep, they’re different: This implies that the maps each have their own copies of the instances — that there’s no sharing of instances between the maps.

image Containers hold copies, not originals. That’s true when you copy containers, too. If you put a structure in a container and copy the container, the latter container has its own copy of the structure. To change the structure, you must change all copies of it. The way around this is to put pointers inside the containers. Then the containers each have their own copies of the pointers, but these pointers point to the same one-and-only object.