Vectors in C++

---

Introduction

Vectors are one of the most versatile and commonly used containers in C++. They combine the convenience of dynamic sizing with the performance benefits of contiguous memory storage, making them the go-to choice for most sequence container needs.

Why Vectors Over Arrays?

Feature	C-Style Array	std::array	std::vector
Dynamic Size	❌	❌	✅
Bounds Checking	❌	✅ (at())	✅ (at())
Size Tracking	❌	✅	✅
Memory Management	Manual	Automatic	Automatic
STL Compatible	Limited	✅	✅
Resizable	❌	❌	✅

---

What are Vectors?

A std::vector is a sequence container that:

• Stores elements contiguously in memory (like arrays)
• Automatically manages memory (grows and shrinks as needed)
• Provides random access to elements in O(1) time
• Supports dynamic resizing at runtime

Header Required

#include <vector>

Memory Layout

Vector Object (on stack):
┌─────────────┬─────────────┬─────────────┐
│   begin()   │    end()    │  capacity   │
│  (pointer)  │  (pointer)  │  (size_t)   │
└──────┬──────┴──────┬──────┴─────────────┘
       │             │
       v             v
Heap: [elem0][elem1][elem2][elem3][ reserved space ]
       └─────── size ───────┘└── unused capacity ──┘

---

Vector Basics

Basic Syntax

#include <vector>
using namespace std;

// Declaration
vector<T> vectorName;      // Empty vector of type T
vector<T> vectorName(n);   // Vector of n default-initialized elements
vector<T> vectorName(n, value);  // Vector of n elements, all set to value

Template Parameter

The T in vector<T> specifies the element type:

vector<int> integers;        // Stores integers
vector<double> decimals;     // Stores doubles
vector<string> words;        // Stores strings
vector<MyClass> objects;     // Stores custom objects

---

Creating Vectors

Method 1: Empty Vector

vector<int> v;  // Empty vector, size = 0, capacity = 0

Method 2: With Size

vector<int> v(5);      // 5 elements, all initialized to 0
vector<int> v(5, 10);  // 5 elements, all initialized to 10

Method 3: Initializer List (C++11)

vector<int> v = {1, 2, 3, 4, 5};    // Direct initialization
vector<int> v{1, 2, 3, 4, 5};       // Uniform initialization

Method 4: From Another Vector

vector<int> original = {1, 2, 3};
vector<int> copy1(original);                      // Copy constructor
vector<int> copy2 = original;                     // Copy assignment
vector<int> partial(original.begin(), original.begin() + 2);  // Range

Method 5: From Array

int arr[] = {1, 2, 3, 4, 5};
vector<int> v(begin(arr), end(arr));  // Copy from C-array
vector<int> v(arr, arr + 5);          // Alternative syntax

Method 6: Move Semantics (C++11)

vector<int> v1 = {1, 2, 3};
vector<int> v2 = move(v1);  // v1 is now empty, v2 has the data

---

Accessing Elements

Operator [] (No Bounds Checking)

vector<int> v = {10, 20, 30};
cout << v[0];     // 10
cout << v[1];     // 20
v[2] = 300;       // Modify element
// v[10] = 5;     // UNDEFINED BEHAVIOR! No bounds check

at() Method (Bounds Checking)

vector<int> v = {10, 20, 30};
cout << v.at(0);  // 10
v.at(1) = 200;    // Safe modification

try {
    cout << v.at(10);  // Throws std::out_of_range
} catch (const out_of_range& e) {
    cerr << "Error: " << e.what() << endl;
}

front() and back()

vector<int> v = {10, 20, 30};
cout << v.front();  // 10 (first element)
cout << v.back();   // 30 (last element)

v.front() = 1;      // Modify first
v.back() = 3;       // Modify last

data() - Raw Pointer Access

vector<int> v = {1, 2, 3};
int* ptr = v.data();        // Pointer to underlying array
cout << ptr[0];             // 1
cout << *(ptr + 1);         // 2

// Useful for C library interoperability
void cFunction(int* arr, int size);
cFunction(v.data(), v.size());

---

Modifying Vectors

Adding Elements

push_back() - Add at End

vector<int> v;
v.push_back(10);    // v: [10]
v.push_back(20);    // v: [10, 20]
v.push_back(30);    // v: [10, 20, 30]

emplace_back() - Construct in Place (C++11)

vector<pair<int, string>> v;
v.push_back(make_pair(1, "one"));      // Creates temp, then copies/moves
v.emplace_back(2, "two");              // Constructs directly in vector (more efficient)

insert() - Add at Position

vector<int> v = {1, 2, 5};

// Insert single element
v.insert(v.begin() + 2, 3);            // v: [1, 2, 3, 5]

// Insert multiple copies
v.insert(v.end(), 3, 10);              // v: [1, 2, 3, 5, 10, 10, 10]

