So far, the only standard containers you’ve used have been vector and map. I mentioned array in Exploration 9 and list in Exploration 44 but never went into depth. This Exploration introduces the remaining containers and discusses the general nature of containers. When third-party libraries implement additional containers, they usually follow the pattern set by the standard library and make their containers follow the same requirements.
Properties of Containers
The container types implement familiar data structures, such as trees, lists, arrays, and so on. They all serve the common purpose of storing a collection of similar objects in a single container object. You can treat the container as a single entity: compare it, copy it, assign it, and so on. You can also access the individual items in the container. What distinguishes one container type from another is how the container stores the items within it, which in turn affects the speed of accessing and modifying items in the container.
The standard containers fall into two broad categories: sequence and associative. The difference is that you can control the order of items in a sequence container but not in an associative container. As a result, associative containers offer improved performance for accessing and modifying their contents. The standard sequence containers are array (fixed-size), deque (double-ended queue), forward_list (singly linked list), list (doubly linked list), and vector (variable-length array). The forward_list type works differently from the other containers (due to the nature of singly linked lists) and is for specialized uses. This book does not cover forward_list, but you can find it in any C++ 11 reference.
The associative containers have two subcategories: ordered and unordered. Ordered containers store keys in a data-dependent order, which is given by the < operator or a caller-supplied functor. Although the standard does not specify any particular implementation, the complexity requirements pretty much dictate that ordered associative containers are implemented as balanced binary trees. Unordered containers store keys in a hash table, so the order is unimportant to your code and is subject to change as you add items to the container.
Another way to divide the associative containers is into sets and maps. Sets are like mathematical sets: they have members and can test for membership. Maps are like sets that store key/value pairs. Sets and maps can require unique keys or permit duplicate keys. The set types are set (unique key, ordered), multiset (duplicate key, ordered), unordered_set, and unordered_multiset. The map types are map, multimap, unordered_map, and unordered_multimap.
Different containers have different characteristics. For example, vector permits rapid access to any item, but insertion in the middle is slow. A list, on the other hand, offers rapid insertion and erasure of any item but provides only bidirectional iterators, not random access. The unordered containers do not permit comparing entire containers.
The C++ standard defines container characteristics in terms of complexity, which is written in big-O notation. Remember from your introductory algorithms course that O(1) is constant complexity, but without any indication of what the constant might be. O(n) is linear complexity: if the container has n items, performing an O(n) operation takes time proportional to n. Operations on sorted data are often logarithmic: O(log n).
Table 53-1 summarizes all the containers and their characteristics. The Insert, Erase, and Lookup columns show the average-case complexity for these operations, where N is the number of elements in the container. Lookup for a sequence container means looking for an item at a particular index. For an associative container, it means looking for a specific item by value. “No” means the container does not support that operation at all.
Table 53-1. Summary of Containers and Their Characteristics
Every container provides a number of useful types and typedefs as members of the container. This section makes frequent use of several of them:
This is a synonym for the type that the container stores. For example, value_type for vector<double> is double and std::list<char>::value_type is char. Using a standard typedef makes it easier to write and read container code. The rest of this Exploration uses value_type extensively.
The mapped containers store key/value pairs, so value_type for map<Key, T> (and multimap, unordered_map, and unordered_multimap) is std::pair<const Key, T>. The key type is const, because you cannot change the key after adding an item to an associative container. The internal structure of the container depends on the keys, so changing the keys would violate the ordering constraints.
The associative containers declare key_type as a typedef for the first template parameter—for example, map<int, double>::key_type is int. For the set types, key_type and value_type are the same.
This is a synonym for a reference to value_type. Except in very rare cases, reference is identical to value_type&.
const_reference is a synonym for a reference to const value_type. Except in very rare cases, const_reference is identical to value_type const&.
This is the iterator type. It might be a typedef, but more likely, it is a class, the definition of which is implementation-dependent. All that matters is that this type meets the requirements of an iterator. Each container type implements a specific category of iterator, as described in Table 53-1.
const_iterator is the iterator type for const items. It might be a typedef, but more likely, it is a class, the definition of which is implementation-dependent. All that matters is that this type meets the requirements of an iterator of const items. Each container type implements a specific category of iterator, as described in Table 53-1.
size_type is a typedef for one of the built-in integer types (which one depends on the implementation). It represents an index for a sequence container or a container size.
In order to store an item in a container, the item’s type must meet some basic requirements. You must be able to copy or move the item and assign it using copy or move. For the built-in types, this is automatic. For a class type, you usually have that capability. The compiler even writes the constructors and assignment operators for you. So far, all the classes in this book meet the basic requirements; you won’t have to concern yourself with non-conforming classes until Exploration 59.
Sequence containers themselves do not have to compare items for equality; they just copy or move elements as required. When they have to make copies, they assume that copies are identical to the original.
Ordered associative containers require an ordering functor. By default, they use a standard functor called std::less<key_type>, which in turn uses the < operator. You can supply a custom functor, provided it implements strict weak ordering, which is defined by the following requirements:
- If a < b and b < c, then a < c.
- a < a is always false.
- The order does not change after an item is stored in a container.
A common error among new C++ programmers is to violate rule 2, typically by implementing <= instead of <. Violations of the strict weak ordering rule result in undefined behavior. Some libraries have a debugging mode that checks your functor to ensure that it is valid. If your library has such a mode, use it.
Unordered associative containers need a hash functor and an equality functor. The default hash functor is std::hash<key_type> (declared in <functional>). The standard library provides specializations for the built-in types and string. If you store a custom class in an unordered container, you have to provide your own hash functor. The simplest way to do that is to specialize hash. Listing 53-1 shows how to specialize hash for the rational type. You have to provide only the function call operator, which must return type std::size_t (an implementation-defined integer type).
Listing 53-1. Specializing the hash Template for the rational Type
#include <array>
#include "rational.hpp"
namespace std {
template<class T>
class hash<rational<T>>
{
public:
std::size_t operator()(rational<T> const& r)
const
{
return hasher_(r.numerator()) + hasher_(r.denominator());
}
private:
std::hash<T> hasher_;
};
} // end of std
The default equality functor is std::equal_to<T> (declared in <functional>), which uses the == operator. If two items are equal, their hash values must also be equal (but the reverse is not necessarily true).
When you insert an item in a container, the container keeps a copy of the item, or you can move an object into a container. When you erase an item, the container destroys the item. When you destroy a container, it destroys all of its elements. The next section discusses insertion and erasure at greater length.
Inserting and Erasing
I’ve presented a number of examples of inserting and erasing elements in vectors and maps. This section explores this topic in greater depth. Except for array and forward_list, the container types follow some basic patterns. The array type has a fixed size, so it provides none of the insertion or erasure functions. And forward_list has its own way of doing things, because a singly linked list cannot insert or erase items directly. All the other containers follow the specification described in this section.
Inserting in a Sequence Container
You have a choice of several member functions with which to insert an item into a sequence container. The most fundamental function is emplace, which constructs an item in place in the container. It has the following form:
iterator emplace(iterator here, args…)
Inserts a newly constructed item into the collection immediately before the position here and returns an iterator that refers to the newly added item. The args can be zero or more arguments that are passed to the value_type constructor. If here is end(), the item is constructed at the end of the container.
If you have objects that are already constructed, call insert, which has three overloaded forms:
iterator insert(iterator here, value_type item)
Inserts item by copying or moving it into the collection immediately before the position here and returns an iterator that refers to the newly added item. If here is end(), item is appended to the end of the container.
void insert(iterator here, size_type n, value_type const& item)
Inserts n copies of item immediately before the position to which here refers. If here is end(), the items are appended to the end of the container.
template<class InputIterator>void insert(iterator here, InputIterator first, InputIterator last)
Copies the values from the range (first, last) into the container, starting at the position immediately before here.
Two additional functions add items to the start (emplace_front and push_front), and two add items to the end (emplace_back and push_back) of a container. The emplace functions pass all their arguments to the constructor of the new element; the push functions copy or move their sole argument into the container. The container type provides only the functions that it can implement with constant complexity. Thus, vector provides emplace_back and push_back but not emplace_front or push_front. Both list and deque provide all four functions.
Erasing from a Sequence Container
The erase function erases, or deletes, items from a container. Sequence containers implement two forms of erase:
iterator erase(iterator pos)
Erases the item to which pos refers and returns an iterator that refers to the subsequent item. Returns end() if the last item is erased. The behavior is undefined if you try to erase end() or if pos is an iterator for a different container object.
iterator erase(iterator first, iterator last)
Erases all the items in the range [first, last) and returns an iterator that refers to the item that immediately followed the last item erased. Returns end() if the last item in the container is erased. The behavior is undefined if the iterators are in the wrong order or refer to a different container object.
The clear() function erases all elements from the container. In addition to the basic erasure functions, sequence containers also provide pop_front to erase the first element and pop_back to erase the last element of a collection. A container implements these two functions only if it can do so with constant complexity. Which sequence containers implement pop_back?
_____________________________________________________________
Which sequence containers implement pop_front?
_____________________________________________________________
As with the push functions, vector provides pop_back, and list and deque provide both pop_back and pop_front.
Inserting in an Associative Container
All the insertion functions for associative containers follow a common pattern for return types. The duplicate-key containers (multimap, multiset, unordered_multimap, unordered_multiset) return an iterator for the newly added item. The unique-key containers (map, set, unordered_map, unordered_set) return a pair<iterator, bool>: the iterator refers to the item in the container, and the bool is true if the item was added or false if the item was already present. In this section, the return type is shown as return. If the item was already present, the existing item is untouched, and the new item is ignored.
Construct a new item in an associative container by calling one of the two emplace functions:
return emplace(args…)
Constructs a new element at the correct position in the container, passing args to the value_type constructor.
iterator emplace_hint(iterator hint, args…)
Constructs a new element as close to hint as possible, passing args to the value_type constructor.
For an ordered container, if the item’s position is immediately after hint, the item is added with constant complexity. Otherwise, the complexity is logarithmic. If you have to store many items in an ordered container, and the items are already in order, you can save some time by using the position of the most recently inserted item as the hint.
As with sequence containers, you can also call the insert function to insert into an associative container. One key difference from the sequence containers is that you don’t have to provide a position (one form does let you provide a position as a hint).
returninsert(value_type item)
Moves or copies item into the container.
iterator insert(iterator hint, value_type item)
Moves or copies item into the container as close to hint as possible, as described earlier with emplace_hint.template<class InputIterator>void insert(InputIterator first, InputIterator last)
Copies the values from the range [first, last) into the container. For the ordered containers, you get optimal performance if the range [first, last) is already sorted.
Write a program that reads a list of strings from the standard input into a set of strings. Use the emplace_hint function. Save the return value to pass as the hint when inserting the next item. Find a large list of strings to use as input. Make two copies of the list, one in sorted order and one in random order. (See this book’s web site if you need help locating or preparing the input files.) Compare the performance of your program reading the two input files.
Write another version of the same program, this time using the simple, one-argument emplace function. Again, run the program with both input files. Compare the performance of all four variations: hinted and unhinted insert, sorted and unsorted input.
Listing 53-2 shows a simple form of the program that uses emplace_hint.
Listing 53-2. Using a Hint Position When Inserting into a Set
#include <iostream>
#include <set>
#include <string>
int main()
{
std::set<std::string> words{};
std::set<std::string>::iterator hint{words.begin()};
std::string word{};
while(std::cin >> word)
hint = words.emplace_hint(hint, std::move(word));
}
When I run the program with a file of more than 200,000 words, the hinted program with sorted input executes in about 1.6 seconds. The unhinted form takes 2.2 seconds. With randomly ordered inputs, both programs run in about 2.3 seconds. As you can see, the hint can make a difference when the input is already sorted. The details depend on the library implementation; your mileage may vary.
Erasing from an Associative Container
The erase function erases, or deletes, items from a container. Associative containers implement two forms of erase:
void erase(iterator pos)iterator erase(iterator pos)
Erases the item to which pos refers; complexity is constant, possibly amortized over many calls. The ordered containers do not return a value; unordered containers return an iterator that refers to the successor value (or end()). The behavior is undefined if you try to erase end() or if pos is an iterator for a different container object.
void erase(iterator first, iterator last)iterator erase(iterator first, iterator last)
Erases all the items in the range [first, last). Ordered containers do not return a value; unordered containers return an iterator that refers to the item that follows the last item erased. Returns end( ) if the last item in the container is erased. The behavior is undefined if the iterators are in the wrong order or refer to a different container object.
As with sequence containers, clear( ) erases all elements of the container.
The containers do their best to keep order if an exception is thrown. Exceptions have two potential sources: the container itself and the items in the containers. Most member functions do not throw exceptions for invalid arguments, so the most common source of exceptions from the container itself is std::bad_alloc, if the container runs out of memory and cannot insert a new item.
If you try to insert a single item into a container, and the operation fails (perhaps because the item’s copy constructor throws an exception, or the container ran out of memory), the container is unchanged.
If you try to insert multiple items, and one of those items throws an exception while it is being inserted into a container (e.g., the item’s copy constructor throws an exception), most containers do not roll back the change. Only the list and forward_list types roll back to their original state. The other containers leave the container in a valid state, and the items that have been inserted successfully remain in the container.
When erasing one or many items, the containers do not throw exceptions themselves, but they may have to move (or in the case of ordered containers, compare) items; if an item’s move constructor throws an exception (a highly unlikely event), the erasure may be incomplete. No matter what, however, the container remains in a valid state.
In order for these guarantees to remain valid, destructors must not throw exceptions.
Tip Never throw an exception from a destructor.
When using containers, one important point that I have not yet covered is the validity of iterators and references. The issue is that when you insert or erase items in a container, some or all iterators for that container can become invalid, and references to items in the container can become invalid. The details of which iterators and references become invalid and under what circumstances depend on the container.
Iterators and references becoming invalid reflect the internal structure of the container. For example, vector stores its elements in a single, contiguous chunk of memory. Therefore, inserting or erasing any elements shifts all the elements at higher indices, which invalidates all iterators and references to those elements at higher indices. As a vector grows, it may have to allocate a new internal array, which invalidates all extant iterators and references for that vector. You never know when that can occur, so it is safest never to hold onto a vector’s iterators or references while adding items to the vector. (But look up the reserve member function in a library reference, if you must keep those iterators and references lying around.)
A list, on the other hand, implements a doubly linked list. Inserting or erasing an element is simply a matter of inserting or deleting a node, which has no effect on iterators and references to other nodes. For all containers, if you erase a node that an iterator refers to, that iterator necessarily becomes invalid, just as a reference to the erased element must become invalid.
In practical terms, you must take care when inserting and erasing elements. These functions often return iterators that you can use to help maintain your program’s logic. Listing 53-3 shows a function template, erase_less, which marches through a container and calls erase for any element that is less than the value that precedes it. It is a function template, and it works with any class that meets the requirements of a sequence container.
Listing 53-3. Erasing Elements from a Sequence Container
template<class Container>
void erase_less(Container& cont)
{
typename Container::iterator prev{cont.end()};
typename Container::iterator iter{cont.begin()};
while (iter != cont.end())
{
if (prev != cont.end() and not (*prev < *iter))
iter = cont.erase(iter);
else
{
prev = iter;
++iter;
}
}
}
Notice how erase_less moves the iterator, iter, through the container. The prev iterator refers to the previous item (or container.end(), when the loop first begins and there is no previous item). As long as *prev is less than *iter, the loop advances by setting prev to iter and incrementing iter. If the container is in ascending order, nothing happens to it. If an item is out of place, however, *prev < *iter is false, and the item at position iter is erased. The value that erase returns is an iterator that refers to the item that follows iter prior to its erasure. That’s exactly where we want iter to point, so we just set iter to the return value and let the loop continue.
The typename keyword tells the compiler that iterator is the name of a type. Because Container is a template, the compiler does not know what the iterator member is (object? function? typedef?), until the template is instantiated. But first it has to parse the template definition, and to do that, it must know what kind of name iterator is. The rule is that the compiler assumes the name is an expression, unless you tell it that the name is a type, by using the typename keyword.
Write a test program to see that erase_less works with a list and with a vector. Make sure it works with ascending data, descending data, and mixed data. Listing 53-4 shows my simple test program.
Listing 53-4. Testing the erase_less Function Template
#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <list>
#include <sstream>
#include <vector>
#include "erase_less.hpp" //Listing 53-3
/// Extract items from a string and store them in a container.
template<class Container>
void read(std::string const& str, Container& cont)
{
std::istringstream in{str};
cont.insert(cont.begin(),
std::istream_iterator<typename Container::value_type>(in),
std::istream_iterator<typename Container::value_type>());
}
/// Print items from a container to the standard output.
template<class Container>
void print(std::string const& label, Container const& cont)
{
std::cout << label;
std::copy(cont.begin(), cont.end(),
std::ostream_iterator<typename Container::value_type>(std::cout, " "));
std::cout << ' ';
}
/// Test erase_less by extracting integers from a string into a container
/// and calling erase_less. Print the container before and after.
/// Double-check that the same results obtain with a list and a vector.
void test(std::string const& str)
{
std::list<int> list{};
read(str, list);
print("before: ", list);
erase_less(list);
print("after: ", list);
std::vector<int> vector{};
read(str, vector);
erase_less(vector);
assert(list.size() == vector.size());
assert(std::equal(list.begin(), list.end(), vector.begin()));
}
int main()
{
test("2 3 7 11 13 17 23 29 31 37");
test("37 31 29 23 17 13 11 7 3 2");
test("");
test("42");
test("10 30 20 40 0 50");
}
Again, notice the use of the typename keyword to inform the compiler that what follows is the name of a type. Use typename only in a template and only for names that the compiler cannot determine on its own, such as members of a template parameter or members of a template that uses a template parameter as an argument.
Sequence Containers
In this book, the most common use of a container has been to add items to the end of vector. A program might then use standard algorithms to change the order, such as sorting into ascending order, shuffling into random order, etc. In addition to vector, the other sequence containers are array, deque, and list.
The primary distinguishing feature of the sequence containers is their complexity characteristics. If you often have to insert and erase from the middle of the sequence, you probably want list. If you have to insert and erase only off one end, use vector. If the container’s size is a fixed, compile-time constant, use array. If the elements of the sequence must be stored contiguously (in a single block of memory), use array or vector.
The following sections include some more details about each container type. Each section presents the same program for comparison. The program constructs a deck of playing cards then randomly selects a card for itself and a card for you. The card with the highest value wins. The program plays ten times then exits. The program plays without replacement—that is, it does not return used cards to the deck after each game. In order to pick a random card, the programs use the randomint class, from Listing 43-5. Save the class definition in a file named randomint.hpp or download the file from the book’s web site. Listing 53-5 shows the card class, which the sample programs use. For the full class definition, download card.cpp from the book’s web site.
Listing 53-5. The card Class, to Represent a Playing Card
#ifndef CARD_HPP_
#define CARD_HPP_
#include <iosfwd>
/// Represent a standard western playing card.
class card
{
public:
typedef char suit;
static suit const spades {4};
static suit const hearts {3};
static suit const clubs {2};
static suit const diamonds {1};
typedef char rank;
static rank const ace {14};
static rank const king {13};
static rank const queen {12};
static rank const jack {11};
card() : rank_{0}, suit_{0} {}
card(rank r, suit s) : rank_{r}, suit_{s} {}
void assign(rank r, suit s);
suit get_suit() const { return suit_; }
rank get_rank() const { return rank_; }
private:
rank rank_;
suit suit_;
};
bool operator==(card a, card b);
bool operator!=(card a, card b);
std::ostream& operator<<(std::ostream& out, card c);
std::istream& operator>>(std::istream& in, card& c);
/// In some games, Aces are high. In other Aces are low. Use different
/// comparison functors depending on the game.
bool acehigh_compare(card a, card b);
bool acelow_compare(card a, card b);
/// Generate successive playing cards, in a well-defined order,
/// namely, 2-10, J, Q, K, A. Diamonds first, then Clubs, Hearts, and Spades.
/// Roll-over and start at the beginning again after generating 52 cards.
class card_generator
{
public:
card_generator();
card operator()();
private:
card card_;
};
#endif
The array type is a fixed-size container, so you cannot call insert or erase. To use array, specify a base type and a size as a compile-time constant expression, as shown in the following:
std::array<double, 5> five_elements;
If you initialize an array with fewer values than the array size, remaining values are initialized to zero. If you omit the initializer altogether, the compiler calls the default initializer if the value type is a class type; otherwise it leaves the array elements uninitialized. Because an array cannot change size, you can’t simply erase the cards after playing. In order to keep the code simple, the program returns cards to the deck after each game. Listing 53-6 shows the high-card program with replacement.
Listing 53-6. Playing High-Card with array
#include <array>
#include <iostream>
#include "card.hpp"
#include "randomint.hpp" // Listing 43-5
int main()
{
std::array<card, 52> deck;
std::generate(deck.begin(), deck.end(), card_generator{});
randomint picker{0, deck.size() - 1};
for (int i{0}; i != 10; ++i)
{
card const& computer_card{deck.at(picker())};
std::cout << "I picked " << computer_card << ' ';
card const& user_card{deck.at(picker())};
std::cout << "You picked " << user_card << ' ';
if (acehigh_compare(computer_card, user_card))
std::cout << "You win. ";
else
std::cout << "I win. ";
}
}
A deque (pronounced “deck”) represents a double-ended queue. Insertion and erasure from the beginning or the end is fast, but the complexity is linear, if you have to insert or erase anywhere else. Most of the time, you can use deque the same way you would use avector, so apply your experience with vector to write the high-card program. Play without replacement: that is, after each game, discard the two cards by erasing them from the container. Listing 53-7 shows how I wrote the high-card program using a deque.
Listing 53-7. Playing High-Card with a deque
#include <deque>
#include <iostream>
#include "card.hpp"
#include "randomint.hpp"
int main()
{
std::deque<card> deck(52);
std::generate(deck.begin(), deck.end(), card_generator{});
for (int i{0}; i != 10; ++i)
{
std::deque<card>::iterator pick{deck.begin() + randomint{0, deck.size()-1}()};
card computer_card{*pick};
deck.erase(pick);
std::cout << "I picked " << computer_card << ' ';
pick = deck.begin() + randomint{0, deck.size() - 1}();
card user_card{*pick};
deck.erase(pick);
std::cout << "You picked " << user_card << ' ';
if (acehigh_compare(computer_card, user_card))
std::cout << "You win. ";
else
std::cout << "I win. ";
}
}
A list represents a doubly linked list. Insertion and erasure is fast at any point in the list, but random access is not supported. Thus, the high-card program uses iterators and the advance function (Exploration 44). Write the high-card program to use list. Compare your solution with that of mine in Listing 53-8.
Listing 53-8. Playing High-Card with a list
#include <iostream>
#include <list>
#include "card.hpp"
#include "randomint.hpp"
int main()
{
std::list<card> deck(52);
std::generate(deck.begin(), deck.end(), card_generator{});
for (int i{0}; i != 10; ++i)
{
std::list<card>::iterator pick{deck.begin()};
std::advance(pick, randomint{0, deck.size() - 1}());
card computer_card{*pick};
deck.erase(pick);
std::cout << "I picked " << computer_card << ' ';
pick = std::next(deck.begin(), randomint{0, deck.size() - 1}());
card user_card{*pick};
deck.erase(pick);
std::cout << "You picked " << user_card << ' ';
if (acehigh_compare(computer_card, user_card))
std::cout << "You win. ";
else
std::cout << "I win. ";
}
}
The deque type supports random access iterators, so it could add an integer to begin( ) to pick a card. But list uses bidirectional iterators, so it must call advance( ) or next( ); Listing 53-8 demonstrates both. Note that you can call advance() or next() for deques, too, and the implementation would still use addition.
A vector is an array that can change size at runtime. Appending to the end or erasing from the end is fast, but complexity is linear when inserting or erasing anywhere else in the vector. Compare deque and list versions of the high-card program. Pick the one you prefer and modify it to work with vector. My version of the program is displayed in Listing 53-9.
Listing 53-9. Playing High-Card with vector
#include <iostream>
#include <vector>
#include "card.hpp"
#include "randomint.hpp"
int main()
{
std::vector<card> deck(52);
std::generate(deck.begin(), deck.end(), card_generator{});
for (int i{0}; i != 10; ++i)
{
std::vector<card>::iterator pick{deck.begin() + randomint{0, deck.size()-1}()};
card computer_card{*pick};
deck.erase(pick);
std::cout << "I picked " << computer_card << ' ';
pick = deck.begin() + randomint{0, deck.size() - 1}();
card user_card{*pick};
deck.erase(pick);
std::cout << "You picked " << user_card << ' ';
if (acehigh_compare(computer_card, user_card))
std::cout << "You win. ";
else
std::cout << "I win. ";
}
}
Notice how you can change the program to use vector instead of deque, just by changing the type names. Their usage is quite similar. One key difference is that deque offers fast (constant complexity) insertion at the beginning of the container, something that vector lacks. The other key difference is that vector stores all of its elements in a single chunk of memory, which can be important when interfacing with external libraries. Neither of these factors matters here.
Associative Containers
The associative containers offer rapid insertion, deletion, and lookup, by controlling the order of elements in the container. The ordered associative containers store elements in a tree, ordered by a comparison functor (default is std::less, which uses <), so insertion, erasure, and lookup occur with logarithmic complexity. The unordered containers use hash tables (according to a caller-supplied hash functor and equality functor) for access with constant complexity in the average case, but with a linear worst-case complexity. Consult any textbook on data structures and algorithms for more information regarding trees and hash tables.
Sets store keys, and maps store key/value pairs. Multisets and multimaps allow duplicate keys. All equivalent keys are stored at adjacent locations in the container. Plain sets and maps require unique keys. If you try to insert a key that is already in the container, the new key is not inserted. Remember that equivalence in an ordered container is determined solely by calling the comparison functor: compare(a, b) is false, and compare(b, a) is false means a and b are equivalent. Unordered containers call their equality functor to determine whether a key is a duplicate. The default is std::equal_to (declared in <functional>), which uses the == operator.
Because associative arrays store keys in an order that depends on the keys’ contents, you cannot modify the contents of a key that is stored in an associative container. This means you cannot use an associative container’s iterators as output iterators. Thus, if you want to implement the high-card program using an associative container, you can use the inserter function to create an output iterator that fills the container. Listing 53-10 shows how to use set to implement the high-card program.
Listing 53-10. Playing High-Card with set
#include <iostream>
#include <iterator>
#include <set>
#include <utility>
#include "card.hpp"
#include "randomint.hpp"
int main()
{
typedef std::set<card, std::function<bool(card, card)>> cardset;
cardset deck(acehigh_compare);
std::generate_n(std::inserter(deck, deck.begin()), 52, card_generator{});
for (int i{0}; i != 10; ++i)
{
cardset::iterator pick{deck.begin()};
std::advance(pick, randomint{0, deck.size() - 1}());
card computer_card{*pick};
deck.erase(pick);
std::cout << "I picked " << computer_card << ' ';
pick = deck.begin();
std::advance(pick, randomint{0, deck.size() - 1}());
card user_card{*pick};
deck.erase(pick);
std::cout << "You picked " << user_card << ' ';
if (acehigh_compare(computer_card, user_card))
std::cout << "You win. ";
else
std::cout << "I win. ";
}
}
When using associative containers, you may experience some difficulty when you use a custom compare functor (for ordered containers) or custom equality and hash functors (for unordered containers). You must specify the functor type as a template argument. When you construct a container object, pass a functor as an argument to the constructor. The functor must be an instance of the type that you specified in the template specialization.
For example, Listing 53-10 uses the acehigh_compare function, which it passes to the constructor for deck. Because acehigh_compare is a function, you must specify a function type as the template argument. The easiest way to declare a function type is with the std::function template. The template argument looks somewhat like a nameless function header: supply the return type and parameter types:
std::function<bool(card, card)>
Another approach is to specialize the std::less class template for type card. The explicit specialization would implement the function call operator to call acehigh_compare. Taking advantage of the specialization, you could use the default template argument and constructor arguments. The specialization should declare some standard member typedefs. Follow the pattern of functors in the <functional> header. The functor should provide a function call operator that uses the argument and return types and implements the strict weak ordering function for your container. Listing 53-11 demonstrates yet another version of the high-card program, this time using a specialization of less. The only real difference is how the deck is initialized.
Listing 53-11. Playing High-Card Using an Explicit Specialization of std::less
#include <functional>
#include <iostream>
#include <iterator>
#include <set>
#include "card.hpp"
#include "randomint.hpp"
namespace std
{
template<>
class less<card>
{
public:
typedef card first_argument_type;
typedef card second_argument_type;
typedef bool result_type;
bool operator()(card a, card b) const { return acehigh_compare(a, b); }
};
}
int main()
{
typedef std::set<card> cardset;
cardset deck{};
std::generate_n(std::inserter(deck, deck.begin()), 52, card_generator{});
for (int i{0}; i != 10; ++i)
{
cardset::iterator pick{deck.begin()};
std::advance(pick, randomint{0, deck.size() - 1}());
card computer_card{*pick};
deck.erase(pick);
std::cout << "I picked " << computer_card << ' ';
pick = deck.begin();
std::advance(pick, randomint{0, deck.size() - 1}());
card user_card{*pick};
deck.erase(pick);
std::cout << "You picked " << user_card << ' ';
if (acehigh_compare(computer_card, user_card))
std::cout << "You win. ";
else
std::cout << "I win. ";
}
}
To use an unordered container, you must write an explicit specialization of std::hash<card>. Listing 53-1 should be able to help. The card.hpp header already declares operator== for card, so you should be ready to rewrite the high-card program one last time, this time for unordered_set. Compare your solution with Listing 53-12. All these programs are remarkably similar, in spite of the different container types, a feat made possible through the judicious use of iterators, algorithms, and functors.
Listing 53-12. Playing High-Card with unordered_set
#include <functional>
#include <iostream>
#include <iterator>
#include <unordered_set>
#include "card.hpp"
#include "randomint.hpp"
namespace std
{
template<>
class hash<card>
{
public:
std::size_t operator()(card a)
const
{
return hash<card::suit>{}(a.get_suit()) * hash<card::rank>{}(a.get_rank());
}
};
} // namespace std
int main()
{
typedef std::unordered_set<card> cardset;
cardset deck{};
std::generate_n(std::inserter(deck, deck.begin()), 52, card_generator{});
for (int i(0); i != 10; ++i)
{
cardset::iterator pick{deck.begin()};
std::advance(pick, randomint{0, deck.size() - 1}());
card computer_card{*pick};
deck.erase(pick);
std::cout << "I picked " << computer_card << ' ';
pick = deck.begin();
std::advance(pick, randomint{0, deck.size() - 1}());
card user_card{*pick};
deck.erase(pick);
std::cout << "You picked " << user_card << ' ';
if (acehigh_compare(computer_card, user_card))
std::cout << "You win. ";
else
std::cout << "I win. ";
}
}
In the next Exploration, you will embark on a completely different journey, one involving world travels to exotic locations, where natives speak exotic languages and use exotic character sets. The journey also touches on new and interesting uses for templates.