Chapter 6

Programming with the Standard Library

IN THIS CHAPTER

Architecting the Standard C++ Library

Managing data in vector, map, list, or set

Stacking and queuing

Interacting with dynamic arrays and unordered data

When you get around in the world of C++ programming, you encounter two different libraries that people use to make their lives easier. These two libraries are:

• Standard C++ Library
• Standard Template Library (STL)

In this case, library means a set of classes that you can use in your applications. These libraries include handy classes, such as string and vector (which is like an array — it’s a list you use to 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. This chapter uses the Standard C++ Library, or simply the Standard Library. The concepts presented here also apply to STL, so if you’re using STL, you can use this chapter.

You don’t have to type the source code for this chapter manually. In fact, using the downloadable source is a lot easier. You can find the source for this chapter in the \CPP_AIO4\BookV\Chapter06 folder of the downloadable source. See the Introduction for details on how to find these source files.

Architecting the Standard Library

When people start using the Standard Library, they often ask about the source code. They see the header files, but no .cpp files. There are no .cpp files. ANSI architected the Standard 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 link in compiled libraries. Just add an include line for the libraries you want.

To see how this works for yourself, open any project file you’re worked on to date that has #include <iostream> and relies on a cout/endl combination to output text. Right-click endl and choose Find Implementation of: ’endl’ from the context menu. Code::Blocks will open the ostream file and take you to the implementation of endl, which basically outputs ’\n’ to the output stream, amid some other confusing code. When you scroll to the beginning of that file, you see:

/** @file include/ostream
* This is a Standard C++ Library header.
*/

There is no .cpp file involved. All of the code appears in the header.

Containing Your Classes

Computers need a place to store objects, so the Standard Library includes containers in which you can put objects. These special containers are called container classes, and the Standard Library implements them as templates. When you create an instance of a container class, you specify what class it holds.

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

The Vectors example, shown in Listing 6-1, demonstrates how to use a container class. This particular container is a data type 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;
}

You use vector as a template. That means that it’s going to have a template parameter, which is string in this case. Note also the included header files. Among them are <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 you use the container called set, you type #include <set>. When you run this example, you see two names as output:

Tom
June

There are a number of advantages to using a vector instead of a regular, plain old, no-frills array:

• 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.
• You don’t need to specifically deallocate a vector, as you do with a dynamically defined array.
• You can obtain the precise size of a vector, so you don’t need to pass the size of the vector to a function.
• When a vector is filled, the underlying code allocates additional memory automatically.
• You can return a vector from a function. To return an array, you must dynamically define it first.
• You can add and remove items from the middle of a vector, something that you can’t easily do with an array.
• You can copy or assign a vector directly.

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 the end back to the beginning.

The Vectors2 example, shown in Listing 6-2, demonstrates how to use multiple vectors in a single application. You can see that each one holds a different type, specified in the template parameter. This example requires C++ 11 or above to use.

LISTING 6-2: Creating More Advanced Vectors

#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"));
for (auto entry : MyAliases)
cout << entry << endl;

// A vector that holds integers
vector<int> LuckyNumbers;
LuckyNumbers.push_back(13);
LuckyNumbers.push_back(26);
LuckyNumbers.push_back(52);
for (auto entry : LuckyNumbers)
cout << entry << endl;

// A vector of default constructed ints.
vector<int> Default(5);
int i = 0;
vector<int>::reverse_iterator rentry = Default.rbegin();
for (; rentry != Default.rend(); rentry++)
*rentry = ++i;
for (auto entry : Default)
cout << entry << endl;

// A vector that holds Employee instances
vector<Employee> GreatWorkers;
GreatWorkers.push_back(Employee("George","123100", 50));
GreatWorkers.push_back(Employee("Tom","052002", 40));
for (auto entry : GreatWorkers)
cout << entry.Name << endl;
return 0;
}

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

Bud The Sailor
Rick Fixit
Bobalou Billow
13
26
52
5
4
3
2
1
George
Tom

Notice that this example relies on an iterated for loop for each of the vectors. Using an iterated for loop greatly reduces the amount of code you write. Plus, you don’t have to worry about the size of the vector you’re processing. All you concern yourself with are the individual entries.

The Default portion of the example is also interesting in that it declares a vector of a specific size and reverse-fills the vector from the end to the beginning. Consequently, Default[0] contains the value 5, rather than 1, as you might expect. To work backward, you must use a standard for loop.

Working with std::array

Sometimes you need a fixed-size array, but without the limitations of the built-in array. In this case, std::array may do the trick for you. It provides built-in functionality, such as knowing its own size, supporting assignment, and providing random access iterators. The StdArray example, shown in Listing 6-3, demonstrates two interesting ways that you can use std::array. You need C++ 17 or above to use this example.

LISTING 6-3: Working with std::array to Overcome array Limitations

#include <iostream>
#include <array>
#include <algorithm>
#include <iterator>

using namespace std;

int main() {
array<char, 5> Letters = {'a', 'b', 'c', 'd', 'e'};

for (entry: Letters)
cout << entry << endl;

reverse_copy(Letters.begin(), Letters.end(),
ostream:iterator<char>(cout, " "));
return 0;
}

