C++ Vector The basics

Question

Following on from my two previous posts.

• An alternative vector
• An Alternative Vector (Copy Assignment Operator)

I have written a detailed blog about how to write a minimal vector like class. This set of articles has been inspired by multiple posts here on http://codereview.stackexchange.com (See Sources).

• Index
  1. Resource Management: Allocation
  2. Resource Management: Copy and Swap
  3. Resource Management: Resize
  4. Resource Management: Simple Optimization
  5. The Other Stuff

The final result is below.
But now it is my turn for some review to make sure I did not screw up too much. :-)

Head:

#ifndef THORSANVIL_CONTAINER_VECTOR
#define THORSANVIL_CONTAINER_VECTOR
#include <type_traits>
#include <memory>
#include <algorithm>
#include <stdexcept>
#include <iterator>
#include <cmath>
namespace ThorsAnvil
{
 namespace Container
 {

Types:

template<typename T>
class Vector
{
 public:
 using value_type = T;
 using reference = T&;
 using const_reference = T const&;
 using pointer = T*;
 using const_pointer = T const*;
 using iterator = T*;
 using const_iterator = T const*;
 using difference_type = std::ptrdiff_t;
 using size_type = std::size_t;
 private:
 size_type capacity;
 size_type length;
 T* buffer;
 struct Deleter
 {
 void operator()(T* buffer) const
 {
 ::operator delete(buffer);
 }
 };

Constructors:

 public:
 Vector(int capacity = 10)
 : capacity(capacity)
 , length(0)
 , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
 {}
 template<typename I>
 Vector(I begin, I end)
 : capacity(std::distance(begin, end))
 , length(0)
 , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
 {
 for(auto loop = begin;loop != end; ++loop)
 {
 pushBackInternal(*loop);
 }
 }
 Vector(std::initializer_list<T> const& list)
 : Vector(std::begin(list), std::end(list))
 {}
 ~Vector()
 {
 // Make sure the buffer is deleted even with exceptions
 // This will be called to release the pointer at the end
 // of scope.
 std::unique_ptr<T, Deleter> deleter(buffer, Deleter());
 clearElements<T>();
 }
 Vector(Vector const& copy)
 : capacity(copy.length)
 , length(0)
 , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
 {
 try
 {
 for(int loop = 0; loop < copy.length; ++loop)
 {
 push_back(copy.buffer[loop]);
 }
 }
 catch(...)
 {
 clearElements<T>();
 ::operator delete(buffer);
 // Make sure the exceptions continue propagating after
 // the cleanup has completed.
 throw;
 }
 }
 Vector& operator=(Vector const& copy)
 {
 copyAssign<T>(copy);
 return *this;
 }
 Vector(Vector&& move) noexcept
 : capacity(0)
 , length(0)
 , buffer(nullptr)
 {
 move.swap(*this);
 }
 Vector& operator=(Vector&& move) noexcept
 {
 move.swap(*this);
 return *this;
 }
 void swap(Vector& other) noexcept
 {
 using std::swap;
 swap(capacity, other.capacity);
 swap(length, other.length);
 swap(buffer, other.buffer);
 }

Access:

 reference operator[](size_type index) {return buffer[index];}
 const_reference operator[](size_type index) const {return buffer[index];}
 reference at(size_type index) {validateIndex(index);return buffer[index];}
 const_reference at(size_type index) const {validateIndex(index);return buffer[index];}
 reference front() {return buffer[0];}
 const_reference front() const {return buffer[0];}
 reference back() {return buffer[length - 1];}
 const_reference back() const {return buffer[length - 1];}

Comparison:

 bool operator!=(Vector const& rhs) const {return !(*this == rhs);}
 bool operator==(Vector const& rhs) const
 {
 return (size() == rhs.size())
 ? std::equal(begin(), end(), rhs.begin())
 : false;
 }

Iterators:

 iterator begin() {return buffer;}
 iterator rbegin() {return std::reverse_iterator<iterator>(end());}
 const_iterator begin() const {return buffer;}
 const_iterator rbegin() const {return std::reverse_iterator<iterator>(end());}
 iterator end() {return buffer + length;}
 iterator rend() {return std::reverse_iterator<iterator>(begin());}
 const_iterator end() const {return buffer + length;}
 const_iterator rend() const {return std::reverse_iterator<iterator>(begin());}
 const_iterator cbegin() const {return begin();}
 const_iterator crbegin() const {return rbegin();}
 const_iterator cend() const {return end();}
 const_iterator crend() const {return rend();}

Non-Mutating Functions:

