C++ vector container

In C++,vectorIt is one of the most commonly used STL containers.

vectorEssentially it is aA dynamic array that can automatically expand.Compared with traditional arrays, vector does not require manual memory management and can automatically expand according to the number of elements.

Because vector has:

• Contiguous memory storage
• Fast random access
• Complete STL ecosystem
• Cache friendly

Therefore, in modern C++ development, vector is the preferred choice for most sequential data storage scenarios.

Core features of vector

• Dynamic size:vector can automatically expand and shrink.
• Contiguous memory:Elements are stored contiguously in memory, so access efficiency is very high.
• Random access:It supports fast access to elements by index, with a time complexity of O(1).
• Automatic memory management:No need to manually malloc/free.
• Supports iterators:It can be easily used together with STL algorithms.

Why is vector fast?

The elements of a vector are arranged contiguously in memory:

[1][2][3][4][5]

This layout is very friendly to the CPU cache.

When the CPU reads the first element, it usually prefetches the following data into the cache in advance, so iterating over a vector is usually very fast.

This is also why in many cases:

vector 比 list 更快

Even though list has a lower theoretical deletion complexity.

Using vector

Before using vector, you need to include the header file:

#include <vector>

Creating vector

Create an empty vector:

std::vector<int>vec;

Specify initial size:

std::vector<int>vec(5);

The above code creates 5 elements with the default value of 0.

Specify initial value:

std::vector<int>vec(5, 10);

Creation result:

[10, 10, 10, 10, 10]

Use an initializer list:

std::vector<int>vec = {1, 2, 3, 4};

Adding elements

Usagepush_back()Add elements to the tail:

vec.push_back(100);

The average time complexity of appending an element to the end of a vector is:

O(1)

Access Elements

Access using subscripts:

int x = vec[0];

Usageat()：

int y = vec.at(1);

Difference:

• []No bounds checking, faster.
• at()Bounds checking is performed, safer.

Getting size

vec.size();

Returns the current number of elements.

The difference between size and capacity

This is one of the most important concepts of vector.

std::vector<int>vec;

vec.push_back(1);
vec.push_back(2);

std::cout << vec.size() << std::endl;
std::cout << vec.capacity() << std::endl;

The output may be:

2
4

• size：Current number of elements.
• capacity：The currently allocated memory capacity.

capacity is usually greater than or equal to size.

This is because vector requests more space in advance to reduce frequent reallocations.

vector expansion mechanism

When the capacity of a vector is insufficient, reallocation occurs:

1. Allocate larger memory
2. Copy old elements
3. Release old memory

This process is relatively costly.

For example:

std::vector<int>vec;

for (int i = 0; i < 1000000; i++) {
    vec.push_back(i);
}

Multiple memory reallocations may occur.

reserve() pre-allocates space.

To avoid frequent reallocations, memory can be allocated in advance:

std::vector<int>vec;

vec.reserve(1000000);

This can reduce:

• Memory reallocation
• Element copying
• Performance overhead

This is a very important optimization technique in engineering development.

Traversing vector

Using subscript

for (size_t i = 0; i < vec.size(); i++) {
    std::cout << vec[i] << " ";
}

Using iterators

for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";
}

Range-based for loop

for (int element : vec) {
    std::cout << element << " ";
}

Delete element

Delete the third element:

vec.erase(vec.begin() + 2);

Note:

When a vector deletes an element in the middle, the subsequent elements are shifted forward as a whole.

For example:

1 2 3 4 5

删除 2 后：

1 3 4 5

Where:

3 4 5

All need to be moved.

Therefore:

erase() 的时间复杂度为 O(n)

Scenarios where vector is not suitable

• Frequent head insertion
• Frequent middle deletion
• Frequent expansion with oversized objects

For example:

vec.insert(vec.begin(), 100);

This is a relatively slow operation.

Iterator invalidation

After vector reallocation, the original memory addresses may become invalid.

For example:

std::vector<int>vec = {1, 2, 3};

auto it = vec.begin();

vec.push_back(4);

std::cout << *it;

hereitMay have been invalidated.

Because push_back() may cause memory reallocation.

This is one of the most common pitfalls of vector.

Notes on clear()

vec.clear();

clear() only clears the elements:

• size becomes 0
• The capacity may still be retained.

That is:

clear() 不一定释放内存

If you want to release memory:

std::vector<int>().swap(vec);

Or:

vec.shrink_to_fit();

push_back and emplace_back

Modern C++ recommends using:

emplace_back()

For example:

vec.push_back(Person("Tom", 20));

Temporary objects may be created.

And:

vec.emplace_back("Tom", 20);

It constructs the object directly in place inside the vector.

Usually more efficient.

Differences between vector and array

Complexity of common vector operations

Example: Student grade management

The output result is as follows:

所有成绩: 85 90 78 92 88 
平均成绩: 86.6
删除后成绩: 85 90 92 88 

Summary

vector is one of the most important and commonly used data structures in modern C++.

Its core advantages:

• Dynamic resizing
• Contiguous memory
• Fast random access
• Cache-friendly
• Complete STL ecosystem

But at the same time, note that:

• Performance cost of expansion
• Low efficiency of middle deletion
• Iterator invalidation issue

For the vast majority of sequential storage scenarios:

vector 通常都是默认首选容器