Notice that the declaration begins by providing the array type, char, and the number of array elements, 5, as template parameters. Letters contains five char values from ’a’ through ’e’.

As shown in the example, you can use a standard iterated for loop to display the individual entries. However, you can also output the Letter content in other ways, such as by performing a reverse_copy() to the console with the ostream:iterator<char>(). The point is to avoid limiting yourself to one coding style when another will do the job better with fewer lines. Here’s the output you see from the example:

a
b
c
d
e
e d c b a

Mapping your data

The Maps example, shown in Listing 6-4, demonstrates a type of container called a map. A map works much the same as a vector, except for one main difference: You look up items in vector by putting a number inside brackets, like this:

cout << names[0] << endl;

But with a map, you can use any class or type you want for the index (called a key), not just numbers. To create an entry, you use a key (the index) and a value (the data) as a pair.

LISTING 6-4: 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;
}

To use map, you declare a variable of class map, supplying two template parameters, the key class and the value class, which are both string in the example. To store a map value, you place a key inside brackets and set it equal to a value:

marriages["Tom"] = "Suzy";

To retrieve that particular item, you supply the key in brackets:

cout << marriages["Tom"] << endl;

When you run this example, you see the following two strings as output:

Suzy
Harriet

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. After you do that, you can use only that type for the particular map. Thus, if you say that the keys will be strings, you cannot then use an integer for a key, as in marriages[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 the following 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, look at the Maps2 example in Listing 6-5. Here, you’re trying out the different ways of storing things in map: instances, pointers, and references.

LISTING 6-5: 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.
// Commented out because it causes an error.)
// map<StoreMe&, StoreMe&> pointers;
return 0;
}

To create the instances of StoreMe, you use 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 property. To create an individual instances entry, you need both a key and a value instance of StoreMe. You then use the key to provide a name for the value stored in the map. Consequently, instances contains two entries consisting of two StoreMe objects each. Here’s what you see when you run the application:

20
34567
12345

This output doesn’t precisely match expectations because the code changes the Item property in value1:

value1.Item = 12345;

When the code outputs the value of instances[key1].Item, you see an output of 20, not 12345. That means that the value stored in map is a copy, not the original. However, when the code changes the value in instances like this:

instances[key1].Item = 34567;

the value portion of the instances entry does change. You see 34567 as output. Consequently, when working with map instances, you must modify the map entry directly.

Now that you’ve figured out that map is storing copies of what you put in it, the idea of storing a pointer should be clear: If you have a pointer variable and then you make a copy of it, although you have a separate pointer variable, the original and the copy both point to the same memory location. That’s the idea behind the second part of Listing 6-5. You create pointers 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 that they point to the same object at the same address. Furthermore, because this map is holding pointers, it’s holding numbers, not instances — something to think about. To store a value when using pointers, you need to use code like this:

pointers[&key10] = &value10;

Note the use of the ampersand (&) used as a reference operator to store addresses in map. It’s now possible to change the Item member of one the value objects:

value10.Item = 12345;

that you print using this carefully parenthesized line:

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

and you see this:

12345

When working with map pointers, you modify the original variable to make a change because the map entries point to the original variable, rather than make a copy of it. However, as you can see, using map pointers also makes your code harder to read.

Don’t worry just now about the bool operator < (const StoreMe & first, const StoreMe & second) function. This function is explained in the “Performing comparisons” section, later in this chapter.

Note that the following line is commented out:

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

It attempts to declare a map that holds references, but the code generates a compiler error instead. Try uncommenting the commented line and see the error message. Here’s an example of what you might see (make sure to add the comment back in when you’re done):

error: conflicting declaration 'std::map<StoreMe&,
StoreMe&> pointers'
error: 'pointers' has a previous declaration as
'std::map<StoreMe*, StoreMe*> pointers'

References are out of the question because the map is making a copy of everything you put in it.

Working with copies

All C++ containers, not just maps, generally make copies of whatever you stick inside them as shown in the previous section. The Vectors3 example, shown in Listing 6-6, replicates the essential functionality of the Maps2 example shown in Listing 6-5.

LISTING 6-6: The vector Version of the Maps2 Example

#include <iostream>
#include <vector>

using namespace std;

class StoreMe {
public:
int Item;
};

int main() {
vector<StoreMe> instances;
StoreMe value1 = {20};
StoreMe value2 = {40};
instances.push_back(value1);
instances.push_back(value2);

value1.Item = 12345;
cout << instances[0].Item << endl;
instances[0].Item = 34567;
cout << instances[0].Item << endl;

vector<StoreMe*> pointers;
StoreMe value10 = {20};
StoreMe value11 = {40};
pointers.push_back(& value10);
pointers.push_back(& value11);

value10.Item = 12345;
cout << (*pointers[0]).Item << endl;
return 0;
}

Oddly enough, the output from this example is precisely the same as the Maps2 example and for the same reason. Whether the container is a vector or a map doesn’t matter; both of them hold copies of the objects or pointers you provide. Consequently, you can remember these two rules about deleting your original objects:

