Vectors in C++

C++ provides many ways to create and initialize vectors. The std::vector template class accepts the element type as a template parameter, giving you type-safe containers for any data type.

// Method 1: Empty vector
vector<int> v1;
cout << "v1 size: " << v1.size() << endl;  // 0

The simplest way to create a vector is to declare it without any initial values. This creates an empty vector with size zero. The vector is ready to use and you can add elements to it later using methods like push_back(). This approach is useful when you don't know the initial values ahead of time and will populate the vector dynamically.

// Method 2: Initialize with size (all zeros)
vector<int> v2(5);
for (int x : v2) cout << x << " ";  // 0 0 0 0 0

When you know how many elements you need but not their specific values, initialize the vector with a size. For numeric types, all elements are automatically set to zero. For objects, the default constructor is called for each element. This is efficient because the vector allocates all the required memory upfront in a single operation.

// Method 3: Initialize with size and value
vector<int> v3(5, 100);
for (int x : v3) cout << x << " ";  // 100 100 100 100 100

Use the two-argument constructor to create a vector with a specific size where all elements have the same initial value. The first argument is the count, and the second is the value to fill with. This is commonly used when you need a pre-sized vector with a default value, such as initializing a grid or matrix.

// Method 4: Initializer list (C++11)
vector<int> v4 = {1, 2, 3, 4, 5};
vector<int> v5{10, 20, 30};  // Also valid without =

Initializer lists provide the most readable way to create vectors with known values. Introduced in C++11, this syntax lets you specify elements directly in curly braces. You can use the assignment-style = {} or direct initialization {}. Both forms are equivalent and the compiler handles memory allocation automatically.

// Method 5: Copy constructor
vector<int> v6(v4);  // Copy of v4
vector<int> v7 = v5; // Copy of v5 using assignment syntax

Create a new vector as a copy of an existing one using the copy constructor. This performs a deep copy, meaning all elements are duplicated into the new vector. Changes to one vector won't affect the other. Both syntaxes produce identical results.

// Method 6: From array
int arr[] = {1, 2, 3, 4, 5};
vector<int> v8(arr, arr + 5);

Convert a C-style array to a vector by passing two pointers - one to the beginning and one past the end of the range. The expression arr + 5 points to one position after the last element. This is useful when integrating legacy C code or working with functions that return arrays.

// Method 7: From another vector's range
vector<int> v9(v4.begin(), v4.begin() + 3);  // {1, 2, 3}

Create a vector from a portion of another vector using iterators. The first iterator points to where you want to start, and the second points past the last element to include. This is powerful for extracting subsets of data without manually copying elements.

// Vectors of different types
vector<string> names = {"Alice", "Bob", "Charlie"};
vector<double> prices = {19.99, 29.99, 39.99};
vector<bool> flags = {true, false, true};

Vectors are templates that work with any data type. You can create vectors of strings, floating-point numbers, booleans, or even custom classes. The element type is specified in angle brackets. Each vector type is type-safe - you can only store elements of the declared type, which helps catch errors at compile time.

vector<int> result(10, -1);
// result: {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

vector<vector<int>> matrix(3, vector<int>(4, 0));
// Creates:
// 0 0 0 0
// 0 0 0 0
// 0 0 0 0

int data[] = {10, 20, 30, 40, 50, 60, 70};

int data[] = {10, 20, 30, 40, 50, 60, 70};
vector<int> result(data + 2, data + 6);
// result: {30, 40, 50, 60}

Vectors provide multiple ways to access elements - from simple indexing to safer bounds-checked methods. Understanding when to use each approach is key to writing robust and efficient code.

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

// Subscript operator [] - no bounds checking
cout << "First element: " << numbers[0] << endl;   // 10
cout << "Third element: " << numbers[2] << endl;   // 30

The subscript operator [] provides the fastest way to access elements by index. It works exactly like array indexing, with zero-based positions. However, it does not perform bounds checking, so accessing an invalid index leads to undefined behavior. Use this when you are confident the index is valid and need maximum performance.

// at() - with bounds checking (throws exception)
cout << "Second element: " << numbers.at(1) << endl;  // 20

The at() method provides safe element access with automatic bounds checking. If you try to access an index outside the valid range, it throws an out_of_range exception instead of causing undefined behavior. This is slightly slower than [] due to the bounds check, but much safer during development and debugging.

// front() and back() - access first and last elements
cout << "First: " << numbers.front() << endl;  // 10
cout << "Last: " << numbers.back() << endl;    // 50

