YouTipCpp Vector
In C++, `vector` is one of the most commonly used STL containers.
`vector` is essentially a **dynamically resizable array**. Compared to traditional arrays, vector does not require manual memory management and can automatically resize based on the number of elements.
Since 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, providing very high access efficiency.
* **Random access:** Supports fast element access via subscript with O(1) time complexity.
* **Automatic memory management:** No need for manual malloc/free.
* **Iterator support:** Can be easily used with STL algorithms.
### Why is vector so fast?
Vector elements are arranged contiguously in memory:
This layout is very CPU cache friendly.
When the CPU reads the first element, it typically preloads the subsequent data into the cache as well, so traversing vector is usually very fast.
This is why in many cases:
vector is faster than list
Even though list has theoretically lower deletion complexity.
### Using vector
Before using vector, you need to include the header file:
#include
### Creating vector
Create an empty vector:
std::vectorvec;
Specify initial size:
std::vectorvec(5);
The above code will create 5 elements with default value 0.
Specify initial value:
std::vectorvec(5, 10);
Result:
[10, 10, 10, 10, 10]
Using initializer list:
std::vectorvec = {1, 2, 3, 4};
### Adding Elements
Use `push_back()` to add elements at the end:
vec.push_back(100);
The average time complexity for appending elements at the end of vector is:
O(1)
### Accessing Elements
Using subscript access:
int x = vec;
Using `at()`:
int y = vec.at(1);
Difference:
* `[]` does not check bounds, faster.
* `at()` checks bounds, safer.
### Getting Size
vec.size();
Returns the current number of elements.
### Difference between size and capacity
This is one of the most important concepts of vector.
std::vectorvec; vec.push_back(1); vec.push_back(2); std::cout << vec.size() << std::endl; std::cout << vec.capacity() << std::endl;
Output might be:
24
* **size:** Current number of elements.
* **capacity:** Currently allocated memory capacity.
Capacity is usually greater than or equal to size.
This is because vector allocates more space in advance to reduce frequent resizing.
### vector Resizing Mechanism
When vector space is insufficient, resizing occurs:
1. Allocate larger memory
2. Copy old elements
3. Release old memory
This process is costly.
For example:
std::vectorvec;for (int i = 0; i < 1000000; i++) { vec.push_back(i);}
Multiple memory reallocations may occur.
### reserve() Pre-allocation
To avoid frequent resizing, you can allocate memory in advance:
std::vectorvec; vec.reserve(1000000);
This can reduce:
* Memory reallocation
* Element copying
* Performance loss
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 << " ";}
#### Using Iterator
for (auto it = vec.begin(); it != vec.end(); ++it) { std::cout << *it << " ";}
#### Range-based for Loop
for (int element : vec) { std::cout << element << " ";}
### Deleting Elements
Delete the third element:
vec.erase(vec.begin() + 2);
Note:
When deleting elements in the middle of vector, the subsequent elements will shift forward as a whole.
For example:
1 2 3 4 5After deleting 2: 1 3 4 5
Among them:
3 4 5
All need to be moved.
Therefore:
The time complexity of erase() is O(n)
### Scenarios Where vector is Not Suitable
* Frequent head insertion
* Frequent middle deletion
* Frequent resizing with large objects
For example:
vec.insert(vec.begin(), 100);
This is a relatively slow operation.
### Iterator Invalidation
After vector resizing, the original memory addresses may become invalid.
For example:
std::vectorvec = {1, 2, 3};auto it = vec.begin(); vec.push_back(4); std::cout << *it;
Here `it` may already be invalid.
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
* capacity may still be retained
In other words:
clear() does not necessarily release memory
If you want to release memory:
std::vector().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));
May create temporary objects.
While:
vec.emplace_back("Tom", 20);
Will construct objects in-place directly inside vector.
Usually more efficient.
### Difference between vector and Array
| Feature | Array | vector |
| --- | --- | --- |
| Fixed size | Yes | No |
| Automatic resizing | No | Yes |
| Contiguous memory | Yes | Yes |
| Random access | Fast | Fast |
| STL support | Limited | Complete |
| Safe access | None | at() |
### Common vector Operation Complexity
| Operation | Time Complexity |
| --- | --- |
| Random access | O(1) |
| push_back | Average O(1) |
| Tail deletion | O(1) |
| Head insertion | O(n) |
| Middle deletion | O(n) |
| clear | O(n) |
* * *
## Example: Student Score Management
## Example
#include
#include
#include
int main(){
std::vectorscores ={85, 90, 78, 92};
scores.push_back(88);
std::cout<<"All scores: ";
for(int score : scores){
std::cout<< score <<" ";
}
std::cout<< std::endl;
int total = std::accumulate(scores.begin(), scores.end(), 0);
double average = total *1.0/ scores.size();
std::cout<<"Average score: "<< average << std::endl;
scores.erase(scores.begin()+2);
std::cout<<"Scores after deletion: ";
for(int score : scores){
std::cout<< score <<" ";
}
std::cout<< std::endl;
return 0;
}
Output is as follows:
All scores: 85 90 78 92 88 Average score: 86.6Scores after deletion: 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, you need to pay attention to:
* Performance cost of resizing
* Low efficiency of middle deletion
* Iterator invalidation issues
For the vast majority of sequential storage scenarios:
vector is usually the default container of choice