Sequential Containers Flashcards Preview

c++ Primer > Sequential Containers > Flashcards

Flashcards in Sequential Containers Deck (26):
1

What are the performance trade off(s) relative to operations in a sequential container?

• The costs to add or delete elements to the container
• The costs to perform nonsequential access to elements of the container

2

list ( and forward_list ) vs containers

The list and forward_list containers are designed to make it fast to add or
remove an element anywhere in the container.
In exchange, these types do not
support random access to elements: We can access an element only by iterating
through the container.
Moreover, the memory overhead for these containers is often
substantial, when compared to vector, deque, and array.

3

A few rules of thumb that apply to selecting which container

• Unless you have a reason to use another container, use a vector.
• If your program has lots of small elements and space overhead matters, don’t
use list or forward_list.
• If the program requires random access to elements, use a vector or a deque.
• If the program needs to insert or delete elements in the middle of the container,
use a list or forward_list.
• If the program needs to insert or delete elements at the front and the back, but
not in the middle, use a deque.
• If the program needs to insert elements in the middle of the container only
while reading input, and subsequently needs random access to the elements:
– First, decide whether you actually need to add elements in the middle of a
container. It is often easier to append to a vector and then call the library
sort function (which we shall cover in § 10.2.3 (p. 384)) to reorder the
container when you’re done with input.
– If you must insert into the middle, consider using a list for the input phase.
Once the input is complete, copy the list into a vector.

4

Revise Container Operations ( Table 9.2) and Defining and Initializing Containers ( Table 9.3 )

Revise Container Operations ( Table 9.2) and Defining and Initializing Containers ( Table 9.3 )

5

Can we define a container without relational operators and/or default ctors?

We can define a container for a type that does not support an operation-specific requirement, but we can use an operation only if the element type meets that operation’s requirements.

// assume noDefault is a type without a default constructor
vector v1(10, init); // ok: element initializer supplied
vector v2(10); // error: must supply an element initializer

6

What are begin, end iterators, Comment about them being a range

The name last, although commonly used, is a bit misleading, because the second iterator never refers to the last element of the range. Instead, it refers to a point one past the last element. The elements in the range include the element denoted by first and every element from first up to but not including last.

This element range is called a left-inclusive interval. The standard mathematical
notation for such a range is [ begin, end) indicating that the range begins with begin and ends with, but does not include, end. The iterators begin and end must refer to the same container. The iterator end may be equal to begin but must not refer to an element before the one denoted by
begin.

Requirements on Iterators Forming an Iterator Range
Two iterators, begin and end, form an iterator range, if
• They refer to elements of, or one past the end of, the same container, and
• It is possible to reach end by repeatedly incrementing begin. In other words, end must not precede begin.

The library uses left-inclusive ranges because such ranges have three convenient properties. Assuming begin and end denote a valid iterator range, then
• If begin equals end, the range is empty
• If begin is not equal to end, there is at least one element in the range, and begin refers to the first element in that range
• We can increment begin some number of times until begin == end

7

Difference between begin, cbegin and rbegin

The functions that do not begin with a c are overloaded. That is, there are actually two members named begin. One is a const member (§ 7.1.2, p. 258) that returns the container’s const_iterator type. The other is nonconst and returns the container’s iterator type. Similarly for rbegin, end, and rend. When we call one of these members on a nonconst object, we get the version that returns iterator. We get a const version of the iterators only when we call these functions on a const object. As with pointers and references to const, we can convert a plain iterator to the corresponding const_iterator, but not vice versa.

8

Can we create copy of container using copy ctor

To create a container as a copy of another container, the container and element types must match. When we pass iterators, there is no requirement that the container types be identical. Moreover, the element types in the new and original containers can differ as long as it is possible to convert the elements we’re copying to the element type of the container we are initializing:

// each container has three elements, initialized from the given initializers
list authors = {"Milton", "Shakespeare", "Austen"};
vector articles = {"a", "an", "the"};
list list2(authors); // ok: types match
deque authList(authors); // error: container types don't match
vector words(articles); // error: element types must match
// ok: converts const char* elements to string
forward_list words(articles.begin(), articles.end());

9

Is size part of std::array's type?

The size of a library array is part of its type. When we define an array, in addition to specifying the element type, we also specify the container size:

array // type is: array that holds 42 ints
array // type is: array that holds 10 strings

10

How many constructed elements does std::array have?