Use front() and back() to access the first and last elements without knowing the vector's size. These methods make your code more readable and express your intent clearly. They are especially useful when implementing queue or stack-like behavior. Note that calling these on an empty vector is undefined behavior.

// data() - get raw pointer to underlying array
int* ptr = numbers.data();
cout << "Via pointer: " << ptr[2] << endl;  // 30

The data() method returns a raw pointer to the internal array. This is useful when interfacing with C libraries or functions that expect a pointer. You can then use pointer arithmetic or array notation to access elements. Be careful with this pointer as it may become invalid if the vector is resized.

// Modifying elements using different access methods
numbers[0] = 100;       // Using subscript operator
numbers.at(1) = 200;    // Using at()
numbers.front() = 111;  // Modify first element
numbers.back() = 555;   // Modify last element

All access methods return references, which means you can use them on the left side of an assignment to modify elements. This allows you to update values in place without needing to remove and re-insert elements. The modification happens directly in the vector's internal storage.

// Bounds checking demonstration with exception handling
try {
    cout << numbers.at(10) << endl;  // Throws out_of_range
} catch (const out_of_range& e) {
    cout << "Error: " << e.what() << endl;
}

When at() detects an invalid index, it throws a std::out_of_range exception. You can catch this exception to handle the error gracefully instead of crashing. The exception's what() method provides a description of the error. This pattern is useful for validating user input or handling uncertain data sources.

Iterating Over Vectors

vector<string> fruits = {"Apple", "Banana", "Cherry", "Date"};

// Range-based for loop (recommended)
for (const string& fruit : fruits) {
    cout << fruit << " ";  // Apple Banana Cherry Date
}

The range-based for loop is the cleanest and most modern way to iterate through a vector. It automatically handles the iteration from beginning to end. Using const string& avoids copying each element and prevents accidental modifications. For read-only access, this is the recommended approach in modern C++.

// Index-based loop - when you need the position
for (size_t i = 0; i < fruits.size(); i++) {
    cout << i << ": " << fruits[i] << endl;
}

Use an index-based loop when you need to know the position of each element, or when you need to access multiple elements relative to the current position. Note that size() returns size_t, an unsigned type, so use size_t for the loop variable to avoid compiler warnings about signed/unsigned comparison.

// Iterator loop - STL compatible
for (auto it = fruits.begin(); it != fruits.end(); ++it) {
    cout << *it << " ";
}

Iterator loops provide the most flexibility and are compatible with all STL algorithms. The begin() method returns an iterator to the first element, and end() returns an iterator past the last element. Use the dereference operator * to access the element the iterator points to. The auto keyword simplifies the syntax.

// Reverse iteration - traverse backward
for (auto it = fruits.rbegin(); it != fruits.rend(); ++it) {
    cout << *it << " ";  // Date Cherry Banana Apple
}

Reverse iterators let you traverse the vector from back to front. The rbegin() method returns a reverse iterator pointing to the last element, and rend() points before the first element. Notice you still use ++it to move backward through the vector. This is useful for processing elements in reverse order.

vector<int> nums = {1, 2, 3, 4, 5};
int sum = 0;
for (int num : nums) {
    sum += num;
}
cout << "Sum: " << sum << endl;  // 15

vector<int> nums = {1, 2, 3, 4, 5};
for (int& num : nums) {  // Note: reference!
    num *= 2;
}
// nums is now: {2, 4, 6, 8, 10}

Understanding the difference between size (number of elements) and capacity (allocated storage) is crucial for writing efficient vector code. Vectors over-allocate memory to minimize reallocations when growing.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v;
    
    cout << "Initial:" << endl;
    cout << "  Size: " << v.size() << endl;       // 0
    cout << "  Capacity: " << v.capacity() << endl; // 0
    cout << "  Empty: " << boolalpha << v.empty() << endl;  // true
    
    // Add elements and watch capacity grow
    for (int i = 1; i <= 10; i++) {
        v.push_back(i);
        cout << "After adding " << i << ": size=" << v.size() 
             << ", capacity=" << v.capacity() << endl;
    }
    
    // Reserve capacity in advance (optimization)
    vector<int> optimized;
    optimized.reserve(100);  // Pre-allocate for 100 elements
    cout << "\nAfter reserve(100):" << endl;
    cout << "  Size: " << optimized.size() << endl;       // 0
    cout << "  Capacity: " << optimized.capacity() << endl; // 100
    
    // resize() changes size (and may add/remove elements)
    optimized.resize(50);  // Size is now 50 (filled with 0s)
    optimized.resize(75, -1);  // Grow to 75, new elements are -1
    
    // shrink_to_fit() reduces capacity to match size
    vector<int> large(1000);
    large.resize(10);
    cout << "\nBefore shrink_to_fit:" << endl;
    cout << "  Size: " << large.size() << endl;       // 10
    cout << "  Capacity: " << large.capacity() << endl; // 1000
    
    large.shrink_to_fit();
    cout << "After shrink_to_fit:" << endl;
    cout << "  Capacity: " << large.capacity() << endl; // 10 (or close to it)
    
    return 0;
}

