Vector in C++

712

Vectors in C++

A vector in C++ is a sequence container provided by the Standard Template Library (STL) that encapsulates dynamic arrays. Vectors are similar to arrays but with the added advantage of being able to automatically resize themselves when elements are added or removed.

Key Features of Vectors:

Dynamic Sizing: Vectors can dynamically adjust their size, meaning you don’t need to know the number of elements in advance. They can grow or shrink as needed.
Contiguous Memory: Vectors store elements in contiguous memory locations, just like arrays. This ensures fast access to elements and better cache performance.
Efficient Access: Accessing elements in a vector is fast, with time complexity (O(1)) for random access.
Automatic Memory Management: Vectors manage their memory automatically, including allocation and deallocation, based on their size and capacity.
Rich Functionality: Vectors provide a wide range of functions for manipulation, including inserting, deleting, and accessing elements, as well as resizing and copying.

Vector Capacity vs. Size:

Size: The number of elements currently stored in the vector.
Capacity: The total amount of space that has been allocated for the vector. The capacity is always greater than or equal to the size.

When the size exceeds the capacity, the vector automatically reallocates its memory to accommodate more elements, typically by doubling its capacity. This reallocation can be costly, so it’s generally more efficient to reserve space in advance if you know the expected size.

Common Operations on Vectors:

Accessing Elements:
- at(index): Returns the element at the specified position with bounds checking.
- operator[]: Provides direct access to elements without bounds checking.
- front(): Returns a reference to the first element.
- back(): Returns a reference to the last element.
- data(): Returns a pointer to the underlying array.
Modifying Elements:
- push_back(value): Adds an element to the end of the vector.
- pop_back(): Removes the last element.
- insert(position, value): Inserts an element at the specified position.
- erase(position): Removes an element from the specified position.
- clear(): Removes all elements from the vector.
Resizing and Capacity Management:
- resize(new_size): Resizes the vector to contain new_size elements.
- reserve(new_capacity): Requests that the vector capacity be at least enough to contain new_capacity elements.
- shrink_to_fit(): Reduces the capacity to fit the current size.

Vector Initialization Methods

Vectors can be initialized in several ways, depending on how you want to set their initial values:

Default Initialization:
- Declares an empty vector with no elements.
```
std::vector<int> v; // Empty vector
```
Initialization with Size:
- Creates a vector of a specified size with default values for the type (e.g., 0 for int).
```
std::vector<int> v(5); // Vector with 5 elements, all initialized to 0
```
Initialization with Size and Value:
- Creates a vector of a specified size and initializes all elements to a specified value.
```
std::vector<int> v(5, 10); // Vector with 5 elements, all initialized to 10
```

List Initialization:

Initializes a vector with a list of values.

std::vector<int> v = {1, 2, 3, 4, 5}; // Vector with 5 elements: 1, 2, 3, 4, 5

Copy Initialization:

Initializes a vector by copying elements from another vector.

std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2(v1); // v2 is a copy of v1

Range Initialization:

Initializes a vector with elements from a range defined by two iterators.

std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2(v1.begin(), v1.begin() + 3); // v2 contains {1, 2, 3}

1. Accessing Elements:

at(index): Returns the element at the specified position with bounds checking.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {10, 20, 30, 40, 50};
    std::cout << "Element at index 2: " << v.at(2) << std::endl; // Output: 30

    try {
        std::cout << v.at(10) << std::endl; // Throws out_of_range exception
    } catch (const std::out_of_range& e) {
        std::cout << "Exception: " << e.what() << std::endl; // Output: vector::_M_range_check: __n (which is 10) >= this->size() (which is 5)
    }

    return 0;
}

operator[]: Provides direct access to elements without bounds checking.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {10, 20, 30, 40, 50};
    std::cout << "Element at index 2: " << v[2] << std::endl; // Output: 30

    // Note: Accessing an out-of-bounds index will lead to undefined behavior.
    std::cout << "Out-of-bounds access: " << v[10] << std::endl; // Undefined behavior

    return 0;
}

front(): Returns a reference to the first element.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {10, 20, 30, 40, 50};
    std::cout << "First element: " << v.front() << std::endl; // Output: 10
    return 0;
}

back(): Returns a reference to the last element.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {10, 20, 30, 40, 50};
    std::cout << "Last element: " << v.back() << std::endl; // Output: 50
    return 0;
}

data(): Returns a pointer to the underlying array.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {10, 20, 30, 40, 50};
    int* p = v.data();
    std::cout << "First element using data(): " << *p << std::endl; // Output: 10
    return 0;
}

2. Modifying Elements:

push_back(value): Adds an element to the end of the vector.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {10, 20, 30};
    v.push_back(40); // Adds 40 to the end
    std::cout << "After push_back: ";
    for (int n : v) std::cout << n << " "; // Output: 10 20 30 40
    std::cout << std::endl;
    return 0;
}

pop_back(): Removes the last element from the vector.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {10, 20, 30, 40};
    v.pop_back(); // Removes the last element (40)
    std::cout << "After pop_back: ";
    for (int n : v) std::cout << n << " "; // Output: 10 20 30
    std::cout << std::endl;
    return 0;
}

insert(position, value): Inserts an element at the specified position.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {10, 20, 40};
    v.insert(v.begin() + 2, 30); // Inserts 30 at position 2
    std::cout << "After insert: ";
    for (int n : v) std::cout << n << " "; // Output: 10 20 30 40
    std::cout << std::endl;
    return 0;
}

