Understanding the C++ Standard Library Type: vector

The standard library type vector represents a collection of objects, all of the same type. Each object in the collection has a corresponding index, which is used to access the object. Because vector contains other objects, it is also referred to as a container.

1.<span>vector</span> Basics

1.1 <span>vector</span> Overview: Core Features

<span>vector</span> (commonly translated as “vector” in Chinese) is essentially a template class (requiring specification of the type of elements stored) that encapsulates the following core features:

• Contiguous Memory Elements are stored in contiguous memory space, supporting random access via index (<span>[]</span>) with a time complexity of O(1), consistent with traditional arrays.
• Dynamic Resizing No need to specify a fixed size at initialization; capacity can be automatically adjusted based on the number of elements added (when memory is insufficient, a larger memory block is requested, original elements are copied, and old memory is released).
• On-Demand Allocation Memory is allocated only when elements are added, avoiding memory waste (traditional arrays occupy a fixed size of memory even if only one element is stored).
• Supports Generics Can store elements of any type (such as <span>int</span>, <span>double</span>, <span>string</span>, or even user-defined class objects), but a single <span>vector</span> can only store elements of the same type.

In simple terms: <span>vector</span> is a “smart dynamic array” that is similar to an array but more flexible and safer.

1.2 Preparation for Use: Header Files and Namespaces

<span>vector</span> belongs to the C++ standard library, and two conditions must be met before use:

Include Header File<span>vector</span> is defined in the header file <span><vector></span>, which must be explicitly included:

#include <vector>  // Must include, otherwise cannot use vector

Specify Namespace<span>vector</span> is under the <span>std</span> namespace, and must be accessed using one of the following two methods:

• Global Declaration: <span>using namespace std;</span> (recommended for simple scenarios, such as example code);
• Local Qualification: <span>std::vector</span> (recommended for large projects to avoid naming conflicts).

#include <iostream>#include <vector>  // Include vector header fileusing namespace std;int main() {    vector<int> vec;  // Define a vector that stores int type elements    return 0;}

1.3 Key Concepts: <span>vector</span> ‘Size’ vs ‘Capacity’

<span>vector</span> has two easily confused concepts – size and capacity, which are core to understanding its dynamic resizing mechanism:

• Size<span>vector</span> refers to the current number of stored elements, which can be obtained through the <span>size()</span> member function.
• Capacity<span>vector</span> refers to the maximum number of elements that the underlying memory can hold (without needing to resize), which can be obtained through the <span>capacity()</span> member function.

• When <span>size == capacity</span>, adding more elements will trigger resizing: <span>vector</span> will request a larger memory block (usually double the original capacity, though this may vary by compiler), copy the original elements to the new memory, release the old memory, and then add the new element.
• Resizing incurs performance overhead (memory allocation + element copying), so if the number of elements can be estimated, using <span>reserve(n)</span> to specify capacity in advance can reduce the number of resizes and improve efficiency.

2.<span>vector</span> Creation: Six Initialization Methods

<span>vector</span> supports various initialization methods, which should be chosen based on whether “elements are known” and “size is known”. The following are sorted by “common usage” and explained with examples:

Initialization Method	Syntax Example	Core Explanation	Applicable Scenarios
Default Initialization	<span>vector<T> vec;</span>	Creates an empty<span>vector</span> (size=0, capacity=0 or default value, no elements), subsequent elements can be added using <span>push_back()</span>.	Unknown number of elements, dynamic addition.
Size + Default Value Initialization	<span>vector<T> vec(n, val);</span>	Creates a <span>vector</span> containing <span>n</span> elements, each initialized to <span>val</span> (where <span>T</span> is the element type).	Known number of elements, all with the same initial value.
List Initialization (<span>{}</span>)	<span>vector<T> vec{val1, val2, val3};</span>	New in C++11, creates a <span>vector</span> containing specified elements, in the order of the list.	All element values and order are known.
Copy Initialization (<span>=</span>)	<span>vector<T> vec = {val1, val2};</span>	Equivalent to list initialization (the <span>=</span> can be omitted, using <span>{}</span> directly), essentially copying the elements from the list.	Uniform style, consistent with <span>string</span> initialization logic.
Copy Other<span>vector</span>	<span>vector<T> vec(other_vec);</span>	Creates a <span>vector</span> that is a copy of <span>other_vec</span> (elements are identical, size and capacity may be the same or different).	Need to reuse all elements of another <span>vector</span>.
Iterator Range Initialization	<span>vector<T> vec(beg, end);</span>	Initializes using elements from the range defined by iterators <span>[beg, end)</span> (where <span>beg</span> and <span>end</span> can come from a <span>vector</span>, array, or <span>string</span>).	Need to use a portion of elements from another container/array.

