The Essential C++ STL Cheat sheet
This cheat sheet provides a quick reference to the most commonly used operations and features of std::vector
in C++.
Vectors
Vectors are a part of the C++ Standard Template Library (STL) and are one of the most commonly used sequence containers. They provide a dynamic array that can grow and shrink in size as needed. The key points about vectors:
Dynamic Size and Automatic Memory Management: Unlike arrays, vectors can dynamically resize themselves when elements are added or removed. This makes them more flexible and easier to use when the number of elements is not known in advance. They allocate memory as needed and deallocate it when it is no longer required.
Contiguous Memory: Vectors store elements in contiguous memory locations, which means that elements can be accessed using pointer arithmetic. This also ensures that vectors are cache-friendly and provide fast access to elements.
Iterators: Vectors support iterators, which are objects that point to elements within the container. Iterators provide a way to traverse the elements of the vector and perform operations on them.
Vector Basics
Initialize a vector
std::vector vec;
std::vector vec(10); // Initializes a vector of size 10
std::vector vec(10, 5); //Size 10 with all elements set to 5
std::vector vec = {1, 2, 3, 4, 5}; Initializes a vector of size 10 with all elements set to 5
Initialization from an Array, Vec, Range and Move:
int arr[] = {1, 2, 3, 4, 5};
std::vector vec(std::begin(arr), std::end(arr));
//Another Vector
std::vector vec1 = {1, 2, 3, 4, 5};
std::vector vec2(vec1); // Copy constructor
std::vector vec3(vec1.begin(), vec1.begin() + 3); // Initializes with the first three elements
//Move Initialization
std::vector vec4(std::move(vec1)); // vec1 is now empty
//Assign method
std::vector vec;
vec.assign(10, 5); // Assigns 10 elements with value 5
Adding Elements
Using
push_back
: Adds an element to the end of the vector.Using
emplace_back
: Constructs an element in place at the end of the vector.Using
insert
: Inserts elements at a specified position in the vector.Using
emplace
: Constructs an element in place at a specified position in the vector.
std::vector vec;
// Using push_back
vec.push_back(1);
// Using emplace_back
vec.emplace_back(3);
// Using insert
vec.insert(vec.begin(), 0); // Inserts 0 at the beginning
vec.insert(vec.begin() + 2, 5); // Inserts 5 at the third position
// Using emplace
vec.emplace(vec.begin() + 1, 6); // Constructs 6 at the second position
Difference between push_back and emplace_back
push_back
adds an element to the end of the vector. It takes an existing object and copies or moves it into the vector.
std::vector<std::string> vec;
std::string str = "Hello";
vec.push_back(str); // Copies str into the vector
emplace_back
constructs an element in place at the end of the vector. It forwards the arguments to the constructor of the element, avoiding unnecessary copies or moves.
std::vector<std::string> vec;
vec.emplace_back("Hello"); // Constructs the string directly in the vector
emplace_back
constructs the element in place, while push_back
requires an existing object. emplace_back
can be more efficient as it avoids unnecessary copies or moves. Use emplace_back when you want to construct the element directly in the container, and push_back when you have an existing object to add.
Similarly, emplace
constructs the element in place, while insert
requires an existing object. And you should emplace when you want to construct the element directly in the container, and insert when you have an existing object to add.
Accessing Elements
int first = vec.front() // Using front method int second = vec.at(1); // Using the at() method (with bounds checking) int third = vec[2]; // Using the subscript operator int last = vec.back(); // Using back method auto it = vec.begin(); int fourth = *(it+3); //Using Iterators
Removing Elements
vec.pop_back(); // Removes the last element
vec.erase(vec.begin()+2); // Removes the element at index 2
vec.erase(vec.begin() + 4, vec.begin() + 6); // Using erase to remove a range of elements
vec.clear(); // Removes all elements
The remove algorithm
The remove algorithm is part of the C++ Standard Library and is used to remove elements from a range. It does not actually remove elements from the container but rather shifts the elements to be removed to the end of the container and returns an iterator to the new end of the range. It is typically used in conjunction with the erase method of the container to actually remove the elements.
std::vector<int> vec = {1, 2, 3, 4, 5, 3, 6, 3, 7};
// Using remove to shift elements to be removed to the end
auto new_end = std::remove(vec.begin(), vec.end(), 3);
// Erase the elements from the container
vec.erase(new_end, vec.end());
// Erase-Remove Idiom
vec.erase(std::remove(vec.begin(), vec.end(), 3), vec.end());
std::remove shifts all elements equal to 3 to the end of the vector and returns an iterator to the new end.
Iterating Over a Vector
// Using Index-Based Loop
for (size_t i = 0; i < vec.size(); ++i) {
cout << vec[i] << " ";
}
// Using Range-Based For Loop
for (int val : vec) {
cout << val << " ";
}
// Using Iterators
for (auto it = vec.begin(); it != vec.end(); ++it) {
cout << *it << " ";
}
// Using for_each Algorithm
std::for_each(vec.begin(), vec.end(), [](int val) {
cout << val << " ";
});
Memory Management Functions
When a vector is created, it allocates a small amount of memory. As elements are added, if the current capacity is exceeded, the vector allocates more memory (usually doubling the current capacity). When the vector's capacity is exceeded, it allocates a new block of memory with a larger capacity. The existing elements are copied to the new memory block, and the old memory is deallocated. This process can be costly in terms of time and memory, which is why vectors allocate more memory than needed to minimize reallocations.
reserve
: Requests that the vector capacity be at least enough to contain n elements. This can prevent multiple reallocations if the number of elements to be added is known in advance.shrink_to_fit
: Requests the container to reduce its capacity to fit its size. This is a non-binding request to reduce memory usage.capacity
: Returns the number of elements that the vector can hold before needing to allocate more memory.
vector vec; vec.reserve(100); // Pre-allocate memory for 100 elements
vector vec = {1, 2, 3, 4, 5};
vec.shrink_to_fit(); // Reduce capacity to match size
//Capacity
cout << "Capacity: " << vec.capacity();
Vector Algorithms
std::sort(vec.begin(), vec.end()); // Sort ascending order by default
bool found = std::binary_search(vec.begin(), vec.end(), 3);
auto it = std::find(vec.begin(), vec.end(), 8); //searches for the first occurrence
std::reverse(vec.begin(), vec.end()); //reverses the order of elements
int sum = std::accumulate(vec.begin(), vec.end(), initial_value);
int count_3 = std::count(vec.begin(), vec.end(), 3); //counts the number of occurrences
// Count If counts the number of elements in a vector that satisfy a given predicate.
int count_greater_than_4 = std::count_if(vec.begin(), vec.end(), [](int val) { return val > 4; });
//The min_element algorithm finds the smallest element in a vector.
auto min_it = std::min_element(vec.begin(), vec.end());
//The max_element algorithm finds the largest element in a vector.
auto max_it = std::max_element(vec.begin(), vec.end());
//The equal algorithm checks if two vectors are equal.
bool are_equal = std::equal(vec.begin(), vec.end(), vec2.begin());
Conclusion
Vectors and Maps in C++ are a powerful and flexible container provided by the Standard Template Library (STL).