Sequential Containers in C++

Overview

A container is a collection of objects of a specific type. Sequential containers give you control over the order in which elements are stored and accessed. Sequential container types:

  • vector: a variable-size array that supports fast random access
  • deque: a double-ended queue that supports fast random access
  • list: a doubly linked list that supports only bidirectional sequential access
  • forward_list: a singly linked list that supports only unidirectional sequential access
  • array: a fixed-size array
  • string: similar to vector, but used only to hold characters

A few guidelines for choosing a sequential container:

  1. Compared with built-in arrays, array is a safer and easier-to-use array type. Modern C++ programs should use standard library containers rather than more primitive data structures such as built-in arrays.
  2. Unless you have a good reason to choose another container, use vector.
  3. The remaining choices can be made based on the properties of the underlying data structure—array, linked list, queue, and so on.

The Container Library and Sequential Container Operations

Most operations on sequential containers can be found in the C++ API, so I won’t go over them in detail here. I’ll only mention a few points worth noting. On iterators:

  1. The iterator returned by c.end() points to the position one past the last element. The range defined by a pair of iterators such as c.begin() and c.end() is left-closed and right-open.
  2. The singly linked list forward_list does not support decrementing iterators, which is easy to understand given the nature of a singly linked list’s data structure.
  3. If begin and end are equal, the range is empty; if they are not equal, the range contains at least one element.
  4. When creating a container as a copy of another container, the two containers and their element types must both match. When copying from a range of iterators, the element types need not match—it is enough that the elements can be converted to the corresponding type.
  5. Except for string, iterators, references, and pointers into a container remain valid after a swap and still point to the same elements as before the swap. For string, however, they are all invalidated.

On swap: to be continued On forward_list: to be continued On string: to be continued

On vector’s Growth

A vector’s objects are stored contiguously. The standard library implementers adopt a strategy that reduces the number of times a container’s storage must be reallocated: when it must obtain new memory, the vector and string implementations typically allocate more memory than the new requirement strictly demands. With this strategy, their growth is usually much faster than that of list or deque.

Note the difference between capacity and size: a container’s size is the number of elements it currently holds, while its capacity is the maximum number of elements it can hold without allocating new memory.

Container Adaptors

In addition to the sequential containers, the standard library also defines three sequential container adaptors: stack, queue, and priority_queue. The adaptor is a general concept in the standard library. There are container adaptors, function adaptors, and iterator adaptors. In essence, an adaptor is a mechanism that makes one thing behave like another. A container adaptor takes an existing container type and makes it behave like a different type.

For example, the stack adaptor takes an existing container type and makes it behave like a stack. You can think of it as a stack class implemented on top of some sequential container, with operations such as pop() and push() abstracted out.

The difference between priority_queue and queue is that priority_queue can assign priorities to the elements in the queue. For the specific operational details of stack, queue, and priority_queue, consult the relevant C++ API.

  • Technology