Vector implementation in C++

Question

I started this because I thought it would be a fun and easy way to brush up on my C++. It turned out to be a lot more complicated than I thought. I learned about std::allocator and move constructors and other things I had never seen before, so it was a good learning exercise.

The interface is based on std::vector, though I haven't implemented everything. It's called WVector because W is my first initial.

I know some people have posted similar things on this site before and I've tried to learn from their mistakes. I hope you will let me know about all mistakes that you find, but I'm worried particularly about reserve(). If an exception is thrown in T's constructor, there will clearly be a leak. But I'm not sure how to handle this.

#include <iostream>
#include <stdexcept>

template<class T> class WVector {
  public:

    typedef T value_type;
    typedef T* iterator;
    typedef const T* const_iterator;

    size_t size() const;

    T& operator[] (size_t index);
    const T& operator[] (size_t index) const;

    T& at(size_t index);
    const T& at(size_t index) const;

    void push_back(const T& element);

    void resize(size_t new_size);
    void resize(size_t new_size, const value_type& val);
    void reserve(size_t n);

    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;

    WVector();
    WVector(size_t n);
    WVector(size_t n, const value_type& val);
    WVector(const WVector& x);
    WVector(WVector&& x);

    ~WVector();

    //This form of the function provides both copy- and move-assignment
    //https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom
    //http://en.cppreference.com/w/cpp/language/operators#Assignment_operator
    WVector& operator= (WVector x);

    //see https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom
    //and https://stackoverflow.com/questions/5695548/public-friend-swap-member-function
    friend void swap(WVector& first, WVector& second) {
      using std::swap;

      swap(first.size_, second.size_);
      swap(first.capacity_, second.capacity_);
      swap(first.data_, second.data_);
    }

  private:
    size_t size_;
    size_t capacity_;
    T* data_;
    std::allocator<T> alloc_;

    void resize_smaller(size_t new_size);
    void expand_capacity(size_t new_size);
};

template<class T>
size_t WVector<T>::size() const {
  return size_;
}

template<class T>
T& WVector<T>::operator[] (size_t index) {
  return data_[index];
}

template<class T>
const T& WVector<T>::operator[] (size_t index) const {
  return data_[index];
}

template<class T>
T& WVector<T>::at(size_t index) {
  if (index >= size_) throw std::out_of_range("index too big");
  return data_[index];
}

template<class T>
const T& WVector<T>::at(size_t index) const {
  if (index >= size_) throw std::out_of_range("index too big");
  return data_[index];
}

template<class T>
void WVector<T>::push_back(const T& element) {
  resize(size_+1,element);
}

template<class T>
void WVector<T>::resize_smaller(size_t new_size) {
  for (iterator it = data_ + new_size; it != data_ + size_; ++it) {
    alloc_.destroy(it);
  }
  size_ = new_size;
}

template<class T>
void WVector<T>::expand_capacity(size_t new_size) {
  size_t new_capacity;
  if (capacity_ == 0) {
    new_capacity = 1;
  } else if (capacity_ < SIZE_MAX/2) {
    new_capacity = capacity_*2;
  } else {
    new_capacity = SIZE_MAX;
  }

  if (new_size > new_capacity) new_capacity = new_size;

  reserve(new_capacity);
}

template<class T>
void WVector<T>::resize(size_t new_size) {
  if (size_ == new_size) return;
  if (new_size < size_) {
    resize_smaller(new_size);
    return;
  }
  if (new_size > capacity_) {
    expand_capacity(new_size);
  }

  for (iterator it = data_ + size_; it != data_ + new_size; ++it) {
    alloc_.construct(it);
  }
  size_ = new_size;
}

template<class T>
void WVector<T>::resize(size_t new_size, const value_type& val) {
  if (size_ == new_size) return;
  if (new_size < size_) {
    resize_smaller(new_size);
    return;
  }
  if (new_size > capacity_) {
    expand_capacity(new_size);
  }

  for (iterator it = data_ + size_; it != data_ + new_size; ++it) {
    alloc_.construct(it,val);
  }
  size_ = new_size;
}

template<class T>
void WVector<T>::reserve(size_t n) {
  if (n <= capacity_) {
    return;
  }

  T* old_data = data_;
  size_t old_capacity = capacity_;

  data_ = alloc_.allocate(n);
  capacity_ = n;
  for (size_t i=0; i<size_; i++) {
    alloc_.construct(data_ + i, old_data[i]);
  }

  for (size_t i=0; i<size_; i++) {
    alloc_.destroy(old_data + i);
  }
  alloc_.deallocate(old_data,old_capacity);
}

template<class T>
typename WVector<T>::iterator WVector<T>::begin() {
  return &data_[0];
}