 size_type size() const {return length;}
 bool empty() const {return length == 0;}

Mutating Functions:

 void push_back(T const& value)
 {
 resizeIfRequire();
 pushBackInternal(value);
 }
 void push_back(T&& value)
 {
 resizeIfRequire();
 moveBackInternal(std::forward<T>(value));
 }
 template<typename... Args>
 void emplace_back(Args&&... args)
 {
 resizeIfRequire();
 constructBackInternal(std::forward<T>(args)...);
 }
 void pop_back()
 {
 --length;
 buffer[length].~T();
 }
 void reserve(size_type capacityUpperBound)
 {
 if (capacityUpperBound > capacity)
 {
 reserveCapacity(capacityUpperBound);
 }
 }

Private:

 private:
 void validateIndex(size_type index)
 {
 if (index >= length)
 {
 throw std::out_of_range("Out of Range");
 }
 }
 void resizeIfRequire()
 {
 if (length == capacity)
 {
 size_type newCapacity = std::max(2.0, capacity * 1.62);
 reserveCapacity(newCapacity);
 }
 }
 void reserveCapacity(size_type newCapacity)
 {
 Vector<T> tmpBuffer(newCapacity);
 simpleCopy<T>(tmpBuffer);
 tmpBuffer.swap(*this);
 }
 void pushBackInternal(T const& value)
 {
 new (buffer + length) T(value);
 ++length;
 }
 void moveBackInternal(T&& value)
 {
 new (buffer + length) T(std::forward<T>(value));
 ++length;
 }
 template<typename... Args>
 void constructBackInternal(Args&&... args)
 {
 new (buffer + length) T(std::forward<Args>(args)...);
 ++length;
 }
 template<typename X>
 typename std::enable_if<std::is_nothrow_move_constructible<X>::value == false>::type
 simpleCopy(Vector<T>& dst)
 {
 std::for_each(buffer, buffer + length,
 [&dst](T const& v){dst.pushBackInternal(v);}
 );
 }
 template<typename X>
 typename std::enable_if<std::is_nothrow_move_constructible<X>::value == true>::type
 simpleCopy(Vector<T>& dst)
 {
 std::for_each(buffer, buffer + length,
 [&dst](T& v){dst.moveBackInternal(std::move(v));}
 );
 }
 template<typename X>
 typename std::enable_if<std::is_trivially_destructible<X>::value == false>::type
 clearElements()
 {
 // Call the destructor on all the members in reverse order
 for(int loop = 0; loop < length; ++loop)
 {
 // Note we destroy the elements in reverse order.
 buffer[length - 1 - loop].~T();
 }
 }
 template<typename X>
 typename std::enable_if<std::is_trivially_destructible<X>::value == true>::type
 clearElements()
 {
 // Trivially destructible objects can be re-used without using the destructor.
 }
 template<typename X>
 typename std::enable_if<(std::is_nothrow_copy_constructible<X>::value
 && std::is_nothrow_destructible<X>::value) == true>::type
 copyAssign(Vector<X>& copy)
 {
 if (this == &copy)
 {
 return;
 }
 if (capacity <= copy.length)
 {
 clearElements<T>();
 length = 0;
 for(int loop = 0; loop < copy.length; ++loop)
 {
 pushBackInternal(copy[loop]);
 }
 }
 else
 {
 // Copy and Swap idiom
 Vector<T> tmp(copy);
 tmp.swap(*this);
 }
 }
 template<typename X>
 typename std::enable_if<(std::is_nothrow_copy_constructible<X>::value
 && std::is_nothrow_destructible<X>::value) == false>::type
 copyAssign(Vector<X>& copy)
 {
 // Copy and Swap idiom
 Vector<T> tmp(copy);
 tmp.swap(*this);
 }
};

Tail:

 }
}
#endif

• Quuxplusone: Not a full answer, but three bug reports: Your rbegin() function needs to return reverse_iterator, not iterator. Your moveBackInternal function needs to call std::move(value), not std::forward<T>(value). I suspect that Vector<int>(1).push_back(2) will corrupt memory.
• Loki Astari: @Quuxplusone: Thanks. rbegin()/rend() oops mistake added unit tests for that. Now fixed. std::forward Vs std::move still working on move semantics; so I get that wrong sometimes. Will have to write an article about the subject. I doubt that there is memory corruption with that. But while adding some unit tests to test the theory; I did find another error. Need std::max() to make sure capacity of 0/1 scales up correctly.
• Quuxplusone: For the record, your "another bug" was indeed the bug I was referring to with that third sentence. :)
• DarthGizka: That must be some new meaning of 'minimal' that I wasn't previously aware of... I'm glad that we can usually get away with #include <vector>.
• Loki Astari: @DarthGizka: Yes this is minimal. That is why other examples on codereview get so many comments when they try and implement their own vector. But also note I wrote this as an exploration of why std::vector is written the way it is. This is the result of five blog posts (so you can see the reason for each feature in the blog). But even my code needs a review. :-)

