Vector implementation in C++

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
#include

template 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) {

Constructor

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

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

template
WVector::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 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 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 a(5);
WVector 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
WVector::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
typename WVector::const_iterator WVector::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
void WVector::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
void WVector::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
void WVector::reserve(size_t n) {
{
if (n 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_.constr

StackExchange Code Review Q#134391, answer score: 4