I am trying to implement a vector-like container of my own (just to gain a better understanding of how std::vector works under the hood). I've been using this as a reference.

Although I've succeeded in implementing most of the interface (only the parts I use the most), I'm still uncertain whether:

  1. There are no memory leaks.
  2. All the routines associate with std::vector with respect to performance and space-usage.

Please review it to see if it can be improved. Any suggestions related to my commenting style are also welcome!

size_t nearest_power_of_2(size_t n)  // Return the nearest( and strictly greater than ) number to "n" which is a power of 2..
{
    int count=0;
    while(n)
    {
        n>>=1;
        count++;
    }
    return 1ULL<<count;
}


template<typename T>
class myvector
{
    T* vector_pointer;  //  A pointer pointing to the start of the dynamic array...
    size_t vector_size,vector_capacity;

public:
    myvector():vector_pointer(NULL),vector_size(0),vector_capacity(0) {}  // Default Constructor

    myvector(const myvector& other):vector_pointer(NULL),vector_size(0),vector_capacity(0)  // Copy Constructor
    {
        vector_pointer=new T[other.capacity()];
        memcpy(vector_pointer,&other[0],sizeof(T)*other.size());
        vector_size=other.vector_size;
        vector_capacity=other.vector_capacity;
    }

    ~myvector()  // Destructor
    {
        delete[] vector_pointer;
    }

    myvector& operator =(myvector other)  // Assignment operator
    {
        swap(*this,other);
        return *this;
    }


    void resize(const size_t &newsize)  // Change the size of the vector exactly to "newsize"..
    {
        if(newsize<vector_size)
        {
            T* temp=new T[newsize];
            memcpy(temp,vector_pointer,sizeof(T)*newsize);
            delete[] vector_pointer;
            vector_pointer=temp;
        }
        else if(newsize>vector_capacity)
        {
            reserve(newsize);
        }
        vector_size=newsize;
    }

    void reserve(size_t newcapacity)  // Change the capacity of the vector to be at least equal to "newcapacity"
    {
        newcapacity=nearest_power_of_2(newcapacity);  // Keep the capacity of the vector as a power of 2 to avoid space wastage..
        if(newcapacity>vector_capacity)
        {
            T* temp=new T[newcapacity];
            memcpy(temp,vector_pointer,sizeof(T)*vector_capacity);
            delete[] vector_pointer;
            vector_pointer=temp;
            vector_capacity=newcapacity;
        }
    }

    void push_back(const T &val)  // Add a new element of value "val" at the end of the vector..
    {
        if(vector_capacity<=vector_size)
            reserve(vector_capacity);
        vector_pointer[vector_size++]=val;
    }

    void pop_back()  // Remove the last element of the vector..
    {
        if(vector_size)
            --vector_size;
    }  //  Doesn't actually deallocate the element block (for performance)..

    size_t size() const
    {
        return vector_size;
    }

    size_t capacity() const
    {
        return vector_capacity;
    }

    T& operator [](const size_t &pos)
    {
        return vector_pointer[pos];
    }

    const T& operator [](const size_t &pos) const
    {
        return vector_pointer[pos];
    }

    bool empty() const
    {
        return vector_size==0;
    }

    T& at(const size_t& pos)  // Same as the "[]" operator, but this one checks for out-of-bound exceptions..
    {
        if(pos>=vector_size)
            throw std::out_of_range("");
        else
            return vector_pointer[pos];
    }

    const T& at(const size_t& pos) const
    {
        if(pos>=vector_size)
            throw std::out_of_range("");
        else
            return vector_pointer[pos];
    }

    void erase(const size_t& pos)  // Erase the element at "pos"..
    {
        for(size_t i=pos; i<vector_size-1; i++)
        {
            vector_pointer[i]=vector_pointer[i+1];   //  Shift all the elements one step left, beginning from "pos+1"
        }
        --vector_size;
    }
    void erase(const size_t& pos1,const size_t& pos2)  // Erase the elements in range [pos1,pos2)..
    {
        for(size_t i=pos1; i<vector_size-(pos2-pos1); i++)
        {
            vector_pointer[i]=vector_pointer[i+pos2-pos1];  // Shift all the elements (pos2-pos1) steps left, beginning from "pos2"
        }
        vector_size-=pos2-pos1;
    }

