Custom STL Vector container Implementation

Question

For practice purposes, I reimplemented a STL Vector container. This container has most/all of the capabilities of STL vector.In my previous post, the reviewers made critical and concised observations which I researched about and considered them very important, thanks to them, I made a more robust class than the previous iteration.

Overview

Class Vector is a STL container ( first class container ) that supports various functionalities such as push_back(), pop_back(), front(), back(), at() and many more.

Purpose/Aim

1. As an exercise to get in-depth knowledge on the rule of 0/3/5
2. I aim to understand more about move semantics
3. To get my hands dirty with templates early on

Major Concerns

1. Comparisons between iterators begin() and cbegin() returns true, I cross-checked with the standard implementation and same case. Since am trying to mimic the standard, I had to implement it that way. Does it make sense to implement otherwise?

General advice, major/common pitfalls, general good practices and constructive critic are highly welcomed

#ifndef VECTOR_H_
#define VECTOR_H_

#include <cstddef>
#include <algorithm>
#include <iostream>
#include <initializer_list>

namespace MyIterator {
    template< typename T >
    class Iterator
    {
        protected:
            std::size_t index_;
            T* memory_ptr;
        public:
            Iterator( T* memory_block ) : index_( 0 ), memory_ptr( memory_block ) {}
            Iterator( T* memory_block, std::size_t end ) : index_( end ), memory_ptr( memory_block ) {}
            Iterator &operator++() {
                ++index_;
                return *this;
            }
            Iterator &operator--() {
                --index_;
                return *this;
            }
            bool operator==( const Iterator &other_it ) const { return ( index_ == other_it.index_ ); }
            bool operator!=( const Iterator &other_it ) const { return !( *this == other_it ); }
            T& operator*() { return memory_ptr[ index_ ]; }
    };

    template< typename T >
    class ConstIterator : public Iterator<T>
    {
        public:
            ConstIterator( T* memory_block ) : Iterator<T>( memory_block ){}
            ConstIterator( T* memory_block, std::size_t end ) : Iterator<T>( memory_block, end ){}
            const T& operator*() const { return this->memory_ptr[ this->index_ ]; }
    };
}

namespace MyVector {
    template< typename T >
    class Vector
    {
        friend void swap( Vector &lhs, Vector &rhs )
        {
            using std::swap;

            swap( lhs.size_index, rhs.size_index );
            swap( lhs.vector_capacity, rhs.vector_capacity );
            swap( lhs.memory_block, rhs.memory_block );
        }

        private:
            std::size_t size_index;
            std::size_t vector_capacity;
            T* memory_block;

        public:
            /* ctors */
            Vector() : size_index( 0 ), vector_capacity( 1 ), memory_block ( new T[ vector_capacity ]{} ){}
            Vector( std::size_t sz ) : size_index( sz ), vector_capacity( sz ), memory_block( new T[ vector_capacity ]{} ) {}
            Vector( std::size_t sz, const T &val ) :  Vector( sz )
            {
                for( std::size_t i = 0; i != vector_capacity; ++i ) {
                    memory_block[ i ] = val;
                    ++size_index;
                }
            }
            Vector( std::initializer_list<T> list ) : Vector( list.size() )
            {
                std::size_t index = 0;
                for( const auto &item : list )
                    memory_block[ index++ ] = item;
            }
            Vector( const Vector &other_vec )
                : size_index( other_vec.size_index),
                vector_capacity( other_vec.vector_capacity ),
                memory_block( new T[ other_vec.vector_capacity ] )
            {
                std::copy( other_vec.memory_block, other_vec.memory_block + vector_capacity, memory_block );
            }

            Vector &operator=( Vector rhs )
            {
                swap( *this, rhs );
                return *this;
            }
            Vector( Vector &&other_vec ) { swap( *this, other_vec ); }

            /* modifiers */
            void push_back( const T &val )
            {
                if( size_index >= vector_capacity ) {
                    // allocates twice the size of the current vector's capacity
                    T * new_memory_block = new T[ vector_capacity * 2 ];

                    // copy each element to new vector's memory_block
                    for( std::size_t i = 0; i != size_index; ++i )
                        new_memory_block[ i ] = memory_block[ i ];

                    delete [] memory_block; // delete old memory; very important!
                    memory_block = new_memory_block;
                    vector_capacity *= 2;
                }
                memory_block[ size_index++ ] = val;
            }
            void insert( int index, const T& val )
            {
                if( index < 0 || index > size_index ) throw std::out_of_range( "Exception: index out of range");
                for( int temp_index = size_index; temp_index >= index; --temp_index )
                {
                    /* Move elements one step back until we get to the desired location */
                    memory_block[ temp_index + 1 ] = memory_block[ temp_index ];
                }
                memory_block[ index ] = val;
                size_index++;
            }
            void erase( int index )
            {
                for( int temp_index = index; temp_index < size_index; ++temp_index )
                {
                    /* Move elements one step back until we get to the desired location */
                    memory_block[ temp_index ] = memory_block[ temp_index + 1 ];
                }
                --size_index;

            }
            void pop_back() { --size_index; }// ignored garbage value
            void clear()
            {
                delete [] memory_block;
                memory_block = nullptr;
                size_index = 0;
            }