// Insert range
vector<int> more = {7, 8};
v.insert(v.begin(), more.begin(), more.end());  // v: [7, 8, 1, 2, 3, 5, 10, 10, 10]

Removing Elements

pop_back() - Remove Last Element

vector<int> v = {1, 2, 3};
v.pop_back();       // v: [1, 2]

erase() - Remove at Position

vector<int> v = {1, 2, 3, 4, 5};

// Erase single element
v.erase(v.begin() + 2);           // v: [1, 2, 4, 5]

// Erase range
v.erase(v.begin(), v.begin() + 2); // v: [4, 5]

clear() - Remove All Elements

vector<int> v = {1, 2, 3};
v.clear();          // v is empty, size = 0
                    // Note: capacity unchanged!

Resizing

resize()

vector<int> v = {1, 2, 3};
v.resize(5);        // v: [1, 2, 3, 0, 0]  (expanded with default value)
v.resize(7, 10);    // v: [1, 2, 3, 0, 0, 10, 10]  (expanded with 10)
v.resize(2);        // v: [1, 2]  (truncated)

assign()

vector<int> v = {1, 2, 3};
v.assign(5, 100);               // v: [100, 100, 100, 100, 100]
v.assign({7, 8, 9});            // v: [7, 8, 9]

Swapping

vector<int> v1 = {1, 2, 3};
vector<int> v2 = {4, 5, 6};
v1.swap(v2);        // v1: [4, 5, 6], v2: [1, 2, 3]
swap(v1, v2);       // Swap back using std::swap

---

Vector Capacity vs Size

Understanding the Difference

Size     = Number of elements currently stored
Capacity = Amount of space allocated (can hold more before reallocation)

Member Functions

vector<int> v = {1, 2, 3};
cout << v.size();       // 3 - actual elements
cout << v.capacity();   // >= 3 - allocated space
cout << v.max_size();   // Maximum possible size (very large number)
cout << v.empty();      // false (true if size == 0)

Controlling Capacity

reserve() - Pre-allocate Memory

vector<int> v;
v.reserve(1000);     // Allocate space for 1000 elements
cout << v.size();    // 0 (no elements yet)
cout << v.capacity(); // >= 1000

// Now push_back won't reallocate until size > capacity
for (int i = 0; i < 1000; i++) {
    v.push_back(i);  // No reallocation, very efficient
}

shrink_to_fit() - Release Excess Memory (C++11)

vector<int> v(1000);
v.resize(10);           // size = 10, capacity still ~1000
v.shrink_to_fit();      // Reduce capacity to match size

Capacity Growth Strategy

When a vector needs more space, it typically doubles its capacity:

vector<int> v;
for (int i = 0; i < 17; i++) {
    v.push_back(i);
    cout << "Size: " << v.size() << ", Capacity: " << v.capacity() << endl;
}
// Typical output:
// Size: 1, Capacity: 1
// Size: 2, Capacity: 2
// Size: 3, Capacity: 4
// Size: 5, Capacity: 8
// Size: 9, Capacity: 16
// Size: 17, Capacity: 32

---

Iterators

Iterator Types

vector<int>::iterator it;              // Read/Write iterator
vector<int>::const_iterator cit;       // Read-only iterator
vector<int>::reverse_iterator rit;     // Reverse read/write
vector<int>::const_reverse_iterator crit;  // Reverse read-only

Getting Iterators

vector<int> v = {1, 2, 3, 4, 5};

// Forward iterators
auto first = v.begin();     // Points to first element
auto last = v.end();        // Points PAST last element

// Reverse iterators
auto rfirst = v.rbegin();   // Points to last element
auto rlast = v.rend();      // Points BEFORE first element

// Const iterators
auto cfirst = v.cbegin();   // Const begin (C++11)
auto clast = v.cend();      // Const end (C++11)

Using Iterators

vector<int> v = {10, 20, 30, 40, 50};

// Traditional iteration
for (auto it = v.begin(); it != v.end(); ++it) {
    cout << *it << " ";     // Dereference to get value
}

// Modify through iterator
for (auto it = v.begin(); it != v.end(); ++it) {
    *it *= 2;               // Double each element
}

// Reverse iteration
for (auto it = v.rbegin(); it != v.rend(); ++it) {
    cout << *it << " ";     // 100 80 60 40 20
}

Range-Based For Loop (Recommended)

vector<int> v = {1, 2, 3, 4, 5};

// Read elements
for (int x : v) {
    cout << x << " ";
}

// Modify elements (use reference)
for (int& x : v) {
    x *= 2;
}

// Read with const reference (efficient for large objects)
for (const auto& x : v) {
    cout << x << " ";
}

---

Vector Algorithms

Include the Algorithm Header

#include <algorithm>
#include <numeric>   // For accumulate, iota, etc.

Sorting