Example: Effects of Various Initialization Methods

#include <iostream>#include <vector>#include <string>using namespace std;int main() {    // 1. Default Initialization: empty vector (size=0, capacity=0)    vector<int> vec1;    // 2. Size + Default Value: 5 elements, each 10 (size=5, capacity=5)    vector<int> vec2(5, 10);    // 3. List Initialization: elements are 1, 2, 3 (size=3, capacity=3)    vector<int> vec3{1, 2, 3};    // 4. Copy Initialization: same as vec3 (size=3, capacity=3)    vector<int> vec4 = {1, 2, 3};    // 5. Copy Other Vector: vec5 is a copy of vec3 (size=3, capacity=3)    vector<int> vec5(vec3);    // 6. Iterator Range Initialization: initializes vec6 with elements from vec3's [vec3.begin()+1, vec3.end()) (i.e., 2, 3)    vector<int> vec6(vec3.begin() + 1, vec3.end());    // Output verification    cout << "vec2: ";    for (int x : vec2) cout << x << " ";  // Output: 10 10 10 10 10    cout << "\nvec6: ";    for (int x : vec6) cout << x << " ";  // Output: 2 3    return 0;}

Pitfall: Distinguishing between “Size Initialization” and “List Initialization” Syntax Differences – <span>vector<int> vec(5, 10)</span> means “5 of 10”, while <span>vector<int> vec{5, 10}</span> means “two elements 5 and 10”; the type of brackets determines the initialization logic and should not be confused.

3.<span>vector</span> Core Operations

3.1 Element Access: Four Methods (Indexing, <span><span>at()</span></span><span><span>, </span></span><code><span><span>front()</span></span><span><span>, </span></span><code><span><span>back()</span></span><span><span>)</span></span>

<span>vector</span> supports multiple ways to access elements, which should be chosen based on “access location” and “safety requirements”:

(1) Index Operator<span>[]</span> (recommended, efficient)

• Syntax: <span>vec[index]</span>, returns the element at index <span>index</span> in the <span>vector</span> (readable and writable, supports modifying elements).
• Rules:
• The index <span>index</span> must be within the valid range (0 ≤ index < vec.size()), otherwise it triggers “undefined behavior” (program crash, garbage output).
• No out-of-bounds checking is performed, making it efficient, similar to traditional arrays.

vector<int> vec{10, 20, 30};cout << vec[0] << endl;  // Output 10 (accessing the first element)vec[1] = 200;            // Modify the second element to 200, vec becomes {10, 200, 30}// cout << vec[3];       // Error: index=3 exceeds size=3, undefined behavior

(2) Member Function <span><span>at()</span></span><span><span> (safe, slightly slower)</span></span>

• Syntax: <span>vec.at(index)</span>, functions the same as <span>[]</span>, but will check for out-of-bounds.
• Rules: If <span>index</span> is invalid, it will throw an <span>out_of_range</span> exception (which needs to be caught using <span>try-catch</span>, explained in later chapters on exceptions), preventing the program from crashing directly.

vector<int> vec{10, 20, 30};cout << vec.at(2) << endl;  // Output 30 (accessing the third element)vec.at(0) = 100;            // Modify the first element to 100, vec becomes {100, 20, 30}// vec.at(3);             // Throws out_of_range exception (with out-of-bounds check)

(3)<span><span>front()</span></span> and <span><span>back()</span></span> (Accessing First and Last Elements)

• Syntax:
• <span>vec.front()</span> returns the first element of the <span>vector</span> (readable and writable).
• <span>vec.back()</span> returns the last element of the <span>vector</span> (readable and writable).
• Rules: Must ensure that the <span>vector</span> is not empty (size > 0), otherwise accessing an empty <span>vector</span> with <span>front()</span> or <span>back()</span> will trigger undefined behavior.