    void insert(const size_t& pos,const T& val)  // Insert 1 element of value "val" at "pos"..
    {
        if(vector_capacity<=vector_size)  // Create some space if it doesn't have enough to take another element..
            reserve(vector_size);
        vector_size++;
        for(size_t i=vector_size-1; i>pos; i--)  //  Shift all the elements one step towards right, beginning from "pos"+1..
        {
            vector_pointer[i]=vector_pointer[i-1];
        }
        vector_pointer[pos]=val;
    }

    void insert(const size_t& pos,const size_t& n,const T& val)  // Insert "n" elements of value "val", beginning from "pos"..
    {
        if(vector_size<n+vector_capacity)
            reserve(vector_size+n);       //  Create space for atleast "n" elements...
        vector_size+=n;
        for(size_t i=vector_size-1; i>=pos+n; i--)   //  Shift all the elements "n" step towards right, beginning from "pos"+1..
        {
            vector_pointer[i]=vector_pointer[i-n];
        }
        for(size_t i=pos; i<pos+n; i++)  // Change all the elements in [pos,pos+n) to "val"..
        {
            vector_pointer[i]=val;
        }
    }

    void clear()
    {
        vector_size=0;
    }  // Again, doesn't actually deallocate (for performance)..

    friend void swap(myvector &a,myvector &b)  // Copy and Swap Idiom ...
    {
        using std::swap;
        swap(a.vector_size,b.vector_size);
        swap(a.vector_capacity,b.vector_capacity);
        swap(a.vector_pointer,b.vector_pointer);
    }
};

template<typename T>std::ostream& operator <<(std::ostream& out,const myvector<T> &a)  // Overloaded output operator to display the contents of a vector..
{
    for(size_t i=0; i<a.size(); i++)
    {
        std::cout<<a[i]<<" ";
    }
    return out;
}  

EDIT (based on the 2 answers):

  1. Modified the nearest_power_of_2() function
  2. Replaced memcpy() with std::copy()
  3. Called the destructor ~T() explicitly wherever required
  4. Modified the output operator <<

size_t nearest_power_of_2(const size_t &n)  // Return the nearest( and strictly greater than ) number to "n" which is a power of 2..
{
    return 1ULL<<(static_cast<size_t>(log2(n))+1);
}


template<typename T>
class myvector
{
    T* vector_pointer;  //  A pointer pointing to the start of the dynamic array...
    size_t vector_size,vector_capacity;

public:
    myvector():vector_pointer(NULL),vector_size(0),vector_capacity(0) {}  // Default Constructor

    myvector(const myvector& other):vector_pointer(NULL),vector_size(0),vector_capacity(0)  // Copy Constructor
    {
        vector_pointer=new T[other.capacity()];
        std::copy(&other[0],&other[0]+other.size(),vector_pointer);
        vector_size=other.vector_size;
        vector_capacity=other.vector_capacity;
    }

    ~myvector()  // Destructor
    {
        delete[] vector_pointer;
    }

    myvector& operator =(myvector other)  // Assignment operator
    {
        swap(*this,other);
        return *this;
    }


    void resize(const size_t &newsize)  // Change the size of the vector exactly to "newsize"..
    {
        if(newsize<vector_size)
        {
            for(size_t i=newsize; i<vector_size; i++)
            {
                vector_pointer[i].~T();
            }
        }
        else if(newsize>vector_capacity)
        {
            reserve(newsize);
        }
        vector_size=newsize;
    }

    void reserve(size_t newcapacity)  // Change the capacity of the vector to be at least equal to "newcapacity"
    {
        newcapacity=nearest_power_of_2(newcapacity);  // Keep the capacity of the vector as a power of 2 to avoid space wastage..
        if(newcapacity>vector_capacity)
        {
            T* temp=new T[newcapacity];
            std::copy(vector_pointer,vector_pointer+vector_capacity,temp);
            delete[] vector_pointer;
            vector_pointer=temp;
            vector_capacity=newcapacity;
        }
    }

