std::vectorSTL Containers
Dynamic Array
Policy-Based Data Structures (PBDS)STL Containers
Ordered Set / Multiset
Bit ManipulationBitwise & Math
Bitwise Operators & Tricks
Modular ArithmeticBitwise & Math
Modulo Arithmetic Rules
Graph AlgorithmsCheatsheets
Complexities & Properties
C++ CP TemplateTemplates & Compilers
Fast IO & Snippets template
C++ Compiler FlagsTemplates & Compilers
g++ & clang++ commands
std::vector
Dynamic Array
Description
A sequence container that encapsulates dynamic size arrays.
Syntax / Includes
#include <vector> std::vector<int> vec;
Time Complexity
Access: O(1) | Insert/Delete End: O(1) amortized | Insert/Delete Middle: O(N)Space Complexity
O(N) linear space layoutCode Snippet
// Example vector usage
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 2, 3};
v.push_back(4); // Insert at end
std::cout << v[2] << " Size: " << v.size();
return 0;
}Common Mistakes
- Accessing out-of-bounds indexes (vec[i] does not perform boundary checks; use vec.at(i) to throw error).
- Repeatedly inserting at the front of a vector (takes O(N) time; use std::deque instead).
Tips & Tricks
- Use vec.reserve(N) before inserting elements to prevent expensive memory reallocations!
Big-O Complexity Limits Scale
| Input N | O(1) | O(log N) | O(N) | O(N log N) | O(N²) | O(2ⁿ) | O(N!) |
|---|---|---|---|---|---|---|---|
| 10 | 1 | 3 | 10 | 33 | 100 | 1,024 | 3,628,800 |
| 20 | 1 | 4 | 20 | 86 | 400 | 1,048,576 | 2,430,000,000,000,000,000 |
| 50 | 1 | 6 | 50 | 282 | 2500 | 1,120,000,000,000,000 | 30,400,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 |
| 100 | 1 | 7 | 100 | 664 | 10000 | 1,260,000,000,000,000,000,000,000,000,000 | 93,300,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 |