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);
std::vector vec(10, 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));
std::vector vec1 = {1, 2, 3, 4, 5};
std::vector vec2(vec1);
std::vector vec3(vec1.begin(), vec1.begin() + 3);
std::vector vec4(std::move(vec1));
std::vector vec;
vec.assign(10, 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;
vec.push_back(1);
vec.emplace_back(3);
vec.insert(vec.begin(), 0);
vec.insert(vec.begin() + 2, 5);
vec.emplace(vec.begin() + 1, 6);
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);
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");
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
Removing Elements
vec.pop_back();
vec.erase(vec.begin()+2);
vec.erase(vec.begin() + 4, vec.begin() + 6);
vec.clear();
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};
auto new_end = std::remove(vec.begin(), vec.end(), 3);
vec.erase(new_end, vec.end());
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
for (size_t i = 0; i < vec.size(); ++i) {
cout << vec[i] << " ";
}
for (int val : vec) {
cout << val << " ";
}
for (auto it = vec.begin(); it != vec.end(); ++it) {
cout << *it << " ";
}
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);
vector vec = {1, 2, 3, 4, 5};
vec.shrink_to_fit();
cout << "Capacity: " << vec.capacity();
Vector Algorithms
std::sort(vec.begin(), vec.end());
bool found = std::binary_search(vec.begin(), vec.end(), 3);
auto it = std::find(vec.begin(), vec.end(), 8);
std::reverse(vec.begin(), vec.end());
int sum = std::accumulate(vec.begin(), vec.end(), initial_value);
int count_3 = std::count(vec.begin(), vec.end(), 3);
int count_greater_than_4 = std::count_if(vec.begin(), vec.end(), [](int val) { return val > 4; });
auto min_it = std::min_element(vec.begin(), vec.end());
auto max_it = std::max_element(vec.begin(), vec.end());
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).