    void push_back(const T &val)  // Add a new element of value "val" at the end of the vector..
    {
        if(vector_capacity<=vector_size)
            reserve(vector_capacity);
        vector_pointer[vector_size++]=val;
    }

    void pop_back()  // Remove the last element of the vector..
    {
        if(vector_size)
        {
            vector_pointer[vector_size-1].~T();
            --vector_size;
        }
    }

    size_t size() const
    {
        return vector_size;
    }

    size_t capacity() const
    {
        return vector_capacity;
    }

    T& operator [](const size_t &pos)
    {
        return vector_pointer[pos];
    }

    const T& operator [](const size_t &pos) const
    {
        return vector_pointer[pos];
    }

    bool empty() const
    {
        return vector_size==0;
    }

    T& at(const size_t& pos)  // Same as the "[]" operator, but this one checks for out-of-bound exceptions..
    {
        if(pos>=vector_size)
            throw std::out_of_range("");
        else
            return vector_pointer[pos];
    }

    const T& at(const size_t& pos) const
    {
        if(pos>=vector_size)
            throw std::out_of_range("");
        else
            return vector_pointer[pos];
    }

    void erase(const size_t& pos)  // Erase the element at "pos"..
    {
        vector_pointer[pos].~T();
        for(size_t i=pos; i<vector_size-1; i++)
        {
            vector_pointer[i]=vector_pointer[i+1];   //  Shift all the elements one step left, beginning from "pos+1"
        }
        --vector_size;
    }
    void erase(const size_t& pos1,const size_t& pos2)  // Erase the elements in range [pos1,pos2)..
    {
        for(size_t i=pos1; i<pos2; i++)
        {
            vector_pointer[i].~T();
        }
        for(size_t i=pos1; i<vector_size-(pos2-pos1); i++)
        {
            vector_pointer[i]=vector_pointer[i+pos2-pos1];  // Shift all the elements (pos2-pos1) steps left, beginning from "pos2"
        }
        vector_size-=pos2-pos1;
    }

    void insert(const size_t& pos,const T& val)  // Insert 1 element of value "val" at "pos"..
    {
        if(vector_capacity<=vector_size)  // Create some space if it doesn't have enough to take another element..
            reserve(vector_size);
        vector_size++;
        for(size_t i=vector_size-1; i>pos; i--)  //  Shift all the elements one step towards right, beginning from "pos"+1..
        {
            vector_pointer[i]=vector_pointer[i-1];
        }
        vector_pointer[pos]=val;
    }

    void insert(const size_t& pos,const size_t& n,const T& val)  // Insert "n" elements of value "val", beginning from "pos"..
    {
        if(vector_size<n+vector_capacity)
            reserve(vector_size+n);       //  Create space for atleast "n" elements...
        vector_size+=n;
        for(size_t i=vector_size-1; i>=pos+n; i--)   //  Shift all the elements "n" step towards right, beginning from "pos"+1..
        {
            vector_pointer[i]=vector_pointer[i-n];
        }
        for(size_t i=pos; i<pos+n; i++)  // Change all the elements in [pos,pos+n) to "val"..
        {
            vector_pointer[i]=val;
        }
    }

    void clear()
    {
        for(size_t i=0; i<vector_size; i++)
        {
            vector_pointer[i].~T();
        }
        vector_size=0;
    }

    friend void swap(myvector &a,myvector &b)  // Copy and Swap Idiom ...
    {
        using std::swap;
        swap(a.vector_size,b.vector_size);
        swap(a.vector_capacity,b.vector_capacity);
        swap(a.vector_pointer,b.vector_pointer);
    }
};

template<typename T>std::ostream& operator <<(std::ostream& out,const myvector<T> &a)  // Overloaded output operator to display the contents of a vector..
{
    std::copy(&a[0], &a[0]+a.size(), std::ostream_iterator<T>(out, " "));
    return out;
}  
  • 2
    Your update is more dangerous than your original. Because you don't use placement new your use of explicit destructor calls is going to get you in trouble. See me update below. – Martin York Aug 3 '13 at 18:48
up vote 8 down vote accepted

You can do this with maths rather than a loop:

size_t nearest_power_of_2(size_t n)  // Return the nearest( and strictly greater than ) number to "n" which is a power of 2..