            /* accessors */
            MyIterator::Iterator<T> begin() { return MyIterator::Iterator<T>( memory_block ); }
            MyIterator::Iterator<T> end() { return MyIterator::Iterator<T>( memory_block, size_index ); }
            const MyIterator::ConstIterator<T> cbegin() const { return MyIterator::ConstIterator<T>( memory_block ); }
            const MyIterator::ConstIterator<T> cend() const { return MyIterator::ConstIterator<T>( memory_block, size_index ); }

            T& front() const { return memory_block[ 0 ]; }
            T& back() const { return memory_block[ size_index - 1 ]; }
            T& front() { return memory_block[ 0 ]; }
            T& back() { return memory_block[ size_index - 1 ]; }
            T& at( const std::size_t i ) const
            {
                if( i < 0 || i >= size_index )
                    throw std::out_of_range( "Exception: index out of range " );
                return memory_block[ i ];
            }
            T& at( const std::size_t i )
            {
                if( i < 0 || i >= size_index )
                    throw std::out_of_range( "Exception: index out of range " );
                return memory_block[ i ];
            }

            T& operator[]( const int i ) const { return memory_block[ i ]; }
            T& operator[]( const int i ) { return memory_block[ i ];  }

            std::size_t capacity() const { return vector_capacity; }
            std::size_t size() const { return size_index; }
            bool empty() const { return ( size_index == 0 ); }

            /* dtor */
            ~Vector() { delete [] memory_block; }
    };
}

#endif

Answer 1

Overview

You have two namespaces.
Any particular reason?

You tried to implement move semantics for the Vector. You missed the move assignment. But you forget to implement move semantics for the T type. So large types in your vector are expensive to use.

You don't provide the strong exception guarantee. You should definitely try. If something throws your object can be left in a bad state.

The standard for this:

// 1: Do anything the can throw on temporary objects.
// 2: Use noexcept safe functions to swap temp with state.
// 3: Cleanup.

A couple of const correctness issues.

Code Review:

Seems relatively generic. I might expect this to have already been used. I normally include the namespace as part of the guard macro.

#ifndef VECTOR_H_
#define VECTOR_H_

---

I would expect swap() to be implemented as a member method but not required. The friend function swap then simply calls the member function.

But you do want to mark it as noexcept. This is because you also want to mark the move constructor / move assignment as noexcept and the easy way to implement these is to call swap.

        friend void swap( Vector &lhs, Vector &rhs )

---

Yes. But be careful with this declaration.

            T* memory_block;

When you allocate you don't want to construct.

---

The problem here:

            Vector() : size_index( 0 ), vector_capacity( 1 ), memory_block ( new T[ vector_capacity ]{} ){}

You are constructing T here. This has a couple of issues. The type T may not have a default constructor. The type T may be very expensive to construct so you don't actually want to construct until you know you are going to use it. Think about when you resize the vector from 100 -> 200 elements. You are now going to construct 100 elements but you may only use 1 of those 100 elements. Do you really want to pay the cost? When you reduce the size of the vector you currently cannot destroy the object but the user may want to force the release of the resources.

So in general you want to allocate space but you don't want to construct the object. That is why we keep a capacity and a size as different values.

---

On the same sort of vein:

In this constructor you are constructing sz objects of type T:

            Vector( std::size_t sz, const T &val ) :  Vector( sz )

Then the first thing you do is copy over all the elements in the container. So you are basically destroying the old value and re-creating the new values.

            {
                for( std::size_t i = 0; i != vector_capacity; ++i ) {
                    memory_block[ i ] = val;
                    ++size_index;
                }
            }

This means you have effectively done the same work twice. Also you are copying elements that are not valid. Simply copy size not capacity elements.

---

I saw you define iterators.
Why can I not use the range-based for loop here?

                for( std::size_t i = 0; i != vector_capacity; ++i ) {
                    memory_block[ i ] = val;
                    ++size_index;
                }

---

Yep. But declare the move constructor as noexcept.

            Vector( Vector &&other_vec ) { swap( *this, other_vec ); }

What happened to the move assignment operator?

The reason for marking the move operations as noexcept is that it allows certain optimizations when your object is placed into container.

---

