Chapter.9

Answers for chapter 9

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.

© 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.

Exercise 9.2: Define a list that holds elements that are deques that hold ints.

std::list<<std::deque<int>> l_d_i;

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.

Exercise 9.4: Write a function that takes a pair of iterators to a vector<int> 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<int>::iterator ibeg,
			 		std::vector<int>::iterator iend) {
	for(auto iter = ibeg; iter != iend; ++iter) {
		if(*iter == i)
			return true;
	}
	return false;
}

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<int>::iterator
vec_iter_find(int i, std::vector<int>::iterator ibeg,
			 		std::vector<int>::iterator iend) {
	for(auto iter = ibeg; iter != iend; ++iter) {
		if(*iter == i)
			return iter;
	}
	return ibeg;
}

Exercise 9.6: What is wrong with the following program? How might you correct it?

list<int> lst1;
list<int>::iterator iter1 = lst1.begin(),
iter2 = lst1.end();
while (iter1 < iter2) /* ... */

list<int> lst1;
list<int>::iterator iter1 = lst1.begin(),
iter2 = lst1.end();
while (iter1 != iter2) /* ... */

Exercise 9.7: What type should be used as the index into a vector of ints?

vector<int>::size_type

Exercise 9.8: What type should be used to read elements in a list of strings? To write them?

list<string>::const_iterator // read
list<string>::iterator //write

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.

Exercise 9.10: What are the types of the following four objects?

vector<int> v1;
const vector<int> v2;
auto it1 = v1.begin(), it2 = v2.begin(); // it1: vector<int>::iterator, it2:vector<int>::const_iterator
auto it3 = v1.cbegin(), it4 = v2.cbegin();//it3, it4: vector<int>::const_iterator

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<int> v1 = {1,2,3}; //list init, v1 has 3 elements 1 ,2 ,3
vector<int> v2 = v1; //copy init, v2 is equal to v1
vector<int> v3(v1.begin(), v1,end())// iterator init, v3 equals to v1
vector<int> v4(10, 1); //size specified init, v4 has 10 elements with value 1
vector<int> v5(10); //size specified init with value init, v5 has 10 elements with value 0
vector<int> v6; //default init, v6 is an emtpy vector

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.

Exercise 9.13: How would you initialize a vector<double> from a list<int>? From a vector<int>? Write code to check your answers.

list<int> li = {1,2,3,4,5};
vector<int> vi = {1,2,3,4,5};
vector<double> vd1(li.begin(), li.end());
vector<int> vd2(vi.begin(), vi.end());

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: Q.1

Exercise 9.15: Write a program to determine whether two vector<int>s are equal.

CODE: Q.1

Exercise 9.16: Repeat the previous program, but compare elements in a list<int> to a vector<int>.

Notices:Two types of containers can't be compared. To complete the comparison, a list to vector conversion is required.

CODE: Q.1

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.

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: Q.1

Rewrite the program from the previous exercise to use a list. List the changes you needed to make.

CODE: Q.1

Exercise 9.20: Write a program to copy elements from a list<int> into two deques. The even-valued elements should go into one deque and the odd ones into the other.

CODE: Q.1

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:

1. iter = v.begin(), v.insert(iter, word); : The statement inserts an element at the beginning of the vector.
2. 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)
3. 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.
4. The loop will be executed until the user stops sending input.

CODE: 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.

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<int>::iterator iter = iv.begin(), 
					  mid = iv.begin() + iv.size()/2;
while (iter != mid)
	if (*iter == some_val)
		iv.insert(iter, 2 * some_val);

• 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: Q.1.

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.

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: 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)

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.

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 };

Write a program to find and remove the odd-valuedelements in a forward_list<int>.

CODE: Q.1.

Exercise 9.28: Write a function that takes a forward_list<string> 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: Q.1.

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.

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.

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: List Forward_List

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

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:

<html>

</html>

TEST CODE: Q.1.

result:

root@Hare:/CppPrimer_5th/ch9# ./a.out
munmap_chunk(): invalid pointer
Aborted (core dumped)

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: Q.1.

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

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.

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.

Exercise 9.38: Write a program to explore how vectors grow in the libraryyou use.

CODE: 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

Exercise 9.39: Explain what the following program fragment does:

vector<string> 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.

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

Exercise 9.41: Write a program that initializes a string from a vector<char>.

CODE: Q.1.

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

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: Q.1.

Exercise 9.44: Rewrite the previous function using an index and replace.

CODE: Q.1.

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: Q.1.

Exercise 9.46: Rewrite the previous exercise using a position and length to manage the strings. This time use only the insert function.

CODE: Q.1.

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: find_first_of find_first_not_of

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

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: Q.1.

Exercise 9.50: Write a program to process a vector<string>s 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: Q.1.

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: header test file

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: Q.1.