C++11 Vector with move semantics

Question

I am practicing move semantics and placement new by writing a custom Vector class but I am not confident that I use them right. I would really appreciate some pieces of advice regarding my code.

Here is my Vector header

#ifndef VECTOR_VECTOR_H
#define VECTOR_VECTOR_H

#include <iostream>
#include <utility>
#include <iterator>
#include <algorithm>

#define _NOEXCEPT noexcept

template < typename T > class Vector { public:  explicit Vector( size_t = INITIAL_CAPACITY );

    Vector( size_t, const T & );

    template < typename InputIterator >     Vector( InputIterator, InputIterator );

    Vector( const Vector & );

    Vector( Vector && ) _NOEXCEPT;

    Vector &operator=( const Vector & );

    Vector &operator=( Vector && ) _NOEXCEPT;

    Vector &operator=( std::initializer_list < T > );

    ~Vector();

    template < class InputIterator >    void assign( InputIterator first, InputIterator last );

    void assign( size_t n, const T &val );

    void assign( std::initializer_list < T > il );


    void push_back( const T & );

    void push_back( T && );

    void pop_back() _NOEXCEPT;

    void reserve( size_t );

    void resize( size_t );

    void resize( size_t, const T & );

    T &operator[]( size_t );

    const T &operator[]( size_t ) const;

    T &at( size_t );

    const T &at( size_t ) const;

    T &front();

    const T &front() const;

    T &back();

    const T &back() const;

    T *data() _NOEXCEPT;

    const T *data() const _NOEXCEPT;

    bool empty() const _NOEXCEPT;

    size_t size() const _NOEXCEPT;

    size_t capacity() const _NOEXCEPT;

    bool contains( const T & ) const _NOEXCEPT;

    void shrink_to_fit();

    void swap( Vector & );

    void clear() _NOEXCEPT;

#include "const_iterator.h"
#include "iterator.h"
#include "const_reverse_iterator.h"
#include "reverse_iterator.h"

    iterator begin() _NOEXCEPT {        return iterator( m_data );  }

    iterator end() _NOEXCEPT {      return iterator( m_data + m_size );     }

    reverse_iterator rbegin() _NOEXCEPT {       return reverse_iterator( m_data + m_size - 1 );     }

    reverse_iterator rend() _NOEXCEPT {         return reverse_iterator( m_data
- 1 );  }

    const_iterator begin() const _NOEXCEPT {        return const_iterator( m_data );    }

    const_iterator end() const _NOEXCEPT {      return const_iterator( m_data + m_size );   }

    const_reverse_iterator rbegin() const _NOEXCEPT {       return const_reverse_iterator( m_data + m_size - 1 );   }

    const_reverse_iterator rend() const _NOEXCEPT {         return const_reverse_iterator( m_data - 1 );    }

    const_iterator cbegin() const _NOEXCEPT {       return const_iterator( m_data );    }

    const_iterator cend() const _NOEXCEPT {         return const_iterator( m_data + m_size );   }

    const_reverse_iterator crbegin() const _NOEXCEPT {      return const_reverse_iterator( m_data + m_size - 1 );   }

    const_reverse_iterator crend() const _NOEXCEPT {        return const_reverse_iterator( m_data - 1 );    }

    iterator erase( const_iterator );

    iterator erase( const_iterator, const_iterator );

    iterator insert( const_iterator position, const T &val );

    iterator insert( const_iterator position, size_t n, const T &val );

    template < class InputIterator >    iterator insert( const_iterator position, InputIterator first, InputIterator last );

    iterator insert( const_iterator position, T &&val );

    iterator insert( const_iterator position, std::initializer_list < T > il );

private:    void allocateMemory_( T *&, size_t );

    void moveFrom_( Vector && ) _NOEXCEPT;

    void destructObjects_() _NOEXCEPT;

    bool makeSpace( iterator, size_t );

private:    T      *m_data;     size_t m_size;  size_t m_capacity;

    static const int INITIAL_CAPACITY = 2;  static const int FACTOR      
= 2; };

template < typename T > bool operator==( const Vector < T > &lhs, const Vector < T > &rhs );

template < typename T > bool operator!=( const Vector < T > &lhs, const Vector < T > &rhs );

