Sequence containers

vector

std::vector is an contiguous-memory, variable-length array (also called a list) data structure provided by the STL. It provides linear-time insertion and deletion, as well as constant-time random access.

Why use vector

As an OIer, the pursuit of program efficiency is far more important than engineering-level stability. Because vector handles memory dynamically, its time efficiency is lower than that of a static array in some cases, and the situation is even worse when the OJ server does not necessarily enable all optimizations. Therefore, vector is usually not chosen for ordinary data storage. Here are several excellent features of vector; when these features are needed, vector can be a great help.

vector can allocate memory dynamically

Often we cannot allocate such a large space in advance (e.g., preprocessing the divisors of every number from 1~n). Although we may know that the total amount of data is within the available space, an individual piece of data may still be very large. In such cases, we need vector to keep memory usage within a suitable range. vector also supports dynamic expansion, which is useful when memory is very tight.

vector overloads comparison and assignment operators

vector overloads six comparison operators, implemented in lexicographic order. This makes it convenient to determine whether two containers are equal (with complexity linear in the container size). For example, vector<char> can be used for string comparison (of course, std::string is still faster and more convenient). In addition, vector overloads the assignment operator, making array copying more convenient.

Convenient initialization of vector

Because vector overloads the = operator, we can conveniently assign to an entire vector. In addition, since C++11, vector has supported list initialization, for example, vector<int> data {1, 2, 3};.

How to use vector

The following introduces common uses; for details, see the C++ documentation.

Constructors

See the following code example (assuming that you have already using-imported the relevant types from the std namespace):

// 1. Create an empty vector; constant complexity
vector<int> v0;
// 1+. This ensures constant time complexity when inserting the first 3 elements into the vector
v0.reserve(3);
// 2. Create a vector with an initial size of 3; its elements default to 0; linear complexity
vector<int> v1(3);
// 3. Create a vector with an initial size of 3; its elements default to 2; linear complexity
vector<int> v2(3, 2);
// 4. Create a vector with an initial size of 3; its elements default to 1,
// and use v2's allocator; linear complexity
vector<int> v3(3, 1, v2.get_allocator());
// 5. Create a copy v4 of v2; its elements have the same contents as v2; linear complexity
vector<int> v4(v2);
// 6. Create a copy v5 of v4; its contents are {v4[1], v4[2]}; linear complexity
vector<int> v5(v4.begin() + 1, v4.begin() + 3);
// 7. Move v2 to the newly created vector v6 without copying; constant complexity; requires C++11
vector<int> v6(std::move(v2));  // or v6 = std::move(v2);

// The following is test code; if interested, compile and run it yourself.
cout << "v1 = ";
copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
cout << endl;
cout << "v2 = ";
copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
cout << endl;
cout << "v3 = ";
copy(v3.begin(), v3.end(), ostream_iterator<int>(cout, " "));
cout << endl;
cout << "v4 = ";
copy(v4.begin(), v4.end(), ostream_iterator<int>(cout, " "));
cout << endl;
cout << "v5 = ";
copy(v5.begin(), v5.end(), ostream_iterator<int>(cout, " "));
cout << endl;
cout << "v6 = ";
copy(v6.begin(), v6.end(), ostream_iterator<int>(cout, " "));
cout << endl;

The methods above are sufficient for constructing a vector for our use.

Element access

vector provides the following methods for accessing elements:

1. at()

   v.at(pos) returns a reference to the element at index pos in the container. If the array index is out of bounds, it throws an exception of type std::out_of_range.

2. operator[]

   v[pos] returns a reference to the element at index pos in the container. It does not perform bounds checking.

3. front()

   v.front() returns a reference to the first element.

4. back()

   v.back() returns a reference to the last element.

5. data()

   v.data() returns a pointer to the first element in the contiguous memory space used to store v's data.

Iterators

vector provides the following iterators:

1. begin()/cbegin()

   Returns an iterator pointing to the first element, where *begin = front.

