Chapter 9. Sequential Containers

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.
• (b) Read an unknown number of words. Always insert new words at the back. Remove the next value from the front.
• (c) Read an unknown number of integers from a file. Sort the numbers and then print them to standard output.

• (a) std::set is the best. now, we can select vector or deque, better than list, cause we don't need insert or delete elements in the middle.
• (b) deque. If the program needs to insert or delete elements at the front and the back, but not in the middle, use a deque
• (c) vector, no need that insert or delete at the front or back. and If your program has lots of small elements and space overhead matters, don’t use list or forward_list.

Exercise 9.2:

Define a list that holds elements that are deques that hold ints.

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

Exercise 9.3:

What are the constraints on the iterators that form iterator ranges?

two iterators, begin and end:

• they refer to elements of the same container.
• It is possible to reach end by repeatedly incrementing begin.

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 find(vector<int>::iterator beg, vector<int>::iterator end, int value)
{
    for (auto iter = beg; iter != end; ++iter)
        if (*iter == value) 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.

vector<int>::iterator find(vector<int>::iterator beg, vector<int>::iterator end, int value)
{
    for (auto iter = beg; iter != end; ++iter)
        if (*iter == value) return iter;
    return end;
}

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) /*ERROR: operator< can't be applied to iterator for list*/

Fixed:

while(iter1 != iter2)

note:

operator < can be used in list,but can't be applied to iterator for list.

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>::iterator || list<string>::const_iterator // read
list<string>::iterator // write

Exercise 9.9:

What is the difference between the begin and cbegin functions?

cbegin is a const member that returns the container’s const_iterator type.

begin is nonconst and returns the container’s iterator type.

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();
auto it3 = v1.cbegin(), it4 = v2.cbegin();

---

@shidenggui:

The question example codes have an error in gcc 4.8:

error: inconsistent deduction for ‘auto’: ‘__gnu_cxx::__normal_iterator<int*, std::vector >’ and then ‘__gnu_cxx::__normal_iterator<const int*, std::vector >’ auto it1 = v1.begin(), it2 = v2.begin();

the correct codes should be:

auto it1 = v1.begin();
auto it2 = v2.begin(), it3 = v1.cbegin(), it4 = v2.cbegin();

---

it1 is vector<int>::iterator

it2,it3 and it4 are 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> vec;    // 0
vector<int> vec(10);    // 0
vector<int> vec(10,1);  // 1
vector<int> vec{1,2,3,4,5}; // 1,2,3,4,5
vector<int> vec(other_vec); // same as other_vec
vector<int> vec(other_vec.begin(), other_vec.end()); // same as other_vec

Exercise 9.12:

Explain the differences between the constructor that takes a container to copy and the constructor that takes two iterators.

• Constructor that takes two iterators copies the items between [first, last),e.g.

auto data = { 1, 2, 3 };
std::vector<int> vec(data.begin(), data.begin()+1); // vec is {1}

• Constructor that takes another container copies all items from it. e.g.

auto data = { 1, 2, 3 };
std::vector<int> vec(data); //vec is {1,2,3}

Exercise 9.13

Exercise 9.14

Exercise 9.15

Exercise 9.16

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?

First, there must be the identical container and same type holded. Second,the type held must support relational operation. (@Mooophy)

Both c1 and c2 are the containers except the unordered associative containers.(@pezy)

Exercise 9.18

Exercise 9.19

Exercise 9.20

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

It's the same.

The first call to insert takes the string we just read and puts it in front of the element denoted by iter. The value returned by insert is an iterator referring to this new element. We assign that iterator to iter and repeat the while, reading another word. As long as there are words to insert, each trip through the while inserts a new element ahead of iter and reassigns to iter the location of the newly inserted element. That element is the (new) first element. Thus, each iteration inserts an element ahead of the first element in the vector.

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

Problems:

1. It's a endless loop. iter never equal mid.
2. mid will be invalid after the insert.(see issue 133)

FIXED:

// cause the reallocation will lead the iterators and references
// after the insertion point to invalid. Thus, we need to call reserver at first.

vector<int> iv = {0,1,2,3,4,5,6,7,8,9}; // For example.
iv.reserver(25); // make sure that enough

vector<int>::iterator iter = iv.begin(), mid = iv.begin() + iv.size()/2;
while (iter != mid)
    if (*mid == some_val)
        mid = iv.insert(mid, 2 * some_val);
    else
        --mid;

The complete test codes, check this.

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?

same value that equal to the first element's.

Exercise 9.24

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?

if elem1 and elem2 are equal, nothing happened.

if elem2 is the off-the-end iterator, it would delete from elem1 to the end.

if both elem1 and elem2 are the off-the-end iterator, nothing happened too.

Exercise 9.26

Exercise 9.27

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.

void insert(forward_list<string> &flst, string find, string insrt)
{
    auto prev = flst.before_begin();
    for (auto curr = flst.begin(); curr != flst.end(); prev = curr++)
        if (*curr == find)
        {
            flst.insert_after(curr, insrt);
            return;
        }
    flst.insert_after(prev, insrt);
}

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);    // adds 75 items to the back of vec. These added items are value initialized.
vec.resize(10);     // erases 90 elements from the back of vec

Exercise 9.30:

What, if any, restrictions does using the version of resize that takes a single argument place on the element type?

If the container holds elements of a class type and resize adds elements we must supply an initializer or the element type must have a default constructor.

Exercise 9.31 use list | use forward_list

Exercise 9.32

Exercise 9.33

Exercise 9.34

Exercise 9.35:

Explain the difference between a vector’s capacity and its size.

The size of a container is the number of elements it already holds;

The capacity is how many elements it can hold before more space must be allocated.

Exercise 9.36:

Can a container have a capacity less than its size?

cannot.

Exercise 9.37:

Why don’t list or array have a capacity member?

list elements does not store contiguously. array has the fixed size, thus cannot added elements to it.

Exercise 9.38

Exercise 9.39:

Explain what the following program fragment does:

vector<string> svec;
svec.reserve(1024);     // sets capacity to at least 1024
string word;
while (cin >> word)     // input word continually
    svec.push_back(word);
svec.resize(svec.size()+svec.size()/2); // sets capacity to at least 3/2's size. may do nothing.

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?

read	size	capacity
256	384	1024
512	768	1024
1000	1500	2000(clang is 2048)
1048	1572	2048

Exercise 9.41

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?

Use member reserve(120) to allocate enough space for this string. (@Mooophy)

Exercise 9.43

Exercise 9.44

Exercise 9.45

Exercise 9.46

Exercise 9.47 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::npos

Exercise 9.49

Exercise 9.50

Exercise 9.51

Exercise 9.52