vector<int> v = {5, 2, 8, 1, 9};

sort(v.begin(), v.end());                 // Ascending: 1, 2, 5, 8, 9
sort(v.begin(), v.end(), greater<int>()); // Descending: 9, 8, 5, 2, 1

// Custom comparison
sort(v.begin(), v.end(), [](int a, int b) {
    return abs(a) < abs(b);               // Sort by absolute value
});

Searching

vector<int> v = {1, 2, 3, 4, 5};

// Find element (returns iterator)
auto it = find(v.begin(), v.end(), 3);
if (it != v.end()) {
    cout << "Found at index: " << distance(v.begin(), it);
}

// Binary search (requires sorted vector)
bool exists = binary_search(v.begin(), v.end(), 3);  // true

// Find position for sorted insert
auto pos = lower_bound(v.begin(), v.end(), 3);  // First >= 3
auto pos2 = upper_bound(v.begin(), v.end(), 3); // First > 3

Other Useful Algorithms

vector<int> v = {5, 2, 8, 2, 1, 5};

// Min/Max
int minVal = *min_element(v.begin(), v.end());  // 1
int maxVal = *max_element(v.begin(), v.end());  // 8

// Count
int cnt = count(v.begin(), v.end(), 2);         // 2

// Sum
int sum = accumulate(v.begin(), v.end(), 0);    // 23

// Reverse
reverse(v.begin(), v.end());

// Remove duplicates (must sort first)
sort(v.begin(), v.end());
auto newEnd = unique(v.begin(), v.end());
v.erase(newEnd, v.end());                       // {1, 2, 5, 8}

// Fill
fill(v.begin(), v.end(), 0);                    // All zeros

// Generate sequence
vector<int> seq(10);
iota(seq.begin(), seq.end(), 1);                // {1, 2, 3, ..., 10}

// Transform
transform(v.begin(), v.end(), v.begin(), [](int x) {
    return x * 2;                                // Double all elements
});

---

2D Vectors

Creating 2D Vectors

// Empty 2D vector
vector<vector<int>> matrix;

// 3x4 matrix filled with zeros
vector<vector<int>> matrix(3, vector<int>(4, 0));

// Initialize with values
vector<vector<int>> matrix = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

Accessing Elements

vector<vector<int>> matrix = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

int val = matrix[1][2];     // 6 (row 1, column 2)
matrix[0][0] = 10;          // Modify

int rows = matrix.size();               // 3
int cols = matrix[0].size();            // 3 (assuming rectangular)

Iterating 2D Vectors

// Using indices
for (int i = 0; i < matrix.size(); i++) {
    for (int j = 0; j < matrix[i].size(); j++) {
        cout << matrix[i][j] << " ";
    }
    cout << endl;
}

// Range-based (cleaner)
for (const auto& row : matrix) {
    for (int val : row) {
        cout << val << " ";
    }
    cout << endl;
}

Adding Rows and Columns

vector<vector<int>> matrix;

// Add rows
matrix.push_back({1, 2, 3});
matrix.push_back({4, 5, 6});

// Add column to each row
for (auto& row : matrix) {
    row.push_back(0);
}

Jagged Arrays (Non-Rectangular)

vector<vector<int>> jagged;
jagged.push_back({1});
jagged.push_back({2, 3});
jagged.push_back({4, 5, 6});
// Rows have different lengths

---

Vector of Objects

Storing Custom Classes

class Student {
public:
    string name;
    int age;

    Student(string n, int a) : name(n), age(a) {}
};

vector<Student> students;
students.push_back(Student("Alice", 20));
students.emplace_back("Bob", 21);  // More efficient

// Access
cout << students[0].name;

Storing Pointers

vector<Student*> studentPtrs;
studentPtrs.push_back(new Student("Alice", 20));

// Remember to delete!
for (auto ptr : studentPtrs) {
    delete ptr;
}
studentPtrs.clear();

Using Smart Pointers (Recommended)

#include <memory>

vector<unique_ptr<Student>> students;
students.push_back(make_unique<Student>("Alice", 20));
// Automatic cleanup when vector goes out of scope

vector<shared_ptr<Student>> sharedStudents;
sharedStudents.push_back(make_shared<Student>("Bob", 21));

---

Performance Considerations

Time Complexity

Operation	Time Complexity
Access by index []	O(1)
push_back()	O(1) amortized
pop_back()	O(1)
insert(pos)	O(n)
erase(pos)	O(n)
find()	O(n)
sort()	O(n log n)
binary_search()	O(log n)

Optimization Tips

1. Reserve Capacity

// Bad: Multiple reallocations
vector<int> v;
for (int i = 0; i < 10000; i++) {
    v.push_back(i);  // May reallocate ~14 times
}

// Good: Pre-allocate
vector<int> v;
v.reserve(10000);
for (int i = 0; i < 10000; i++) {
    v.push_back(i);  // No reallocations
}