vector<string> vec{"hello", "world"};cout << vec.front() << endl;  // Output "hello" (first element)cout << vec.back() << endl;   // Output "world" (last element)vec.back() = "C++";           // Modify the last element, vec becomes {"hello", "C++"}

Usage Recommendations: Use <span>[]</span> for daily development (efficient), and if the index comes from user input or other uncertain scenarios, use <span>at()</span> (safe); prefer using <span>front()</span>/<span>back()</span> for accessing first and last elements (for clearer code).

3.2 Dynamic Modification: Adding, Deleting, and Clearing Elements

(1) Adding Elements: <span><span>push_back()</span></span> (Adding to the End, Most Common)

• Syntax: <span>vec.push_back(val)</span>, adds an element <span>val</span> to the end of the vector.
• Rules:
• If <span>size < capacity</span>: directly adds, no need for resizing, high efficiency.
• If <span>size == capacity</span>: triggers resizing (allocates new memory → copies original elements → releases old memory → adds new element), incurs performance overhead.

vector<int> vec;  // Default initialization, empty vector (size=0, capacity=0)vec.push_back(10); // Add 10, size=1, capacity=1 (first addition, resized to 1)vec.push_back(20); // Add 20, size=2, capacity=2 (size==capacity, resized to 2)vec.push_back(30); // Add 30, size=3, capacity=4 (size==capacity, resized to 4)// Final vec: {10, 20, 30}, size=3, capacity=4

(2) Deleting Elements:<span><span>pop_back()</span></span> (Deleting from the End)

• Syntax: <span>vec.pop_back()</span>, deletes the last element of the <span>vector</span>.
• Rules:
• Only deletes the element, does not release memory (capacity remains unchanged, size decreases by 1).
• Must ensure that the <span>vector</span> is not empty (size > 0), otherwise deleting from an empty <span>vector</span> will trigger undefined behavior.

vector<int> vec{10, 20, 30};  // size=3, capacity=3vec.pop_back();               // Deletes the last element 30, size=2, capacity=3// Final vec: {10, 20}, size=2, capacity=3 (memory not released)

(3) Clearing Elements:<span><span>clear()</span></span> (Clearing All Elements)

• Syntax: <span>vec.clear()</span>, deletes <span>all elements</span> of the <span>vector</span>.
• Rules:
• Only clears elements (size=0), does not release memory (capacity remains unchanged), avoiding the need to resize when adding elements later.
• If memory needs to be released simultaneously, the “swap trick” can be used: <span>vector<T>().swap(vec);</span> (creates a temporary empty <span>vector</span>, swaps memory with the original <span>vector</span>, and the temporary object is destroyed, releasing memory).

vector<int> vec{10, 20, 30};  // size=3, capacity=3vec.clear();                  // Clears all elements, size=0, capacity=3 (memory not released)vector<int>().swap(vec);      // Releases memory, size=0, capacity=0

(4) Inserting Elements:<span><span>insert()</span></span> (Inserting at Any Position, Use with Caution)

• Syntax: <span>vec.insert(pos, val)</span>, inserts an element <span>val</span> at the position pointed to by the iterator <span>pos</span> (subsequent elements are shifted).
• Rules:
• The insertion position must be a valid iterator (such as <span>vec.begin()</span> or <span>vec.end()</span>).
• May trigger resizing (if <span>size == capacity</span>), and shifting subsequent elements incurs performance overhead (time complexity O(n)), so frequent insertions are not recommended with <span>vector</span> (recommended to use <span>list</span>, explained in later chapters).

vector<int> vec{10, 30};  // size=2, capacity=2// Insert 20 after the first element (iterator points to vec.begin()+1)vec.insert(vec.begin() + 1, 20);// Final vec: {10, 20, 30}, size=3, capacity=4 (triggered resizing)

3.3 Querying Properties:<span><span>size()</span></span>, <span><span>capacity()</span></span>, <span><span>empty()</span></span>

