Sequence Containers

vector

std::vector is a memory-contiguous, variable-length array (also known as a list) data structure provided by the STL. It offers linear complexity for insertion and deletion, and constant complexity for random access.

Why Use vector

As OIers, we prioritize program efficiency far more than engineering-level stability. Since vector handles memory dynamically, its time efficiency can be lower than static arrays in some cases, and even worse when OJ servers may not enable full optimization. Therefore, vector is usually not chosen for normal data storage. Below are several excellent features of vector. When these features are needed, vector can be very helpful.

vector Can Dynamically Allocate Memory

Often we cannot allocate such large space in advance (e.g., precomputing divisors for all numbers from 1 to n). Even if we know the total data volume is within acceptable memory limits, individual data entries can still be very large. In such cases, we need vector to keep memory usage within an appropriate range. vector also supports dynamic expansion, which can be useful when memory is very tight.

vector Overloads Comparison and Assignment Operators

vector overloads six comparison operators, implemented in lexicographical order, allowing us to easily determine whether two containers are equal (complexity linear with container size). For example, we can use vector<char> to implement string comparison (though using std::string is faster and more convenient). Additionally, vector overloads the assignment operator, making array copying more convenient.

Convenient Initialization of vector

Since vector overloads the = operator, we can easily perform whole-vector assignment. Moreover, starting from C++11, vector also supports list initialization, e.g., vector<int> data {1, 2, 3};.

How to Use vector

The following introduces common usages. For detailed information, refer to the C++ documentation.

Constructors

See the following code examples (assuming you have usinged the relevant types from the std namespace):

// 1. Create empty vector; constant complexity
vector<int> v0;
// 1+. This line ensures constant time complexity when inserting the first 3 elements
v0.reserve(3);
// 2. Create a vector with initial size 3; elements default to 0; linear complexity
vector<int> v1(3);
// 3. Create a vector with initial size 3; elements default to 2; linear complexity
vector<int> v2(3, 2);
// 4. Create a vector with initial size 3; 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; same content as v2; linear complexity
vector<int> v4(v2);
// 6. Create a copy v5 of v4; content is {v4[1], v4[2]}; linear complexity
vector<int> v5(v4.begin() + 1, v4.begin() + 3);
// 7. Move v2 to newly created vector v6; no copying; constant complexity; requires C++11
vector<int> v6(std::move(v2));  // or v6 = std::move(v2);

Test Code

// The following is test code; interested readers can compile and run this code.
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;

You can construct a vector using the above methods, which is sufficient for our use.

Element Access

vector provides the following methods for element access:

1. at()

   v.at(pos) returns a reference to the element at index pos. Throws std::out_of_range if out of bounds.

2. operator[]

   v[pos] returns a reference to the element at index pos. No 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 used internally by v.

Iterators

vector provides the following iterators:

1. begin()/cbegin()

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

2. end()/cend()

   Returns an iterator to the placeholder after the last element (note: there is no element there).

3. rbegin()/crbegin()

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

4. rend()/crend()

   Returns a reverse iterator to the position after the last element of the reversed array, corresponding to the position before the first element of the container (no element).

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

Size and Capacity

vector has several functions related to container size and capacity. Note: the size of a vector refers to the number of valid elements, while capacity refers to the actual allocated memory length. For details, see the implementation details later.

Related to size:

• empty() returns a bool value, i.e., v.begin() == v.end(); true if empty, false otherwise.

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

• resize(n) changes the size of vector to n. If n is greater than the current size, elements are appended; if a value to fill is provided in the parameters, that value is used; otherwise, the default value is used. If n is less than the current size, the first n elements are kept, and subsequent elements are removed.

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

  Related to capacity:

• reserve() causes vector to reserve a certain amount of memory space, avoiding unnecessary memory allocation and copying.

• capacity() returns the capacity of the container, i.e., how many elements the current vector has allocated space for.

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

Element Insertion, Deletion, and Modification

• clear() removes all elements.
• insert() supports inserting elements at a certain iterator position; multiple elements can be inserted. Complexity is linear with the distance from pos to the end, not constant.
• erase() deletes elements at a certain iterator or range, returning the iterator after the last deleted element. Complexity same as insert.
• push_back() inserts an element at the end; amortized complexity constant, worst-case linear.
• pop_back() removes the last element; constant complexity.
• swap() exchanges with another container; this operation is constant complexity, not linear.

Implementation Details of vector

