Vectors in C++

Table of Contents

1. •Introduction
2. •What are Vectors?
3. •Vector Basics
4. •Creating Vectors
5. •Accessing Elements
6. •Modifying Vectors
7. •Vector Capacity vs Size
8. •Iterators
9. •Vector Algorithms
10. •2D Vectors
11. •Vector of Objects
12. •Performance Considerations
13. •Common Pitfalls
14. •Best Practices
15. •Summary

---

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?

---

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

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

---

Best Practices

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

Quick Reference

#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