Couple of issues with the copy constructor.

myvector(const myvector& other):vector_pointer(NULL),vector_size(0),vector_capacity(0)  // Copy Constructor
{
    // Don't assign to this object until you
    // know that no exceptions can be thrown.
    // This means all memory allocation and
    // object copying must be completed first.
    vector_pointer=new T[other.capacity()];

    // You can use this for POD types.
    // But any non POD types must be copied using their copy constructor.
    memcpy(vector_pointer,&other[0],sizeof(T)*other.size());


    vector_size=other.vector_size;
    vector_capacity=other.vector_capacity;
}

Similar issues with resize()

        // You can use this for POD types.
        // But any non POD types must be copied using their copy constructor.
        memcpy(temp,vector_pointer,sizeof(T)*newsize);

Making the size smaller is easier. You don't need to re-allocate. You can just reduce the size value and manually call the destructor on all the objects that don't exist anymore.

Same but slightly different in reserve()

        // The trouble with use T as the underlying type.
        // As that this call will call the constructor on all objects
        // upto `capacity`. You don't want that you only want to call
        // the constructor on values upto `newcapacity`
        T* temp=new T[newcapacity];

        // You can use this for POD types.
        // But any non POD types must be copied using their copy constructor.
        memcpy(temp,vector_pointer,sizeof(T)*vector_capacity);

Your push back is very inefficient:

void push_back(const T &val)  // Add a new element of value "val" at the end of the vector..
{
    if(vector_capacity<=vector_size)
        // As noted calls copy constructor
        reserve(vector_capacity);

    // Now using the assignment operator.
    // To copy over object that you just fully initialized.
    vector_pointer[vector_size++]=val;

    // A better solution is not to construct in the copy constructor.
    // Then here use placement new to create the object in place
}

The pop back needs work

void pop_back()  // Remove the last element of the vector..
{
    if(vector_size)
        --vector_size;

    // RAII is an important concept in C++
    // When you pop something out of your vector it should no longer exist.
    // This means you need to call the destructor for the object.
    // Here that means manually calling the destructor.

}  //  Doesn't actually deallocate the element block (for performance)..

More times when destructor needs to be called.

void erase(const size_t& pos)  // Erase the element at "pos"..
void clear()

// For the elements passed the end of the valid vector (vector_size)
// You need to call the destructors of these elements as they no longer exist.

Fix your output operator:

template<typename T>std::ostream& operator <<(std::ostream& out,const myvector<T> &a)  // Overloaded output operator to display the contents of a vector..
{
    for(size_t i=0; i<a.size(); i++)
    {
        // Should be `out`
        std::cout<<a[i]<<" ";
    }
    return out;
}

For loops like this use the standard algorithms: Personally I don't see the point. I can achieve the same effect in one line:

std::copy(a.begin(), a.end(), std::ostream_iterator<T>(out, " "));

Simple Vector:

template<typename T>
class LokiVector
{
    std::size_t              size;
    std::size_t              capacity;
    std::unique_ptr<char[]>  data;  // Use char so we don't worry about 
                                    // constructor/destructor issues.

