Chapter.11

Answers for chapter 11

Exercise 11.1: Describe the differences between a map and a vector.

There are three main difference in:

• how elements are structured:
  • Maps are associated containers. They contain elements that have key-value pairs types.
  • Vectors are sequential containers. They hold elements of normal type.
• how elements are stored:
  • Map elements are organized through either an order or a hash table.
  • Vector elements are stored in memory as a sequence.
• advantange:
  • The map performs much better when looking up elements, as it finds contents using a key.
  • The vector has better performance in random access, however, since its elements are associated with the index, looking up an element in one sometimes requires traversal.

Give an example of when each of list, vector, deque, map, and set might be most useful.

* list: A place where elements need to be inserted and removed in the middle of it., for example, a file in file system.

• vector: Places where you need frequent to do random_access.
• deque: FIFO
• map: dictionary
• set: keyword black list.

Exercise 11.3: Write your own version of the word-counting program.

CODE: Q.1.

Exercise 11.4: Extend your program to ignore case and punctuation. Forexample, “example.” “example,” and “Example” should all increment the samecounter.

CODE: Q.1.

Exercise 11.5: Explain the difference between a map and a set. When might you use one or the other?

The map element type is key-value pair and a set element contains only a key. Use map if there is any value associated with key.

Exercise 11.6: Explain the difference between a set and a list. When might you use one or the other?

• A set is an associated container, holding ordered and unique elements.
• A list is a sequential container. Its element is neither unique nor ordered.

A set is useful when you want better performance when looking up elements. However, Editing the contents of a set may not be a good idea since it might break the order of the elements. If this is your intent, use a list.

Define a map for which the key is the family’s last name and the value is a vector of the children’s names. Write code to add new families and to add new children to an existing family.

CODE: Q.1.

Exercise 11.8: Write a program that stores the excluded words in a vector instead of in a set. What are the advantages to using a set?

CODE: Q.1.

Exercise 11.9: Define a map that associates words with a list of line numbers on which the word might occur.

map<string, list<int>> words_line;

Exercise 11.10: Could we define a map from vector<int>::iterator to int? What about from list<int>::iterator to int? In each case, if not, why not?

The vector<int>::iterator can be used as the key because it has the < operation defined, however, a list<int>::iterator cannot be used as the key since it only has the equality operation defined.

Exercise 11.11: Redefine bookstore without using decltype.

using comp_T = bool (*)(const Sales_data &, const Sales_data &); 
std::multiset<Sales_data, comp_T> bookstore(compareIsbn);

Exercise 11.12: Write a program to read a sequence of strings and ints, storing each into a pair. Store the pairs in a vector.

CODE: Q.1.

Exercise 11.13: There are at least three ways to create the pairs in the program for the previous exercise. Write three versions of that program, creating the pairs in each way. Explain which form you think is easiest to write and understand, and why.

In my opinion, the list return is the best choice. One of the primary benefits of using a list return is that it checks whether the return type matches the type of the pair, since narrowing conversion is not allowed during list initialization.

CODE: Q.1.

Exercise 11.14: Extend the map of children to their family name that you wrote for the exercises in § 11.2.1 (p. 424) by having the vector store a pair that holds a child’s name and birthday.

CODE: Q.1.

Exercise 11.15: What are the mapped_type, key_type, and value_type of a map from int to vector<int>?

• mapped_type: vector<int>
• key_type: int
• value_type : vector<int>

Exercise 11.16: Using a map iterator write an expression that assigns a value to an element.

map_it->seond = val;

Exercise 11.17: Assuming c is a multiset of strings and v is a vector of strings, explain the following calls. Indicate whether each call is legal:

//legal, using the multiset as a destination
copy(v.begin(), v.end(), inserter(c, c.end()));
//illegal, push_back() is not avaliable for a multiset
copy(v.begin(), v.end(), back_inserter(c));
//legal, using the multiset as an source sequence
copy(c.begin(), c.end(), inserter(v, v.end()));
//legal, equivalent to the above
copy(c.begin(), c.end(), back_inserter(v));

Exercise 11.18: Write the type of map_it from the loop on page 430 without using auto or decltype.

std::map<std::string, size_t>::const_iterator

Exercise 11.19: Define a variable that you initialize by calling begin() on the multiset named bookstore from § 11.2.2 (p. 425). Write the variable’s type without using auto or decltype.

using comp_T = bool (*)(const Sales_data &, const Sales_data &); 
std::multiset<Sales_data, comp_T> bookstore(compareIsbn);
std::multiset<Sales_data, comp_T>::iterator mset_it = bookstore.begin();

Exercise 11.20: Rewrite the word-counting program from § 11.1 (p. 421) to use insert instead of subscripting. Which program do you think is easier to write and read? Explain your reasoning.

Compared to the iterator version, I prefer the subscript version because we can rely on the unique key features for the word counting, which is more understandable, and the code is easier to write. Not to mention that the insert operation is waived. CODE: Q.1.

