1
\$\begingroup\$

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 goal here is to understand how the vector works behind the scenes, rather than using it for my applications.

#include <initializer_list>
#include <algorithm>
#include <memory>

struct out_of_range {};

template<typename T, typename A>
struct vector_base
{
    A alloc;    //allocator
    T* elem;    //start of allocation
    int sz;     //number of elements
    int space;  //amount of allocated space
    vector_base(int n)
        :elem{alloc.allocate(n)}, sz{n}, space{n} {}

    void construct(T def) {for (int i = 0; i < sz; i++) alloc.construct(&elem[i], def); }

    ~vector_base() 
    {
        //for(int i = 0; i < sz; i++) alloc.destroy(&elem[i]);
        alloc.deallocate(elem, space);
        std::cout << "Vector destroyed.\n";
    }
};

template<typename T, typename A = std::allocator<T>> //requires Element<T>()
class vector : private vector_base<T,A>
{
    void reserve(int newspace);

public:
    
    vector (int size, T def = T())
        : vector_base<T,A>(size)
    {
        this->construct(def); // initialize each element to 0
        std::cout << "Vector constructed\n";
    }

    //~vector() {delete [] this->elem;}

    //{} initialization
    vector (std::initializer_list<int> lst)
        :vector_base<T,A>(lst.size())
    {
        std::copy (lst.begin(), lst.end(), this->elem);
        std::cout << "Vector constructed\n";
    }

    //destruction of elements is managed in vector_base

    vector (const vector& arg); //copy constructor
    vector& operator= (const vector& arg); //copy assignment

    vector ( vector&& arg); //move constructor
    vector& operator= (vector&& arg); //move assignment

    //subscript operators
    T& operator[] (int n) { return this->elem[n]; }
    const T& operator[] (int n) const { return this->elem[n]; }

    T& at(int n);
    const T& at(int n) const;

    int size() const { return this->sz; }
    int capacity() const { return this->space; }

    void resize(int newspace, T def = T()); //growth
    void push_back(const T& d);
    void erase();
};

//copy constructor
template<typename T,typename A> 
vector<T,A>::vector (const vector<T,A>& arg)
    :vector_base<T,A>{arg.size()}
{
    std::copy (arg.elem, arg.elem + arg.sz, this->elem);
    std::cout << "Vector constructed\n";
}

//copy assignment
template<typename T,typename A> 
vector<T,A>& vector<T,A>::operator= (const vector<T,A>& arg)
{
    if (this == &arg) return *this; //self-assignment, do nothing

    if (arg.sz <= this->space) // enough space, no need for extra allocation
    {
        for (int i = 0; i < arg.sz; i++) this->elem[i] = arg.elem[i]; //copy elements
        this->sz = arg.sz;
        return *this;
    }

    T* n = this->alloc.allocate(arg.sz);
    for (int i = 0; i < arg.sz; i++) n[i] = arg.elem[i];  //copy all the elements from a to the newly allocated array
    //for (int i = 0; i < arg.sz; i++) this->alloc.destroy(&this->elem[i]);
    this->alloc.deallocate(this->elem, this->space);
    this->space = arg.space;
    this->sz = arg.sz;
    this->elem = n; //set the elem (of the current vector) to the argumen's elem
    return *this; //return a self-reference
}

template<typename T, typename A>
T& vector<T,A>::at(int n)
{
    if (n < 0 || n >= this->sz) throw out_of_range();
    return this->elem[n];
}

template<typename T, typename A>
const T& vector<T,A>::at(int n) const
{
    if (n < 0 || n >= this->sz) throw out_of_range();
    return this->elem[n];  
}

//move constructor
template<typename T,typename A> 
vector<T,A>::vector (vector<T,A> && arg)
    :vector_base<T,A>{arg.size()}
{
    this->elem = arg.elem;
    arg.elem = nullptr;
    arg.space = 0;
    arg.sz = 0;
    std::cout << "Vector constructed\n";
}

//move assignment
template<typename T,typename A> 
vector<T,A>& vector<T,A>::operator= (vector<T,A> && arg)
{
    
    this->elem = arg.elem;
    this->sz = arg.sz;

    for (int i = 0; i < arg.sz; i++) this->alloc.destroy(&this->elem[i]);
    arg.elem = nullptr;
    arg.sz = 0;
    return *this;
}

template<typename T,typename A> 
void vector<T,A>::reserve(int newspace)
{
    if(newspace <= this->space) return; //never allocate less memory
    T* p = this->alloc.allocate(newspace);
    for(int i = 0; i < this->sz; i++) this->alloc.construct(&p[i], this->elem[i]); //copy the elements from the old array to the new one
    //for(int i = 0; i < this->sz; i++) this->alloc.destroy(&this->elem[i]);
    this->alloc.deallocate(this->elem, this->space);
    this->elem = p; //point elem to the newly allocated array p
    this->space = newspace;
}

template<typename T,typename A> 
void vector<T,A>::resize(int newspace, T def)
//make the vector have newspace elements
//initialize each new element with a default value 
//  -default T value 
//  -or a value d if specified
{
    reserve(newspace);
    for (int i = this->sz; i < newspace; i++) this->alloc.construct(&this->elem[i],def);
    for (int i = newspace; i < this->sz; i++) this->alloc.destroy(&this->elem[i]);
    this->sz = newspace;
}