Unlike the other containers, a default-constructed array is not empty: It has as many elements as its size. These elements are default initialized just as are elements in a built-in array. If we list initialize the array, the number of the initializers must be equal to or less than the size of the array. If there are fewer initializers than the size of the array, the initializers are used for the first elements and any remaining elements are value initialized

array ia1; // ten default-initialized ints
array ia2 = {0,1,2,3,4,5,6,7,8,9}; // list initialization
array ia3 = {42}; // ia3[0] is 42, remaining elements are 0

It is worth noting that although we cannot copy or assign objects of built-in array types, there is no such restriction on array:

int digs[10] = {0,1,2,3,4,5,6,7,8,9};
int cpy[10] = digs; // error: no copy or assignment for built-in arrays
array digits = {0,1,2,3,4,5,6,7,8,9};
array copy = digits; // ok: so long as array types match

11

Does assignment work on std::array ?

Unlike built-in arrays, the library array type does allow assignment. The left-and right-hand operands must have the same type:

array a1 = {0,1,2,3,4,5,6,7,8,9};
array a2 = {0}; // elements all have value 0
a1 = a2; // replaces elements in a1
a2 = {0}; // error: cannot assign to an array from a braced list

12

Comment on assignment operator and assign functions in sequential container

The assignment operator requires that the left-hand and right-hand operands have the same type. It copies all the elements from the right-hand operand into the left-hand operand. The sequential containers (except array) also define a member named assign that lets us assign from a different but compatible type, or assign from a subsequence of a container.

list names;
vector oldstyle;
names = oldstyle; // error: container types don't match
// ok: can convert from const char*to string
names.assign(oldstyle.cbegin(), oldstyle.cend());

A second version of assign takes an integral value and an element value.

// equivalent to slist1.clear();
// followed by slist1.insert(slist1.begin(), 10, "Hiya!");
list slist1(1); // one element, which is the empty string
slist1.assign(10, "Hiya!"); // ten elements; each one is Hiya !

13

Comment on std::swap

After the swap, svec1 contains 24 string elements and svec2 contains ten. With the exception of arrays, swapping two containers is guaranteed to be fast—the elements themselves are not swapped; internal data structures are swapped.

The fact that elements are not moved means that, with the exception of string, iterators, references, and pointers into the containers are not invalidated. They refer to the same elements as they did before the swap. However, after the swap, those elements are in a different container. For example, had iter denoted the string at position svec1 [3] before the swap, it will denote the element at position svec2[3] after the swap. Differently from the containers, a call to swap on a string may invalidate iterators, references and pointers.
Unlike how swap behaves for the other containers, swapping two arrays does exchange the elements. As a result, swapping two arrays requires time proportional to the number of elements in the array.
After the swap, pointers, references, and iterators remain bound to the same element they denoted before the swap.

14

Does std::swap copy, delete or insert elements

Excepting array, swap does not copy, delete, or insert any elements and is
guaranteed to run in constant time.
Only internal data structures are swapped

15

Which size functions are present in most containers

With exception of forward_list, the container types have three size-related operations. The size member returns the number of elements in the container; empty returns a bool that is true if size is zero and false otherwise; and max_size returns a number that is greater than or equal to the number of elements a containerof that type can contain.

16

How do relational operators work in containers

Comparing two containers performs a pairwise comparison of the elements. These operators work similarly to the string relationals :
• If both containers are the same size and all the elements are equal, then the two containers are equal; otherwise, they are unequal.
• If the containers have different sizes but every element of the smaller one isequal to the corresponding element of the larger one, then the smaller one is less than the other.
• If neither container is an initial subsequence of the other, then the comparisondepends on comparing the first unequal elements.

The following examples illustrate how these operators work:

vector v1 = { 1, 3, 5, 7, 9, 12 };
vector v2 = { 1, 3, 9 };
vector v3 = { 1, 3, 5, 7 };
vector v4 = { 1, 3, 5, 7, 9, 12 };
v1 < v2 // true; v1 and v2 differ at element [2]: v1[2] is less than v2[2]
v1 < v3 // false; all elements are equal, but v3 has fewer of them;
v1 == v4 // true; each element is equal and v1 and v4 have the same size()
v1 == v2 // false; v2 has fewer elements than v1

17

Whats is container's first argument for insert function. Comment on its functionality

Each of the insert functions takes an iterator as its first argument. The iterator indicates where in the container to put the element(s).
Because the iterator might refer to a nonexistent element off the end of the container, and because it is useful to have a way to insert elements at the beginning of a container, element(s) are inserted before the position denoted by the iterator

18

Container's insert-ing range of elements

