I have attempted to implement a similar version of the STL Vector; several functions are missing but I'd like a few words of advice on whether I am indeed on the right track or whether I should change my approach.
My objective is to understand how the vector works from behind the scenes and not to replace or use it for my own applications. I would like to eventually continue this process for all the STL containers.
namespace mystl
{
template <typename T>
class Vector
{
private:
std::unique_ptr<T[]> values;
std::size_t m_size;
std::size_t m_capacity;
unsigned int m_capacity_inc;
protected:
std::unique_ptr<T[]> get_values();
public:
/* Type definitions */
typedef T* iterator;
typedef const T* const const_iterator;
/* default constructor */
explicit Vector();
/* filling constructor*/
explicit Vector(std::size_t num, const T& val = T());
/* Copy constructor needs to use move since copy is a deleted function in unique_ptr*/
explicit Vector(const Vector<T>& v);
/* Move constructor */
explicit Vector(Vector<T>&& v);
/* Initializer list constructor */
explicit Vector(std::initializer_list<T> l);
/* iterator functions */
iterator begin();
iterator end();
/* capacity info functions */
std::size_t size() const;
std::size_t capacity() const;
bool empty() const;
/* modifier functions*/
void push_back(T t);
void pop_back();
void clear();
void resize(std::size_t new_size);
/* element access*/
T& operator[](int index)
{
return values[index];
}
};
/* move constructor */
template <typename T>
Vector<T>::Vector(Vector<T>&& v)
{
m_capacity = v.capacity();
m_size = v.size();
m_capacity_inc = m_capacity / 2;
values = (v.get_values());
v.clear();
}
/* initializer list constructor */
template <typename T>
Vector<T>::Vector(std::initializer_list<T> l)
{
m_size = 0;
m_capacity = l.size();
m_capacity_inc = m_size / 2;
values = std::make_unique<T[]>(m_capacity);
for (auto val : l)
{
push_back(val);
}
}
/* check is vector is empty */
template <typename T>
bool Vector<T>::empty() const
{
return m_size == 0;
}
/* returns pointer to first vector element */
template <typename T>
typename Vector<T>::iterator Vector<T>::begin()
{
return values.get();
}
/* returns pointer to last vector element */
template <typename T>
typename Vector<T>::iterator Vector<T>::end()
{
return values.get() + m_size;
}
/* size private member getter */
template <typename T>
std::size_t Vector<T>::size() const
{
return m_size;
}
/* capacity private member getter */
template <typename T>
std::size_t Vector<T>::capacity() const
{
return m_capacity;
}
/* pushes new value to the end of the vector*/
template <typename T>
void Vector<T>::push_back(T t)
{
if (m_size >= m_capacity)
{
/* size has reached capacity so we must reallocate a new, larger array */
m_capacity = m_capacity + m_capacity_inc;
/* double the capacity increase size */
m_capacity_inc = m_capacity_inc << 1;
/* allocate the new memory for the vector*/
std::unique_ptr<T[]> new_vec = std::make_unique<T[]>(m_capacity);
/* copy the old values to the new array */
for (std::size_t index = 0; index < m_size; ++index)
{
new_vec[index] = values[index];
}
/* move ownership of the new array to the current vector pointer */
values = std::move(new_vec);
}
/* input the new value and increase the size; */
values[m_size++] = t;
}
/* removes the last item and deletes the memory area related to that object and decreases the size. capacity is not affected.*/
template <typename T>
void Vector<T>::pop_back()
{
(values)[m_size - 1].~T();
--m_size;
}
/* clear function resets capacity info and deallocates memory.*/
template <typename T>
void Vector<T>::clear()
{
m_size = 0;
m_capacity = 0;
m_capacity_inc = 1;
values.reset();
}
/* resizes the container to the argument size. if the new size is less than the old size, values after the new_size are set as the default value of the
type of the template object */
template<typename T>
void Vector<T>::resize(std::size_t new_size)
{
auto new_array = std::make_unique<T[]>(new_size);
m_capacity = new_size;
m_capacity_inc = new_size;
int array_end = m_size < new_size ? m_size : new_size;
for (auto i = 0; i < array_end; i++)
{
new_array = values[i];
}
values = std::move(new_array);
m_size = new_size;
}
/* a protected function that returns the container array. */
template <typename T>
std::unique_ptr<T[]> Vector<T>::get_values()
{
/* returns an l value reference */
return std::move(values);
}
/* default vector constructor, with an empty array allocated of 0 size. */
template <typename T>
Vector<T>::Vector()
{
m_size = 0;
m_capacity = 0;
m_capacity_inc = 1;
values = std::make_unique<T[]>(m_capacity);
}
/* constructs container with size and capacity of the argument, with all values initiated with the value argument */
template <typename T>
Vector<T>::Vector(std::size_t num, const T& val)
{
/* allocate memory */
m_size = m_capacity = num;
m_capacity_inc = num / 2;
values = std::make_unique<T[]>(num);
/* initialize values */
for (std::size_t i = 0; i < m_size; ++i)
{
values[i] = val;
}
}
/* copy constructor: copies the capacity information and values from the argument vector*/
template <typename T>
Vector<T>::Vector(const Vector<T>& v)
{
m_capacity = v.m_capacity;
m_size = v.size();
m_capacity_inc = m_capacity / 2;
values = std::make_unique<T[]>(m_capacity);
for (auto i = 0; i < m_size; ++i)
{
values[i] = v.values[i];
}
}
}
I have omitted several functions which I will continue to implement - such as shrink_to_fit, reverse iterators, emplacers, operator overlaods.
Allocation in my case is being performed using smart pointers - should I opt to use the same allocator functionality implemented by the native vector or would that be an exercise in futility?
new[]
(even when/if hidden insidemake_unique
) can't work correctly. To make it work correctly, you want to allocate raw memory withoperator new
, then use placement new to create objects in that memory. As it is now, you're creating actual objects in the unused part of the memory, which isn't allowed. – Jerry Coffin Jan 10 at 22:30