Chapter 15 - Sequential Containers Notes

Notes

Iterator

Think of iterators as pointers, which are essentially memory addresses of each element.

In most containers other than vector, the elements are not stored contiguously in memory, and so we cannot simply use pointers with offsets to access subsequent elements.

Iterators hide this detail, by providing us a value that we can get, increment to access the next element, decrement to get the previous element, just as we would do with pointers.

container.begin() returns an iterator to the first element of the container.

container.end() returns a value outside of the container, it is not the "end", nor is it the last element. Think of it as one after the last element.

Iterator vs. Indexing

Certain containers don't support indexing, and so iterators are the only way to enumerate over the container.

Insertion vs. Push

The term "insert" usually refers to adding an element at some position in a sequential container. The position where the element is to be inserted has to be provided, commonly as an iterator.

The term "push" usually refers to adding an element to either the back or front of a sequential container, often distinguished with a push_back or push_front function. Since the position of the item to be added is apparent, you do not need to specify it with an iterator.

Vectors

std::vector - cppreference.comen.cppreference.com

Characteristics

• Internally represented by an dynamic array.

• Elements are stored contiguously, meaning subsequent elements can not be accessed through iterators, but also pointers and offsets.

• Storage of a vector is handled automatically, being expanded and contracted as needed.

Good for...

• Random access (indexing) into an array, done in O(1) time

• Insertion or removal of elements at the end, done in O(1) time

Not good for...

• Insertion or removal of elements not at the end, done in linear time proportional to distance to the end, since every element has to be shifted back.

List

std::list - cppreference.comen.cppreference.com

Characteristics

• Internally represented as a linked list

• Elements are not contiguously stored

Good for...

• Adding, removing, or inserting elements from anywhere in the container, done in O(1) time.

Not good for...

• Random access (indexing) in the array is not supported, only enumeration

• Tight and sequential access is slower than contiguously stored containers

Deque

std::deque - cppreference.comen.cppreference.com

Characteristics

• Internally represented as a linked list of dynamic arrays

• Elements are mostly contiguous, but not strictly so

• Storage of a deque is automatically handled, being expanded and contracted as needed.

Good for...

• Random access (indexing) into a deque, done in O(1) time

• Insertion or removal of elements at the end or beginning, done in O(1) time

• Best of both worlds of a vector and a list, at a slight memory overhead.

Not good for...

• Insertion or removal of elements anywhere but the end of beginning of the deque, done in linear time proportional to the distance from the end or back

• Tight and sequential access, since the elements are not stored contiguously in memory, but negligibly so.

Reading Material

• Iterators: https://www.youtube.com/watch?v=SgcHcbQ0RCQ

• Containers: https://www.youtube.com/watch?v=6OoSgY6NVVk