vector<int> data;  // Empty vector
if (!data.empty()) {
    cout << "First: " << data.front() << endl;
} else {
    cout << "Vector is empty!" << endl;
}

vector<int> userIds;
userIds.reserve(1000);  // Pre-allocate memory

for (int id = 1; id <= 1000; id++) {
    userIds.push_back(id);  // No reallocations!
}
cout << "Size: " << userIds.size() << endl;       // 1000
cout << "Capacity: " << userIds.capacity() << endl; // 1000

Vectors provide powerful methods to add, remove, and modify elements. From simple push/pop operations to complex insertions and erasures, you have full control over your data.

Adding Elements

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

// push_back() - add to end
v.push_back(40);
v.push_back(50);
// v: {10, 20, 30, 40, 50}

The push_back() method is the most common way to add elements to a vector. It appends the given value to the end of the vector in amortized O(1) time. The vector automatically grows its capacity if needed. This is efficient because adding to the end doesn't require shifting any existing elements.

// emplace_back() - construct in place (more efficient)
v.emplace_back(60);
// v: {10, 20, 30, 40, 50, 60}

The emplace_back() method constructs the element directly in the vector's memory instead of creating a temporary object and copying it. For simple types like integers, the difference is minimal, but for complex objects with expensive constructors, emplace_back can be significantly faster. It accepts constructor arguments directly.

// insert() - add at specific position
auto it = v.begin() + 2;
v.insert(it, 25);  // Insert 25 at index 2
// v: {10, 20, 25, 30, 40, 50, 60}

The insert() method adds an element at any position specified by an iterator. All elements from that position onward are shifted to make room, making this an O(n) operation. Use begin() + index to get an iterator to a specific position. The method returns an iterator to the newly inserted element.

// Insert multiple copies at once
v.insert(v.begin(), 3, 5);  // Insert three 5s at beginning
// v: {5, 5, 5, 10, 20, 25, 30, 40, 50, 60}

You can insert multiple copies of the same value in one operation. The second argument specifies how many copies, and the third is the value to insert. This is more efficient than calling insert multiple times because the vector only needs to shift elements once and may only need one reallocation.

// Insert range from another vector
vector<int> extras = {100, 200};
v.insert(v.end(), extras.begin(), extras.end());
// v: {5, 5, 5, 10, 20, 25, 30, 40, 50, 60, 100, 200}

Insert an entire range of elements from another container using iterator pairs. The first argument is where to insert, followed by iterators to the beginning and end of the source range. Inserting at v.end() effectively appends all elements from the source vector. This is useful for merging vectors.

Removing Elements

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

// pop_back() - remove last element
v.pop_back();
// v: {10, 20, 30, 40, 50, 60}

The pop_back() method removes the last element from the vector in O(1) time. It does not return the removed element, so if you need the value, access it with back() before calling pop_back. This is the fastest way to remove an element because no shifting is required. Calling pop_back on an empty vector is undefined behavior.

// erase() - remove at specific position
v.erase(v.begin() + 2);  // Remove element at index 2
// v: {10, 20, 40, 50, 60}

The erase() method removes the element at the specified iterator position. All elements after the removed one are shifted forward to fill the gap, making this an O(n) operation. The method returns an iterator to the element that now occupies the erased position, which is useful when erasing in a loop.

// erase() - remove a range of elements
v.erase(v.begin() + 1, v.begin() + 3);  // Remove indices 1 and 2
// v: {10, 50, 60}

You can erase multiple consecutive elements by passing two iterators defining a range. The first iterator points to the first element to remove, and the second points past the last element to remove. This is more efficient than erasing elements one by one because the remaining elements only need to be shifted once.

// Remove by value using erase-remove idiom
vector<int> nums = {1, 2, 3, 2, 4, 2, 5};
nums.erase(remove(nums.begin(), nums.end(), 2), nums.end());
// nums: {1, 3, 4, 5} - all 2s removed

To remove all occurrences of a specific value, use the erase-remove idiom. The std::remove() algorithm moves all non-matching elements to the front and returns an iterator to the new logical end. Then erase() removes the leftover elements. This requires including the <algorithm> header.

