Writing your own vector<T> training implementation
“If you know
std::vector, you know half of C++.”– Bjarne Stroustrup
In this blog post, we will write a naive vector<T> training implementation. Coding up these training implementations, handling corner cases, getting your code reviewed, revisiting your design is very effective at understanding the inner workings of STL data-strucures and writing good C++ code. I adopt a gradual refinement approach, so my first versions will be simpler but less efficient.
Informally, a std::vector<T> represents a dynamically allocated array that can grow as needed. As with any array, a std::vector<T> is a sequence of elements of type T arranged contigously in memory. We will put our homegrown version of vector<T> under the dev namespace.
The internal representation of a vector like type has a book-keeping node that consists of: - A pointer to the raw data (a block of memory that will hold elements of type T) - Size of the container(the number of elements in the container) - Capacity
It’s important to distinguish between size and capacity. size is the number of elements currently in the container. When size == capacity, the container becomes full and will need to grow, which means allocating more member, copying the elements from the old storage to the new storage and getting rid of the old storage.
For those of you, who want to first attempt writing a basic implementation yourself, I present it in the form a task.
The problem statement
Your Task
Implement your own version of a vector with the following methods:
push_back– Adds an element to the back.at– Retrieves an element by index.getSize– Gets the size of the container.getCapacity– Gets the capacity of the container.shrinkToFit– Shrinks the capacity to equal the size of the container.pop_back– Removes the last element in the container. Will never be called on an empty container.
Requirements
- Do not worry about memory alignment or advanced optimizations.
- Do not use
std::vectorin yourdev::vectorimplementation. - Your vector’s capacity must start at 1.
- The capacity should triple every time it is reached.
For more such C++ coding tasks, visit getcracked.io.
A basic implementation
// Write your solution here
// C++20 for C++
#include <cstddef>
#include <cstdint>
#include <format>
#include <initializer_list>
#include <memory>
#include <print>
#include <stdexcept>
#include <type_traits>
#include <utility>
namespace getcracked {
template <typename Element>
class vector {
constexpr static std::size_t initial_capacity{1};
private:
Element* m_data;
std::size_t m_size;
std::size_t m_capacity;
public:
std::size_t get_size() const { return m_size; }
std::size_t get_capacity() const { return m_capacity; }
vector()
: m_data{static_cast<Element*>(operator new(sizeof(Element)))},
m_size{0},
m_capacity{initial_capacity} {}
vector(size_t n, Element& initial_value)
: m_data{static_cast<Element*>(operator new(sizeof(Element) * n))},
m_size{0},
m_capacity{n} {
try {
std::uninitialized_fill_n(m_data, n, initial_value);
m_size = n;
} catch (std::exception& ex) {
operator delete(m_data);
m_capacity = 0;
}
}
vector(std::initializer_list<Element> list)
: m_data{static_cast<Element*>(operator new(sizeof(Element) *
list.size()))},
m_size{list.size()},
m_capacity{list.size()} {
try {
if constexpr (std::is_nothrow_move_constructible_v<Element>) {
std::uninitialized_move(list.begin(), list.end(), m_data);
} else {
std::uninitialized_copy(list.begin(), list.end(), m_data);
}
} catch (std::exception& ex) {
operator delete(m_data);
m_size = 0;
m_capacity = 0;
}
}
vector(const vector& other)
: m_data{operator new(sizeof(Element) * other.get_size())},
m_size{other.get_size()},
m_capacity{other.get_capacity()} {
try {
// Perform a deep-copy of all the elements
std::uninitialized_copy(other.m_data, other.m_data + other.m_size,
m_data);
} catch (std::exception& ex) {
operator delete(m_data);
std::string error_msg =
std::format("Error while copying in copy ctor {}", ex.what());
throw std::logic_error(error_msg);
}
}
vector(vector&& other) noexcept
: m_data{std::exchange(other.m_data, nullptr)},
m_size{std::exchange(other.m_size, 0)},
m_capacity{std::exchange(other.m_capacity, 0)} {}
void swap(vector& other) noexcept {
std::swap(this->m_data, other.m_data);
std::swap(this->m_size, other.m_size);
std::swap(this->m_capacity, other.m_capacity);
}
vector& operator=(const vector& other) {
vector(other).swap(*this);
return *this;
}
vector& operator=(vector&& other) {
vector(std::move(other)).swap(*this);
return *this;
}
bool is_full() { return get_size() == get_capacity(); }
void push_back(Element element) {
std::size_t offset = get_size();
if (m_size == m_capacity - 1) {
// Allocate new memory
std::size_t new_size = get_size() + 1;
std::size_t new_capacity = 3 * m_capacity;
Element* new_memory_block = static_cast<Element*>(operator new(
sizeof(Element) * new_capacity));
Element* ptr_to_new_element{nullptr};
try {
// Construct the new element in new memory block
ptr_to_new_element =
new (new_memory_block + offset) Element(element);
} catch (std::exception& ex) {
operator delete(new_memory_block);
std::string error_msg = std::format(
"Failed to copy-construct element : {}", ex.what());
throw std::logic_error(error_msg);
}
try {
// Copy/move- the elements from the old storage to new
if constexpr (std::is_nothrow_move_constructible_v<Element>) {
std::uninitialized_move(m_data, m_data + offset,
new_memory_block);
} else {
std::uninitialized_copy(m_data, m_data + offset,
new_memory_block);
}
} catch (std::exception& ex) {
std::destroy_at(ptr_to_new_element);
operator delete(new_memory_block);
std::string error_msg = std::format(
"Failed to copy/move data from old to new storage, "
"exception : {}",
ex.what());
throw std::logic_error(error_msg);
}
// Destroy the objects in the old storage
auto p{m_data};
for (auto p{m_data}; p < m_data + m_size; ++p) {
p->~Element();
}
// Deallocate old storage
operator delete(m_data);
// Reassign internal buffer pointer and update size and capacity
m_data = new_memory_block;
m_size = new_size;
m_capacity = new_capacity;
} else {
try {
std::construct_at(m_data + offset, element);
m_size += 1;
} catch (std::exception& ex) {
std::string error_msg = std::format(
"Failed to copy-construct element, exception : {}",
ex.what());
throw std::logic_error(error_msg);
}
}
}
const Element& at(std::size_t index) const {
if (index < 0 || index >= m_size)
throw std::out_of_range("Array index out of bounds!");
return m_data[index];
}
void shrink_to_fit() {
// Allocate a new memory block of capacity = m_size
Element* new_memory_block =
static_cast<Element*>(operator new(sizeof(Element) * m_size));
try {
// Copy/move the elements from the old storage to new storage
if constexpr (std::is_nothrow_move_constructible_v<Element>) {
std::uninitialized_move(m_data, m_data + m_size,
new_memory_block);
} else {
std::uninitialized_copy(m_data, m_data + m_size,
new_memory_block);
}
} catch (std::exception& ex) {
operator delete(new_memory_block);
std::string error_msg = std::format(
"Internal error in shrink_to_fit() : {}", ex.what());
throw std::logic_error(error_msg);
}
// Destroy objects in old storage and deallocate memory
for (auto p{m_data}; p < m_data + m_size; ++p) {
std::destroy_at<Element>(p);
}
// Deallocate memory
operator delete(m_data);
// Reassign internal buffer pointer and set size and capacity
m_data = new_memory_block;
m_capacity = m_size;
}
void pop_back() {
Element* ptr_to_last = m_data + m_size - 1;
std::destroy_at(ptr_to_last);
--m_size;
}
};
} // namespace getcracked
int main() {
getcracked::vector<double> v;
v.push_back(1);
v.push_back(2);
std::println("v[0] = {}", v.at(0));
std::println("size = {}", v.get_size());
std::println("capacity = {}", v.get_capacity());
}