template<class T>
typename WVector<T>::const_iterator WVector<T>::begin() const {
  return &data_[0];
}

template<class T>
typename WVector<T>::iterator WVector<T>::end() {
  return &data_[size_];
}

template<class T>
typename WVector<T>::const_iterator WVector<T>::end() const {
  return &data_[size_];
}

template<class T>
WVector<T>::WVector() {
  size_ = 0;
  capacity_ = 0;
  data_ = nullptr;
}

template<class T>
WVector<T>::WVector(size_t n) {
  size_ = n;
  capacity_ = n;
  data_ = alloc_.allocate(capacity_);
  for (iterator it = data_; it != data_ + size_; ++it) {
    alloc_.construct(it);
  }
}

template<class T>
WVector<T>::WVector(size_t n, const value_type& val) {
  size_ = n;
  capacity_ = n;
  data_ = alloc_.allocate(capacity_);
  for (iterator it = data_; it != data_ + size_; ++it) {
    alloc_.construct(it, val);
  }
}

template<class T>
WVector<T>::WVector(const WVector& x) {
  size_ = x.size_;
  capacity_ = x.capacity_;
  data_ = alloc_.allocate(capacity_);
  for (size_t i=0; i<size_; i++) {
    alloc_.construct(data_ + i, x.data_[i]);
  }
}

template<class T>
WVector<T>::WVector(WVector&& x)
   : WVector() //initialize this via default constructor
{
  swap(*this,x); //then swap the empty vector with the vector to be moved
}

template<class T>
WVector<T>::~WVector() {
  for (iterator it = data_; it != data_ + size_; ++it) {
    alloc_.destroy(it);
  }
  alloc_.deallocate(data_,capacity_);
}


template<class T>
WVector<T>& WVector<T>::operator=(WVector<T> x) { //x is constructed by either the copy or move constructor as appropriate
  swap(*this, x);
  return *this;
} //destructor of x is called, free resources originally held by *this


template<typename T>
std::ostream& operator<< (std::ostream& out, const WVector<T>& vec) {
  for (const auto &iter : vec) {
    out << iter << ",";
  }
  return out;
}

Answer 1

Constructor

You can dry up this code by only having a single constructor here:

template<class T>
WVector<T>::WVector(size_t n) {
  size_ = n;
  capacity_ = n;
  data_ = alloc_.allocate(capacity_);
  for (iterator it = data_; it != data_ + size_; ++it) {
    alloc_.construct(it);
  }
}

template<class T>
WVector<T>::WVector(size_t n, const value_type& val) {
  size_ = n;
  capacity_ = n;
  data_ = alloc_.allocate(capacity_);
  for (iterator it = data_; it != data_ + size_; ++it) {
    alloc_.construct(it, val);
  }
}

These two basically do exactly the same thing. The difference is that the first one default constructs the object type T into the array. You can re-use the code of the second one to do this; just bind a default(ly) constructed object to the second parameter.

template<class T>
class WVector
{
    public:
        WVector(size_t n, const value_type& val = T()) {
                                               ^^^^^^
          size_ = n;
          capacity_ = n;
          data_ = alloc_.allocate(capacity_);
          for (iterator it = data_; it != data_ + size_; ++it) {
            alloc_.construct(it, val);
          }
        }
};

###Move constructor (and move assignment) noexcept

The move semantics should normally be declared as noexcept (unless they are not (but they usually are). The standard librarys will enable optimizations if these two are noexcept as you can then provide some extra guarantees that allows the container resize() (and probably other stuff) to provide the strong exception gurantee on resize (with your type as the object).

template<class T>
class WVector
{
    public:
        WVector(WVector&& rhs) noexcept;
};

###Copy Assignment (as Move Assignment) I am reassessing this. I am not longer convinced I am correct. WVector& WVector::operator=(WVector x) { //x is constructed by either the copy or move constructor as appropriate

Not sure I believe the comment here.

You can do this:

WVector<char> a(5);
WVector<char> b(5);

a = std::move(b);

// But `b` will not be moved.
// It will be copied into the assignment operator.
// Thus you don't get the advantages of move assignment.
// Note: Which should also be `noexcept`

###Default construction.

template<class T>
WVector<T>::WVector() {
  size_ = 0;
  capacity_ = 0;
  data_ = nullptr;
}

You may want to allocate a zero sized object for data.

This is because of this function.

template<class T>
typename WVector<T>::const_iterator WVector<T>::end() const {
  return &data_[size_];
}

If you default construct a WVector then call begin() or end() is the result UB. I think it is fine. But I have had some long arguments with people that disagree (I have not yet been convinced I am wrong; so I think the above is good. BUT there are some people I respect that don't think its correct. Easier to sidestep the issue and create a zero sized dynamically allocated object (or give it a real capacity).

###Re-use copy and swap on resize

This is fine as long as construction or destruction of T does not throw. But if the do then you will leak data and potentially have a half built object.

template<class T>
void WVector<T>::reserve(size_t n) {
  if (n <= capacity_) {
    return;
  }

  T* old_data = data_;
  size_t old_capacity = capacity_;

  data_ = alloc_.allocate(n);
  capacity_ = n;
  for (size_t i=0; i<size_; i++) {
    alloc_.construct(data_ + i, old_data[i]);
  }

  for (size_t i=0; i<size_; i++) {
    alloc_.destroy(old_data + i);
  }
  alloc_.deallocate(old_data,old_capacity);
}

You should do the resize in three distinct phases.

1) Allocate new object in temporary storage. (may throw)
2) Swap temporary and current storage        (must not throw)
3) Deallocate temorary storage               (may throw)