template < typename T > bool operator>( const Vector < T > &lhs, const Vector < T > &rhs );

template < typename T > bool operator>=( const Vector < T > &lhs, const Vector < T > &rhs );

template < typename T > bool operator<( const Vector < T > &lhs, const Vector < T > &rhs );

template < typename T > bool operator<=( const Vector < T > &lhs, const Vector < T > &rhs );

#include "vector_implementations.h"


#endif //VECTOR_VECTOR_H

My Vector implementations are in a separate header for readability purposes.

#ifndef VECTOR_VECTOR_IMPLEMENTATIONS_H
#define VECTOR_VECTOR_IMPLEMENTATIONS_H

template < typename T >
inline Vector < T >::Vector( size_t capacity ) :m_data( nullptr ), m_size( 0 ), m_capacity( capacity ) {
    allocateMemory_( m_data, m_capacity );
}

template < typename T >
inline Vector < T >::Vector( const Vector &rhs ) : Vector( rhs . m_size ) {
    std::copy( rhs . begin(), rhs . end(), begin());
}

template < typename T >
inline Vector < T >::Vector( Vector &&rhs ) _NOEXCEPT {

    moveFrom_( std::move( rhs ));
}

template < typename T >
inline Vector < T > &Vector < T >::operator=( const Vector &rhs ) {
    if ( this != &rhs ) {
        //copy-swap idiom
        Vector tmp( rhs );
        swap( tmp );
    }
    return *this;
}

template < typename T >
inline Vector < T > &Vector < T >::operator=( Vector &&rhs ) _NOEXCEPT {
    if ( this != &rhs ) {
        clear();
        moveFrom_( std::move( rhs ));
    }
    return *this;
}

template < typename T >
inline Vector < T >::~Vector() {
    clear();
}

template < typename T >
inline void Vector < T >::pop_back() _NOEXCEPT {
    m_data[ --m_size ] . ~T();
}

template < typename T >
inline void Vector < T >::push_back( const T &element ) {
    if ( !m_data || m_size == m_capacity ) {
        reserve( m_capacity ? m_capacity * FACTOR : INITIAL_CAPACITY );
    }
    new( m_data + m_size )T( element );
    ++m_size;
}

template < typename T >
inline void Vector < T >::push_back( T &&element ) {
    if ( !m_data || m_size == m_capacity ) {
        reserve( m_capacity ? m_capacity * FACTOR : INITIAL_CAPACITY );
    }

    new( m_data + m_size )T( std::move( element ));
    ++m_size;
}

template < typename T >
inline T &Vector < T >::operator[]( size_t idx ) {
    return *( m_data + idx );
}

template < typename T >
inline const T &Vector < T >::operator[]( size_t idx ) const {
    return *( m_data + idx );
}

template < typename T >
inline T &Vector < T >::at( size_t idx ) {
    if ( idx >= m_size ) {
        throw ( std::out_of_range( "Invalid index" ));
    }
    return *( m_data + idx );
}

template < typename T >
inline const T &Vector < T >::at( size_t idx ) const {
    if ( idx >= m_size ) {
        throw ( std::out_of_range( "Invalid index" ));
    }
    return *( m_data + idx );
}

template < typename T >
inline T &Vector < T >::front() {
    return *m_data;
}

template < typename T >
inline const T &Vector < T >::front() const {
    return *m_data;
}

template < typename T >
inline T &Vector < T >::back() {
    return *( m_data + m_size - 1 );
}

template < typename T >
inline const T &Vector < T >::back() const {
    return *( m_data + m_size - 1 );

}

template < typename T >
inline T *Vector < T >::data() _NOEXCEPT {
    return m_data;
}

template < typename T >
inline const T *Vector < T >::data() const _NOEXCEPT {
    return m_data;
}

template < typename T >
inline bool Vector < T >::empty() const _NOEXCEPT {
    return ( m_size == 0 );
}

template < typename T >
inline size_t Vector < T >::size() const _NOEXCEPT {
    return m_size;
}

template < typename T >
inline size_t Vector < T >::capacity() const _NOEXCEPT {
    return m_capacity;
}

