======Chapter.9======
Answers for chapter 9
----
====Ex.9.1-9.10====
==ex.9.1==
>Exercise 9.1: Which is the most appropriate—a vector, a deque, or a list—for the following program tasks? Explain the rationale for your choice. If there is no reason to prefer one or another container, explain why not.
**//(a) Read a fixed number of words, inserting them in the container alphabetically as they are entered. We’ll see in the next chapter that associative containers are better suited to this problem.//**\\ \\
Because the program requires insert elements in the middle of the container, a List is a better choice.\\ \\
**(b) Read an unknown number of words. Always insert new words at theback. Remove the next value from the front.**\\ \\
Because the number of inputs is unknown, a flexible container is needed. Additionally, since delete and insert operations are required both in front and at the back of the container, the deque is recommended. \\ \\
//**(c) Read an unknown number of integers from a file. Sort the numbers and then print them to standard output.**//\\ \\
In this case, Vector would be a good choice because it is a flexible container.
==ex.9.2==
>Exercise 9.2: Define a list that holds elements that are deques that hold ints.
std::list<> l_d_i;
==ex.9.3==
>Exercise 9.3: What are the constraints on the iterators that form iterator ranges?
* The ''end'' iterator must not precede the ''begin'' iterator.
* Those two iterators must point to the same container.
==ex.9.4==
>Exercise 9.4: Write a function that takes a pair of iterators to a vector and an int value. Look for that value in the range and return a bool indicating whether it was found.
bool
vec_ele_find(int i, std::vector::iterator ibeg,
std::vector::iterator iend) {
for(auto iter = ibeg; iter != iend; ++iter) {
if(*iter == i)
return true;
}
return false;
}
==ex.9.5==
>Exercise 9.5: Rewrite the previous program to return an iterator to the requested element. Note that the program must handle the case where the element is not found.
std::vector::iterator
vec_iter_find(int i, std::vector::iterator ibeg,
std::vector::iterator iend) {
for(auto iter = ibeg; iter != iend; ++iter) {
if(*iter == i)
return iter;
}
return ibeg;
}
==ex.9.6==
>Exercise 9.6: What is wrong with the following program? How might you correct it?
list lst1;
list::iterator iter1 = lst1.begin(),
iter2 = lst1.end();
while (iter1 < iter2) /* ... */
The relational operation ''<'' cannot be applied to the container ''List''. Fix:
list lst1;
list::iterator iter1 = lst1.begin(),
iter2 = lst1.end();
while (iter1 != iter2) /* ... */
==ex.9.7==
>Exercise 9.7: What type should be used as the index into a vector of ints?
vector::size_type
==ex.9.8==
>Exercise 9.8: What type should be used to read elements in a list of strings? To write them?
list::const_iterator // read
list::iterator //write
==ex.9.9==
>Exercise 9.9: What is the difference between the begin and cbegin functions?
* //begin// take a non-const object, returns a plain iterator;
* //cbegin// can take both non-const / const object and return a //const_iterator//.
==ex.9.10==
>Exercise 9.10: What are the types of the following four objects?
vector v1;
const vector v2;
auto it1 = v1.begin(), it2 = v2.begin(); // it1: vector::iterator, it2:vector::const_iterator
auto it3 = v1.cbegin(), it4 = v2.cbegin();//it3, it4: vector::const_iterator
====Ex.9.11-9.20====
==ex.9.11==
>Exercise 9.11: Show an example of each of the six ways to create and initialize a vector. Explain what values each vector contains.
vector v1 = {1,2,3}; //list init, v1 has 3 elements 1 ,2 ,3
vector v2 = v1; //copy init, v2 is equal to v1
vector v3(v1.begin(), v1,end())// iterator init, v3 equals to v1
vector v4(10, 1); //size specified init, v4 has 10 elements with value 1
vector v5(10); //size specified init with value init, v5 has 10 elements with value 0
vector v6; //default init, v6 is an emtpy vector
==ex.9.12==
>Exercise 9.12: Explain the differences between the constructor that takes a container to copy and the constructor that takes two iterators.
* Copy initialization that takes a container requires two containers and all of its elements have exactly the same type.
* Copy initialization that takes two iterators allows the different types between containers. For the elements, as long as there is a conversion existing between the source elements and the target elements, it's fine to initialize.
==ex.9.13==
>Exercise 9.13: How would you initialize a vector from a list? From a vector? Write code to check your answers.
list li = {1,2,3,4,5};
vector vi = {1,2,3,4,5};
vector vd1(li.begin(), li.end());
vector vd2(vi.begin(), vi.end());
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_13.cc|Q.1]]
==ex.9.14==
>Exercise 9.14: Write a program to assign the elements from a list of char* pointers to C-style character strings to a vector of strings.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_14.cc|Q.1]]
==ex.9.15==
>Exercise 9.15: Write a program to determine whether two vectors are equal.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_15.cc|Q.1]]
==ex.9.16==
>Exercise 9.16: Repeat the previous program, but compare elements in a list to a vector.
Notices:Two types of containers can't be compared. To complete the comparison, a list to vector conversion is required.\\ \\
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_16.cc|Q.1]]
==ex.9.17==
>Exercise 9.17: Assuming c1 and c2 are containers, what (if any) constraints does the following usage place on the types of c1 and c2?
if (c1 < c2)
* Both ''c1'' and ''c2'' must have the same type on their containers and elements.
* Relational operations must be defined for the elements.
==ex.9.18==
>Exercise 9.18: Write a program to read a sequence of strings from the standard input into a deque. Use iterators to write a loop to print the elements in the deque.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_18.cc|Q.1]]
==ex.9.19==
>Rewrite the program from the previous exercise to use a list. List the changes you needed to make.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_19.cc|Q.1]]
==ex.9.20==
>Exercise 9.20: Write a program to copy elements from a list into two deques. The even-valued elements should go into one deque and the odd ones into the other.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_20.cc|Q.1]]
====Ex.9.21-9.30====
==ex.9.21==
>Explain how the loop from page 345 that used the return from insert to add elements to a list would work if we inserted into a vector instead.
The loop on p.345 is equivalent to the 'push_front()' operation. It follows the same logic regardless of whether the container is a vector:
- iter = v.begin(), v.insert(iter, word); : The statement inserts an element at the beginning of the vector.
- iter = insert(iter, word) We update the insert location with this statement, bringing the iter back to the beginning of the vector (v.begin() again)
- Since insert adds an element before the element pointed by iter, each time a new word is added, it goes in front of the last element that we added.
- The loop will be executed until the user stops sending input.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_21.cc|A test program]]. \\ \\
PS: well, personally I don't recommond anyone to do this. It is extramely expensive to add element at the beginning of the vector. Imaging every time you insert a new element, you have to move every single other element in the vector one element back. It's an O(n) operation.
==ex.9.22==
Exercise 9.22: Assuming iv is a vector of ints, what is wrong with the following program? How might you correct the problem(s)?
vector::iterator iter = iv.begin(),
mid = iv.begin() + iv.size()/2;
while (iter != mid)
if (*iter == some_val)
iv.insert(iter, 2 * some_val);
This program may have two problems, and both are associated with the iterator.
* First, the while loop is run indefinitely because the iter which is used to update the while condition doesn't get updated correctly.
* The second problem is that even if we update the iter, the loop still cannot end. Whenever a new insert operation is made, ''mid'' is invalidated.
A fix:
* To ensure the while loop will end, do a ''++iter'' to push ''iter'' toward the middle point of the vector. Update the ''iter'' as well if the element that ''iter'' pointed to matches ''some_val''.
* Keeping the ''mid'' iterator valid by updating the ''mid'' to point at the middle of the **newest** vector, if an insert operation happened.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_22.cc|Q.1]]. \\ \\
==ex.9.23==
>Exercise 9.23: In the first program in this section on page 346, what would the values of val, val2, val3, and val4 be if c.size() is 1?
All of them hold a copy of the first element.
==ex.9.24==
>Exercise 9.24: Write a program that fetches the first element in a vector using at, the subscript operator, front, and begin. Test your program on an empty vector.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_24.cc|Q.1]].
/* if an emtpy vector vi */
vi.front(); //Segmentation fault (core dumped)
*vi.cbegin(); //Segmentation fault (core dumped)
vi[0]; //Segmentation fault (core dumped)
vi.at(0); //terminate called after throwing an instance of 'std::out_of_range' what(): vector::_M_range_check: __n (which is 0) >= this->size() (which is 0) Aborted (core dumped)
==ex.9.25==
>Exercise 9.25: In the program on page 349 that erased a range of elements, what happens if elem1 and elem2 are equal? What if elem2 or both elem1 and elem2 are the off-the-end iterator?
**//what happens if elem1 and elem2 are equal?//** \\ \\
No element will be deteled.\\ \\
**//What if elem2 or both elem1 and elem2 are the off-the-end iterator?//**
* if elem2 is the of-the-end iterator, the deteting range will be [elem1, elem2)
* if elem1 and elem2 both refer to the off-the-end iterator, no element will be deteled.
==ex.9.26==
>Using the following definition of ia, copy ia into a vector and into a list. Use the single-iterator form of erase to remove the elements with odd values from your list and the even values from your vector.
int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_26.cc|Q.1]].
==ex.9.27==
>Write a program to find and remove the odd-valuedelements in a forward_list.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_27.cc|Q.1]].
==ex.9.28==
>Exercise 9.28: Write a function that takes a forward_list and two additional string arguments. The function should find the first string and insert the second immediately following the first. If the first string is not found, then insert the second string at the end of the list.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_28.cc|Q.1]].
==ex.9.29==
>Exercise 9.29: Given that vec holds 25 elements, what does //vec.resize(100)// do? What if we next wrote //vec.resize(10)//?
vec.resize(100); //The container size will be increased to 100. The 75 new elements will be default-initialized, or value-initialized if an initial value is provided.
vec.resize(10); //90 of the right-most elements will be truncated.
==ex.9.30==
>Exercise 9.30: What, if any, restrictions does using the version of resize that takes a single argument place on the element type?
If no initial-value is specified, a default initialization will be applied to all new elements. As a result, the element must have a default constructor.
====Ex.9.31-9.40====
==ex.9.31==
>Exercise 9.31: The program on page 354 to remove even-valued elements and duplicate odd ones will not work on a list or forward_list. Why? Revise the program so that it works on these types as well.
* For the list, this is becuase list iterator member only support self increment.
* For the forward_list, this is due to forward_list doesn't have //insert()// and //erase()// members. In order to achieve a similar result, we should use the //insert_after// and //erase_after// members. Additionally, the //forwad_list// loop requires two iterators, so a slight modification is needed.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_31.cc|List]] [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_31_fl.cc|Forward_List]]
==ex.9.32==
>Exercise 9.32: In the program onpage 354 would it be legal to write the call to insert as follows? If not, why not?
It won't work. The order of evaluation of argument is unspecified therefore we can't guarantee the argument ''iter'' is going to be evaluated first. \\ \\
Ref:[[https://stackoverflow.com/questions/9566187/function-parameter-evaluation-order|https://stackoverflow.com/questions/9566187/function-parameter-evaluation-order]]
==ex.9.33==
>Exercise 9.33: In the final example in this section what would happen if we did not assign the result of insert to begin? Write a program that omitsthis assignment to see if your expectation was correct.
When we take a vector as a container, the insert member has a chance to invalidate the iterator ''begin'' if we don't update it by assigning the return value of insert to it. In this case, there are two situations that would cause the iterator invalid:
* The first circumstance is that the vector may be reallocated due to the increasing elements. A reallocate operation will cause all iterators invalid.
* This second situation is that iterator ''begin'' might pass the insert point. The iterator that after the insert point will be invalidated by the insert operation:
\\ \\
TEST CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_33.cc|Q.1]].\\ \\
result:
root@Hare:/CppPrimer_5th/ch9# ./a.out
munmap_chunk(): invalid pointer
Aborted (core dumped)
==ex.9.34==
>Exercise 9.34: Assuming vi is a container of ints that includes even and odd values, predict the behavior of the following loop. After you’ve analyzed this loop, write a program to test whether your expectations were correct.
The //iter++// is not a part of the loop. As a result, the iteration will never reach the //vi.end()//, and the program will be an infinite loop. \\ \\
Furthermore, an //insert()// operation must move the ''iter'' 2 units to the right in order to get the correct position of the iterator for the subsequent loop. Even with a //++iter// in the loop, if there is one of the elements meets the condition, the ''iter'' will move back to the element over and over again.This will result in an endless loop as well.\\ \\
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_34.cc|Q.1]].
==ex.9.35==
>Exercise 9.35: Explain the difference between a vector’s capacity and its size.
* capacity: the maximum number of elements a vector can hold before reallocating
* size: the number of elements in the vector
==ex.9.36==
>Exercise 9.36: Can a container have a capacity less than its size?
No. For a vector, once its size exceeds its capcity, the vector will be reallocated and the new capcity will be twice as large as the original one.
==ex.9.37==
>Exercise 9.37: Why don’t list or array have a capacity member?
* Adding elements to a list is much cheaper than doing it in a vector because of its structure. In this way, we increase capacity each time we insert an element.
* An array is a container with a fixed size. Therefore, its capacity does not need to be changed.
==ex.9.38==
>Exercise 9.38: Write a program to explore how vectors grow in the libraryyou use.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_38.cc|Q.1]].
#test result
Current size: 2 Current capacity 2
1
Current size: 3 Current capacity 4
1
Current size: 4 Current capacity 4
1
Current size: 5 Current capacity 8
==ex.9.39==
>Exercise 9.39: Explain what the following program fragment does:
vector svec;
svec.reserve(1024);
string word;
while (cin >> word)
svec.push_back(word);
svec.resize(svec.size()+svec.size()/2);
* The program claims it can store up to 1024 strings.
* Each time it gets a string from the input, the string is stored at the end of the vector.
* When the loop ends, the number of elements increases by 1.5 times the current vector size. The default value for adding elements is an empty string.
* There will be a reallocation for the vector once the number of elements exceeds the capacity.
==ex.9.40==
>Exercise 9.40: If the program in the previous exercise reads 256 words, what is its likely capacity after it is resized? What if it reads 512? 1,000? 1,048?
element 256 | size 384 | capacity 1024
element 512 | size 768 | capacity 1024
element 1000 | size 1500 | capacity 2048
element 1048 | size 1572 | capacity 2048
====Ex.9.41-9.50====
==ex.9.41==
>Exercise 9.41: Write a program that initializes a string from a vector.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_41.cc|Q.1]].
==ex.9.42==
>Exercise 9.42: Given that you want to read a character at a time into a string, and you know that you need to read at least 100 characters, how might you improve the performance of your program?
* increase the capacity of the string(I prefer to 200)
* using push_back() to add element
==ex.9.43==
>Exercise 9.43: Write a function that takes three strings, s, oldVal, and newVal. Using iterators, and the insert and erase functions replace all instances of oldVal that appear in s by newVal. Test your function by using it to replace common abbreviations, such as “tho” by “though” and “thru” by “through”.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_43.cc|Q.1]].
==ex.9.44==
>Exercise 9.44: Rewrite the previous function using an index and replace.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_44.cc|Q.1]].
==ex.9.45==
>Exercise 9.45: Write a funtion that takes a string representing a name and two other strings representing a prefix, such as “Mr.” or “Ms.” and a suffix, such as “Jr.” or “III”. Using iterators and the insert and append functions, generate and return a new string with the suffix and prefix added to the given name.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_45.cc|Q.1]].
==ex.9.46==
>Exercise 9.46: Rewrite the previous exercise using a position and length to manage the strings. This time use only the insert function.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_46.cc|Q.1]].
==ex.9.47==
>Exercise 9.47: Write a program that finds each numeric character and then each alphabetic character in the string "ab2c3d7R4E6". Write two versions of the program. The first should use find_first_of, and the second find_first_not_of.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_47.cc|find_first_of]] [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_47_2.cc|find_first_not_of]]
==ex.9.48==
>Exercise 9.48: Given the definitions of name and numbers on page 365, what does numbers.find(name) return?
string numbers("0123456789"), name("r2d2"); //return std::string::npos
==ex.9.49==
>Exercise 9.49: A letter has an ascender if, as with d or f, part of the letter extends above the middle of the line. A letter has a descender if, as with p or g, part of the letter extends below the line. Write a program that reads a file containing words and reports the longest word that contains neither ascenders nor descenders.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_49.cc|Q.1]].
==ex.9.50==
>Exercise 9.50: Write a program to process a vectors whose elements represent integral values. Produce the sum of all the elements in that vector. Change the program so that it sums of strings that represent floating-point values.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_50.cc|Q.1]].
====Ex.9.51-9.52====
==ex.9.51==
>Exercise 9.51: Write a class that has three unsigned members representing year, month, and day. Write a constructor that takes a string representing a date. Your constructor should handle a variety of date formats, such as January 1, 1900, 1/1/1900, Jan 1, 1900, and so on.
Notes:
* My implementation can only verify input in the mm-dd-yy format. Any other order might result in bugs.
* Using the delimiter as a mark, I separated all segments, then handled each one separately.
* There are a few drawbacks to my method:
* Complex logic.
* The month, day, or year cannot be recognized when the value is less than 13.
* Does not support other formats, such as U.S. time.
* In the future, I will revise it and publish the improved version here.
//First version//: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_51.h|header]] [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_51.cc|test file]]
==ex.9.52==
>Exercise 9.52: Use a stack to process parenthesized expressions. When you see an open parenthesis, note that it was seen. When you see a close parenthesis after an open parenthesis, pop elements down to and including the open parenthesis off the stack. push a value onto the stack to indicate that a parenthesized expression was replaced.
CODE: [[https://github.com/CodingHare/Book_Solutions/blob/master/CppPrimer_5th/ch9/ex_9_52.cc|Q.1]].