In computing, sequence containers refer to a group of container class templates in the standard library of the C++ programming language that implement storage of data elements. Being templates, they can be used to store arbitrary elements, such as integers or custom classes. One common property of all sequential containers is that the elements can be accessed sequentially. Like all other standard library components, they reside in namespace std.

The following containers are defined in the current revision of the C++ standard: array, vector, list, forward_list, deque. Each of these containers implements different algorithms for data storage, which means that they have different speed guarantees for different operations:^[1]

• array implements a compile-time non-resizable array.
• vector implements an array with fast random access and an ability to automatically resize when appending elements.
• deque implements a double-ended queue with comparatively fast random access.
• list implements a doubly linked list.
• forward_list implements a singly linked list.

Since each of the containers needs to be able to copy its elements in order to function properly, the type of the elements must fulfill CopyConstructible and Assignable requirements.^[2] For a given container, all elements must belong to the same type. For instance, one cannot store data in the form of both char and int within the same container instance.

History

Originally, only vector, list and deque were defined. Until the standardization of the C++ language in 1998, they were part of the Standard Template Library (STL), published by SGI. Alexander Stepanov, the primary designer of the STL, bemoans the choice of the name vector, saying that it comes from the older programming languages Scheme and Lisp but is inconsistent with the mathematical meaning of the term.^[3]

The array container at first appeared in several books under various names. Later it was incorporated into a Boost library, and was proposed for inclusion in the standard C++ library. The motivation for inclusion of array was that it solves two problems of the C-style array: the lack of an STL-like interface, and an inability to be copied like any other object. It firstly appeared in C++ TR1 and later was incorporated into C++11.

The forward_list container was added to C++11 as a space-efficient alternative to list when reverse iteration is not needed.

Properties

array, vector and deque all support fast random access to the elements. list supports bidirectional iteration, whereas forward_list supports only unidirectional iteration.

array does not support element insertion or removal. vector supports fast element insertion or removal at the end. Any insertion or removal of an element not at the end of the vector needs elements between the insertion position and the end of the vector to be copied. The iterators to the affected elements are thus invalidated. In fact, any insertion can potentially invalidate all iterators. Also, if the allocated storage in the vector is too small to insert elements, a new array is allocated, all elements are copied or moved to the new array, and the old array is freed. deque, list and forward_list all support fast insertion or removal of elements anywhere in the container. list and forward_list preserves validity of iterators on such operation, whereas deque invalidates all of them.

Overview of functions

The containers are defined in headers named after the names of the containers, e.g. vector is defined in header <vector>. All containers satisfy the requirements of the Container concept, which means they have begin(), end(), size(), max_size(), empty(), and swap() methods.

Usage example

The following example demonstrates various techniques involving a vector and C++ Standard Library algorithms, notably shuffling, sorting, finding the largest element, and erasing from a vector using the erase-remove idiom.

#include <iostream>
#include <vector>
#include <array>
#include <algorithm> // sort, max_element, random_shuffle, remove_if, lower_bound 
#include <functional> // greater
#include <iterator> // begin, end, cbegin, cend, distance

// used here for convenience, use judiciously in real programs. 
using namespace std;

int main()
{
  array arr{ 1, 2, 3, 4 };

  // initialize a vector from an array
  vector<int> numbers(cbegin(arr), cend(arr));

  // insert more numbers into the vector
  numbers.push_back(5);
  numbers.push_back(6);
  numbers.push_back(7);
  numbers.push_back(8);
  // the vector currently holds { 1, 2, 3, 4, 5, 6, 7, 8 }

  // randomly shuffle the elements
  shuffle(begin(numbers), end(numbers));
  
  // locate the largest element, O(n)
  auto largest = max_element(cbegin(numbers), cend(numbers));
  
  cout << "The largest number is " << *largest << "\n";
  cout << "It is located at index " << distance(largest, cbegin(numbers)) << "\n";
  
  // sort the elements
  sort(begin(numbers), end(numbers));

  // find the position of the number 5 in the vector 
  auto five = lower_bound(cbegin(numbers), cend(numbers), 5);  
  
  cout << "The number 5 is located at index " << distance(five, cbegin(numbers)) << ‘\n’;
  
  // erase all the elements greater than 4   
  numbers.erase(
    remove_if(begin(numbers),
              end(numbers),
              [](auto n) constexpr { return n > 4; });
  
  // print all the remaining numbers
  for (const auto& element : numbers)
    cout << element << " ";
}

The output will be the following:

The largest number is 8
It is located at index 6 (implementation-dependent)
The number 5 is located at index 4
1 2 3 4

References

• William Ford, William Topp. Data Structures with C++ and STL, Second Edition. Prentice Hall, 2002. ISBN 0-13-085850-1. Chapter 4: The Vector Class, pp. 195–203.
• Josuttis, Nicolai M. (1999). The C++ Standard Library. Addison-Wesley. ISBN 0-201-37926-0.

Notes