======Chapter.11======
Answers for chapter 11
----
====Ex.11.1-11.10====
==ex.11.1==
>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.
==ex.11.2==
>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.
==ex.11.3==
>Exercise 11.3: Write your own version of the word-counting program.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch11/ex_11_3.cc|Q.1]].
==ex.11.4==
>Exercise 11.4: Extend your program to ignore case and punctuation. Forexample, “example.” “example,” and “Example” should all increment the samecounter.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch11/ex_11_4.cc|Q.1]].
==ex.11.5==
>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.
==ex.11.6==
>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.
==ex.11.7==
>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: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch11/ex_11_7.cc|Q.1]].
==ex.11.8==
>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: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch11/ex_11_8.cc|Q.1]].
==ex.11.9==
>Exercise 11.9: Define a map that associates words with a list of line numbers on which the word might occur.
map> words_line;
==ex.11.10==
>Exercise 11.10: Could we define a map from vector::iterator to int? What about from list::iterator to int? In each case, if not, why not?
The ''vector::iterator'' can be used as the key because it has the ''<'' operation defined, however, a ''list::iterator'' cannot be used as the key since it only has the equality operation defined.
====Ex.11.11-11.20====
==ex.11.11==
>Exercise 11.11: Redefine bookstore without using decltype.
using comp_T = bool (*)(const Sales_data &, const Sales_data &);
std::multiset bookstore(compareIsbn);
==ex.11.12==
>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: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch11/ex_11_12.cc|Q.1]].
==ex.11.13==
>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: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch11/ex_11_13.cc|Q.1]].
==ex.11.14==
>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: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch11/ex_11_14.cc|Q.1]].
==ex.11.15==
>Exercise 11.15: What are the mapped_type, key_type, and value_type of a map from int to vector?
* **mapped_type**: ''vector''
* **key_type**: ''int''
* **value_type** : ''vector''
==ex.11.16==
>Exercise 11.16: Using a map iterator write an expression that assigns a value to an element.
map_it->seond = val;
==ex.11.17==
>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));
==ex.11.18==
>Exercise 11.18: Write the type of map_it from the loop on page 430 without using auto or decltype.
std::map::const_iterator
==ex.11.19==
>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 bookstore(compareIsbn);
std::multiset::iterator mset_it = bookstore.begin();
==ex.11.20==
>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: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch11/ex_11_20.cc|Q.1]].
====Ex.11.21-11.30====
==ex.11.21==
>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;
According to the operator precedence, the statement in the loop will be evaluate as the following order:
- insert function cast: the element pair ''{word, 0}'' will be inserted to the map ''word_count''. The function returns a pair . The iter points to the ''{word, 0}''.
- member access: the member call ''.first->second'' actually calls the value of the ''{word, 0}'';
- 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.
==ex.11.22==
>Exercise 11.22: Given a map>, write the types used as an argument and as the return value for the version of insert that inserts one element.
std::pair> //argument type
std::pair>::iterator, bool> //return type
==ex.11.23==
>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: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch11/ex_11_23.cc|Q.1]].
==ex.11.24==
>Exercise 11.24: What does the following program do?
map m;
m[0] = 1;
It inserts a key-value pair element ''{0, 1}'' into map ''m''.
==ex.11.25==
>Exercise 11.25: Contrast the following program with the one in the previous exercise.
vector v;
v[0] = 1;
It is an undefined behavior since ''v[0]'' tries to access an element that does not exist.
==ex.11.26==
>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 '''' has a key of ''int'' type and a subscription on the key returns ''std::string'' type. \\ \\
Test code: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch11/ex_11_26.cc|source]].
\\ \\
Result:
i NSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE
==ex.11.27==
>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.
==ex.11.28==
>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>::iterator iter = msv.find(key);
//or you may use auto instead
auto iter = msv.find(key);
Test code: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch11/ex_11_28.cc|source]].
==ex.11.29==
>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
==ex.11.30==
>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
is actually accessing the authors' first book, then reading out the title(value) of that book.
====Ex.11.31-11.38====
==ex.11.31==
>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: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch11/ex_11_31.cc|Q.1]].
==ex.11.32==
>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：[[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch11/ex_11_32.cc|source]].
* using map> to store everything (idea from [[https://github.com/pezy/CppPrimer/blob/master/ch11/ex11_32.cpp|Pezy's solution]], much better that mine): [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch11/ex_11_32_b.cc|source]].
==ex.11.33==
>Exercise 11.33: Implement your own version of the word-transformation program.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch11/ex_11_33.cc|Q.1]].
Data files should **NOT** be created in Windows and read or written in Linux and vice versa. Different systems have different ways of interpreting the file. My case was that I created the file in Windows and then read it in Ubuntu. That resulted in print errors. The problem could be solved by converting the file using the **dos2unix** program.
==ex.11.34==
>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.
==ex.11.35==
>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)});
//insert()// will do nothing if the key is already exsit in the map. In this case, since we are transferring the map data to the new map ''trans_map'', it is ok to use //insert()// member instead if there are no different relationship with the same key. Otherwise:
* subscript will relplace the old relationship with the new one.
* //insert()// will hold the old one.
==ex.11.36==
>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
==ex.11.37==
>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
==ex.11.38==
>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: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch11/ex_11_38_1.cc|Q.1]]. [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch11/ex_11_38_2.cc|Q.2]].