template < typename T >
inline bool Vector < T >::contains( const T &element ) const _NOEXCEPT {
    for ( int i = 0 ;
          i < m_size ;
          ++i ) {
        if ( m_data[ i ] == element ) {
            return true;
        }
    }
    return false;
}

template < typename T >
inline void Vector < T >::shrink_to_fit() {
    Vector( *this ) . swap( *this );
}

template < typename T >
inline void Vector < T >::swap( Vector &rhs ) {
    //check ADL look up
    using std::swap;
    swap( m_data, rhs . m_data );
    swap( m_size, rhs . m_size );
    swap( m_capacity, rhs . m_capacity );
}

template < typename T >
inline void Vector < T >::clear() _NOEXCEPT {
    destructObjects_();

    operator delete( m_data );
    m_capacity = 0;
}

template < typename T >
inline void Vector < T >::allocateMemory_( T *&destination, size_t capacity ) {
    destination = static_cast< T * >( operator new[]( capacity * sizeof( T )));
}

template < typename T >
inline void Vector < T >::moveFrom_( Vector &&rhs ) _NOEXCEPT {
    m_data = rhs . m_data;
    rhs . m_data = nullptr;

    m_size     = rhs . m_size;
    m_capacity = rhs . m_capacity;
}

template < typename T >
inline void Vector < T >::destructObjects_() _NOEXCEPT {
    while ( !empty()) {
        pop_back();
    }
}

template < typename T >
inline void Vector < T >::reserve( size_t size ) {
    if ( size <= m_capacity ) {
        return;
    }

    T *newData = nullptr;
    allocateMemory_( newData, size );

    size_t i = 0;
    for ( ; i < m_size ;
            ++i ) {
        new( newData + i )T( std::move( m_data[ i ] ));
    }

    clear();

    m_size     = i;
    m_data     = newData;
    m_capacity = size;
}

template < typename T >
inline void Vector < T >::resize( size_t size ) {
    resize( size, T());
}

template < typename T >
inline void Vector < T >::resize( size_t size, const T &value ) {
    reserve( size );
    if ( size <= m_size ) {
        while ( m_size > size ) {
            pop_back();
        }
    } else {
        while ( m_size < size ) {
            push_back( value );
        }
    }
}

template < typename T >
inline typename Vector < T >::iterator Vector < T >::erase( typename Vector < T >::const_iterator position ) {
    //std::advance(it,std::distance(cbegin(),position));
    //iterator iter = begin() + ( position - cbegin() );
    //std::move( iter + 1, end(), iter );
    //pop_back();
    //return iter;
    return erase( position, position + 1 );
}

template < typename T >
inline typename Vector < T >::iterator Vector < T >::erase
        ( typename Vector < T >::const_iterator first, typename Vector < T >::const_iterator last ) {
    //UB on invalid range
    iterator iter             = begin() + ( first - cbegin());
    int      removed_elements = last - first;

    std::move( last, cend(), iter );
    while ( removed_elements-- ) {
        pop_back();
    }
    return iter;
}

template < typename T >
bool Vector < T >::makeSpace( Vector::iterator position, size_t space ) {
    size_t elementsToMove = end() - position;
    std::cout << "POSITION " << elementsToMove << std::endl;
    if ( m_size + space >= m_capacity ) {
        reserve( m_capacity ? m_capacity * FACTOR : INITIAL_CAPACITY );
    }
    for ( int i = 0 ;
          i < elementsToMove ;
          ++i ) {
        new( m_data + m_size + space - i ) T( std::move( m_data[ m_size - i ] ));
    }

    m_size += space;
}

template < typename T >
Vector < T >::Vector( size_t n, const T &val ) :Vector( n ) {
    while ( n-- ) {
        push_back( val );
    }
}

template < typename T >
template < typename InputIterator >
Vector < T >::Vector( InputIterator first, InputIterator last ) {
    size_t numElements = last - first;
    allocateMemory_( m_data, numElements );
    while ( first != last ) {
        push_back( *first );
        ++first;
    }
}

template < typename T >
Vector < T > &Vector < T >::operator=( std::initializer_list < T > il ) {
    Vector tmp( il . begin(), il . end());
    swap( tmp );

    return *this;
}

