Programming: Principles and Practice Using C++ (2014)

21.5.3 Inner product

Take two vectors, multiply each pair of elements with the same subscript, and add all of those products. That’s called the inner product of the two vectors and is a most useful operation in many areas (e.g., physics and linear algebra; see §24.6). If you prefer code to words, here is the STL version:

template<typename In, typename In2, typename T>
// requires Input_iterator<In> && Input_iterator<In2>
// && Number<T> (§19.3.3)
T inner_product(In first, In last, In2 first2, T init)
// note: this is the way we multiply two vectors (yielding a scalar)
{
while(first!=last) {
init = init + (*first) * (*first2); // multiply pairs of elements
++first;
++first2;
}
return init;
}

This generalizes the notion of inner product to any kind of sequence of any type of element. As an example, consider a stock market index. The way that works is to take a set of companies and assign each a “weight.” For example, in the Dow Jones Industrial index Alcoa had a weight of 2.4808 when last we looked. To get the current value of the index, we multiply each company’s share price with its weight and add all the resulting weighted prices together. Obviously, that’s the inner product of the prices and the weights. For example:

// calculate the Dow Jones Industrial index:
vector<double> dow_price = { // share price for each company
81.86, 34.69, 54.45,
// . . .
};

list<double> dow_weight = { // weight in index for each company
5.8549, 2.4808, 3.8940,
// . . .
};

double dji_index = inner_product( // multiply (weight,value) pairs and add
dow_price.begin(), dow_price.end(),
dow_weight.begin(),
0.0);

cout << "DJI value " << dji_index << '\n';

Note that inner_product() takes two sequences. However, it takes only three arguments: only the beginning of the second sequence is mentioned. The second sequence is supposed to have at least as many elements as the first. If not, we have a run-time error. As far as inner_product() is concerned, it is OK for the second sequence to have more elements than the first; those “surplus elements” will simply not be used.

The two sequences need not be of the same type, nor do they need to have the same element types. To illustrate this point, we used a vector to hold the prices and a list to hold the weights.

21.5.4 Generalizing inner_product()

The inner_product() can be generalized just as accumulate() was. For inner_product() we need two extra arguments, though: one to combine the accumulator with the new value, exactly as for accumulate(), and one for combining the element value pairs:

template<typename In, typename In2, typename T, typename BinOp,
typename BinOp2>
// requires Input_iterator<In> && Input_iterator<In2> && Number<T>
// && Binary_operation<BinOp,T, Value_type<In>()
// && Binary_operation<BinOp2,T, Value_type<In2>()
T inner_product(In first, In last, In2 first2, T init, BinOp op, BinOp2 op2)
{
while(first!=last) {
init = op(init, op2(*first, *first2));
++first;
++first2;
}
return init;
}

In §21.6.3, we return to the Dow Jones example and use this generalized inner_product() as part of a more elegant solution.

21.6 Associative containers

After vector, the most useful standard library container is probably the map. A map is an ordered sequence of (key,value) pairs in which you can look up a value based on a key; for example, my_phone_book["Nicholas"] could be the phone number of Nicholas. The only potential competitor to map in a popularity contest is unordered_map (see §21.6.4), and that’s a map optimized for keys that are strings. Data structures similar to map and unordered_map are known under many names, such as associative arrays, hash tables, and red-black trees. Popular and useful concepts always seem to have many names. In the standard library, we collectively call all such data structures associative containers.

The standard library provides eight associative containers:

These containers are found in <map>, <set>, <unordered_map>, and <unordered_set>.

21.6.1 map

Consider a conceptually simple task: make a list of the number of occurrences of words in a text. The obvious way of doing this is to keep a list of words we have seen together with the number of times we have seen each. When we read a new word, we see if we have already seen it; if we have, we increase its count by one; if not, we insert it in our list and give it the value 1. We could do that using a list or a vector, but then we would have to do a search for each word we read. That could be slow. A map stores its keys in a way that makes it easy to see if a key is present, thus making the searching part of our task trivial:

int main()
{
map<string,int> words; // keep (word,frequency) pairs

for (string s; cin>>s; )
++words[s]; // note: words is subscripted by a string

for (const auto& p : words)
cout << p.first << ": " << p.second << '\n';
}

The really interesting part of the program is ++words[s]. As we can see from the first line of main(), words is a map of (string,int) pairs; that is, words maps strings to ints. In other words, given a string, words can give us access to its corresponding int. So, when we subscript words with astring (holding a word read from our input), words[s] is a reference to the int corresponding to s. Let’s look at a concrete example:

words["sultan"]