    void init(T const& value)
    {
    public:
        LokiVector(std::size_t startSize = 0, T const& defaultValue = T())
            : size(startSize)
            , capacity(std::min(startSize, 16))
            , data(new char[sizeof(T) * capacity])
        {
            T*   localData = reinterpret_cast<T*>(data.get());
            for(int loop = 0;loop < size; ++loop)
            {
                new (&localData[loop]) T(defaultValue);
            }
        }
        LokiVector(LokiVector const& rhs)
            : size(rhs.size)
            , capacity(rhs.capacity)
            , data(new char[sizeof(T) * capacity])
         {
            T*   localData = reinterpret_cast<T*>(data.get());
            for(int loop = 0;loop < size; ++loop)
            {
                new (&localData[loop]) T(rhs[loop]);
            }
         }
         ~LokiVector()
         {
            T*   localData = reinterpret_cast<T*>(data.get());
            for(int loop = 0;loop < size; ++loop)
            {
                // Destroy from tail to front (like arrays do)
                localData[size-1-loop].~T();
            }
         }
         LokiVector& operator=(LokiVector rhs)
         {
            swap(rhs);
            return *this;
         }
         void swap(LokiVector& other) noexcept
         {
            std::swap(size,       other.size);
            std::swap(capacity,   other.capacity);
            std::swap(data,       other.data);
         }

         void push_back(T const& value)
         {
              reserve(size+1);
              T*   localData = reinterpret_cast<T*>(data.get());
              new (&localData[size]) T(value);
              ++size;
         }

         void pop_back()
         {
              if (size > 0)
              {
                  --size;
                  T*   localData = reinterpret_cast<T*>(data.get());
                  localData[size].~T();
              }
         }

         void reserve(std::size_t min)
         {
             if (min < capacity)
             {
                 size_t tmp_capacity = min;   // Plus any padding you want to add
                 std::unique_ptr<char>  tmp_data(new char[sizeof(T) * tmp_capacity);
                 T*   localData = reinterpret_cast<T*>(data.get());
                 T*   tmpLocal  = reinterpret_cast<T*>(tmp_data.get());

                 for(int loop = 0;loop < size; ++loop)
                 {
                     new (&tmpLocal[loop]) T(localData[loop]);
                 }

                 // Update the state of the local object
                 std::swap(data,     tmp_data);
                 std::swap(capacity, tmp_capcity);

                 // Destroy all the old members
                 // Remember these may potentially throw so this is done
                 // after the state of the object is completely defined.
                 for(int loop = 0;loop < size; ++loop)
                 {
                     // Destroy from tail to front (like arrays do)
                     // Remember that local data still points at the old
                     // data even after the swap.
                     localData[size-1-loop].~T();
                 }
             }
         }
         T& operator[](std::size_t index)
         {
             T*   localData = reinterpret_cast<T*>(data.get());
             return localData[index];
         }
         T const& operator[] (std::size_t index) const
         {
             return const_cast<LokiVector&>(*this)[index];
         }
    }
  • Making the size smaller is easier....manually call the destructor on all the objects that don't exist anymore. How can we do it??! I asked a similar question some time back. Similarly, in erase(), how to destruct a single element? ( except for the usual way of reallocating ) . In, reserve(), // The trouble with use T as the ....constructor on values upto newcapacity.. I don't get it..Is there any other way too? – Anmol Singh Jaggi Aug 3 '13 at 10:41
  • 2
    The "similar question" is about delete, which frees memory. @LokiAstari is talking about calling the destructor, which causes the object in question to clean up the resources it owns: elem->~T(); – Lstor Aug 3 '13 at 11:38
  • 1
    Updated with an example of how I might do it. Needs some cleanup but it should work. – Martin York Aug 3 '13 at 18:36
  • Hi Loki, I was just wondering two things and I am interested in what you think about them. First, shouldn't the unique_ptr<char be a unique_ptr<char[]> so that the correct version of delete is called? Second, don't you have to destroy all already constructed elements in the constructors when a T constructor would throw an exception. – inf Nov 13 '13 at 19:24
  • 1
    @bamboon: You are correct on both points. I have fixed the easy one. Calling the destructor I have not done here because that is a lot of work (you can't just do the obvious because pointers and fundamental types don't have destructors). – Martin York Nov 13 '13 at 20:35
  • That's an okay guide for reference, but I'd highly recommend searching for pages that give in-depth information about std::vectors. There's a lot going on under the hood, and one general guide cannot teach you everything.

  • I'm not sure how far you want to go with the STL (minus std::vector of course), but I'd still make use of it. Without it, your code will be too C-like and improper use of raw pointers (also C-like) could attract all sorts of bugs.

  • count should also be a size_t.

  • The size_t parameters don't really need to be const, but that's not a big issue.

  • std::out_of_range() requires <stdexcept>.

  • I'd really test the shifting in both erase()es. It's not quite a straightforward algorithm. For one thing, your algorithm will eventually leave a garbage value at the very end if shifting left. Correcting that won't be so easy, which is why this may need to be approached differently.

  • std::pop_back() destroys the last element in the vector, yet you're just reducing its size to "remove" it. What happens if you increment the size again? Yes, that element will still be there. Vectors are always shrinking and growing, so do just that. Despite the performance hit that you're trying to avoid, this method is not at all like the original. It is supposed to call the destructor for the removed element to make sure it's destroyed for good.

  • Why are you forcing the size to 0 in clear()? Your destruction method should reduce the size itself, thereby giving you an accurate count of the remaining elements (which should be 0). Again, don't take the easy way out in favor of performance. Do what the original is supposed to do.

  • Again, your operator<< is putting the output into std::cout instead of out.

Follow-up from comments:

  • Here's a rough idea of how your declarations and definitions should be structured. These can be in separate files (.h for declaration and .cpp for definition), or in this form in one .h file.

    Class declaration

    template<typename T>
    class myvector
    {
        T* vector_pointer;
        // these should go on separate lines
        size_t vector_size;
        size_t vector_capacity;
    
    public:
        myvector();
        myvector(const myvector&);
        ~myvector();
        myvector& operator=(myvector);
        void resize(size_t);
        void reserve(size_t);
        void push_back(const T&);
        void pop_back();
        T& at(size_t);
        const T& at(size_t);
        void erase(size_t);
        void erase(size_t, size_t);
        void insert(size_t, const T&);
        void insert(size_t, size_t, const T&);
        void clear();
        friend void swap(myvector&, myvector&);
    
        // these are the accessors (moved to the end for organization)
        // they may be implemented within the class declaration
        //   because they merely return private data and each have one line
        size_t size() const {return vector_size;}
        size_t capacity() const {return vector_capacity;}
        T& operator[](size_t pos) const {return vector_pointer[pos];}
        const T& operator[](size_t pos) const {return vector_pointer[pos];}
        bool empty() const {return vector_size == 0;}
    };
    

    Class definition

        // if a function belongs to the class,
        //   it must have the scope operator with the class name
        // (fill in the curly braces with your definitions)
    
        myvector::myvector() : vector_pointer(NULL), vector_size(0), vector_capacity(0) {}
        myvector::myvector(const myvector& other) {}
        myvector::~myvector() {}
        myvector::myvector& operator=(myvector other) {}
        void myvector::resize(size_t newsize) {}
        void myvector::reserve(size_t newcapacity) {}
        void myvector::push_back(const T& val) {}
        void myvector::pop_back() {}
        T& myvector::at(size_t pos) {}
        const T& myvector::at(size_t pos) {}
        void myvector::erase(size_t pos) {}
        void myvector::erase(size_t pos1, size_t pos2) {}
        void myvector::insert(size_t pos, const T& val) {}
        void myvector::insert(size_t pos, size_t n, const T& val) {}
        void myvector::clear() {}
        // swap() is a friend of myvector, so it doesn't get the scope operator
        //   friend is also removed from the definition but stays in the declaration
        void swap(myvector& a, myvector& b) {}
    
  • 1
    The pop_back() should force the elements destructor to be called. RAII is an important concept and when you pop something you expect it to be destroyed and the destructor called. – Martin York Aug 3 '13 at 7:25
  • @LokiAstari: Right. I'm already making some changes now. I just didn't want give any false information about it. – Jamal Aug 3 '13 at 7:26
  • The class declarations and implementations should be noticeably separate, even if they're in one file. I had to scrounge for that };. Sorry, but I didn't actually get it. How do you differentiate between declarations and implementations? I agree with you on the usage of STL in C++. I use them a lot!! In fact, that was the only reason I was so much curious on how they were implemented! I am not gonna use these implementations in place of the original stuff. I practice that just for the sake of learning ( and fun! ). – Anmol Singh Jaggi Aug 3 '13 at 10:50
  • 2
    In class: void resize(const size_t &newsize); Outside: void myvector<T>::resize(const size_t& newsize) { /* implementation */ }. Any book on C++ will show you this. By defining member functions inside the class definition, you are implicitly asking that the compiler inlines them. – Lstor Aug 3 '13 at 11:41
  • Ah. You could've asked me about that before if you were confused. Anyway, Lstor is correct. You could still get an idea online, but I can give you an example in my answer as a start. – Jamal Aug 3 '13 at 16:53

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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