• When the container holds instances: If you’re putting instances in the container, you can delete the original instances after they’re added. This is okay because the container has its own copies of the instances.
• When the container holds pointers: If you’re putting pointers in the container, you don’t want to delete the original instances because the pointers in the container still point to these instances.

It’s up to you to decide which method is better. 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: 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. The following sections describe how to provide comparison capability when working with containers.

Considering comparison issues

For humans 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. When writing code, you must consider whether the two variables are equal:

• Value: When considering the value alone, the two string objects are equal.
• Memory location: When considering the pointer instead of the value, the two string objects aren’t equal.

Now look at this code:

string *pointer3 = new string("abc");
string *pointer4 = pointer3;

These two pointers point to the same object, which means that the memory locations are equal. Because they point to the same object, they also contain the same string of characters. So, from a value perspective, they’re also equal.

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 element of the pair — the key element. 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 search term (key) you passed in to the search. However, you need to consider these essentials when working with the keys:

• When using the pointer approach, two keys could contain the same value but point to different memory locations. So, you must consider whether the key search is based on value or memory location.
• When sorting the keys to make them easier to access in order, you must consider whether value is the only criterion by which to make the sort order correct.

Here’s an example. You create a class called Employee that contains these properties: FirstName, LastName, and SocialSecurityNumber. Next, you create a Salary class that contains payroll information for an employee. This class has properties MonthlySalary and Deductions.

With these two objects in place, you create a map instance, where each key/value pair contains an Employee instance for the key and a Salary instance for the value. To look up an employee, you would make an instance of Employee and fill in the FirstName, LastName, and SocialSecurityNumber properties. You then retrieve the value based on this key. There are two issues here:

• You’d create an instance and allow map to find the key that matches the instance. It’s essential to know whether map is looking for the exact same instance or one identical to it. When looking for the exact same instance, you need a pointer to the original object, not a new object that you fill in with values.
• If map is looking for an instance identical to the object you create, the search will fail if the employee changed names (such as during a marriage). In this case, your code needs logic to tell map to make the match based on the SocialSecurityNumber, without worrying about the other properties.

The bottom line is that you need code within your classes to determine how to make comparisons. The comparisons are made based on what you see as essential data traits. These traits vary by dataset because how you use the dataset varies. Consequently, you can’t create a one-size-fits-all solution; you must consider each dataset individually.

Performing comparisons

The previous section provides details on two issues you must resolve when comparing objects. 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, the first is less than the second, or the first is greater than the second.

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. For example, you might choose to sort an Employee class in one of these ways:

• Social Security number
• Last name, first name
• First name, last name
• Employee ID
• Address
• Organizational department

The point is that the computer can’t make this decision; you need to choose how you want the data to appear. After you decide how you want them sorted, you’d create a function that determines when one record 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. But if you want your list to sort by Social Security number, you would write your function to compare the Social Security numbers.

The Maps3 example, shown in Listing 6-7, contains a map class with a comparison function that determines whether two keys are equal.

LISTING 6-7: Containing Instances and Needing Functions That Compare Them

#include <iostream>
#include <map>

using namespace std;

class Emp {
public:
string Nickname;
string SSN;

Emp(string anickname, string asocial) :
Nickname(anickname),
SSN(asocial) {}

Emp() : Nickname(""), SSN("") {}
};

class Salary {
public:
int YearlyInc;
int Taxes;

Salary(int aannual, int adeductions) :
YearlyInc(aannual),
Taxes(adeductions) {}

Salary() : YearlyInc(0), Taxes(0) {}
};

bool operator < (const Emp& first, const Emp& second) {
return first.Nickname < second.Nickname;
}

int main() {
map<Emp, Salary> employees;

Emp emp1("sparky", "123-22-8572");
Salary sal1(135000, 18);
employees[emp1] = sal1;

Emp emp2("buzz", "234-33-5784");
Salary sal2(150000, 23);
employees[emp2] = sal2;

// Now test it out!
Emp emptest("sparky", "");
cout << employees[emptest].YearlyInc << endl;
return 0;
}

When you run this application, you see the YearlyInc 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, you don’t need the Employee instance for Sparky. Instead, you create an instance of Employee and set up the Nickname member without worrying about the SSN member. Then you retrieve the value by using the bracket notation for map:

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

The map code uses the less-than function to perform this task. The < function compares only the Nickname members, not the SSN member. Notice that this function must return a bool value and that you precede the < with the operator keyword, defining this as an operator function — one that defines an operation between operands. You could change things around a bit by comparing the SSN members like so:

bool operator < (const Emp& first, const Emp& second) {
return first.SSN < second.SSN;
}

Then you can locate Sparky’s salary based on the SSN:

Employee emptest("", "123-22-8572");
cout << employees[emptest].SSN << endl;

A single < function may not seem like enough to perform all the required comparisons, such as equality. However, the code calls the less-than function twice, the second time flip-flopping the order of the parameters; and if the function returns false both times, the computer determines that they are equal. Using this approach makes life easier because you need to provide only a single comparison function.

UNDERSTANDING THE DEFAULT < FUNCTION

Containers in the Standard Library have a default < function. If you don’t supply a < function of your own, the container supplies this default < function for you. This default function relies on a template class called less. This template is simple: It includes a single method that returns the Boolean value:

x < y

For most basic types, the default works fine. For example, the compiler can easily use the default when you’re working with integers. However, the compiler doesn’t understand the < operator when working with custom classes unless you provide your own < operator function, as you see 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 pass this class as a third parameter, rather than relying on the default:

map<MyClass, MyClass, MyLess> mymap;

Then you don’t need your own less-than function. The advantage of this approach is that you now have a standardized < function implementation to use everywhere, and it’s especially helpful when working within a team environment.

Iterating through a container

Containers in the Standard Library provide an overview of the container’s content. If you have a container filled with objects ,you normally get an overview of what’s there, but being able to drill down into the details would be nice. You use an iterator to drill down into the container. An iterator works with a container to let you step object by object through the container. The following sections tell you about iterators and how to work with them.

Working with iterators

Each container class contains an embedded type called iterator. You use the fully qualified name to create an iterator instance. For example, if you have a map that holds integers and strings, as in map<int, string>, you 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. To initialize loopy to point to the first item in the container, you call the container’s begin() method, storing the results in loopy. Then loopy will point to the first item in the container. You can access the item by dereferencing loopy; then, when you’re finished, you can move to the next item by incrementing loopy like this:

loopy++;

You can use this technique in various ways, such as by using the call to reverse_copy() shown previously in Listing 6-3. You can tell whether you’re finished by checking to see whether loopy points to the last item in the container. To do this, you call the container’s end() method and compare loopy to the end() value. If it’s equal, you’re done. The following few lines of code perform these steps:

vector<string>::iterator vectorloop = Words.begin();
while (vectorloop != Words.end())
{
cout << *vectorloop << endl;
vectorloop++;
}

You can see the type used for the iterator, in this case called vectorloop, which is initialized by calling begin(). vectorloop is dereferenced to access the data, and is then incremented to get to the next item. The while loop tests vectorloop against the results of end() to determine when the processing is complete. The Iterators example code, shown in Listing 6-8, shows a more complete example of how to use an iterator.

LISTING 6-8: 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;
}

When you compile and run this application, you see the following output:

ten 10
thirty 30
twenty 20
hello
there
ladies
and
aliens

Avoiding pointer problems

When you create a vector, it allocates some space for the data you put in it. When the memory fills with data, the vector resizes itself, adding more space. To perform this task, vector 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.

Saving the pointer you receive when you use the various iterator functions to access a certain vector item (giving you a pointer to the item) is a bad idea because, after vector allocates more memory, that pointer will no longer be valid. It will point to somewhere in the original memory block that’s no longer being used. The IteratorPointer example, shown in Listing 6-9, helps you understand the ramifications of this problem.

LISTING 6-9: Seeing the Pointer Problem in Action

#include <iostream>
#include <vector>

using namespace std;

int main() {
vector<int> test{1, 2, 3};

vector<int>::iterator i1 = test.begin();
i1++;
cout << &i1 << endl;

test.push_back(4);

vector<int>::iterator i2 = test.begin();
i2++;
cout << &i2 << endl;
}

When you run this example, the code creates test with space for three items. The code then prints the address of the second item. Adding just one item means that test has to resize. The code then prints the address for the second item. The outputs won’t match because the pointer to the second item changed during the resizing process.

A map of pairs in your hand

When you iterate through map, you get back not just the value of each item nor do you get just the key of each item. Instead, you get back a pair of things — the key and the value together. These objects live inside an instance of a template class called Pair, which has two properties, 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. Be careful: 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 code

while (loopy != NumberWords.end())
{
loopy->second = loopy->second * 2;
loopy++;
}

you change the value stored in map — not a copy of it.

The Great Container Showdown

The sections that follow provide a rundown of containers available in the Standard Library. Each container has a different purpose. In the following sections, you see where you can use each of them.

Associating and storing with a set

First things first: set is not a mathematical set. If you have any background in mathematics, you’ve likely come across the notion of a set. In math, a set doesn’t have an order to it. It’s a group of well-defined distinct objects stored in a collection.

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. The Sets example, shown in Listing 6-10, demonstrates how to use set.

LISTING 6-10: Using set to Look up Items

#include <iostream>
#include <set>

using namespace std;

class Emp {
public:
string Nickname;
string SSN;

Emp(string anickname, string asocial) :
Nickname(anickname),
SSN(asocial) {}

Emp() : Nickname(""), SSN("") {}
};

bool operator < (const Emp& first, const Emp& second) {
return first.SSN < second.SSN;
}

ostream& operator << (ostream &out, const Emp &emp) {
cout << "(" << emp.Nickname;
cout << "," << emp.SSN;
cout << ")";
return out;
}

int main() {
set<Emp> employees;

Emp emp1("sparky", "123-22-8572");
employees.insert(emp1);
Emp emp2("buzz", "234-33-5784");
employees.insert(emp2);
Emp emp3("albert", "123-22-8572");
employees.insert(emp3);
Emp emp4("sputz", "199-19-0000");
employees.insert(emp4);

// List the items
set<Emp>::iterator iter = employees.begin();
while (iter != employees.end())
{
cout << *iter << endl;
iter++;
}

// Find an item
cout << "Finding…" << endl;
Emp findemp("", "123-22-8572");
iter = employees.find(findemp);
cout << *iter << endl;
return 0;
}

