If you learn only one STL container, make it std::vector. It is a dynamic array: it stores elements next to each other in memory just like a normal array, so indexing is instant, but it can grow and shrink at run time and it manages its own memory. No new[], no delete[], no fixed size decided in advance.
In Arrays we saw that a built-in array's size is fixed at compile time, and in Dynamic Memory Allocation we saw how painful (and leak-prone) it is to resize a heap array by hand. vector does that work for you, correctly and efficiently. In Introduction to the STL we called it the default container; in this chapter we learn how to use it and, just as important, how it works inside, because that explains its performance and its traps.
What Is a vector?
std::vector<T>is a sequence container, declared in<vector>, that stores elements of typeTin one contiguous block of dynamically allocated memory, resizing automatically as elements are added.
A vector object itself is small. In typical implementations (such as GCC's libstdc++) it holds just three pointers: the start of the buffer, the end of the used part, and the end of the allocated part. The elements live on the heap:
std::vector<int> v (on the stack, 24 bytes on a 64-bit system)
┌─────────┬─────────┬─────────┐
│ begin │ end │ cap_end │
└────┬────┴────┬────┴────┬────┘
│ │ │
▼ ▼ ▼
┌────┬────┬────┬────┬────┬────┐ heap buffer
│ 10 │ 20 │ 30 │ 40 │ │ │
└────┴────┴────┴────┴────┴────┘
◀──── size() = 4 ────▶
◀──────── capacity() = 6 ────────▶Two numbers describe every vector:
size: how many elements it currently holds.
capacity: how many elements fit in the memory already allocated, so
capacity() ≥ size()always.
The gap between them is spare room that lets push_back be fast most of the time. When the destructor runs, the vector destroys its elements and frees the buffer automatically. This is the RAII idea from Constructors & Destructors, and it is why vectors do not leak.
Creating a vector
#include <iostream>
#include <vector>
#include <string>
void show(const std::string& label, const std::vector<int>& v) {
std::cout << label << " (size " << v.size() << "): ";
for (int x : v) std::cout << x << ' ';
std::cout << '\n';
}
int main() {
std::vector<int> a; // empty
std::vector<int> b(4); // 4 elements, value-initialized to 0
std::vector<int> c(4, 7); // 4 elements, each 7
std::vector<int> d = {1, 2, 3}; // initializer list (C++11)
std::vector<int> e(d); // copy of d
std::vector<int> f(d.begin() + 1, d.end()); // from an iterator range
std::vector g{5, 6}; // C++17 CTAD: deduced as vector<int>
show("a", a);
show("b", b);
show("c", c);
show("d", d);
show("e", e);
show("f", f);
show("g", g);
std::vector<int> p(3, 9); // parentheses: 3 copies of 9
std::vector<int> q{3, 9}; // braces: two elements, 3 and 9
show("p", p);
show("q", q);
}Output:
a (size 0):
b (size 4): 0 0 0 0
c (size 4): 7 7 7 7
d (size 3): 1 2 3
e (size 3): 1 2 3
f (size 2): 2 3
g (size 2): 5 6
p (size 3): 9 9 9
q (size 2): 3 9 Points to notice:
std::vector<int> b(4)creates four elements that are value-initialized, which means 0 for numbers. Unlike a local built-in array, a vector never holds garbage values.std::vector g{5, 6}works without writing<int>because of class template argument deduction (C++17), introduced in Templates.Parentheses vs braces is a famous trap:
p(3, 9)means "3 copies of 9", whileq{3, 9}means "the two elements 3 and 9". Braces prefer the initializer-list constructor whenever it can be used.
Adding, Accessing and Removing at the End
#include <iostream>
#include <vector>
#include <string>
#include <stdexcept>
int main() {
std::vector<std::string> names;
names.push_back("Asha"); // a string is created, then moved in
names.emplace_back("Bilal"); // the string is constructed in place
names.emplace_back(3, 'z'); // calls string(3, 'z') -> "zzz"
std::cout << "front: " << names.front() << '\n';
std::cout << "back : " << names.back() << '\n';
std::cout << "names[1]: " << names[1] << '\n';
names[2] = "Chitra"; // modify through operator[]
names.pop_back(); // removes "Chitra"
std::cout << "size after pop_back: " << names.size() << '\n';
try {
std::cout << names.at(5) << '\n'; // at() checks the index
} catch (const std::out_of_range& e) {
std::cout << "out_of_range caught\n";
}
std::cout << std::boolalpha << "empty? " << names.empty() << '\n';
}Output:
front: Asha
back : zzz
names[1]: Bilal
size after pop_back: 2
out_of_range caught
empty? false| Member | Does | Cost |
|---|---|---|
push_back(x) | Adds a copy of x (or moves it, if x is a temporary) at the end | O(1) amortized |
emplace_back(args...) | Constructs a new element at the end directly from args (C++11; returns a reference to it since C++17) | O(1) amortized |
pop_back() | Removes the last element (undefined behavior if empty) | O(1) |
v[i] | Element i, no bounds check; out of range is undefined behavior | O(1) |
v.at(i) | Element i with bounds check; throws std::out_of_range | O(1) |
front() / back() | First / last element (undefined behavior if empty) | O(1) |
size(), empty() | Number of elements; whether it is zero | O(1) |
push_back vs emplace_back: push_back needs an already-made object; emplace_back forwards its arguments to the element's constructor and builds it directly inside the vector, as in emplace_back(3, 'z'), which no push_back call could accept. For simple values like int there is no difference. The at() exception is caught exactly as shown in Exception Handling.
How a vector Grows: size vs capacity
What happens when you push_back into a full vector? The vector cannot just extend its block, because the memory after it may belong to someone else. So it reallocates:
Allocate a new, bigger block.
Move (or copy) all existing elements into the new block.
Construct the new element.
Destroy the old elements and free the old block.
Let us watch the capacity change:
#include <iostream>
#include <vector>
int main() {
std::vector<int> v;
std::size_t lastCap = v.capacity();
std::cout << "size 0, capacity " << lastCap << '\n';
for (int i = 1; i <= 100; ++i) {
v.push_back(i);
if (v.capacity() != lastCap) { // a reallocation just happened
lastCap = v.capacity();
std::cout << "size " << v.size() << ", capacity " << lastCap << '\n';
}
}
}Output (GCC / libstdc++):
size 0, capacity 0
size 1, capacity 1
size 2, capacity 2
size 3, capacity 4
size 5, capacity 8
size 9, capacity 16
size 17, capacity 32
size 33, capacity 64
size 65, capacity 128With GCC the capacity doubles each time. The exact growth factor is not fixed by the standard: Microsoft's library grows by about 1.5×, for example. What the standard does require is that push_back takes amortized constant time, and that is only possible with geometric growth (multiplying by a factor), never with "add 10 more slots each time".
Why is push_back amortized O(1)?
A single reallocation copies all n elements, which is O(n). But it happens rarely. With doubling, inserting n elements causes copies of 1 + 2 + 4 + … elements, each term a power of two smaller than n, and such a sum is always less than 2n. So n pushes cost at most n (constructing the new elements) + 2n (all the copying), that is under 3n element operations: O(1) per push on average. "Amortized" means averaged over a sequence of operations; one particular push can still be O(n).
pushes: 1 2 3 4 5 6 7 8 9 ...
copies: 0 1 2 0 4 0 0 0 8 ... (copy happens only when full)
capacity: 1 2 4 4 8 8 8 8 16 ...
total copies for n = 9 pushes: 1 + 2 + 4 + 8 = 15 < 2 × 9reserve, resize, shrink_to_fit, clear
#include <iostream>
#include <vector>
int main() {
std::vector<int> v;
v.reserve(100); // allocate room for 100 up front
std::cout << "after reserve: size " << v.size()
<< ", capacity " << v.capacity() << '\n';
const int* where = v.data();
for (int i = 0; i < 100; ++i) v.push_back(i);
std::cout << "after 100 push_backs: capacity " << v.capacity()
<< ", moved? " << std::boolalpha << (where != v.data()) << '\n';
v.resize(10); // keep the first 10 elements
std::cout << "after resize(10): size " << v.size()
<< ", capacity " << v.capacity() << '\n';
v.shrink_to_fit(); // a request, not a promise
std::cout << "after shrink_to_fit: capacity " << v.capacity() << '\n';
v.clear(); // removes elements, keeps memory
std::cout << "after clear: size " << v.size()
<< ", capacity " << v.capacity() << '\n';
v.resize(3, -1); // grow to 3, new elements = -1
for (int x : v) std::cout << x << ' ';
std::cout << '\n';
}Output (GCC / libstdc++):
after reserve: size 0, capacity 100
after 100 push_backs: capacity 100, moved? false
after resize(10): size 10, capacity 100
after shrink_to_fit: capacity 10
after clear: size 0, capacity 10
-1 -1 -1 | Function | Changes size? | Changes capacity? |
|---|---|---|
reserve(n) | No | Ensures capacity ≥ n (never shrinks) |
resize(n) / resize(n, val) | Yes, to exactly n (new elements value-initialized or set to val) | Only if n > capacity |
clear() | Yes, to 0 | No, memory is kept |
shrink_to_fit() | No | Requests capacity = size; the standard makes this non-binding (C++11) |
Use reserve when you know roughly how many elements are coming. It avoids repeated reallocations, and as the output shows, the buffer did not move during all 100 pushes. A very common mistake is to call reserve(100) and then write v[5] = 1: reserve does not create elements, so size() is still 0 and that write is undefined behavior. Use resize if you want elements to exist.
Inserting and Erasing in the Middle
#include <iostream>
#include <vector>
void print(const std::vector<int>& v) {
for (int x : v) std::cout << x << ' ';
std::cout << '\n';
}
bool isOdd(int x) { return x % 2 != 0; }
int main() {
std::vector<int> v = {10, 20, 30, 40, 50};
v.insert(v.begin() + 2, 25); // before index 2
print(v);
v.insert(v.begin(), 3, 0); // three 0s at the front
print(v);
v.erase(v.begin()); // remove index 0
print(v);
v.erase(v.begin(), v.begin() + 2); // remove the range [0, 2)
print(v);
std::vector<int> w = {1, 2, 3, 2, 6, 2, 8};
auto removed = std::erase(w, 2); // C++20: remove every 2
std::cout << "removed " << removed << ": ";
print(w);
removed = std::erase_if(w, isOdd); // C++20: remove by condition
std::cout << "removed " << removed << ": ";
print(w);
}Output:
10 20 25 30 40 50
0 0 0 10 20 25 30 40 50
0 0 10 20 25 30 40 50
10 20 25 30 40 50
removed 3: 1 3 6 8
removed 2: 6 8 insert and erase take iterators, not indexes: position i is written v.begin() + i. Because elements must stay contiguous, inserting at position i shifts every element after it one place right, and erasing shifts them left:
insert 25 at index 2:
before: │ 10 │ 20 │ 30 │ 40 │ 50 │ │
└──→ └──→ └──→ each shifts right by one
after: │ 10 │ 20 │ 25 │ 30 │ 40 │ 50 │So insertion or erasure in the middle is O(n) (linear in the number of elements after the position), and at the very end it is cheap. If your program inserts at the front all the time, consider deque or list from the list, deque & array chapter.
Removing all elements that match: before and after C++20
C++20 added the free functions std::erase(v, value) and std::erase_if(v, predicate), used above. Both return how many elements were removed. Before C++20 the standard way was the erase–remove idiom, which you will still see in a lot of code and in interviews:
#include <iostream>
#include <vector>
#include <algorithm>
void print(const std::vector<int>& v) {
std::cout << "size " << v.size() << ": ";
for (int x : v) std::cout << x << ' ';
std::cout << '\n';
}
int main() {
std::vector<int> v = {1, 2, 3, 2, 6, 2, 8};
// std::remove only shifts the kept elements forward.
auto newEnd = std::remove(v.begin(), v.end(), 2);
print(v); // size unchanged; the tail holds leftover values
std::cout << "kept elements: " << (newEnd - v.begin()) << '\n';
v.erase(newEnd, v.end()); // now actually delete the tail
print(v);
}Output:
size 7: 1 3 6 8 6 2 8
kept elements: 4
size 4: 1 3 6 8 As explained in Introduction to the STL, the algorithm std::remove cannot change a container's size. It moves the elements to keep to the front and returns the new logical end; the elements after that are in a valid but unspecified state (here they happen to be 6 2 8). Only erase really deletes them. Both versions are O(n), much better than erasing matches one at a time, which can become O(n²).
Iterator Invalidation: the Most Important Trap
Because a vector may move its elements to a new buffer, any pointer, reference or iterator to an element can become invalid (dangling) after the vector is modified. Using an invalid one is undefined behavior: it may print garbage, crash, or seem to work today and fail tomorrow.
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3};
v.shrink_to_fit(); // libstdc++: capacity becomes exactly 3
int& first = v[0]; // reference into the vector's buffer
v.push_back(4); // size would exceed capacity: buffer reallocated
std::cout << first << '\n'; // BUG: 'first' refers to freed memory
}Compiled with g++ -std=c++23 -g -fsanitize=address,undefined, AddressSanitizer catches the bug (addresses vary from run to run; report shortened):
==978==ERROR: AddressSanitizer: heap-use-after-free on address 0x77962c9e0010 ...
READ of size 4 at 0x77962c9e0010 thread T0
#0 ... in main v7.cpp:9
...
freed by thread T0 here:
...
#8 ... in std::vector<int, std::allocator<int> >::push_back(int&&) ...
#9 ... in main v7.cpp:8The report says it exactly: line 9 read memory that push_back on line 8 had freed. Without the sanitizer this program may well print 1 and look fine, which is what makes this bug dangerous. The rules (from the standard) are:
| Operation | What becomes invalid |
|---|---|
push_back, emplace_back | If the new size exceeds capacity: everything. Otherwise only end(). |
insert, emplace | If reallocation happens: everything. Otherwise everything at or after the insertion point (and end()). |
erase | Everything at or after the erased position, including end(). |
pop_back | The last element and end(). |
reserve, shrink_to_fit | Everything, if the capacity actually changes. |
clear | Everything (all elements are gone). |
resize | Like insert/erase at the end: everything if it reallocates. |
Fixes: refer to elements by index instead of pointer/reference when the vector may grow, take references only after you finish adding, or reserve enough capacity first.
Erasing inside a loop, correctly
A loop like for (auto it = v.begin(); it != v.end(); ++it) if (...) v.erase(it); is broken: after erase(it), it is invalid, and ++it on it is undefined behavior. erase returns a valid iterator to the element after the removed one, so use that:
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5, 6};
// Remove even numbers while walking the vector.
for (auto it = v.begin(); it != v.end(); ) {
if (*it % 2 == 0)
it = v.erase(it); // erase returns an iterator to the next element
else
++it; // advance only when nothing was erased
}
for (int x : v) std::cout << x << ' ';
std::cout << '\n';
}Output:
1 3 5 (For this exact task, std::erase_if is simpler and O(n); the loop version is O(n²) in the worst case because each erase shifts the rest. The loop is still worth knowing because the same pattern is used for list, map and set.)
2D vectors
A vector of vectors gives a 2D table whose dimensions are decided at run time, which is very common in matrix and grid problems:
#include <iostream>
#include <vector>
int main() {
int rows = 3, cols = 4;
std::vector<std::vector<int>> grid(rows, std::vector<int>(cols, 0));
for (int r = 0; r < rows; ++r)
for (int c = 0; c < cols; ++c)
grid[r][c] = r * cols + c;
grid[1].push_back(99); // rows may have different lengths ("jagged")
for (const auto& row : grid) {
for (int x : row) std::cout << x << ' ';
std::cout << '\n';
}
std::cout << "rows: " << grid.size() << ", row 1 length: " << grid[1].size() << '\n';
}Output:
0 1 2 3
4 5 6 7 99
8 9 10 11
rows: 3, row 1 length: 5grid(rows, std::vector<int>(cols, 0)) means "rows copies of a row that has cols zeros". Each row is a separate vector with its own heap buffer, so rows can even have different lengths. The cost is that the rows are not one contiguous block; for performance-critical code, a single vector<int> of size rows × cols indexed as r * cols + c is faster.
vectors and Functions
#include <iostream>
#include <vector>
// const reference: no copy, and the function cannot modify the caller's vector
long long sum(const std::vector<int>& v) {
long long s = 0;
for (int x : v) s += x;
return s;
}
// non-const reference: modifies the caller's vector
void doubleAll(std::vector<int>& v) {
for (int& x : v) x *= 2; // int& so we change the element, not a copy
}
// return by value: cheap, the result is moved (or constructed in place)
std::vector<int> firstN(int n) {
std::vector<int> r;
r.reserve(n);
for (int i = 1; i <= n; ++i) r.push_back(i);
return r;
}
int main() {
std::vector<int> v = firstN(5);
std::cout << "sum = " << sum(v) << '\n';
doubleAll(v);
for (int x : v) std::cout << x << ' ';
std::cout << '\n';
}Output:
sum = 15
2 4 6 8 10 Pass by
const&when you only read. Passing by value copies every element: O(n) time and memory for nothing.Pass by non-const
&when the function must modify the caller's vector (as in References).Return by value freely. Since C++11 a returned local vector is moved (just three pointers change hands) or, more often, built directly in the caller's variable (copy elision), so returning a big vector is cheap. The details are in Move Semantics & Rvalue References.
In
for (int& x : v)the&is required to modify elements;for (int x : v)changes only a copy.
Copying, Comparing and Swapping
#include <iostream>
#include <vector>
int main() {
std::vector<int> a = {1, 2, 3};
std::vector<int> b = {1, 2, 4};
std::vector<int> c = {1, 2};
std::cout << std::boolalpha;
std::cout << (a == b) << '\n'; // element-by-element
std::cout << (a < b) << '\n'; // lexicographic: 3 < 4 decides
std::cout << (c < a) << '\n'; // c is a prefix of a, so c is smaller
std::vector<int> d = a; // deep copy: independent elements
d[0] = 100;
std::cout << a[0] << ' ' << d[0] << '\n';
a.swap(c); // O(1): just exchanges internal pointers
std::cout << a.size() << ' ' << c.size() << '\n';
std::vector<int> e = {7, 8};
e.append_range(b); // C++23: append a whole range
for (int x : e) std::cout << x << ' ';
std::cout << '\n';
}Output:
false
true
true
1 100
2 3
7 8 1 2 4 Copying a vector is a deep copy: new buffer, all elements copied. The class follows the rule of three/five correctly, so you never write a copy constructor for it.
==compares sizes and then elements.<compares lexicographically, like words in a dictionary. (Since C++20 these come fromoperator==andoperator<=>.)swapis O(1): it exchanges the internal pointers and does not touch elements.append_rangeis new in C++23 (withinsert_rangeandassign_range), supported by GCC 15. On older compilers writee.insert(e.end(), b.begin(), b.end()).
A Special Case: vector<bool>
std::vector<bool> is a specialization (see Templates) that packs bools into bits to save memory. As a result it does not behave like other vectors: v[i] returns a proxy object instead of a real bool&, you cannot take &v[0] as a bool*, and it has no data(). It works for simple use, but if you need normal vector behavior use std::vector<char>, or std::bitset for a fixed number of bits.
Complexity Summary
| Operation | Complexity |
|---|---|
v[i], at, front, back, size, empty | O(1) |
push_back, emplace_back | O(1) amortized (O(n) on a reallocation) |
pop_back | O(1) |
insert / erase at position p | O(number of elements after p) plus number inserted/erased |
Search by value (std::find) | O(n) |
Copy, clear, destruction | O(n) |
swap, move construction | O(1) |
vector vs built-in array
| Feature | Built-in array int a[10] | std::vector<int> |
|---|---|---|
| Size | Fixed at compile time | Changes at run time |
| Knows its size | No (decays to a pointer when passed) | Yes, size() |
| Memory | Stack (if local) | Heap buffer, freed automatically |
| Bounds checking | Never | Optional with at() |
Copy with = | Not allowed | Yes, deep copy |
| Element access speed | O(1) | O(1), same contiguous layout |
Common Mistakes
Indexing out of range with
[].v[v.size()]is undefined behavior; useat()while debugging or check the index.Calling
front(),back()orpop_back()on an empty vector: undefined behavior. Checkempty()first.Confusing
reservewithresize. Afterreserve(n)the size is still 0.Keeping references/iterators across
push_back. A reallocation leaves them dangling.Signed/unsigned comparison.
size()returns an unsignedstd::size_t.for (int i = 0; i < v.size(); ++i)triggers a-Wsign-comparewarning, andv.size() - 1on an empty vector wraps around to a huge number. Prefer range-basedfor, orstd::size_tindexes, or C++20std::ssize(v).vector<int> v(5)vsvector<int> v{5}: five zeros vs one element 5.Passing vectors by value to functions that only read them.
Interview / GATE-Style Questions
Q1. What is the difference between size and capacity of a vector?
Size is the number of elements stored. Capacity is how many elements the allocated buffer can hold before a reallocation is needed. Always capacity ≥ size.
Q2. Why is push_back amortized O(1) and not O(1) in the worst case?
When the vector is full, push_back reallocates and moves all n elements, which is O(n). Because capacity grows geometrically (for example doubling), such reallocations are rare: n pushes cause fewer than 2n element copies in total, so the average cost per push is constant.
Q3. What is printed?
vector<int> a(3, 1), b{3, 1};
cout << a.size() << b.size();
32. a is three copies of 1; b uses the initializer-list constructor and holds two elements, 3 and 1.
Q4. Can a reference to v[0] become invalid when you call push_back? When?
Yes, if the push makes the size exceed the current capacity. The vector then moves its elements to a new buffer and frees the old one, so all existing references, pointers and iterators dangle. If capacity is sufficient, only end() is invalidated.
Q5. Difference between v[i] and v.at(i)?
Both return a reference to element i in O(1). v[i] does no checking, so an invalid index is undefined behavior; v.at(i) checks the index and throws std::out_of_range if it is invalid.
Q6. Does clear() free the vector's memory?
No. It destroys the elements and sets size to 0, but capacity is unchanged. To request releasing memory, call shrink_to_fit() afterwards (non-binding), or swap with an empty vector: std::vector<int>().swap(v);.
Q7. What is the erase–remove idiom?
v.erase(std::remove(v.begin(), v.end(), x), v.end());. std::remove moves the elements to keep to the front and returns the new logical end; erase then deletes the leftover tail. Since C++20 the same is written std::erase(v, x);.
Summary
std::vector<T>is a dynamic array: contiguous elements, O(1) indexing, automatic memory management.size is the element count, capacity the allocated room; geometric growth makes
push_backamortized O(1).reservechanges capacity only,resizechanges size,clearkeeps the memory,shrink_to_fitis only a request.[]is unchecked,at()throwsstd::out_of_range.Insertion and erasure in the middle are O(n) because elements shift; use
std::erase/std::erase_if(C++20) or the erase–remove idiom to remove by value.Reallocation invalidates all iterators, pointers and references;
eraseinvalidates everything from the erased point onward. Use the iterator returned byerase.Pass by
const&, return by value; copying is deep andswapis O(1).vector<bool>is a bit-packed special case that does not behave like a normal container.