• <span>size()</span> returns the current number of elements in the <span>vector</span> (of type <span>size_t</span>, an unsigned integer).
• <span>capacity()</span> returns the maximum number of elements that the underlying memory can hold (of type <span>size_t</span>).
• <span>empty()</span> checks whether the <span>vector</span> is empty (i.e., <span>size == 0</span>), returning a <span>bool</span> value (i.e., <span>true</span> if empty, <span>false</span> if not empty), which is more efficient than <span>size() == 0</span> (directly checking a flag, no calculation needed).

vector<int> vec{10, 20, 30};cout << "size: " << vec.size() << endl;       // Output size: 3cout << "capacity: " << vec.capacity() << endl; // Output capacity: 3cout << "is empty: " << vec.empty() << endl;  // Output is empty: 0 (false)vec.pop_back();cout << "size: " << vec.size() << endl;       // Output size: 2cout << "capacity: " << vec.capacity() << endl; // Output capacity: 3cout << "is empty: " << vec.empty() << endl;  // Output is empty: 0 (false)

4.<span>vector</span> Traversal: Three Methods (Range for, Indexing, Iterators)

4.1 Range for Loop (New in C++11, Recommended)

• Syntax: <span>for (declaration : vec)</span>, traverses all elements of the <span>vector</span>, without needing to manually manage indices or iterators, making the code the simplest.
• Rules:
• If you need to modify elements: <span>declaration</span> must be a reference (<span>auto &x</span>).
• If you only need to read elements: use <span>const auto &x</span> (to avoid copying, which is more efficient) or <span>auto x</span> (for simple scenarios).

vector<int> vec{10, 20, 30};// 1. Reading elements (const reference, efficient)cout << "Reading elements:";for (const auto &x : vec) {    cout << x << " ";  // Output: 10 20 30}// 2. Modifying elements (reference)for (auto &x : vec) {    x *= 2;  // Each element multiplied by 2, vec becomes {20, 40, 60}}// 3. Output modified elementscout << "\nAfter modification:";for (auto x : vec) {    cout << x << " ";  // Output: 20 40 60}

4.2 Index Traversal (Similar to Traditional Arrays)

• Syntax: Use a <span>for</span> loop to traverse indices (from 0 to <span>vec.size()-1</span>), accessing elements via <span>vec[index]</span>, suitable for scenarios where indices are needed (e.g., to get element positions).
• Note: <span>vec.size()</span> returns <span>size_t</span> (unsigned), avoid mixing with <span>int</span> (e.g., <span>for (int i = 0; i < vec.size(); ++i)</span> is safe, but <span>for (int i = vec.size()-1; i >= 0; --i)</span> will cause an infinite loop when <span>vec</span> is empty due to <span>size_t</span> converting to <span>int</span>).

vector<string> vec{"hello", "world", "C++"};// Traverse indices, output elements and indicesfor (size_t i = 0; i < vec.size(); ++i) {    cout << "Index " << i << ": " << vec[i] << endl;}// Output:// Index0: hello// Index1: world// Index2: C++

4.3 Iterator Traversal (Universal, Compatible with STL)

• Syntax: Use the <span>vector</span> iterators (<span>begin()</span>/<span>end()</span>) to traverse, supporting any starting/ending position, and compatible with STL algorithms (such as <span>sort</span>, <span>find</span>, explained in later chapters).
• Iterator Types:
• Normal Iterator (<span>vector<T>::iterator</span>): can read and write elements.
• Constant Iterator (<span>vector<T>::const_iterator</span>): can only read elements (suitable for <span>const vector</span>).

vector<int> vec{10, 20, 30};// 1. Normal Iterator (modifying elements)vector<int>::iterator it1;for (it1 = vec.begin(); it1 != vec.end(); ++it1) {    *it1 += 5;  // Each element plus 5, vec becomes {15, 25, 35}}// 2. Constant Iterator (reading elements, using auto to simplify type)cout << "Iterator traversal:";for (auto it2 = vec.cbegin(); it2 != vec.cend(); ++it2) {    cout << *it2 << " ";  // Output: 15 25 35 (cbegin()/cend() returns constant iterators)}

5.<span>vector</span> Pitfall Guide