SO if we re-write your code to adhere to these principles:

template<class T>
void WVector<T>::reserve(size_t n) {
  if (n <= capacity_) {
    return;
  }

  // Phase 1
  // Create Temporary    
  size_t new_capacity =n;
  size_t new_size = size;
  T*     new_data = alloc_.allocate(n);

  // Copy data into temporary
  for (size_t i=0; i<size_; i++) {
    alloc_.construct(new_data + i, data[i]);
  }

  // Phase 2 Swap
  std::swap(new_capacity, capacity);
  std::swap(new_size,     size);
  std::swap(new_data,     data);

  // Phase 3 Deallocate temporary (was original data)
  for (size_t i=0; i<size_; i++) {
    alloc_.destroy(new_data + i);
  }
  alloc_.deallocate(new_data, new_capacity);
}

The above is still not perfect as it still leaks on a throw. But I am just using it to illustrate the different parts. If you look at this it looks very much like (copy/swap/destroy). So can be much more simply written as:

template<class T>
void WVector<T>::reserve(size_t n) {
{
  if (n <= capacity_) {
    return;
  }

  // Phase 1
  // Create Temporary    
  WVector<T> tmp(0);                    // All of phase 1 here
  tmp.data     = tmp.alloc.allocate(n); // Should be moved to a private constructor.
  tmp.capacity = n;                     // This is just for illustration.

  // Copy data into temporary
  for (size_t i=0; i<size_; i++) {
    tmp.alloc_.construct(tmp.data + i, data[i]);
    tmp.size = i;
  }

  // Phase 2
  tmp.swap(*this);

  // Phase 3 (Handled by destructor.
}
    

###Resizeing

A value of 2 sounds good as a multiplier.

  } else if (capacity_ < SIZE_MAX/2) {
    new_capacity = capacity_*2;

But 1.5 is better. See:
https://lokiastari.com/posts/MemoryResizing

###Pushing back

You push_back() is fine as it goes. But it may be worth having a couple of overloads to handle moving and constructing in place.

void push_back(const T& element);
void push_back(T&& element);
template<typename... Args>
void emplace_back(Args... args);

###Swap as member and friend.

You should define swap as a member (that is noexcept). You can then call this from the friend version. This allows for easier calling from your noexcept move operators.

    void swap(WVector& rhs) noexcept
    {
      using std::swap;

      swap(size_, rhs.size_);
      swap(capacity_, rhs.capacity_);
      swap(data_, rhs.data_);
    }
    friend void swap(WVector& lhs, WVector& rhs) {
        lhs.swap(rhs);
    }

Comments

I would have put these comments next to the functions definitions (not the declarations).

    //This form of the function provides both copy- and move-assignment
    //https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom
    //http://en.cppreference.com/w/cpp/language/operators#Assignment_operator
    WVector& operator= (WVector x);

    //see https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom
    //and https://stackoverflow.com/questions/5695548/public-friend-swap-member-function

So that when I read the implementation of these functions I could see why it was being done this way. Still don't believe the copy and move can be done in the same assignment.

Try this:

#include <utility>
#include <iostream>
class V
{
    public:
        V()
        {}
        V(V const& copy)
        {
            std::cerr << "Copy\n";
        }
        V& operator=(V copy)
        {
            return *this;
        }
};

int main()
{
    V   a;
    V   b;
    a = std::move(b);
}

Then:

> g++ -std=c++14 -O3 t2.cpp
> ./a.out
> Copy

###Output operator.

Usually when you provide an output operator you also provide an equivalent input operator that is able to read the streamed output of the structure.

Your list of elements has a trailing , with no last element. Not a huge problem but it looks untidy.

template<typename T>
std::ostream& operator<< (std::ostream& out, const WVector<T>& vec) {
  for (const auto &iter : vec) {
    out << iter << ",";
  }
  return out;
}