When you compile and run this example, you see the following output:

(sparky,123-22-8572)
(sputz,199-19-0000)
(buzz,234-33-5784)
Finding…
(sparky,123-22-8572)

Listing 6-10 includes an Employee class along with a < operator that compares the SSN member of two Employee instances. This comparison results in two things:

• Ordering: The items in set are in Social Security number order. This isn’t true with all containers, but it’s the way a set works.
• Duplicates: The set ignores any attempt to add two employees with matching SSN values (even if other properties differ).

You can see in this listing that the code tries to add two employees with the same SSN values:

Employee emp1("sparky", "123-22-8572");
employees.insert(emp1);

and

Employee emp3("albert", "123-22-8572");
employees.insert(emp3);

Later, when the code prints all the items in set, you see only the one for "sparky", not the one for "albert". set ignored the second employee.

Finding an item in set is interesting. You create an instance of Employee and fill in only the SSN value, because that’s the only property that the < function looks at. Call find() to perform the search. The find() function returns an iterator because the iterator type is really a typedef for a pointer to an item inside set. To access the item, you dereference the pointer.

Listing 6-7 shows a handy function that lets you use the Employee instance with cout by overloading the insertion (<<) operator 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 output value. Inside this function, you write to cout the individual members of the Employee. It also helps to know that you can perform map comparisons as needed using the same technique found in the “Understanding the default < function” sidebar. This same technique works with a class, but it requires more coding to implement.

SHOWDOWN: MAPS VERSUS SETS

It’s important to realize the difference between map and set. map lets you store information based on a key, through which you can retrieve a value. Listing 6-7, presented earlier in the “Performing comparisons” section, shows an example in which the key is an Emp instance and the value is a Salary instance. But with set, you can achieve something similar: Listing 6-10 could use a single class containing both Emp and Salary information. Also, you can see in Listing 6-10 that it’s possible to look up the Emp instance based on nothing but a Social Security number. So in this sense, the Listing 6-10 example shows a map in which the key is a Social Security number and the value is the rest of the employee information. The fact is, you can often accomplish associations with set, as you can with map. 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. The advantage to map is that you can use the nice bracket notation. The choice is yours.

Unionizing and intersecting sets

When you work with sets, you commonly do the following:

• Combine two sets to get the union (all the elements in both sets without any duplicates).
• Find the common elements to get the intersection (those unique elements that appear in both sets).

When you #include <set>, you automatically get a couple of handy functions for finding the union and intersection of some sets. The Sets2 example, shown in Listing 6-11, demonstrates how you can find the intersection and union of two sets.

LISTING 6-11: Finding an Intersection and a Union Is Easy!

#include <iostream>
#include <set>
#include <algorithm>

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> English;
English.insert("Zeus");
English.insert("Magellan");
English.insert("Vulcan");
English.insert("Ulysses");
English.insert("Columbus");

set<string> History;
History.insert("Vulcan");
History.insert("Ulysses");
History.insert("Ra");
History.insert("Odin");

set<string> Intersect;
insert_iterator<set<string> >
IntersectIterate(Intersect, Intersect.begin());
set_intersection(English.begin(), English.end(),
History.begin(), History.end(), IntersectIterate);
cout << "===Intersection===" << endl;
DumpClass(&Intersect);

set<string> Union;
insert_iterator<set<string> >
UnionIterate(Union, Union.begin());
set_union(English.begin(), English.end(),
History.begin(), History.end(), UnionIterate);
cout << endl << "===Union===" << endl;
DumpClass(&Union);
return 0;
}

When you run the code in Listing 6-11, 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(Intersect, Intersect.begin());

This code is used in the call to set_intersection(). It’s 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 Intersect) and an iterator pointing to the beginning of the set, which is Intersect.begin().

The variable that these two lines create is an iterator, which is a helper object that another function can use to insert multiple items into a list. In this case, the function is set_intersection(). The set_intersection() function doesn’t take the sets as input; instead, it takes the beginning and ending iterators of the two sets, along with the IntersectIterate iterator declared earlier. You can see in Listing 6-11 that those are the five items passed to the set_intersection() function. After calling set_intersection(), the Intersect object contains the intersection of the two sets. set_union() works precisely the same way as set_intersection(), except it figures out the union of the two sets, not the intersection.

To use set_intersection() and set_union(), you need to add #include <algorithm> to the top of your listing. This is one of the header files in the Standard Library.

If you find the code in Listing 6-11 particularly ugly, a slightly easier way to call set_intersection(), one that doesn’t require you to directly create an instance of insert_iterator, is available. It turns out that a function exists that will do it for you. To use this function, you can remove the declarations for IntersectIterate and UnionIterate, and then instead call set_intersection(), like this:

set_intersection(English.begin(), English.end(),
History.begin(), History.end(),
inserter(Intersect, Intersect.begin()));

The third line simply calls inserter(), which creates an instance of insert_iterator for you. Then you can do the same for set_union():