Good try. But you potentially leak.

            void push_back( const T &val )
            {

               // STUFF

                    T * new_memory_block = new T[ vector_capacity * 2 ];

                    // What happens if the copy constructor of T throws
                    // an exception during this operation?
                    //
                    // In that case you have leaked `new_memory_block`
                    // and all the resources held by the T objects in this
                    // block.   
                    for( std::size_t i = 0; i != size_index; ++i )
                        new_memory_block[ i ] = memory_block[ i ];

                    // What happens if the destructor throws in a T?
                    // probably an application quits but you don't know.
                    //
                    // If the delete throws and is escapes the destructor
                    // and the excetion is caught higher in the call stack
                    // then you have leaked `new_memory_block` and resouces
                    // this object is in an invlalid state as the memory_block
                    // is no longer valid.
                    delete [] memory_block;

                    // Sure this is safe. :-)
                    memory_block = new_memory_block;
                    vector_capacity *= 2;
                }
                memory_block[ size_index++ ] = val;
            }

A simpler way to implement this:

 void push_back( const T &val )
 {
     if( size_index >= vector_capacity ) {
         Vector<T>  temp(vector_capacity * 2);
         std::move(std::begin(*this), std::end(*this), std::begin(temp));                                                 
         swap(*this, temp);
     }
     memory_block[ size_index++ ] = val;
 }

---

The push back is fine:

 void push_back(T const& val);

But T could be large. You should allow T to be moved into your vector or constructed in place.

 void push_back(T&& val);
 template<typename... Args)
 void emplace_back(Args&&... args);

---

In your insert, you copy elements when resizing.

            void insert( int index, const T& val )
            {
                    // This is a copy operation not a move operation.
                    // If T is large then this can be costly.
                    memory_block[ temp_index + 1 ] = memory_block[ temp_index ];
                }
            }

            }

---

Interesting:

            void clear()
            {
                delete [] memory_block;
                memory_block = nullptr;
                size_index = 0;
            }

---

For const versions of front() and back. I would expect them to return a const reference.

            T& front() const { return memory_block[ 0 ]; }
            T& back() const { return memory_block[ size_index - 1 ]; }

---

Answer 2

• First, your iterator:

It doesn't have STL-required fields (pointer, reference, iterator_category, etc... checkout the reference) and methods so it won't work for variety of STL based algorithms and some common operations aren't supported, like: itr++ (different from ++itr) or itr2-itr1 as well as operators like +=,-=,+,- and [].

Furthermore, some algorithms like sorting require < and/or <= operators to function.

Besides, you const version will not function properly. As it requires T* to instantiate instead of const T*. So implementing it as a derived class from regular iterator is a wrong approach.

Also the operator * of the iterator is a const method.

Note: I don't understand why people write members variables with suffix _ like index_. What's the purpose of this suffix? If you wrote it with prefix m_ like m_index then you'd at least be able to auto find them quickly in IDEs by typing m_ and then searching through found options. Just don't use _ solo for prefix as those are reserved for compiler MACROS.

• Second, your vector:

There are people that propagate swap idiom. It was surely a wise choice prior to C++11 before move semantics were introduced but these days I don't find it good approach. While it is definitely possible to implement the vector via this approach your implementation definitely isn't one such and has several issues.

1. Move constructor: your move constructor swaps between *this and source. So Vector A = std::move(B); will result in A having B's data but A's variables weren't initialized so content of B is pure garbage and will break the program in destructor.

2. Assignment: you should implement it properly with Copy-Assignment and Move-Assignment instead of hoping that constructors will do everything for you. In the Copy-Assignment you miss the opportunity to reuse to already allocated memory by the vector and instead allocate new one. This causes some issues, like user would definitely expect you to reuse the memory if newly copied data doesn't exceed capacity - notice that iterators get invalidated upon reallocation which would cause UB if user expected no reallocations.

3. Copy Constructor: you shouldn't copy the capacity and instead allocate the required amount.

4. Default Constructor: You should initialize it to completely empty instead of 1-sized allocation.

5. Why does you front(), back(), operator [] const versions return T& instead of const T&? This contradicts the idea of what const vector is meant to be.

6. There are reasons why std::vector doesn't support insert operation. It is a very slow one and shouldn't be used. So don't bother implementing it.

7. You didn't implement reserve(...), resize(...), emplace_back(...) methods as well as move version for push_back(T&&).

These were easy to fix issues. But the bigger problem is that you assumed your T type is some trivial object like int. This is not the case in general. The type might be non-copyable, have costly default construction, or non-trivial destructor.

Because of this you cannot just write T * new_memory_block = new T[ vector_capacity * 2 ]; upon a reallocation you need to allocate the memory and in a for-loop appropriately move/copy/default - construct each element according to new size and not capacity. All the while avoid the unnecessary construction calls for trivial types else it will be inefficient. Also, the pop_back() must call destructor of the last element instead of just reducing size_index and similarly in push_back() it should call copy/move-constructor to the newly allocated element instead of copy assignment when reallocation is not used.

Yeah, unfortunately because of these issues you cannot quite use new[]/delete[] in a vector implementation.

This isn't a beginner's' task as to implement it properly and efficiently you need to utilize SFINAE which has a very troublesome syntax.

Edit: forgot to mention. It is rather important. Move-Assignment and Move-Constructor must be marked noexcept as otherwise various STL based algorithm and containers will perform poorly while using your class.