template<typename T,typename A> 
void vector<T,A>::push_back(const T& d)
{
    if(this->space == 0) //if there's no space (default constructor)
        reserve(8); //reserve space for 8 elements

    else if (this->sz == this->space) //if the space is equal to the size
        reserve(this->space * 2); //double the space

    this->alloc.construct(&this->elem[this->sz], d); // add d at the end
    ++this->sz; // increase size by 1
}
\$\endgroup\$
3
  • \$\begingroup\$ @BCdotWEB The purpose of the project was to understand how it worked, not that he doesn't understand it now. \$\endgroup\$
    – Parekh
    Jan 12 at 11:41
  • \$\begingroup\$ exactly. I am a beginner, and I really want to understand how vector (and later, other containers, data structures and algorithms ) work. \$\endgroup\$ Jan 12 at 11:55
  • \$\begingroup\$ have a read of the vector series: lokiastari.com/series \$\endgroup\$ Jan 12 at 18:13
2
\$\begingroup\$

Summary

Broken.

  • It leaks memory.
  • It does not construct/destruct the object correctly.

Please have a read of the articles I wrote on building your own vector.

Have a read of the vector series: lokiastari.com/series

Code Review

There is one of these in the standard!

struct out_of_range {};

If you are going to define your own exceptions then please at least inherit from std::exception but preferably std::runtime_error. These base classes allow you to store an error message that you can use for logging.


Sure it is fine to use a standard allocator. But remember that allocators simply allocate the space they do not call the constructor or the destructor of the object that they store.

template<typename T, typename A> struct vector_base {
    A alloc;    //allocator

All relatively standard.

    T* elem;    //start of allocation
    int sz;     //number of elements
    int space;  //amount of allocated space

You only have one constructor here?

    vector_base(int n)
        :elem{alloc.allocate(n)}, sz{n}, space{n} {}

What happens when the vector is move constructed? Having this as a base class will force you to allocate space when the move constructor is not supposed to. You are supposed to move the pre-allocated storage from the source to the new vector.


Another question above this constructor.

    vector_base(int n)
        :elem{alloc.allocate(n)}, sz{n}, space{n} {}

Why is size sz set to n? You always allocate all the objects in the array on construction. That sort of defeats the purpose of pre-allocating with extra space. There is a difference between the space you have and the number of elements you have. There should be a constructor that allows the child to establish this.


Side note here:
The std::vector behaves like a normal C array. It destroys the objects contained in the reverse order. This mimics the normal behavior of RAII objects. The most recently created is the first to be destroyed.

I would use this behavior as well.

    ~vector_base() 
    {
        //for(int i = 0; i < sz; i++) alloc.destroy(&elem[i]);
        alloc.deallocate(elem, space);
        std::cout << "Vector destroyed.\n";
    } };

I don't see a default constructor ?

    vector (int size, T def = T())
        : vector_base<T,A>(size)
    {
        this->construct(def); // initialize each element to 0
        std::cout << "Vector constructed\n";
    }

What happens if I want to create an empty vector? I need to explicitly set the size to zero? Sure it's a valid design (but not what I would expect).


Delete commented out code.

    //~vector() {delete [] this->elem;}

    //{} initialization

Normally the move operators are marked noexcept.

    vector ( vector&& arg); //move constructor
    vector& operator= (vector&& arg); //move assignment

This is because if they are added to standard containers objects with noecept move operations can have certain optimizations done to them without violating the string exception gurantee.


When I grow the internal array it because I want to put more stuff in it.

    void resize(int newspace, T def = T()); //growth

The stuff I put in it may not necessarily be a default initialized T object, nor will I usually want to put the same object into all locations. Forcing me to initialize all the objects now is going to be very inefficient if I am just going to overwrite them.

You should allocate the space (increase space) but not increase size sz and not initalize the objects. When you add more items to the containre then you can initialize the objects either via copy or move.


You only support copy insertion into the contaienr.

    void push_back(const T& d);

I would add move and build in place.

    void push_back(T&& d);
    template<typename... Args>
    void emplace_back(Args&&...);

Copy only works if the elements are already constructed.

//copy constructor
template<typename T,typename A>  vector<T,A>::vector (const vector<T,A>& arg)
    :vector_base<T,A>{arg.size()} {
    std::copy (arg.elem, arg.elem + arg.sz, this->elem);
    std::cout << "Vector constructed\n";
}