template < typename T >
Vector::iterator Vector < T >::insert( Vector::const_iterator position, const T &val ) {
    size_t offset = position - cbegin();
    makeSpace( begin() + offset - 1, 1 );
    m_data[ offset ] = val;
    return ( begin() + offset );
}

template < typename T >
Vector::iterator Vector < T >::insert( Vector::const_iterator position, size_t n, const T &val ) {
    size_t offset = position - cbegin();
    makeSpace( begin() + offset - 1, n );
    for ( int i = 0 ; i < n ; ++i ) {
        m_data[ offset + i ] = val;
    }
    return ( begin() + offset );

}

template < typename T >
template < class InputIterator >
Vector::iterator Vector < T >::insert( Vector::const_iterator position, InputIterator first, InputIterator last ) {
    size_t offset = position - cbegin();

    makeSpace( begin() + offset - 1, last - first );
    int i = 0;
    while ( first != last ) {
        m_data[ offset + i ] = *first;
        ++first;
        ++i;
    }
    return ( begin() + offset );
}

template < typename T >
Vector::iterator Vector < T >::insert( Vector::const_iterator position, T &&val ) {
    size_t offset = position - cbegin();
    makeSpace( begin() + offset - 1, 1 );
    m_data[ offset ] = std::move( val );
    return ( begin() + offset );
}

template < typename T >
Vector::iterator Vector < T >::insert( Vector::const_iterator position, std::initializer_list < T > il ) {
    return insert( position, il . begin(), il . end());
}

template < typename T >
template < class InputIterator >
void Vector < T >::assign( InputIterator first, InputIterator last ) {
    swap( Vector( first, last ));
}

template < typename T >
void Vector < T >::assign( size_t n, const T &val ) {
    swap( Vector( n, val ));
}

template < typename T >
void Vector < T >::assign( std::initializer_list < T > il ) {
    swap( Vector( il ));
}

template < typename T >
inline bool operator==( const Vector < T > &lhs, const Vector < T > &rhs ) {
    if ( lhs . size() != rhs . size()) {
        return false;
    }
    for ( int i = 0 ;
          i < lhs . size() ;
          ++i ) {
        if ( lhs[ i ] != rhs[ i ] ) {
            return false;
        }
    }
    return true;

}

template < typename T >
inline bool operator!=( const Vector < T > &lhs, const Vector < T > &rhs ) {
    return !( lhs == rhs );
}

template < typename T >
inline bool operator>( const Vector < T > &lhs, const Vector < T > &rhs ) {
    return rhs < lhs;
}

template < typename T >
inline bool operator>=( const Vector < T > &lhs, const Vector < T > &rhs ) {
    return !( lhs < rhs );
}

template < typename T >
inline bool operator<( const Vector < T > &lhs, const Vector < T > &rhs ) {
    int i = 0;
    while ( i < lhs . size() && i < rhs . size() && lhs[ i ] == rhs[ i ] ) {
        ++i;
    }
    if ( i == lhs . size() || i == rhs . size()) {
        return lhs . size() < rhs . size();
    }
    return lhs[ i ] < rhs[ i ];
}

template < typename T >
inline bool operator<=( const Vector < T > &lhs, const Vector < T > &rhs ) {
    return !( rhs < lhs );
}

#endif //VECTOR_VECTOR_IMPLEMENTATIONS_H

And I will just post the code for one of the iterators type, because the rest are identical.

#ifndef VECTOR_CONST_REVERSE_ITERATOR_H
#define VECTOR_CONST_REVERSE_ITERATOR_H


class const_reverse_iterator : public std::iterator<std::random_access_iterator_tag, const T>
{
    friend class Vector;
    friend class const_iterator;
public:
    const_reverse_iterator( const T* data = nullptr ) : m_data( data )
    {}

    const T& operator*() const
    {
        return *m_data;
    }

    const T* operator->() const
    {
        return m_data;
    }

