# Chapter 9. Sequential Containers
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.
std::list is the best one. To keep sorted alphabetically, each inserting into vector takes theta(n) time complexity, whereas that of list (essentially doubly linked list) takes only O(n). Hence theoretically list has better performance. deque. If the program needs to insert or delete elements at the front and the back, but not in the middle, use a dequevector, 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.Define a list that holds elements that are deques that hold ints.
std::list<std::deque<int>> a_list_of_deque_of_ints;What are the constraints on the iterators that form iterator ranges?
two iterators, begin and end:
end by repeatedly incrementing begin.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 contains(vector<int>::const_iterator first, vector<int>::const_iterator last, int value)
{
for(; first != last; ++first)
if(*first == value) return true;
return false;
}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.
auto find(vector<int>::const_iterator first, vector<int>::const_iterator last, int value)
{
for(; first != last; ++first)
if(*first == value) return first;
return last;
}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)Fixed:
while(iter1 != iter2)operator < is not implemented in std::list, because std::list is essetially a doubly linked list. Addresses of nodes of linked list are not necessarily continuous.
What type should be used as the index into a vector of ints?
vector<int>::size_typeWhat type should be used to read elements in a list of strings? To write them?
list<string>::const_iterator // to read
list<string>::iterator // to writeWhat is the difference between the
beginandcbeginfunctions?
cbegin is a const member that returns the container’s const_iterator type.
begin is nonconst and returns the container’s iterator type.
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();
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
Show an example of each of the six ways to create and initialize a vector. Explain what values each vector contains.
vector<int> vec; // vec is empty
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_vecExplain the differences between the constructor that takes a container to copy and the constructor that takes two iterators.
list<int> numbers = { 1, 2, 3, 4, 5 };
list<int> numbers2(numbers); // ok, numbers2 has the same elements as numbers
vector<int> numbers3(numbers); // error: no matching function for call...
list<double> numbers4(numbers); // error: no matching function for call...list<int> numbers = { 1, 2, 3, 4, 5 };
list<int> numbers2(numbers.begin(), numbers.end); // ok, numbers2 has the same elements as numbers
vector<int> numbers3(numbers.begin(), --numbers.end()); // ok, numbers3 is { 1, 2, 3, 4 }
list<double> numbers4(++numbers.beg(), --numbers.end()); // ok, numbers4 is { 2, 3, 4 }
forward_list<float> numbers5(numbers.begin(), numbers.end()); // ok, number5 is { 1, 2, 3, 4, 5 }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)
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
inserttakes thestringwe just read and puts it in front of the element denoted byiter. The value returned byinsertis an iterator referring to this new element. We assign that iterator toiterand repeat thewhile, reading another word. As long as there are words to insert, each trip through thewhileinserts a new element ahead ofiterand reassigns toiterthe 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 thevector.
Assuming
ivis avectorofints, 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:
iter never equal mid.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.
#include <iostream>
#include <vector>
void double_and_insert(std::vector<int>& v, int some_val)
{
auto mid = [&]{ return v.begin() + v.size() / 2; };
for (auto curr = v.begin(); curr != mid(); ++curr)
if (*curr == some_val)
++(curr = v.insert(curr, 2 * some_val));
}
int main()
{
std::vector<int> v{ 1, 9, 1, 9, 9, 9, 1, 1 };
double_and_insert(v, 1);
for (auto i : v)
std::cout << i << std::endl;
}The complete test codes, check this.
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.
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.
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 find_and_insert(forward_list<string> &list, string const& to_find, string const& to_add)
{
auto prev = list.before_begin();
for (auto curr = list.begin(); curr != list.end(); prev = curr++)
{
if (*curr == to_find)
{
list.insert_after(curr, to_add);
return;
}
}
list.insert_after(prev, to_add);
}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 elements of value 0 to the back of vec
vec.resize(10); // erases 90 elements from the back of vecWhat, 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.
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.
Can a container have a capacity less than its size?
cannot.
Why don’t list or array have a capacity member?
list does not hold elements contiguously. array has the fixed size statically.
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 while loop will read words from cin and store them in out vector. Even if we initially reserved 1024 elements, if there are more words read from cin, our vector's capacity will be automatically increased (most implementations will double the previous capacity) to accommodate them.
And now comes the catch. resize() is different from reserve(). In this case resize() will add another svec.size()/2 value initialized elements to svec. If this exceeds svec.capacity() it will also automatically increase it to accommodate the new elements.
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 |
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)
Given the definitions of name and numbers on page 365, what does numbers.find(name) return?
string::npos