If we have not seen the string "sultan" before, "sultan" will be entered into words with the default value for an int, which is 0. Now, words has an entry ("sultan",0). It follows that if we haven’t seen "sultan" before, ++words["sultan"] will associate the value 1 with the string "sultan". In detail: the map will discover that "sultan" wasn’t found, insert a ("sultan",0) pair, and then ++ will increment that value, yielding 1.

Now look again at the program: ++words[s] takes every “word” we get from input and increases its value by one. The first time a new word is seen, it gets the value 1. Now the meaning of the loop is clear:

for (string s; cin>>s; )
++words[s]; // note: words is subscripted by a string

This reads every (whitespace-separated) word on input and computes the number of occurrences for each. Now all we have to do is to produce the output. We can iterate through a map, just like any other STL container. The elements of a map<string,int> are of type pair<string,int>. The first member of a pair is called first and the second member second, so the output loop becomes

for (const auto& p : words)
cout << p.first << ": " << p.second << '\n';

As a test, we can feed the opening statements of the first edition of The C++ Programming Language to our program:

C++ is a general purpose programming language designed to make programming more enjoyable for the serious programmer. Except for minor details, C++ is a superset of the C programming language. In addition to the facilities provided by C, C++ provides flexible and efficient facilities for defining new types.

We get the output

C: 1
C++: 3
C,: 1
Except: 1
In: 1
a: 2
addition: 1
and: 1
by: 1
defining: 1
designed: 1
details,: 1
efficient: 1
enjoyable: 1
facilities: 2
flexible: 1
for: 3
general: 1
is: 2
language: 1
language.: 1
make: 1
minor: 1
more: 1
new: 1
of: 1
programmer.: 1
programming: 3
provided: 1
provides: 1
purpose: 1
serious: 1
superset: 1
the: 3
to: 2
types.: 1

If we don’t like to distinguish between upper- and lowercase letters or would like to eliminate punctuation, we can do so: see exercise 13.

21.6.2 map overview

So what is a map? There is a variety of ways of implementing maps, but the STL map implementations tend to be balanced binary search trees; more specifically, they are red-black trees. We will not go into the details, but now you know the technical terms, so you can look them up in the literature or on the web, should you want to know more.

A tree is built up from nodes (in a way similar to a list being built from links; see §20.4). A Node holds a key, its corresponding value, and pointers to two descendant Nodes.

Here is the way a map<Fruit,int> might look in memory assuming we had inserted (Kiwi,100), (Quince,0), (Plum,8), (Apple,7), (Grape,2345), and (Orange,99) into it:

Given that the name of the Node member that holds the key value is first, the basic rule of a binary search tree is

left->first<first && first<right->first

That is, for every node,

• Its left sub-node has a key that is less than the node’s key, and

• The node’s key is less than the key of its right sub-node

You can verify that this holds for each node in the tree. That allows us to search “down the tree from its root.” Curiously enough, in computer science literature trees grow downward from their roots. In the example, the root node is (Orange, 99). We just compare our way down the tree until we find what we are looking for or the place where it should have been. A tree is called balanced when (as in the example above) each sub-tree has approximately as many nodes as every other sub-tree that’s equally far from the root. Being balanced minimizes the average number of nodes we have to visit to reach a node.

A Node may also hold some more data which the map will use to keep its tree of nodes balanced. A tree is balanced when each node has about as many descendants to its left as to its right. If a tree with N nodes is balanced, we have to at most look at log₂(N) nodes to find a node. That’s much better than the average of N/2 nodes we would have to examine if we had the keys in a list and searched from the beginning (the worst case for such a linear search is N). (See also §21.6.4.) For example, have a look at an unbalanced tree:

This tree still meets the criteria that the key of every node is greater than that of its left sub-node and less than that of its right sub-node:

left->first<first && first<right->first

However, this version of the tree is unbalanced, so we now have three “hops” to reach Apple and Kiwi, rather than the two we had in the balanced tree. For trees of many nodes the difference can be very significant, so the trees used to implement maps are balanced.

We don’t have to understand about trees to use map. It is just reasonable to assume that professionals understand at least the fundamentals of their tools. What we do have to understand is the interface to map provided by the standard library. Here is a slightly simplified version:

template<typename Key, typename Value, typename Cmp = less<Key>>
// requires Binary_operation<Cmp,Value>() (§19.3.3)
class map {
// . . .
using value_type = pair<Key,Value>; // a map deals in (Key,Value) pairs

using iterator = sometype1; // similar to a pointer to a tree node
using const_iterator = sometype2;

iterator begin(); // points to first element
iterator end(); // points one beyond the last element

Value& operator[](const Key& k); // subscript with k

iterator find(const Key& k); // is there an entry for k?

void erase(iterator p); // remove element pointed to by p
pair<iterator, bool> insert(const value_type&); // insert a (key,value) pair
// . . .
};