The underlying implementation of vector is still a fixed-length array. The reason it can achieve dynamic expansion is by adding operations to avoid overflow. First, note that the number of elements (size) \(n\) in a vector and the number of elements it can contain in allocated memory (capacity) \(N\) are different; vector stores these two quantities separately. When adding elements to vector, if \(n>N\) is detected, the container allocates an array of size \(2N\), copies the old data from the original location to the new array, and then releases the original memory. Although the asymptotic complexity of this operation is \(O(n)\), it can be proven that its amortized complexity is \(O(1)\). Deleting elements at the end and accessing elements remain \(O(1)\) overhead. Therefore, as long as the size of vector is estimated correctly and resize() and reserve() are used properly, the efficiency of vector will not differ much from that of a fixed-length array.

vector<bool>

The standard library provides a specialization for bool in vector, where each "bool" occupies only 1 bit and supports dynamic growth. 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> as alternatives. If you need to save space, directly use bitset.

array (C++11)

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

Why Use array

array is actually the STL's encapsulation of arrays. Compared to vector, it sacrifices dynamic expansion but gains performance almost identical to native arrays (with full optimization enabled). Therefore, if C++11 features are available, almost anywhere a native array can be used, fixed-length arrays can be replaced with array, while dynamically allocated arrays can be replaced with vector.

Member Functions

Implicitly Defined Member Functions

Function	Effect
operator=	Overwrites each element of array with the corresponding element from another array

Element Access

Function	Effect
at	Accesses the specified element with bounds checking
operator[]	Accesses the specified element without bounds checking
front	Accesses the first element
back	Accesses the last element
data	Returns a pointer to the first element in memory

at throws std::out_of_range if pos >= size().

Capacity

Function	Effect
empty	Checks if the container is empty
size	Returns the number of contained elements
max_size	Returns the maximum number of elements that can be contained

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

Operations

Function	Effect
fill	Fills the container with a specified value
swap	Swaps contents

Note: swapping two arrays is \(\Theta(\text{size})\), not \(O(1)\) as with regular STL containers.

Non-member Functions

Function	Effect
operator== etc.	Compares values in array lexicographically
std::get	Accesses an element of array
std::swap	Specialized std::swap algorithm

Below is an example of using array:

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

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

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

deque

std::deque is a double-ended queue data structure provided by the STL. It offers linear complexity for insertion and deletion, and constant complexity for random access.

How to Use deque

The following introduces common usages. For detailed information, refer to the C++ documentation. The iterator functions of deque are the same as those of vector, so they are not detailed here.

Constructors

See the following code (assuming you have usinged the relevant types from the std namespace):

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

Element Access

Same as vector, but cannot access underlying memory. Its efficient element access speed can be referenced in the implementation details.

• at() returns a reference to the element at the specified position, performs bounds checking, constant complexity.
• operator[] returns a reference to the element at the specified position. No bounds checking, constant complexity.
• front() returns a reference to the first element.
• back() returns a reference to the last element.

Iterators

Same as vector.

Size

Same as vector, but lacks reserve() and capacity() functions. (Still has shrink_to_fit().)

Element Insertion, Deletion, and Modification

Same as vector, with additional functions to add elements at the head of the queue.

• clear() removes all elements.
• insert() supports inserting elements at a certain iterator position; multiple elements can be inserted. Complexity linear with the smaller distance from pos to either end.
• erase() deletes elements at a certain iterator or range, returning the iterator after the last deleted element. Complexity same as insert.
• push_front() inserts an element at the head, constant complexity.
• pop_front() removes the head element, constant complexity.
• push_back() inserts an element at the end, constant complexity.
• pop_back() removes the last element, constant complexity.
• swap() exchanges with another container; this operation is constant complexity, not linear.

Implementation Details of deque

The typical underlying implementation of deque is multiple non-contiguous buffers, where memory within each buffer is contiguous. Each buffer also records a head pointer and a tail pointer to mark the range of valid data. When a buffer is full, a new buffer is allocated before or after it to store more data. For a more detailed explanation, refer to 《STL Source Code Analysis》deque implementation principle.

list

std::list is a doubly linked list data structure provided by the STL. It offers linear complexity for random access, and constant complexity for insertion and deletion.

How to Use list

The usage of list is basically the same as deque, but the complexity of insertion, deletion, and access differs. For detailed information, refer to the C++ documentation. The iterator, size, element insertion/deletion/modification functions of list are the same as those of deque, so they are not detailed here.

Element Access

Since list is implemented as a linked list, it does not provide random access interfaces. To access middle elements, iterators must be used.

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

Operations

The list type also provides some STL algorithm functions tailored to its characteristics. Since these algorithms require random access iterators, list provides special implementations for ease of use. These algorithms include splice(), remove(), sort(), unique(), merge(), etc.

forward_list (C++11)

std::forward_list is a singly linked list data structure provided by the STL, which reduces space overhead compared to std::list.

How to Use forward_list

The usage of forward_list is almost identical to list, but its iterators are only forward, so its specific usage is not detailed here. For detailed information, refer to the C++ documentation.

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用