// clear() - remove all elements
vector<int> temp = {1, 2, 3};
temp.clear();
cout << "After clear: size=" << temp.size() << endl;  // 0

The clear() method removes all elements from the vector, setting its size to zero. Note that clear does not reduce capacity - the vector still holds the allocated memory. If you need to free memory, call shrink_to_fit() after clear, or use the swap idiom: vector<int>().swap(temp).

Other Modifications

vector<int> v1 = {1, 2, 3};
vector<int> v2 = {10, 20, 30, 40, 50};

// swap() - exchange contents
v1.swap(v2);
// v1: {10, 20, 30, 40, 50}
// v2: {1, 2, 3}

The swap() method exchanges the contents of two vectors in O(1) time. It swaps internal pointers rather than copying elements, making it extremely efficient regardless of vector size. This is commonly used in the swap idiom to free memory or in sorting algorithms. Both vectors must have the same element type.

// assign() - replace all contents with copies
v1.assign(5, 100);  // 5 copies of 100
// v1: {100, 100, 100, 100, 100}

The assign() method replaces all existing contents with new values. The two-argument form creates multiple copies of a value, similar to the constructor. This completely replaces the vector's contents - any previous elements are removed. It is useful for reinitializing a vector without creating a new one.

// assign() with initializer list
v1.assign({7, 8, 9});  // From initializer list
// v1: {7, 8, 9}

You can also use assign() with an initializer list to replace contents with specific values. This is equivalent to creating a new vector with those values and swapping. It provides a clean way to reset a vector to a new set of values without declaring a temporary variable.

// Sorting in ascending order
vector<int> nums = {5, 2, 8, 1, 9, 3};
sort(nums.begin(), nums.end());
// nums: {1, 2, 3, 5, 8, 9}

The std::sort() algorithm from <algorithm> sorts elements in ascending order by default. It uses an optimized introsort algorithm with O(n log n) average complexity. Pass iterators to the range you want to sort. The elements must support the less-than operator or you must provide a custom comparator.

// Sorting in descending order
sort(nums.begin(), nums.end(), greater<int>());
// nums: {9, 8, 5, 3, 2, 1}

To sort in descending order, pass greater<int>() as the third argument. This is a function object that reverses the comparison. You can also use a lambda for custom sorting: sort(nums.begin(), nums.end(), [](int a, int b) { return a > b; }). This gives you full control over the sorting criteria.

// Reverse the order of elements
reverse(nums.begin(), nums.end());
// nums: {1, 2, 3, 5, 8, 9}

The std::reverse() algorithm reverses the order of elements in the specified range. It operates in-place with O(n) complexity, swapping elements from both ends toward the middle. This is useful for reversing sorted data or processing elements in opposite order without using reverse iterators.

vector<int> data = {5, -3, 8, -1, 0, -7, 12};

vector<int> data = {5, -3, 8, -1, 0, -7, 12};

auto newEnd = remove_if(data.begin(), data.end(), 
    [](int x) { return x < 0; });
data.erase(newEnd, data.end());

// data: {5, 8, 0, 12}

vector<int> sorted = {10, 20, 30, 50, 60};
int newVal = 40;

// Find correct position using lower_bound
auto pos = lower_bound(sorted.begin(), sorted.end(), newVal);
sorted.insert(pos, newVal);

// sorted: {10, 20, 30, 40, 50, 60}

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

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

// unique() moves duplicates to end, returns iterator to "new end"
auto last = unique(nums.begin(), nums.end());
nums.erase(last, nums.end());

// nums: {1, 2, 3, 4, 5}

Iterators are the bridge between containers and algorithms in C++. They act like smart pointers that know how to traverse a container. Understanding iterators is essential for working effectively with the STL.

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

// begin() and end() - forward iterators
for (auto it = nums.begin(); it != nums.end(); ++it) {
    cout << *it << " ";  // 10 20 30 40 50
}

The begin() method returns an iterator pointing to the first element, while end() returns an iterator pointing past the last element. Use the dereference operator * to access the value. The loop continues while the iterator has not reached the end. Always use pre-increment ++it for better performance with iterators.

// rbegin() and rend() - reverse iterators
for (auto it = nums.rbegin(); it != nums.rend(); ++it) {
    cout << *it << " ";  // 50 40 30 20 10
}

Reverse iterators traverse the vector from back to front. The rbegin() method returns an iterator to the last element, and rend() returns one before the first. Notice you still use ++it to move through the vector - the reverse iterator handles the backward movement internally. This is useful for processing data in reverse order.