5.1 Pitfall 1: Accessing Elements of an Empty <span><span>vector</span></span>

• Problem: Using <span>[]</span>, <span>at()</span>, <span>front()</span>, or <span>back()</span> on an empty <span>vector</span> (size=0) will trigger undefined behavior or throw an exception.
• Solution: Check if the <span>vector</span> is non-empty using <span>empty()</span> before accessing:

vector<int> vec;if (!vec.empty()) {  // Check if non-empty    cout << vec[0] << endl;  // Safe}

5.2 Pitfall 2:<span><span>size_t</span></span> and <span><span>int</span></span> Mixing Leading to Infinite Loops

• Problem: <span>vec.size()</span> returns <span>size_t</span> (unsigned integer), mixing it with <span>int</span> (signed) can lead to logical errors (e.g., <span>vec.size()-1</span> becomes a large value when <span>vec</span> is empty).

vector<int> vec;  // Empty vector, size=0// Infinite loop: i initialized to vec.size()-1 (0-1=4294967295, unsigned max value), i >= 0 always truefor (int i = vec.size() - 1; i >= 0; --i) {    cout << vec[i];}

Solution: Use <span>size_t</span> as the index type, or traverse backwards using iterators:

// Correct: Use size_t as the index typevector<int> vec{10, 20, 30};for (size_t i = vec.size() - 1; i < vec.size(); --i) {    cout << vec[i] << " ";  // Output: 30 20 10 (i decreases to 0, then decreases to size_t max value, not satisfying i < vec.size(), loop ends)}// More recommended: Use reverse iteratorsfor (auto it = vec.rbegin(); it != vec.rend(); ++it) {    cout << *it << " ";  // Output: 30 20 10}

5.3 Pitfall 3: Invalidating Iterators (Iterators Become Invalid After Resizing)

• Problem: When <span>vector</span> resizes (when <span>size == capacity</span>, adding elements triggers this), the underlying memory address changes, and existing iterators (pointing to old memory) become “dangling pointers” (invalid), using invalid iterators will trigger undefined behavior.

vector<int> vec{10, 20};  // size=2, capacity=2auto it = vec.begin();    // Iterator points to the first element (old memory)vec.push_back(30);        // Triggers resizing (capacity changes to 4, memory address changes, it becomes invalid)// cout << *it;           // Error: it is invalid, undefined behavior

• Solution:
• Reacquire iterators after resizing (e.g., <span>it = vec.begin()</span>).
• Use <span>reserve(n)</span> in advance to specify capacity, avoiding resizing (if the number of elements can be estimated).

5.4 Pitfall 4: Frequent Insertions/Deletions in the Middle

• Problem: <span>vector</span> uses contiguous memory, inserting/deleting elements in the middle causes subsequent elements to shift (time complexity O(n)), frequent operations can severely impact performance.
• Solution: If frequent insertions/deletions in the middle are needed, it is recommended to use <span>list</span> (doubly linked list, insertion/deletion time complexity O(1)); if <span>vector</span> must be used, try to concentrate operations (e.g., collect all elements to be inserted first, then insert them all at once).

Summary

1. Basic Understanding<span>vector</span> is a dynamic array container, storing in contiguous memory, supporting random access and automatic resizing, requiring the inclusion of the <span><vector></span> header file and specification of the <span>std</span> namespace.
2. Core Operations

• Creation Choose default initialization, list initialization, or size + default value initialization based on whether the number of elements is known.
• Access<span>[]</span> is efficient, <span>at()</span> is safe, and <span>front()</span>/<span>back()</span> access the first and last elements.
• Modification<span>push_back()</span> adds to the end (commonly used), <span>pop_back()</span> deletes from the end, and <span>clear()</span> clears elements (does not release memory).
• Traversal Range for (concise), indexing (requires indices), iterators (universal, compatible with STL).

Key Concepts Distinguish between <span>size</span> (number of elements) and <span>capacity</span> (capacity), resizing incurs performance overhead, and using <span>reserve(n)</span> in advance can optimize.

Pitfall Focus Check for non-empty before accessing, avoid mixing <span>size_t</span> with <span>int</span>, be aware of iterator invalidation, and avoid frequent insertions/deletions in the middle.