erase(position): Removes an element from the specified position.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {10, 20, 30, 40};
    v.erase(v.begin() + 2); // Removes the element at position 2 (30)
    std::cout << "After erase: ";
    for (int n : v) std::cout << n << " "; // Output: 10 20 40
    std::cout << std::endl;
    return 0;
}

clear(): Removes all elements from the vector.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {10, 20, 30, 40};
    v.clear(); // Removes all elements
    std::cout << "After clear, size: " << v.size() << std::endl; // Output: 0
    return 0;
}

3. Resizing and Capacity Management:

resize(new_size): Resizes the vector to contain new_size elements.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {10, 20, 30};
    v.resize(5); // Resizes the vector to have 5 elements
    std::cout << "After resize to 5 elements: ";
    for (int n : v) std::cout << n << " "; // Output: 10 20 30 0 0
    std::cout << std::endl;
    return 0;
}

reserve(new_capacity): Requests that the vector capacity be at least enough to contain new_capacity elements.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;
    v.reserve(10); // Reserves space for 10 elements
    std::cout << "Capacity after reserve: " << v.capacity() << std::endl; // Output: 10
    return 0;
}

shrink_to_fit(): Reduces the capacity to fit the current size.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {10, 20, 30, 40, 50};
    v.reserve(100); // Reserves space for 100 elements
    std::cout << "Capacity before shrink_to_fit: " << v.capacity() << std::endl; // Output: 100
    v.shrink_to_fit(); // Reduces capacity to fit the current size
    std::cout << "Capacity after shrink_to_fit: " << v.capacity() << std::endl; // Output: 5
    return 0;
}

Iterators in C++

An iterator in C++ is an object (like a pointer) that allows traversing through the elements of a container (e.g., vector, list, set). Iterators provide a way to access and modify elements in a container without exposing the underlying data structure.

Types of Iterators:

Input Iterator: Used for reading elements in a sequence from the beginning to the end (e.g., istream_iterator).
Output Iterator: Used for writing elements to a sequence (e.g., ostream_iterator).
Forward Iterator: Combines the capabilities of both input and output iterators but allows traversal only in a single direction.
Bidirectional Iterator: Extends forward iterators by allowing traversal in both forward and backward directions (e.g., iterators used in std::list).
Random Access Iterator: Allows direct access to any element in constant time, supporting arithmetic operations (e.g., iterators used in std::vector).

Common Operations with Iterators:

Accessing Elements:
- *it: Dereferences the iterator to access the value of the element it points to.
- it->member: Accesses a member of the object pointed to by the iterator (used with iterators pointing to objects).
Traversal:
- ++it: Moves the iterator to the next element (pre-increment).
- it++: Moves the iterator to the next element but returns the previous position (post-increment).
- --it: Moves the iterator to the previous element (pre-decrement).
- it--: Moves the iterator to the previous element but returns the previous position (post-decrement).
Comparing Iterators:
- it1 == it2: Checks if two iterators point to the same element.
- it1 != it2: Checks if two iterators point to different elements.
- it1 < it2: Checks if it1 comes before it2 (only for random access iterators).
Arithmetic with Iterators (Random Access Iterators):
- it + n: Moves the iterator forward by n positions.
- it - n: Moves the iterator backward by n positions.
- it2 - it1: Returns the distance between two iterators.

Iterator Types in Vectors:

begin() and end():

begin(): Returns an iterator to the first element of the vector.
end(): Returns an iterator to the position just past the last element.

std::vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << " "; // Output: 1 2 3 4 5
}

rbegin() and rend():
- rbegin(): Returns a reverse iterator pointing to the last element.
- rend(): Returns a reverse iterator pointing to the position just before the first element.
```
std::vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.rbegin(); it != v.rend(); ++it) {
    std::cout << *it << " "; // Output: 5 4 3 2 1
}
```

cbegin() and cend():

cbegin() and cend() return constant iterators, which prevent modification of the elements they point to.

std::vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.cbegin(); it != v.cend(); ++it) {
    std::cout << *it << " "; // Output: 1 2 3 4 5
}

emplace() and emplace_back():
- emplace(position, args...): Inserts a new element in the vector at the specified position using arguments passed to the constructor.
- emplace_back(args...): Adds a new element to the end of the vector using the arguments passed to the constructor.
```
std::vector<std::pair<int, int>> v;
v.emplace_back(1, 2); // Inserts {1, 2} at the end
```

Practical Problem: Implementing a Vector Operations Program

Problem Statement:

Write a C++ program that performs the following operations using vectors and iterators:

Initialize a vector with a range of values.
Use iterators to traverse and display the vector elements.
Modify elements at specific positions using iterators.
Insert and delete elements using iterators.

Sample Solution:

#include <iostream>
#include <vector>

int main() {
    // Step 1: Initialize a vector with values 1 to 5
    std::vector<int> v = {1, 2, 3, 4, 5};

    // Step 2: Traverse and display elements using iterators
    std::cout << "Original Vector: ";
    for (auto it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // Step 3: Modify elements at specific positions using iterators
    *(v.begin() + 2) = 10; // Modify the 3rd element (index 2)
    std::cout << "After Modification: ";
    for (auto it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // Step 4: Insert and delete elements using iterators
    v.insert(v.begin() + 1, 20); // Insert 20 at the 2nd position (index 1)
    v.erase(v.begin() + 4); // Remove the 5th element (index 4)
    std::cout << "After Insertion and Deletion: ";
    for (auto it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

Thank you for read the document.

Comments (0)