Module 4 · array and deque: Fixed Size, and Growing at Both Ends

Every array and deque Operation, One by One, With Its Cost

Free with an accountReadingLesson 2 of 9

Bob needs a list of numbers in reverse. In Module 2 he inserted each one at v.begin() of a vector, and 100,000 of them took about a third of a second. Now he writes the same line on a deque, d.insert(d.begin(), x), and it finishes in well under a millisecond. Same call, same count, about eight hundred times faster. "Is the deque cheating?" he asks. No: the cost of each call depends on the container, and this lesson writes that cost under every operation.

Checking what this lesson needs for you…

What is inside Every array and deque Operation, One by One, With Its Cost

array: making one, and the braces that zero it
array: operator[] and at
array: front and back
array: size and empty
array: fill
array: swap
array: == and <
array: data, begin and endIntermediate
array: std::get<i>Intermediate
deque: four ways to make one
deque: push_back and push_front
deque: pop_back and pop_front
deque: operator[] and at
deque: front, back, size and empty
deque: insert and erase in the middle
deque: clear and resize
deque: shrink_to_fitIntermediate
What a deque does not have
Every cost in two tables, and Bob's measurement