本 Wiki 开启了 HTTPS。但由于同 IP 的 Blog 也开启了 HTTPS,因此本站必须要支持 SNI 的浏览器才能浏览。为了兼容一部分浏览器,本站保留了 HTTP 作为兼容。如果您的浏览器支持 SNI,请尽量通过 HTTPS 访问本站,谢谢!
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.
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) /* ... */
The relational operation <
cannot be applied to the container List
. Fix:
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;
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.
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());
CODE: Q.1
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)
c1
and c2
must have the same type on their containers and 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:
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);
This program may have two problems, and both are associated with the iterator.
mid
is invalidated.A fix:
++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
.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?
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: Q.1.
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.
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:
begin
might pass the insert point. The iterator that after the insert point will be invalidated by the insert operation:<html>
<img src=“/_media/programming/cpp/cpp_primer/answers/ex_9_33.svg” width=“500”>
</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
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.
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);
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?
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.
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:
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.