2. end()/cend()

   Returns an iterator pointing to the placeholder at the end of the container; note that it contains no element.

3. rbegin()/crbegin()

   Returns a reverse iterator pointing to the first element of the reversed array, which can be understood as the last element of the forward container.

4. rend()/crend()

   Returns an iterator pointing to the position after the last element of the reversed array, corresponding to the position before the first element of the container; it contains no element.

Among the iterators listed above, those containing the character c are read-only iterators. You cannot modify the values of elements in a vector through a read-only iterator. If a vector itself is read-only, its ordinary and read-only iterators are completely equivalent. Read-only iterators have been supported since C++11.

Size and capacity

vector has several functions related to container size and capacity. Note that the size of a vector refers to the number of valid elements, while its capacity refers to the length of the memory actually allocated; see the later implementation details for more information.

Related to size:

• empty() returns a bool value, namely v.begin() == v.end(); true means empty and false means non-empty.

• size() returns the container size (number of elements), namely std::distance(v.begin(), v.end()).

• resize(n) changes the length of the vector to n. If n is greater than the current length, elements are added; if an element to add is provided as an argument, that argument is used, otherwise the default value is used. If n is less than the current length, the first n elements are retained and the remaining elements are deleted.

• max_size() returns the maximum possible length of the container.

  Related to capacity:

• reserve() makes the vector reserve a certain amount of memory, avoiding unnecessary memory allocation and copying.

• capacity() returns the capacity of the container, namely the number of elements for which the current vector has allocated space.

• shrink_to_fit() makes the capacity of the vector equal to its size, removing the unused capacity of the vector.

Adding, removing, and modifying elements

• clear() removes all elements
• insert() supports inserting elements at an iterator position, including inserting multiple elements. Its complexity is linear in the distance from pos to the end, rather than constant
• erase() removes an element or a range of elements at an iterator position and returns the iterator of the last element removed. Its complexity is the same as insert.
• push_back() inserts one element at the end, with amortized constant complexity and worst-case linear complexity.
• pop_back() removes the last element, with constant complexity.
• swap() exchanges contents with another container; this operation has constant complexity, not linear complexity.

Implementation details of vector

The underlying implementation of vector is still essentially a fixed-length array. It can dynamically expand because it includes operations that avoid a quantity overflow. First, note that the number of elements (size) $n$ in a vector and the number of elements that its allocated memory can contain at most (capacity) $N$ are different; vector stores these two quantities separately. When an element is added to a vector, if it finds that $n>N$, the container allocates an array of size $2N$, copies the old data from its original location into the new array, and then releases the original memory. Although the asymptotic complexity of this operation is $O(n)$, its amortized complexity can be shown to be $O(1)$. Deleting an element at the end and accessing an element still both cost $O(1)$. Therefore, as long as the size of the vector is estimated appropriately and resize() and reserve() are used well, the efficiency of vector will not differ greatly from that of a fixed-length array.

vector<bool>

The standard library provides a special bool specialization of vector: each “bool” occupies only 1 bit and dynamic growth is supported. However, the return type of its operator[] is not bool& but vector<bool>::reference. Therefore, use vector<bool> with caution; consider using deque<bool> or vector<char> instead. If you need to save space, use bitset directly.

array(C++11)

std::array is a contiguous-memory, fixed-length array data structure provided by the STL. It is essentially a direct wrapper around a native array.

Why use array

array is essentially the STL's wrapper around an array. Compared with vector, it gives up dynamic expansion in exchange for performance almost identical to that of a native array (provided all optimizations are enabled). Therefore, when C++11 features can be used, almost anywhere a native array can be used, a fixed-length array can be directly replaced with array, while dynamically allocated arrays can be replaced with vector.

Member functions

Implicitly defined member functions

Element access

If at encounters pos >= size(), it throws std::out_of_range.

Capacity

Since every array is a fixed-size container, the value returned by size() equals the value returned by max_size().

Operations

Note that swapping two array objects takes $\Theta(\text{size})$ time, rather than $O(1)$ as with ordinary STL containers.

