Sequential Containers and Container Adapters in C++ STL

Side Note: This is a post I wrote on Jul 7 2008. It was on my previous blog.

This article discusses the usage of three sequential containers in C++ STL, namely vectors, deques, and lists. It also covers two container adapters based on these containers, stack and queue.

<0> Sequential Containers

<0.0> Common operations for all sequential containers

a. Size operations.

There are three size operations for all of the three sequential containers.

size() returns the actual number of elements of the container.

empty() indicates whether the container is empty or not, it is usually more efficient than size() == 0.

max_size() returns the maximum number of elements a container might contain. The number is usually limited by PC hardwareor the maximum value of the type of the index.

b. Comparisons.

The common comparison operators ==, !=, <, >, <=, >= are applicable for containers. And they follow the rules listed below,

    b.0    Both containers must have the same type.

    b.1    Two containers are equal if both the elements and orders are the same.

    b.2    A lexicographical comparison is done when check if a container is less than the other.

c. [Speed Performance] Assignment and swap()

swap() is a preferrable way to do assignment if you don’t need the source container any more.

When you do assignment with containers, it copies all the elements of the source container and remove all the old elements in the destination container. The operation is usually of linear complexity.

swap() only swaps the internal pointers and it takes constant time.

<0.1> Vectors

The internal nature of a vector is dynamic array. Some points worth note-taking are,

a. random access: if the position is known, one can access any element directly using index in constant time. The iterator for a vector is random access iterator, so all the algorithms implemented in STL can be used.

b. Insert and delete: Insert [push_back()] and delete [pop_back()] at the end of a vector takes constant time. But the inerstions [insert()] and deletions [erase()] occurs at other parts of a vector normally requires linear time because these operations may need to displace a lot of elements.

c. Capacity: vector provides one additional size operation in addition to the three mentioned above, capacity(). It returns the number of elements a vector could hold without having to reallocate memory.

[Speed Performance] Reallocation takes linear time, to avoid it, we can use reserve() to ensure enough capacity for our vectors. reserve() takes linear time also, but it reduces the number of reallocations.

d. [Memory Performance] vector<bool>: it usually uses internally only 1 bit for an element. One can apply vectorName.flip() or vectorName[index].flip() to negate all the bits or a single bit.

<0.2> Deques

a. deques are very similar to vector, except that the underlying dynamic array is open at both ends for a deque.

Because of this differences, deque is fast for insertions and deletions at both ends.

b. Deque provides no support to control the capacity at the reallocation, so no capacity() and reserve() operations for deque.

<0.3> Lists

a. list is quite different from vector and deque, and it manages its elements as doubly linked list. The results are the following,

    a.0    A list does not provide random access.

    a.1    Deletion and insertion takes constant time at any position.

[Speed Performance] a.2 Lists provide special members for moving elements. These are faster versions of general algorithms that have the same names, because they only redirect pointers rather than copy and move the values.

            These functions include remove(), merge(), splice(), unique(), sort() and so on.

<1> Container Adapters

Container adapters adapt standard STL containers to fit special needs.

There are three container adapters in C++ STL, namely stack, queue and priority queue. Because priority queue is closely related to some other data structure called heaps, it is not covered here.

<1.0> Stacks

a. operations: push(), pop(), top(), empty(), size().

b. Implementation: the default implementation is deque. But since it only requires the push and pop elements at the top, it can also be implemented by vector or list also.

<1.1> Queues

a. operations: push(), pop(), front(), back(), size(), empty().

b. Implementation: the default implementation is deque. Because it requires push at the end and pop at the front, it can implemented by list also, but not vector.