    const_reverse_iterator& operator++()
    {
        --m_data;
        return *this;
    }
    const_reverse_iterator operator++( int )
    {
        const_reverse_iterator res( *this );
        --( *this );
        return res;
    }
    const_reverse_iterator& operator+=( int n )
    {
        while ( --n )
            ++( *this );
        return *this;

    }
    const_reverse_iterator operator+( int n ) const
    {
        const_reverse_iterator tmp( *this );
        tmp -= n;
        return tmp;
    }
    const_reverse_iterator& operator--()
    {
        ++m_data;
        return *this;
    }
    const_reverse_iterator operator--( int )
    {
        const_reverse_iterator res( *this );
        ++( *this );
        return res;
    }
    const_reverse_iterator& operator-=( int n )
    {
        while ( n-- )
            --( *this );
        return *this;
    }
    const_reverse_iterator operator-( int n ) const
    {
        const_reverse_iterator tmp( *this );
        tmp += n;
        return tmp;
    }
    ptrdiff_t operator- ( const const_reverse_iterator& rhs ) const
    {
        return m_data - rhs.m_data;
    }
    const_iterator base()
    {
        return const_iterator( m_data + 1 );
    }
    const T& operator[] ( size_t ind ) const
    {
        return ( *( m_data - ind ) );
    }

    bool operator==( const const_reverse_iterator& other ) const _NOEXCEPT
    {
        return m_data == other.m_data;
    }
    bool operator!=( const const_reverse_iterator& other ) const _NOEXCEPT
    {
        return !( other == *this );
    }
    bool operator<( const const_reverse_iterator& other ) const _NOEXCEPT
    {
        return m_data > other.m_data;
    }
    bool operator>( const const_reverse_iterator& other ) const _NOEXCEPT
    {
        return *this < other;
    }
private:

    const T* m_data;
};


#endif //VECTOR_CONST_REVERSE_ITERATOR_H

Answer 1

1. We have consistently misspelt std::size_t.
2. _NOEXCEPT is a reserved identifier and may even be expanded as a macro.
3. We should have an initializer-list constructor - as a guide, construction and assignment argument lists should parallel each other.
4. inline is redundant and just adds clutter.
5. makeSpace() has no return statement.
6. Logging output should go to std::clog, not std::cout.
7. Outside of the class definition, the return type of insert() and other functions must be written as typename Vector<T>::iterator rather than Vector::iterator (or use trailing return type syntax).
8. Don't assume that an input iterator has operator-() (but do provide optimised overloads where std::distance() is usable).
9. We can't use T::operator= to populate uninitialized memory with an object - we need to construct in-place, or use one of the std::uninitialized_copy() family of functions.
10. We don't need moveFrom_() if we implement move construction and assignment using swap().
11. We can simplify copy-assign by implementing it in terms of move-assign (see below).
12. Relational operators could be simpler, if we used std::lexicographical_compare() instead of writing those loops.
13. The contains() member function is equivalent to calling std::find() and comparing the result against an end iterator.
14. There's too much whitespace for my taste - I'd certainly remove that around the . operator, and I suggest grouping related declarations on adjacent lines. Spaces around < and > makes template arguments harder to distinguish from the < and > operators.
15. Inheriting from std::iterator is now deprecated.
16. We could use std::reverse_iterator to create a reverse iterator from a forward iterator.
17. We could use a plain pointer as forward iterator.

---

Regarding the iterators, I successfully replaced those four files with:

using iterator = T*;
using const_iterator = const T*;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;

We need to also remove the -1 from the reverse begin/end (and we can further simplify):

iterator begin() noexcept { return m_data; }
iterator end() noexcept { return m_data + m_size; }

const_iterator begin() const noexcept { return m_data; }
const_iterator end() const noexcept { return m_data + m_size; }

reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
reverse_iterator rend() noexcept { return reverse_iterator(begin()); }

const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }

const_iterator cbegin() const noexcept { return begin(); }
const_iterator cend() const noexcept { return end(); }

const_reverse_iterator crbegin() const noexcept { return rbegin(); }
const_reverse_iterator crend() const noexcept { return rend(); }

---

Copy-assign implemented in terms of move-assign:

template<typename T>
inline Vector<T> &Vector<T>::operator=(const Vector& rhs)
{
    return *this = Vector<T>{rhs};
}

We can't implement copy-construct the same way, because passing by value depends on copy-construction, giving us a chicken-and-egg issue!

Answer 2

Overall

You need to use namespaces in your code. Nearly everybody and their granddaughter builds a Vector class at some point. So the likelhood of a clash is very high. Build yours into your own namespace (then you get not clashes).