2. Use emplace_back

// Less efficient: creates temporary
v.push_back(make_pair(1, 2));

// More efficient: constructs in place
v.emplace_back(1, 2);

3. Pass by Reference

// Bad: copies entire vector
void processVector(vector<int> v) { ... }

// Good: pass by const reference
void processVector(const vector<int>& v) { ... }

// Good: pass by reference if modifying
void modifyVector(vector<int>& v) { ... }

4. Move Semantics

vector<int> createVector() {
    vector<int> v = {1, 2, 3};
    return v;  // Automatically moved (RVO/NRVO)
}

vector<int> v1 = createVector();  // No copy, move or RVO
vector<int> v2 = move(v1);        // Explicit move

---

Common Pitfalls

1. Iterator Invalidation

vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it == 3) {
        v.erase(it);  // BUG! Iterator invalidated
    }
}

// Correct approach:
for (auto it = v.begin(); it != v.end(); ) {
    if (*it == 3) {
        it = v.erase(it);  // erase returns next valid iterator
    } else {
        ++it;
    }
}

// Or use erase-remove idiom:
v.erase(remove(v.begin(), v.end(), 3), v.end());

2. Accessing Empty Vector

vector<int> v;
// v.front();  // UNDEFINED BEHAVIOR!
// v[0];       // UNDEFINED BEHAVIOR!

if (!v.empty()) {
    cout << v.front();  // Safe
}

3. Bounds Errors with []

vector<int> v = {1, 2, 3};
// cout << v[10];  // UNDEFINED BEHAVIOR - no bounds check

cout << v.at(10);  // Throws exception - safe

4. Reference Invalidation

vector<int> v = {1, 2, 3};
int& ref = v[0];
v.push_back(4);   // May reallocate!
// ref is now dangling if reallocation occurred

---

Recommended Conventions

1. Prefer vector Over Raw Arrays

// Avoid
int* arr = new int[100];
// ... must remember to delete[]

// Prefer
vector<int> v(100);
// Automatic cleanup

2. Use Appropriate Container

// Use vector for:
// - Random access needs
// - Mostly append operations
// - When you need contiguous memory

// Consider alternatives:
// - deque: frequent front insertions
// - list: frequent middle insertions
// - set/map: unique elements, sorted access
// - unordered_set/map: fast lookup

3. Initialize with Size When Known

// Know you need 1000 elements?
vector<int> v(1000);       // All initialized to 0
vector<int> v(1000, -1);   // All initialized to -1

// Or reserve:
vector<int> v;
v.reserve(1000);           // Capacity allocated, size = 0

4. Use auto with Iterators

// Verbose
vector<int>::iterator it = v.begin();

// Clean
auto it = v.begin();

5. Const Correctness

void readOnly(const vector<int>& v) {
    for (const auto& elem : v) {  // const reference
        cout << elem;
    }
    // v.push_back(1);  // Compile error - good!
}

---

Summary

Key Points

1. Dynamic sizing: Vectors grow automatically
2. Contiguous memory: Fast random access, cache-friendly
3. RAII: Automatic memory management
4. STL compatible: Works with all algorithms
5. Prefer over arrays: Safer and more convenient

Cheat Sheet

#include <vector>
using namespace std;

// Creation
vector<int> v;
vector<int> v(n);
vector<int> v(n, value);
vector<int> v = {1, 2, 3};

// Access
v[i];           // No bounds check
v.at(i);        // Bounds check
v.front();      // First element
v.back();       // Last element

// Modify
v.push_back(x); // Add to end
v.emplace_back(args); // Construct in place
v.pop_back();   // Remove from end
v.insert(it, x); // Insert at position
v.erase(it);    // Remove at position
v.clear();      // Remove all

// Size/Capacity
v.size();       // Number of elements
v.capacity();   // Allocated space
v.empty();      // Check if empty
v.reserve(n);   // Pre-allocate
v.resize(n);    // Change size

// Iterators
v.begin(), v.end();    // Forward
v.rbegin(), v.rend();  // Reverse
v.cbegin(), v.cend();  // Const

When to Use Vectors

✅ Use vectors when:

• You need a dynamic-size array
• Random access is important
• Most operations are at the end
• You need to pass data to C APIs (via data())

❌ Consider alternatives when:

• Frequent insertions at the front (use deque)
• Frequent insertions in the middle (use list)
• Elements must be unique (use set)
• You need key-value pairs (use map)

---

Practice Files

• examples.cpp: Comprehensive code examples demonstrating all vector operations
• exercises.cpp: Practice problems from beginner to advanced

Compilation

g++ -std=c++17 -Wall -Wextra examples.cpp -o examples
g++ -std=c++17 -Wall -Wextra exercises.cpp -o exercises
./examples
./exercises