Exercise 11.21: Assuming word_count is a map from string to size_t and word is a string, explain the following loop:

while (cin >> word)
	++word_count.insert({word, 0}).first->second;

1. insert function cast: the element pair {word, 0} will be inserted to the map word_count. The function returns a pair <iter, bool>. The iter points to the {word, 0}.
2. member access: the member call .first→second actually calls the value of the {word, 0};
3. increament: change the value of {word, 0}, now it is {word, 1}

As the result, the program actually does the same thing as the previous word counting program.

Exercise 11.22: Given a map<string, vector<int», write the types used as an argument and as the return value for the version of insert that inserts one element.

std::pair<std::string, std::vector<int>> //argument type
std::pair<std::map<std::string, std::vector<int>>::iterator, bool> //return type

Exercise 11.23: Rewrite the map that stored vectors of children’s names with a key that is the family last name for the exercises in § 11.2.1 (p. 424) to use a multimap.

CODE: Q.1.

Exercise 11.24: What does the following program do?

map<int, int> m;
m[0] = 1;

Exercise 11.25: Contrast the following program with the one in the previous exercise.

vector<int> v;
v[0] = 1;

What type can be used to subscript a map? What type does the subscript operator return? Give a concrete example—that is, define a map and then write the types that can be used to subscript the map and the type that would be returned from the subscript operator.

What type can be used to subscript a map?

A key_type

What type does the subscript operator return?

A mapped_type

Beacuse a key_type in map is an alias to the type of key, whereas a mapped_type in map is an alias to the type of its bound value. Therefore, for example, a map with pair type <int, string> has a key of int type and a subscription on the key returns std::string type.

Test code: source.

Result:

i NSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE

Exercise 11.27: What kinds of problems would you use count to solve? When might you use find instead?

The count can be used if the numbers of elements will be useful, for example, when determining loop times.The find may be used to find out if a key is present in the container.

Define and initialize a variable to hold the result of calling find on a map from string to vector of int.

//full type of the iterator that returned by find member
std::map<std::string, std::vector<int>>::iterator iter = msv.find(key);
//or you may use auto instead
auto iter = msv.find(key);

Exercise 11.29: What do upper_bound, lower_bound, and equal_range return when you pass them a key that is not in the container?

• upper_bound: returns the off-the-end iterator
• lower_bound: returns the off-the-end iterator
• equal_range: returns a pair of off-the-end iterator

Exercise 11.30: Explain the meaning of the operand pos.first→second used in the output expression of the final program in this section.

In the program:

• pos is an std::pair that contains two iterators.
• The first iterator of pos denotes the first element of the key, which is the first book of the author.

Therefore, the statment

pos.first->second

Exercise 11.31: Write a program that defines a multimap of authors and their works. Use find to find an element in the multimap and erase that element. Be sure your program works correctly if the element you look for is not in the map.

Note: I am not sure what the “element” means. In my opinion, it can either be the author and all of his / her books, or just a single book under the specified author. My implementation uses the second explanation, which removes the specific book instead of the author and all of his/her books.

CODE: Q.1.

Exercise 11.32: Using the multimap from the previous exercise, write a program to print the list of authors and their works alphabetically.

• using set to store the book list：source.
• using map<string, multiset<string» to store everything (idea from Pezy's solution, much better that mine): source.

Exercise 11.33: Implement your own version of the word-transformation program.

CODE: Q.1.

Exercise 11.34: What would happen if we used the subscript operator instead of find in the transform function?

With subscript, if the keyword doesn't exist in the map, a new transform relationship will be created, from the new word to the empty string.

Exercise 11.35: In buildMap, what effect, if any, would there be from rewriting as follows?

trans_map[key] = value.substr(1);
trans_map.insert({key, value.substr(1)});

• subscript will relplace the old relationship with the new one.
• insert() will hold the old one.

exercise 11.36: Our program does no checking on the validity of either input file. In particular, it assumes that the rules in the transformation file are all sensible. What would happen if a line in that file has a key, one space, and then the end of the line? Predict the behavior and then check it against your version of the program.

The program will report a runtime_error(“No rule for ” + name of the key ). This is because a key following a line with a size less than 1 will be treated as a bad rule.

Test result:

//changed y+space+why to y+space
//output
terminate called after throwing an instance of 'std::runtime_error'
  what():  No rule for y

Exercise 11.37: What are the advantages of an unordered container as compared to the ordered version of that container? What are the advantages of the ordered version?

Unordered version:

• better performence with appropriate hash function
• better performence when ordering cost is prohibitive

Ordered version:

• Doesn't require tweaking and testing hash function
• must have if ordered elements is needed
• easy to use

Exercise 11.38: Rewrite the word-counting (§ 11.1, p. 421) and wordtransformation (§ 11.3.6, p. 440) programs to use an unordered_map.

CODE: Q.1. Q.2.