Your base class allocated the space but does not initialize the objects in that space. So you have uninitialized memory there. You then try and copy into that un-initialized memory. This will invoke the copy assignment operator on the objects (this makes the assumption that the object has been constructed (which it has not).

You need to construct each if the elements. The easy way to do this is to call push_back.

//copy constructor
template<typename T,typename A>
vector<T,A>::vector(vector<T,A> const& arg)
    : vector_base<T,A>{arg.size()}
{
    // First set size to zero as your base class sets it to n.
    sz = 0;
    for (auto const& element: arg) {
       push_back(element);
    }
}

Note: push back needs to call the constructor (I will check that when I get there).


You make things hard for your self by doing this manually. Look up the copy and swap idiom.

template<typename T,typename A> 
vector<T,A>& vector<T,A>::operator= (const vector<T,A>& arg) {

    // Sure.
    // But this pattern is self deeating as normally you
    // don't do self assignment so you on average this makes the
    // copy slower because now every time you have to do this check.
    //
    // The copy and swap idium goes the other way.
    // Normally operations (which is 99.9999999999999% of them) don't pay
    // the cost for this test.
    // unfortunately on self assignment you do lots of extra work and
    // make an unnecessary copy. But on average it is still cheaper as
    // self assignment happens rareally in normal code (if it happens a lot
    // in your code then make an exception and do the test but prove that
    // you are doing a lot of self assignment first to make it worth the
    // hassle.
    if (this == &arg) return *this; //self-assignment, do nothing



    if (arg.sz <= this->space) // enough space, no need for extra allocation
    {
        // You can use copy for the first `this->sz` elements.
        // But from this->sz to arg.sz you need to initialize the elements first.
        // and if arg.sz is smaller than this->sz you will need to call
        // the destructor on the elements.
        for (int i = 0; i < arg.sz; i++) this->elem[i] = arg.elem[i]; //copy elements
        this->sz = arg.sz;
        return *this;
    }


    // Get some space.
    // Remember the allocator has not initialized the object in this
    // storage so you can not simply copy. You must initialize
    // each member (call the constructor).
    // note: calling the constructor can throw. If this happens you
    //       should make sure to release the allocated array correctly.
    T* n = this->alloc.allocate(arg.sz);
    for (int i = 0; i < arg.sz; i++) n[i] = arg.elem[i]; 

    // Before you call deallocate you must call the destructor on all the
    // elements that have been stored in this space. The allocator does not
    // do this for you.
    // Note: Calling the destructor can potentially throw. You must make sure
    //       to call deallocate even if you throw otherwise you will leak.
    this->alloc.deallocate(this->elem, this->space);

    // Make sure this still happens if there is an exception thrown.
    // otherwise your object will be in some funcky state.
    this->space = arg.space;
    this->sz = arg.sz;
    this->elem = n; //set the elem (of the current vector) to the argumen's elem
    return *this; //return a self-reference }

This move does extra allocation (why).
But then leaks it.

template<typename T,typename A>
vector<T,A>::vector (vector<T,A> && arg)
    // The base class allocates space you are not going to use.
    :vector_base<T,A>{arg.size()} {
    // You just leaked the memory allocated in the base class constructor.
    this->elem = arg.elem;

    // Sure.
    arg.elem = nullptr;
    arg.space = 0;
    arg.sz = 0;
    std::cout << "Vector constructed\n"; }

Again you are leaking memory.

template<typename T,typename A>
vector<T,A>& vector<T,A>::operator= (vector<T,A> && arg) {
    
    // You just leaked this->elem
    this->elem = arg.elem;
    this->sz = arg.sz;

    // Now you are calling the destructor
    // on the elements thus making them invalid.
    // There seems be an ordering issue here.
    // destory and release this object first.
    // then copy over the elements.
    for (int i = 0; i < arg.sz; i++) this->alloc.destroy(&this->elem[i]);
    arg.elem = nullptr;
    arg.sz = 0;
    return *this; }

Reserve should not initialize the memory.

template<typename T,typename A>  void vector<T,A>::reserve(int newspace) {
    if(newspace <= this->space) return; //never allocate less memory
    T* p = this->alloc.allocate(newspace);

    // What happens if the constructor throws an exception.?
    for(int i = 0; i < this->sz; i++) this->alloc.construct(&p[i], this->elem[i]); 
    

    // You have not called the destructor on the current elements.
    this->alloc.deallocate(this->elem, this->space);
    this->elem = p; //point elem to the newly allocated array p
    this->space = newspace; }

\$\endgroup\$
8
  • \$\begingroup\$ Thank you a lot for this answer. I think I will rebuild and go through the process of building the vector again. I followed the Programming Principles and Practice Using C++, where the constructor would use new to allocate memory for the array. The problem is that classes with no default constructor couldn't be used as a template argument, as new searches for a default constructor for the type initialized. Therefore, I tried using allocators for basically everything; it seems like I kinda broke it. \$\endgroup\$ Jan 13 at 5:58
  • \$\begingroup\$ Oh and also, calling alloc.destroy() for each object means that I am properly destroying that object. Am I right ? \$\endgroup\$ Jan 13 at 6:53
  • \$\begingroup\$ When you use it yes But you don't use it in all the places needed (see copy assignment and move assignment). \$\endgroup\$ Jan 13 at 9:06
  • \$\begingroup\$ The problem is you should not be initializing the objects until they are placed in the container. Initializing the memory retrieved from the allocator is wrong. \$\endgroup\$ Jan 13 at 9:07
  • \$\begingroup\$ Please read the articles I wrote. It goes through all the issues you have here and many more in some detail. \$\endgroup\$ Jan 13 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.