Answer 1

I've only had a chance to glance at things so far, but this almost jumped out at me:

 bool operator==(Vector const& rhs) const
 {
 return (size() == rhs.size())
 ? std::equal(begin(), end(), rhs.begin())
 : false;
 }

This seems rather convoluted, at least to me. I'd prefer:

bool operator==(Vector const& rhs) const
{
 return (size() == rhs.size()) && std::equal(begin(), end(), rhs.begin()); 
}

I believe this shows the intent much more directly, and (thanks to short-circuit evaluation) still avoids evaluating std::equal if the sizes aren't equal.

Some of the names also seem somewhat misleading. For example, I'd rename resizeIfRequire to something like reallocIfRequired, since it can only affect the capacity, not the size.

Oh, looking at the multiplier you've used: 1.62 is a poor choice. The point of using the golden mean is that it's the largest multiplier you can use that guarantees that (if they're contiguous) the discarded pieces will eventually add together to be large enough to fulfill the next larger request size. Note that wording carefully though: the golden mean is the largest multiplier you can use and still get this result. By rounding up from the golden mean (1.618...) to 1.62, you've basically assured this can't happen.

To get the desired behavior, you need to use a multiplier that's less than or equal to the golden mean. In most cases, the memory manager will add a little overhead to the block size you use, so if you use exactly the golden mean, it'll never happen either. I'd recommend a multiplier no greater than 1.6. In many cases, it's easiest to use 1.5, which makes integer math easy, and still gets roughly the same effects (and a fair amount of empirical testing indicates works well in general).

• Loki Astari: Thanks. Need to read more on that topic. Here i was trying to be clever and kicking myself in the butt.
• Dmitry Rubanovich: Golden ratio will still likely cause rounding errors. If you want to do it right, precompute the first few (dozen... or hundred?) fibonacci numbers and use them as multipliers. This way you'll have actual integer multipliers and you can set the initial value to something sane. So all the values after will be sane*fib(n).

Answer 2

My 5 cents:

This does not seems legal to use std::forward, unless it is not universal reference.

Change it to std::move or add template<class UT>.

 void push_back(T&& value)
 {
 resizeIfRequire();
 moveBackInternal(std::forward<T>(value));
 }

You did this everywhere.

• Loki Astari: Yep: SO agrees with you: stackoverflow.com/a/36142477/14065

Answer 3

Reverse iterator don't compile.

for (auto k = b.rbegin(); k != b.rend(); ++k)
{ std::cout << k; }

Give: error: no viable conversion from 'std::reverse_iterator' to 'iterator' (aka 'int *')

You shouldn't use a pointer as reverse iterator, the ++ on a reverse iterator should decrement the position.

---

The move operator should invalidate the moved object.

Vector& operator=(Vector&& move) noexcept
{
 move.swap(*this);
 // move should be deallocated and invalidated
 return *this;
}

---

Apart from that I didn't spot any other obvious mistake. And Valgrind didn't spot any leaks. Also I like the format and the use of enable_if to optimize the copy of POD.

• ilmale: I notice now that they spotted the iterator bug in a comment of the original post.. >_>
• Loki Astari: Thanks for the review. All input gratefully received. There is no need to invalidate the moved object though (after a move the object just needs to be valid). And you should definitely not deallocate the memory. The move objects destructor will handle this until then it could be potentially re-used.
• ilmale: I think you are right, but the expected behaviour is that a moved object is not the owner of the resource. From cppreference "Move assignment operators typically "steal" the resources held by the argument (e.g. pointers to dynamically-allocated objects, file descriptors, TCP sockets, I/O streams, running threads, etc.), rather than make copies of them, and leave the argument in some valid but otherwise indeterminate state. For example, move-assigning from a std::string or from a std::vector may result in the argument being left empty. However, this behaviour should not be relied upon."
• Loki Astari: Yes. After you have moved an object what is left behind is unspeciied as long as the object is valid. But you can still re-use it if you set it to a known state before use. std::string a = "X";std::string b = "Y";a = std::move(b); /* b can still be used. But you need to set it to a known state before you can do anything useful */ b.clear();. If I had deallocate the memory associated with b then you would have had lots of unnessacery work in resource management. But simply setting its state to empty it becomes re-usable with no memory allocation required.