set_union(English.begin(), English.end(),
History.begin(), History.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 with an array. You don’t use list when you need to access 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() method or its push_back() method. 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. Using insert() and splice() enables you to place items in other locations in the list. You use an iterator to find the location you want and then splice the new item at that location.

For operations in which 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.

Although 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 that you obtain by traversing the list. It has no find() function, 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.

The Lists example, shown in Listing 6-12, demonstrates lists by using a duck metaphor (as in, getting all your ducks in a row). This example creates a list, adds ducks, and then reverses it. Next, the code creates a second list and splices its members into the first list.

LISTING 6-12: 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 Dump(list<Duck> *mylist) {
list<Duck>::iterator iter = mylist->begin();
while (iter != mylist->end())
{
cout << *iter << endl;
iter++;
}
}

list<Duck>::iterator Move(list<Duck> *mylist, int pos) {
list<Duck>::iterator res = mylist->begin();
for (int loop = 1; loop <= pos; loop++)
{
res++;
}
return res;
}

bool operator < (const Duck& first, const Duck& second) {
return first.name < second.name;
}

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 = {"Betty", 18, 25};
Inarow.push_front(d3);
Duck d4 = {"Arnold", 19, 26};
Inarow.push_front(d4);

// Display the ducks
cout << "===Ducks===" << endl;
Dump(&Inarow);

// Reverse
Inarow.reverse();
cout << "\n==Reversed==" << endl;
Dump(&Inarow);

// Create the second list.
list<Duck> extras;
Duck d5 = {"Grumpy", 8, 8};
extras.push_back(d5);
Duck d6 = {"Sleepy", 8, 8};
extras.push_back(d6);

// Display the extras list.
cout << "\n===Extras===" << endl;
Dump(&extras);

// Determine the positions.
list<Duck>::iterator first = Move(&extras, 0);
list<Duck>::iterator last = Move(&extras, 2);
list<Duck>::iterator into = Move(&Inarow, 2);

// Perform the splicing.
Inarow.splice(into, extras, first, last);
cout << "\n==Extras After Splice==" << endl;
Dump(&extras);
cout << "\n==Inarow After Splice==" << endl;
Dump(&Inarow);

// Sort the list.
Inarow.sort();
cout << "\n===Sorted===" << endl;
Dump(&Inarow);
return 0;
}

Move() moves to a position in the list. This function may seem counterproductive because the list template doesn’t allow random access. But you need three iterators to perform the splice: two to target the start and end position of the second list (the source list) and one to target the position in the first list used to hold the spliced members. Move() locates the target position.

Move() is a template function. However, when calling the function, you don’t provide the type name in angle brackets; the compiler determines which class version to use based on the object type passed into the function as a parameter.

To use sort(), you must provide a < operator function, as described in earlier examples. Here’s the application output:

===Ducks===
(Arnold,19,26)
(Betty,18,25)
(Sally,15,12)
(Jim,20,15)

==Reversed==
(Jim,20,15)
(Sally,15,12)
(Betty,18,25)
(Arnold,19,26)

===Extras===
(Grumpy,8,8)
(Sleepy,8,8)

==Extras After Splice==

==Inarow After Splice==
(Jim,20,15)
(Sally,15,12)
(Grumpy,8,8)
(Sleepy,8,8)
(Betty,18,25)
(Arnold,19,26)

===Sorted===
(Arnold,19,26)
(Betty,18,25)
(Grumpy,8,8)
(Jim,20,15)
(Sally,15,12)
(Sleepy,8,8)

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

SHOWDOWN: LISTS VERSUS VECTORS

Lists provide sequential access, which means 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 start at the beginning or the end and work your way through it one item at a time. A vector allows random access using brackets, as in MyVector[3]. This requirement may seem like a disadvantage for the list, but the ANSI document says that “many algorithms only need sequential access anyway.” 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.

Stacking the deque

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

deque<int> mydek;
mydek.push_front(10);
mydek.push_front(20);
mydek.push_back(30);
mydek.push_back(40);

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();
}

SHOWDOWN: DEQUES VERSUS VECTORS

If you go online to any discussion board and use a search phrase like C++ deque vector, you see a lot of discussion, arguments, and confusion over 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 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 doesn’t use the contiguous approach that vector does. Inserting is easier for deque because it doesn’t need to shuffle things around. Also, deque doesn’t have to add new elements to perform a resize, whereas vector does when it runs out of space. And finally, deque includes a push_front() method that allows adding an item at the beginning.

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: You put items on top of a stack one by one — and you take items off the top of the stack one by one. You can add several items, one after the other, before taking an item off the top. This process is sometimes called a Last In, First Out (LIFO) algorithm.
• Queue: A queue is like waiting in line at the post office — the line gets longer as people arrive. Each new person goes to the back of the line. People leave from the front of the line. 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 deque:

stack<int> MyStack;

For a queue, you can’t use vector because vectors don’t include operations for dealing with the front of an item list. So, you can use either deque or list. 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;

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 action puts the item on top of the stack or at the back of the queue.
• peek: When you look at the top of the stack or the front of the queue, you peek. The peek operation doesn’t remove the item.
• pop: When you remove an item from the top of a stack or from the front of the queue, you pop it off.