Non-member functions

Here is an example of using an array:

// 1. Create an empty array of length 3; constant complexity
std::array<int, 3> v0;
// 2. Create an array with specified constants; constant complexity
std::array<int, 3> v1{1, 2, 3};

v0.fill(1);  // Fill the array

// Access the array
for (int i = 0; i != arr.size(); ++i) cout << arr[i] << " ";

deque

std::deque is a deque data structure provided by the STL. It provides linear-time insertion and deletion, as well as constant-time random access.

How to use deque

The following introduces common uses; for details, see the C++ documentation. The iterator functions of deque are the same as those of vector, so they are not described in detail.

Constructors

See the following code (assuming that you have already using-imported the relevant types from the std namespace):

// 1. Define an empty deque of int, v0
deque<int> v0;
// 2. Define a deque of int, v1, with an initial size of 10; linear complexity
deque<int> v1(10);
// 3. Define a deque of int, v2, initialized with ten 1s; linear complexity
deque<int> v2(10, 1);
// 4. Copy the existing deque v1; linear complexity
deque<int> v3(v1);
// 5. Create a copy deque v4 of v2, whose contents are v4[0] through v4[2]; linear complexity
deque<int> v4(v2.begin(), v2.begin() + 3);
// 6. Move v2 to the newly created deque v5 without copying; constant complexity; requires C++11
deque<int> v5(std::move(v2));

Element access

The same as vector, but the underlying memory cannot be accessed. Its efficient element access can be understood from the implementation details.

• at() returns a reference to the element at the specified position and performs bounds checking, with constant complexity.
• operator[] returns a reference to the element at the specified position. It does not perform bounds checking, with constant complexity.
• front() returns a reference to the first element.
• back() returns a reference to the last element.

Iterators

The same as vector.

Size

The same as vector, but there are no reserve() or capacity() functions. (The shrink_to_fit() function is still available.)

Adding, removing, and modifying elements

The same as vector, with an additional function for adding elements to the front of the deque.

• clear() removes all elements
• insert() supports inserting elements at an iterator position, including inserting multiple elements. Its complexity is linear in the smaller of the distances from pos to the two ends.
• erase() removes an element or a range of elements at an iterator position and returns the iterator of the last element removed. Its complexity is the same as insert.
• push_front() inserts one element at the front, with constant complexity.
• pop_front() removes the first element, with constant complexity.
• push_back() inserts one element at the end, with constant complexity.
• pop_back() removes the last element, with constant complexity.
• swap() exchanges contents with another container; this operation has constant complexity, not linear complexity.

Implementation details of deque

The usual underlying implementation of deque consists of multiple discontinuous buffers, while the memory within each buffer is contiguous. Each buffer also records a head pointer and a tail pointer to mark the range of valid data. Once a buffer is full, a new buffer is allocated before or after it to store more data. For a more detailed explanation, see the implementation principles of deque in STL Source Code Analysis.

list

std::list is a doubly linked list data structure provided by the STL. It provides linear-time random access and constant-time insertion and deletion.

How to use list

The usage of list is basically the same as that of deque, but the complexities of insertion, deletion, and access differ. For details, see the C++ documentation. The iterator, size, and element insertion, deletion, and modification functions of list are the same as those of deque, so they are not described in detail.

Element access

Because list is implemented as a linked list, it does not provide a random-access interface. To access an element in the middle, an iterator is required.

• front() returns a reference to the first element.
• back() returns a reference to the last element.

Operations

The list type also provides several STL algorithm functions implemented for its characteristics. Because these algorithms require random-access iterators, list provides special implementations for convenient use. These algorithms include splice(), remove(), sort(), unique(), and merge().

forward_list（C++11）

std::forward_list is a singly linked list data structure provided by the STL, reducing space overhead compared with std::list.

How to use forward_list

The usage of forward_list is almost identical to that of list, but its iterators are only unidirectional, so its specific usage is not described in detail. For details, see the C++ documentation