You can find the real version in <map>. You can imagine the iterator to be similar to a Node*, but you cannot rely on your implementation using that specific type to implement iterator.

The similarity to the interfaces for vector and list (§20.5 and §B.4) is obvious. The main difference is that when you iterate, the elements are pairs — of type pair<Key,Value>. That type is another useful STL type:

template<typename T1, typename T2>
struct pair { // simplified version of std::pair
using first_type = T1;
using second_type = T2;

T1 first;
T2 second;

// . . .
};

template<typename T1, typename T2>
pair<T1,T2> make_pair(T1 x, T2 y)
{
return {x,y};
}

We copied the complete definition of pair and its useful helper function make_pair() from the standard.

Note that when you iterate over a map, the elements will come in the order defined by the key. For example, if we iterated over the fruits in the example, we would get

(Apple,7) (Grape,2345) (Kiwi,100) (Orange,99) (Plum,8) (Quince,0)

The order in which we inserted those fruits doesn’t matter.

The insert() operation has an odd return value, which we most often ignore in simple programs. It is a pair of an iterator to the (key,value) element and a bool which is true if the (key,value) pair was inserted by this call of insert(). If the key was already in the map, the insertion fails and thebool is false.

Note that you can define the meaning of the order used by a map by supplying a third argument (Cmp in the map declaration). For example:

map<string, double, No_case> m;

No_case defines case-insensitive compare; see §21.8. By default the order is defined by less<Key>, meaning “less than.”

21.6.3 Another map example

To better appreciate the utility of map, let’s return to the Dow Jones example from §21.5.3. The code there was correct if and only if all weights appear in the same position in their vector as their corresponding name. That’s implicit and could easily be the source of an obscure bug. There are many ways of attacking that problem, but one attractive one is to keep each weight together with its company’s ticker symbol, e.g., (“AA”,2.4808). A “ticker symbol” is an abbreviation of a company name used where a terse representation is needed. Similarly we can keep the company’s ticker symbol together with its share price, e.g., (“AA”,34.69). Finally, for those of us who don’t regularly deal with the U.S. stock market, we can keep the company’s ticker symbol together with the company name, e.g., (“AA”,“Alcoa Inc.”); that is, we could keep three maps of corresponding values.

First we make the (symbol,price) map:

map<string,double> dow_price = { // Dow Jones Industrial index (symbol,price);
// for up-to-date quotes see
// www.djindexes.com
{"MMM",81.86},
{"AA",34.69},
{"MO",54.45},
// . . .
};

The (symbol,weight) map:

map<string,double> dow_weight = { // Dow (symbol,weight)
{"MMM", 5.8549},
{"AA",2.4808},
{"MO",3.8940},
// . . .
};

The (symbol,name) map:

map<string,string> dow_name = { // Dow (symbol,name)
{"MMM","3M Co."},
{"AA"] = "Alcoa Inc."},
{"MO"] = "Altria Group Inc."},
// . . .
};

Given those maps, we can conveniently extract all kinds of information. For example:

double alcoa_price = dow_price ["AAA"]; // read values from a map
double boeing_price = dow_price ["BA"];

if (dow_price.find("INTC") != dow_price.end()) // find an entry in a map
cout << "Intel is in the Dow\n";

Iterating through a map is easy. We just have to remember that the key is called first and the value is called second:

// write price for each company in the Dow index:
for (const auto& p : dow_price) {
const string& symbol = p.first; // the “ticker” symbol
cout << symbol << '\t'
<< p.second << '\t'
<< dow_name[symbol] << '\n';
}

We can even do some computation directly using maps. In particular, we can calculate the index, just as we did in §21.5.3. We have to extract share values and weights from their respective maps and multiply them. We can easily write a function for doing that for any twomap<string,double>s:

double weighted_value(
const pair<string,double>& a,
const pair<string,double>& b
) // extract values and multiply
{
return a.second * b.second;
}

Now we just plug that function into the generalized version of inner_product() and we have the value of our index:

double dji_index =
inner_product(dow_price.begin(), dow_price.end(), // all companies
dow_weight.begin(), // their weights
0.0, // initial value
plus<double>(), // add (as usual)
weighted_value); // extract values and weights
// and multiply

Why might someone keep such data in maps rather than vectors? We used a map to make the association between the different values explicit. That’s one common reason. Another is that a map keeps its elements in the order defined by its key. When we iterated through dow above, we output the symbols in alphabetical order; had we used a vector we would have had to sort. The most common reason to use a map is simply that we want to look up values based on the key. For large sequences, finding something using find() is far slower than looking it up in a sorted structure, such as a map.