To peek at the front of a queue, you call the front() method. For a stack, you call the top() method. For pushing and popping, the queue and stack each include a push() function and a pop() function. The StackAndQueue example, shown in Listing 6-13, demonstrates both a stack and a queue.

LISTING 6-13: 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;
MyStack.push(5);
MyStack.push(10);
MyStack.push(15);

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;
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;
}

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. Here is the output from this example:

===Stack Demo===
15
10
40
===Queue Demo===
5
10
15

Copying Containers

Structures are easy to copy when using well-designed class libraries — meaning that 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. The CopyContainer example shown in Listing 6-14 demonstrates how to perform this task.

LISTING 6-14: Copying Containers Couldn’t Be Easier

#include <iostream>
#include <map>

using namespace std;

class Tasty {
public:
string Dessert;
};

bool operator < (const Tasty & One, const Tasty & Two) {
return One.Dessert < Two.Dessert;
}

class Nutrition {
public:
int VitaminC;
int Potassium;
};

int main() {
map<Tasty, Nutrition> ItsGoodForMe;
Tasty ap = {"Apple Pie"}; // Braces notation!
Nutrition apn = {7249, 9722};
Tasty ic = {"Ice Cream"};
Nutrition icn = {2459, 19754};
Tasty cc = {"Chocolate Cake"};
Nutrition ccn = {9653, 24905};
Tasty ms = {"Milk Shake"};
Nutrition msn = {46022, 5425};

ItsGoodForMe[ap] = apn;
ItsGoodForMe[ic] = icn;
ItsGoodForMe[cc] = ccn;
ItsGoodForMe[ms] = msn;

map<Tasty,Nutrition> Duplicate1 = ItsGoodForMe;
map<Tasty,Nutrition> Duplicate2(ItsGoodForMe);
ItsGoodForMe[ap].Potassium = 20;
Duplicate1[ap].Potassium =40;

cout << ItsGoodForMe[ap].Potassium << endl;
cout << Duplicate1[ap].Potassium << endl;
cout << Duplicate2[ap].Potassium << endl;
return 0;
}

You can see that Listing 11-14 contains two classes, Tasty and Nutrition. A map called ItsGoodForMe associates Tasty instances with Nutrition instances. The code copies map twice, using both an equals sign and a copy constructor:

map<Tasty,Nutrition> Duplicate1 = ItsGoodForMe;
map<Tasty,Nutrition> Duplicate2(ItsGoodForMe);

The code changes one of the elements in the original map to see what happens and prints that element, as well as the corresponding element in the two copies (one of which is also changed). Here’s the output:

20
40
9722

The output implies that the maps each have their own copies of the instances — that there’s no sharing of instances between the maps.

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 each container has its own copy of the pointer, but all these pointers point to the same one-and-only object.

Creating and Using Dynamic Arrays

Sometimes you don’t know the array size you need until runtime. The default arrays provided with C++ rely on static sizes. In other words, you need to know what size array you need at the time you write the code. Unfortunately, the real world is dynamic — it changes. The earlier sections of this chapter discuss a number of array alternatives, such as stacks, queues, and deques. However, these solutions all require that you use a library. They also tend to increase the memory requirements of your application and slow it down as well. You have another alternative in the form of dynamic arrays. The following sections describe dynamic arrays and show how to use them. You need a minimum of C++ 11 to use these examples.

A dynamic array relies on the heap, the common area of memory that your application allocates for use by your application’s functions. (See the “Heaping and Stacking the Variables” section of Book 1 Chapter 8 for more details.) You create a pointer to a variable of the correct type and then allocate memory for the resulting array. The functionality for performing this task is found in the new header file, so you need to include it as part of your application. The DynamicArray example, shown in Listing 6-15, demonstrates the use of a dynamic array.

LISTING 6-15: Creating and Using Dynamic Arrays

#include <iostream>
#include <new>

using namespace std;

int main() {
int HowMany;
int* DynArray;
cout << "How many numbers would you like?" << endl;
cin >> HowMany;
DynArray = new (nothrow) int[HowMany];

if (DynArray == nullptr)
cout << "Error: Could not allocate memory!";
else {
for(int i = 0; i < HowMany; i++)
DynArray[i] = i;

cout << "Displaying entries:" << endl;
for (int i = 0; i < HowMany; i++)
cout << DynArray[i] << endl;

delete[] DynArray;
}
return 0;
}

The example begins by creating variables to hold the number of array elements and the array itself, which is a pointer to an array of int elements. The application asks you how many array elements to create. It then uses the new operator to create the dynamic array, DynArray. Notice the technique used to do this. The new operator is followed by (nothrow). This tells the application that if there isn’t enough memory to create the array, it should return a nullptr value, which is simply a pointer that doesn’t point to anything.

The (nothrow) method may not work with certain compiler versions, especially when using the GNU Compiler Collection (GCC). The (nothrow) still works for low memory conditions, but it doesn’t work for conditions created explicitly as part of the application execution. In this case, you see a std::bad_array_new_length exception under these conditions:

• The array length is negative
• The total size of the new array would exceed implementation-defined maximum value
• The number of initializer-clauses exceeds the number of elements to initialize