// cbegin() and cend() - const iterators (read-only)
for (auto it = nums.cbegin(); it != nums.cend(); ++it) {
    cout << *it << " ";
    // *it = 100;  // Error! Cannot modify through const iterator
}

Const iterators prevent modification of elements through the iterator. Use cbegin() and cend() when you only need to read values. This makes your intent clear and catches accidental modifications at compile time. There are also crbegin() and crend() for const reverse iteration.

// Iterator arithmetic - random access
auto start = nums.begin();
auto third = start + 2;  // Points to 30 (index 2)
cout << "Third element: " << *third << endl;

Vector iterators are random access iterators, meaning you can add or subtract integers to jump to any position. Adding 2 to the begin iterator gives you the third element (index 2). You can also use subtraction: nums.end() - 1 points to the last element. This arithmetic works in O(1) time for vectors.

// Distance between iterators
cout << "Distance: " << distance(start, third) << endl;  // 2

The distance() function calculates how many elements are between two iterators. It returns a signed integer representing the number of increments needed to go from the first iterator to the second. For vector iterators this is O(1), but for other container types it may be O(n). Always pass iterators from the same container.

// Modifying elements through iterator
for (auto it = nums.begin(); it != nums.end(); ++it) {
    *it *= 2;  // Double each element
}
// nums: {20, 40, 60, 80, 100}

Non-const iterators allow you to modify elements by dereferencing and assigning. This is useful when you need to transform data in place. The iterator provides direct access to each element's memory location, so changes are made directly in the vector without any copying. This pattern is common in many STL algorithms.

Iterators with Algorithms

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

// find() - returns iterator to element
auto it = find(nums.begin(), nums.end(), 5);
if (it != nums.end()) {
    cout << "Found 5 at index: " << distance(nums.begin(), it) << endl;  // 4
}

The std::find() algorithm searches for a value and returns an iterator to the first occurrence. If the element is not found, it returns end(). Always check against end before dereferencing the result. Use distance() to convert the iterator to an index. This performs a linear O(n) search.

// count() - count occurrences of a value
int ones = count(nums.begin(), nums.end(), 1);
cout << "Number of 1s: " << ones << endl;  // 2

The std::count() algorithm returns how many times a value appears in the range. It traverses the entire range and counts matching elements. For counting elements that satisfy a condition, use count_if() with a predicate function or lambda. Both operate in O(n) time.

// accumulate() - sum all elements (from <numeric>)
int sum = accumulate(nums.begin(), nums.end(), 0);
cout << "Sum: " << sum << endl;  // 31

The std::accumulate() function from the <numeric> header computes the sum of all elements. The third argument is the initial value. You can also provide a custom binary operation as a fourth argument for other aggregations like product. For example, use accumulate(begin, end, 1, multiplies<int>()) for product.

// min_element() and max_element() - find extremes
auto minIt = min_element(nums.begin(), nums.end());
auto maxIt = max_element(nums.begin(), nums.end());
cout << "Min: " << *minIt << ", Max: " << *maxIt << endl;  // Min: 1, Max: 9

These algorithms return iterators to the minimum and maximum elements respectively. They perform a linear scan through the range. If there are multiple elements with the same min/max value, they return an iterator to the first one. Use minmax_element() to find both in a single pass for better efficiency.

// sort() - sort the vector in ascending order
sort(nums.begin(), nums.end());
// nums: {1, 1, 2, 3, 4, 5, 6, 9}

The std::sort() algorithm sorts elements in ascending order with O(n log n) average complexity. It modifies the vector in place. For descending order, use greater<int>() as the third argument. The algorithm requires random access iterators, so it works with vectors and arrays but not with lists.

// binary_search() - check if element exists (requires sorted vector)
bool found = binary_search(nums.begin(), nums.end(), 4);
cout << "4 exists: " << boolalpha << found << endl;  // true

The std::binary_search() algorithm performs an O(log n) search but requires the range to be sorted first. It returns a boolean indicating whether the element exists. If you need the position, use lower_bound() or upper_bound() instead, which also require sorted data and return iterators.

vector<int> nums = {5, 2, 9, 1, 7};
auto maxIt = max_element(nums.begin(), nums.end());
int index = distance(nums.begin(), maxIt);
cout << "Max value " << *maxIt << " at index " << index << endl;
// Max value 9 at index 2

vector<int> scores = {45, 67, 32, 89, 51, 28, 73};
int count = count_if(scores.begin(), scores.end(), 
    [](int x) { return x > 50; });
cout << "Elements greater than 50: " << count << endl;  // 4