Code Review

This is a good start.

#ifndef VECTOR_VECTOR_H
#define VECTOR_VECTOR_H

But does not look very unique to me (especially since everybody builds a Vector). Add the namespace into this guard and you will have something at least reasonably unique.

Don' do this.

#define _NOEXCEPT noexcept

In addition to _NOEXCEPT being a reserved identifier; why are you trying to obfuscate your code? Just put noexcept out there. Everybody understands it nowadays.

That's a lot to put on one line!

template < typename T > class Vector { public:  explicit Vector( size_t = INITIAL_CAPACITY );

In the rest of your code you put an empty line between every function (which I also find annoying) but here you force FOUR different things on a single line. Give the reader a break this needs to be broken up. Also group your methods into logical groups.

OK. This is a good constructor. But do you actually need to specify a default value? Can that not be inferred by the value taking on the default constructed version of the type?

    Vector( size_t, const T & );
    // I would have done
    Vector(size_t size, T const& init = T{});

I wish you would break the template stuff onto one row and the method stuff onto another row. That's a more common way of writing these declarations.

    template < typename InputIterator >     Vector( InputIterator, InputIterator );

OK. I see assignment to an initializer list but given this why can't I construct the vector with an initializer list? While we are at it why do you pass initializer lists by value?See comments below.

    Vector &operator=( std::initializer_list < T > );

    void assign( std::initializer_list < T > il );

Nice Standard set of push operations.

    void push_back( const T & );
    void push_back( T && );
    void pop_back() _NOEXCEPT;

But why don't I see an emplace_back() in the same area? Am I going to find it below?

Including other header files inside a class (and thus probably a namespace). That's not a disaster waiting to happen (sarcasm). These header files are dependent on this header file. What happens if a user includes them directly. You should at least set up some header guards that makes it hard to do that accidentally.

#include "const_iterator.h"
#include "iterator.h"
#include "const_reverse_iterator.h"
#include "reverse_iterator.h"

Don't really think you need any special iterator classes for a vector. A pointer to the member should work just fine (assuming contiguous memory for the data).

    iterator begin() _NOEXCEPT {        return iterator( m_data );  }
    iterator end() _NOEXCEPT {      return iterator( m_data + m_size );     }

My gosh.

private:    T      *m_data;     size_t m_size;  size_t m_capacity;

One variable per line please. Also brave of you to use T* as the pointer type. Let's see if you get the allocation correct.

Not sure why these are standalone methods. Why are they not members of the class?

template < typename T > bool operator==( const Vector < T > &lhs, const Vector < T > &rhs );    
template < typename T > bool operator!=( const Vector < T > &lhs, const Vector < T > &rhs );    
template < typename T > bool operator>( const Vector < T > &lhs, const Vector < T > &rhs );    
template < typename T > bool operator>=( const Vector < T > &lhs, const Vector < T > &rhs );    
template < typename T > bool operator<( const Vector < T > &lhs, const Vector < T > &rhs );    
template < typename T > bool operator<=( const Vector < T > &lhs, const Vector < T > &rhs );

OK. Copy swap idiom usually does not check for self-assignment.

template < typename T >
inline Vector < T > &Vector < T >::operator=( const Vector &rhs ) {
    if ( this != &rhs ) {
        //copy-swap idiom
        Vector tmp( rhs );
        swap( tmp );
    }
    return *this;
}

Yes. A self-assignment check will save you a lot if you actually do a self-assignment. But self-assignment is so vanishingly rare that you are actually pessimizing the normal action. Now this pessimization is a small cost but done so very frequently that the overall cost is on average higher than the cost of a self-assignment copy.

Prob(SelfAssigment) * {Cost Of SelfAssigment} < Prob(NormAssigment) * {Cost Of NormAssigment}

The standard way of writing this is:

// Pre Move semantics.
template < typename T >
inline Vector < T > &Vector < T >::operator=(Vector rhs) {
    swap( rhs );
    return *this;
}

// Post Move semantics as passing by value and RValue ref causes
// conflicting definitions for the compiler.
template < typename T >
inline Vector < T > &Vector < T >::operator=(Vector const& rhs) {
    Vector tmp(rhs);
    swap( tmp );
    return *this;
}