Normally, the application would display an incomprehensible error message that only geeks could love if there wasn’t enough memory. Using the (nothrow) approach gives you the opportunity to handle the error differently. The application handles the error by displaying a human-readable error message if (DynArray == nullptr).

You work with a dynamic array just as you do any other array. The example shows how to fill the array with data and to display the data onscreen. The array has the same capabilities, advantages, and disadvantages of any other array. However, when you get done using the array, you need to use the delete[] operator to delete the dynamic array and free the memory it uses for some other purpose. The output from this example looks like this if you request four array elements:

How many numbers would you like?
4
Displaying entries:
0
1
2
3

Working with Unordered Data

Creating data that has a particular order is appealing because it’s a) easier to search and b) it makes certain tasks, such as removing old elements, easier. However, creating an ordered set of information is also problematic because you need to spend time keeping it in order. Newer versions of C++ provide access to an unordered set that is both searchable and easy to maintain. It has the advantage of adding the data in any order in which it comes. Minimal overhead is associated with trying to keep the data in a particular order. The following sections provide an overview of using unordered data. You need a minimum of C++ 11 to use these examples.

Using std::unordered_set to create an unordered set

Like the other containers discussed in this chapter, an unordered_set provides a particular method for storing data in a manner that makes it easy to access later. In this case, you have access to functions that insert() and erase() elements from the container. A special function, emplace() enables you to add new elements only if the element doesn’t exist. Otherwise, the unordered set will allow as many duplicates as you want (and you can easily count them using count()). You can also use the find() function to track down elements that you want. Special functions tell you when you’re at the beginning or end of the set.

Manipulating unordered sets

The easiest way to see how an unordered set works is to create one. The UnorderedSet example, shown in Listing 6-16, demonstrates how to use the various unordered_set features to maintain a listing of colors.

LISTING 6-16: Creating and Using Dynamic Arrays

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
unordered_set<string> Colors;
Colors.insert("Red");
Colors.insert("Green");
Colors.insert("Blue");

if(Colors.find("Red")!= Colors.end())
cout << "Found Red!" << endl;

auto ReturnValue = Colors.emplace("Red");
if(!ReturnValue.second)
cout << "Red is Already in Set!" << endl;

cout << "There are " << Colors.count("Red")
<< " Red entries." << endl;

ReturnValue = Colors.emplace("Orange");
if(!ReturnValue.second)
cout << "Orange is Already in Set!" << endl;
else
cout << "Orange Added to Set!" << endl;

Colors.erase("Red");
if(Colors.find("Red")!= Colors.end())
cout << "Found Red!" << endl;
else
cout << "Red Missing!" << endl;
return 0;
}

The example begins by creating a new unordered_set, Colors. Notice that this is a template, so you need to provide a type for the information that the set will hold. The code uses the insert() function to add three colors to the set.

The find() function enables you to look for a particular value in the set. When the value is missing, the find() function returns end(), which means that the current position within the set is at the end.

This example uses the auto data type. ReturnValue is used to detect when a value that you want to add to the set using emplace() already exists. If the value already exists, unordered_set refuses to add it when you call emplace(). On the other hand, if you call insert(), unordered_set will add duplicate entries.

To remove entries from a set, you call erase() with the value you want to remove. In this case, the example removes the color Red. It then searches for Red using find(). As you might expect, Red isn’t found this time. The output from this example is as follows:

Found Red!
Red is Already in Set!
There are 1 Red entries.
Orange Added to Set!
Red Missing!

Working with Ranges

C++ now offers support for ranges, which you can read about at https://en.cppreference.com/w/cpp/ranges. A range is the set of objects between a beginning point and an ending point. The concept of ranges depends on iterators. A view is an iteration that manages data in some manner, and a range acts on this iteration. The example in this section requires C++ 20. As mentioned elsewhere in the book, such as Book 1 Chapter 5, if your compiler doesn’t offer C++ 20 support, you can use Wandbox (https://wandbox.org/).

The Ranges example, shown in Listing 6-17, gives you a starting point for working with both ranges and views in C++ 20. In this example, the code creates a vector, MyList, fills it with data, and then uses the ranges::size() method to determine the size MyList. The code then creates a view that filters MyList and places the result in Filtered. A for loop prints the result.

LISTING 6-17: Working with Ranges and Views

#include <iostream>
#include <vector>
#include <ranges>

using namespace std;

int main() {
vector<int> MyList {9, 2, 1, 6, 3, 8, 4};
cout << "There are " << ranges::size(MyList) <<
" items in MyList" << endl;

auto Filtered = MyList | views::filter([](int n){
return n % 3 == 0; });
cout << "Items divisible by 3: " << endl;
for (int i : Filtered)
cout << i << endl;
return 0;
}

Filtered is a range adapter, which is an iterable range. To create this variable, you specify the list you want to use, such as MyList, a pipe symbol (|), and the view or views you want to create. This example uses views::filter(). When you want to create multiple views, you separate them with addition pipes. You can also find views that will transform your data, drop certain elements, split ranges, join ranges, and so on. Whatever the range adapter creates appears in Filtered. As the code shows, you iterate over the view using a standard for loop.