The arguments to insert that appear after the initial iterator argument are analogous to the container constructors that take the same parameters.

svec.insert(svec.end(), 10, "Anna");
This code inserts ten elements at the end of svec and initializes each of those elements to the string "Anna".

Under the new standard ( C++11 + ), the versions of insert that take a count or a range return an iterator to the first element that was inserted. If the range is empty, no elements are inserted, and the operation returns its first parameter.

19

What emplace functions in containers

The new standard introduced three new members—emplace_front, emplace, and emplace_back—that construct rather than copy elements.

When we call an emplace member, we pass arguments to a constructor for the element type. The emplace members use those arguments to construct an element directly in space managed by the container.

20

Whats is container's erase function return?

Both forms of erase return an iterator referring to the location after the (last) element that was removed.

list lst = {0,1,2,3,4,5,6,7,8,9};
auto it = lst.begin();
while (it != lst.end())
if (*it % 2) // if the element is odd
it = lst.erase(it); // erase this element
else
++it;

21

When is an iterator invalidated for an add operation

After an operation that adds elements to a container
• Iterators, pointers, and references to a vector or string are invalid if the container was reallocated. If no reallocation happens, indirect references to elements before the insertion remain valid; those to elements after the insertion are invalid.
• Iterators, pointers, and references to a deque are invalid if we add elements anywhere but at the front or back. If we add at the front or back, iterators are invalidated, but references and pointers to existing elements are not.
• Iterators, pointers, and references (including the off-the-end and the beforethe-beginning iterators) to a list or forward_list remain valids

22

When is an iterator invalidated for a remove operation

After we remove an element,
• All other iterators, references, or pointers (including the off-the-end and the before-the-beginning iterators) to a list or forward_list remain valid.
• All other iterators, references, or pointers to a deque are invalidated if the removed elements are anywhere but the front or back. If we remove elements at the back of the deque, the off-the-end iterator is invalidated but other iterators, references, and pointers are unaffected; they are also unaffected if we remove from the front.
• All other iterators, references, or pointers to a vector or string remain valid for elements before the removal point. Note: The off-the-end iterator is always invalidated when we remove elements.

23

Should end iterator be computed everytime in a loop?

Yes, don’t cache the iterator returned from end() in loops that insert or delete
elements in a deque, string, or vector.

Rather than storing the end() iterator, we must recompute it after each insertion:

// safer: recalculate end on each trip whenever the loop adds/erases elements
while (begin != v.end()) {
// do some processing
++begin; // advance begin because we want to insert after this element
begin = v.insert(begin, 42); // insert the new value
++begin; // advance begin past the element we just added
}

24

How do vectors grow?

To support fast random access, vector elements are stored contiguously—each element is adjacent to the previous element.

Given that elements are contiguous, and that the size of the container is flexible, when we add an element if there is no room for the new element, the container must allocate new memory to hold the existing elements plus the new one, move the elements from the old location into the new space, add the new element, and deallocate the old memory. If vector did this memory allocation and deallocation each time we added an element, performance would be unacceptably slow.

When they have to get new memory, vector and string implementations typically allocate capacity beyond what is immediately needed. The container holds this storage in reserve and uses it to allocate new elements as they are added.

25

Describe std::string::replace

The replace functions provide two ways to specify the range of characters to
remove. We can specify that range by a position and a length, or with an iterator
range. The insert functions give us two ways to specify the insertion point: with
either an index or an iterator. In each case, the new element(s) are inserted in front
of the given index or iterator.

26

Explain container adaptors

By default both stack and queue are implemented in terms of deque, and a priority_queue is implemented on a vector. We can override the default container type by naming a sequential container as a second type argument when we create the adaptor:

// empty stack implemented on top of vector
stack> str_stk;
// str_stk2 is implemented on top of vector and initially holds a copy of svec
stack> str_stk2(svec);

There are constraints on which containers can be used for a given adaptor. All of the adaptors require the ability to add and remove elements. As a result, they cannot be built on an array. Similarly, we cannot use forward_list, because all of the adaptors require operations that add, remove, or access the last element in the container. A stack requires only push_back, pop_back, and back operations, so we can use any of the remaining container types for a stack. The queue adaptor requires back, push_back, front, and push_front, so it can be built on a list or deque but not on a vector. A priority_queue requires random access in addition to the front, push_back, and pop_back operations; it can be built on a vector or a deque but not on a list.

Each container adaptor defines its own operations in terms of operations provided by the underlying container type. We can use only the adaptor operations and cannot use the operations of the underlying container type