An alternative vector

Question

Based on this question (as a starting point) and a couple of other questions about rewriting vector in C++, I am planning to write another blog article to show the best way (or more precisely, the common pitfalls that most people fall into).

Before I start the blog article just wanted feedback to make sure I am not doing anything stupid.

#include <new>
#include <algorithm>
#include <stdexcept>
namespace ThorsAnvil
{
 template<typename T>
 class V
 {
 std::size_t capacity;
 std::size_t length;
 T* buffer;
 void makeSpaceAvailable()
 {
 if (length == capacity)
 {
 int newCapacity = std::max(10ul, capacity) * 1.62;
 V tmp(newCapacity);
 std::move(buffer, buffer + length, tmp.buffer);
 tmp.swap(*this);
 }
 }
 void validateIndex(std::size_t size)
 {
 if (size >= length)
 {
 std::stringstream message;
 message << "V: out of range: " << size << " is larger than: " << length;
 throw std::out_of_range(message.str());
 }
 }
 public:
 V(std::size_t cap = 10)
 : capacity(std::max(1ul, cap))
 , length(0)
 , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
 {}
 V(V const& copy)
 : capacity(copy.capacity)
 , length(copy.length)
 , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
 {
 std::copy(copy.buffer, copy.buffer + copy.length, buffer);
 }
 V& operator=(V value) // pass by value so this is a copy.
 {
 value.swap(*this); // Copy and Swap idiom
 return *this;
 }
 V(V&& move) noexcept
 : capacity(0)
 , length(0)
 , buffer(nullptr)
 {
 move.swap(*this); // Move just swaps content.
 }
 V& operator=(V&& value) noexcept
 {
 value.swap(*this);
 return *this;
 }
 ~V() noexcept
 {
 for(int loop = 0; loop < length; ++loop)
 {
 try {
 buffer[loop].~V();
 }
 catch(...) {} // catch and discard exceptions.
 }
 try {
 ::operator delete(buffer);
 } catch(...) {}
 }
 void swap(V& other) noexcept
 {
 using std::swap;
 swap(capacity, other.capacity);
 swap(length, other.length);
 swap(buffer, other.buffer);
 }
 T& operator[](std::size_t index) {return buffer[index];}
 T const& operator[](std::size_t index) const{return buffer[index];}
 T& at(std::size_t index) {validateIndex(index);return buffer[index];}
 T const& at(std::size_t index) const{validateIndex(index);return buffer[index];}
 void push(T const& u)
 {
 makeSpaceAvailable();
 ::new(&buffer[length++]) T(u);
 }
 void push(T&& u)
 {
 makeSpaceAvailable();
 ::new(&buffer[length++]) T(std::forward<T>(u));
 }
 template<class... Args>
 void emplace(Args&&... args)
 {
 makeSpaceAvailable();
 ::new(&buffer[length++]) T(std::forward<Args>(args)...);
 }
 void pop()
 {
 validateIndex(length-1);
 buffer[--length].~T();
 }
 };
 template<typename T>
 void swap(V<T>& lhs, V<T>& rhs)
 {
 lhs.swap(rhs);
 }
}

• R Sahu: I would move the public section of the class to the top and move the private section of the class to the bottom.
• Loki Astari: @RSahu Do you have a reason for that?
• R Sahu: private sections of a class, if we could, we would like to hide. Hence, I prefer to move them to the bottom of the class definition.
• Loki Astari: @RSahu: You should write that in an answer. I agree with the private methods. I disagree with the private variables; I believe putting them close to the constructor makes the class easier to read and understand. If this were purely an interface design (ie no implementation) I may put all the private at the bottom.

Answer 1

I think it is a great example for an article. Vector-like classes are probably the second most reimplemented library containers, probably only losing for string classes.

My comments

Even though this is example code for your post, you might consider giving the class a longer name. V confuses itself with a template parameter, so much that you've made a typo in here:

for(int loop = 0; loop < length; ++loop)
{
 try {
 buffer[loop].~V();
 }
 catch(...) {} // catch and discard exceptions.
}

It was supposed to be ~T(), but that's not a problem, the compiler will remind you ;)

---

void validateIndex(std::size_t size)
{
 if (size >= length)
 {
 std::stringstream message;
 message << "V: out of range: " << size << " is larger than: " << length;
 throw std::out_of_range(message.str());
 }
}

A few things about this method:

• Using a stringstream seems overcomplicating in this case. You could do with a simple std::string and std::to_string(). That would import less dependencies into the code, which might be important for frequently used stuff like vectors.

• The method itself should be const. Right now the code will not compile if I try to call at() on a const vector, because it will select the const overload which attempts to call non-const validateIndex(). Alternatively, you could also make it a static method and explicitly pass the length that is supposed to be validated against.

• Minor nitpicking, but validateIndex(size) seems a bit off. You're validating an index, so why is the param called size?

---

Don't know your thoughts, but I'm not a huge fan of using the global raw new directly. It is just so verbose and prone to typing errors, forgetting the sizeof, etc.

static_cast<T*>(::operator new(sizeof(T) * capacity))

You could wrap that into a private static helper that just takes a number of T elements and handles the rest in a cleaner way:

static T* allocate(std::size_t numOfElements)
{
 return static_cast<T*>(::operator new(sizeof(T) * numOfElements));
}

Miscellaneous

• Still missing all the size/capacity/empty accessors. front/back might also be interesting. If you have lots of free time, why not also go for some iterators?

• As far as I know, delete is always noexcept, so this should be pointless:

  try {
   ::operator delete(buffer);
  } catch(...) {}
  

• BTW, I also agree that catching an exception from the user destructor is dangerous. Could hide more serious problems. You might consider just letting the program terminate or call std::terminate/std::abort directly to trap right there and then.

Other than what was already said in Deduplicator's answer, it looks quite good.

Answer 2

Ok, you asked for it, so let's see what we can find.

1. There's seriously no reason for your default-constructor or move-constructor to ever throw an exception, as they don't actually need to aquire any resources (buffer != nullptr is already not an invariant anyway).
   Actually, a move-constructor which can throw is nigh useless.
   Thus, in C++1z they will be marked noexcept, if neccessary dependent on allocator default-constructor.

2. I would change makeSpaceAvailable in two ways:

   • Make it accept the new capacity, so one can pre-reserve as much as needed.
   • Split out the part actually doing the hard work of resizing, for reuse and so the rest can be easily inlined.
3. For validateIndex, I would also split out the error-case into its own method, so the rest is more likely to be inlined.
4. Your copy-constructor depends on the element-type having a trivial default constructor.
   Otherwise, treating raw memory as initialized objects would invoke UB.

5. You special-cased move-assignment, so the assignment-operator accepting by value only handles copying. Considering you thus forego the advantage of only having one of them, consider optimizing that one too, by making the copy in the function instead:

   V& operator=(V&& value) noexcept; // See question
   V& operator=(const V& value) { swap(V(value)); return *this; }
   

6. The destructor is ... interesting. You are catching exceptions if thrown by the individual destructors or the deallocation-function, and then silently swallow them.
   Which is at best harmless (if the element-type's destructor is well-behaved and thus cannot throw, as is the deallocation-function).
   At worst, you masked a catastrophic error which will now wipe out much more, so don't do that.
   Simply remove all exception-handling there, and let the language call std::terminate due to trying to propagate an exception from a noexcept-function.

7. I suggest you delegate all the hard work from the non-const version of at to the const one, as the const-qualifiers are the only difference.
8. As you have emplace, there's no sense in re-implementing that functionality for push. Just delegate.
9. You decided to define the behavor of pop on underflow. That's a valid decision, though it certainly adds some overhead...
10. There are quite some members which could be noexcept-qualified.

• Loki Astari: 1: Yes: move constructor should not throw. I believe I marked it as such. No: Default constructor can definitely throw in most objects (especially when there is resource allocation).
• Loki Astari: 4: Don't think it depends on it at all. The copy constructor provides the strong exception guarantee. Are you referring to the potential for a leak if T does not provide nothrow construction/destruction?
• Loki Astari: 5: Don't understand what you are saying. This is consider the standard way of writing a copy assignment operator. stackoverflow.com/a/3279616/14065
• Loki Astari: 7: If there was actually any code in there I might use an inlined function. But for this trivial of a function it just adds extra complexity that is not worth the effort.
• Loki Astari: 6: Yes. I deliberately wrote it this way to try and provoke a discussion. Still thinking this one threw.

Answer 3

Lots of good stuff from @glampert and @Deduplicator.

Destructor

I missed an obvious one.
The destructor (to be like an array) must destroy the members in reverse order (taking the catch and throw out for now as I am still working on that).

 ~V() noexcept
 {
 for(std::size_t loop = 0; loop < length; ++loop)
 {
 // Change this line.
 buffer[loop].~V();
 // Into
 buffer[length - 1 - loop].~T();
 }
 ::operator delete(buffer);
 }

Optimize Copy Constructor/Assignment

I believe what @Deduplicator is getting at is that the copy/assignment operator can be optimized under certain situations. If the type T has a no-throw copy constructor and no-throw destrcutor then we can optimize the copy of the array.

The Copy/Swap idiom is designed to be great when there is the possibility of failure and if that happens uses RAII to cleanup and destroy any temporary objects created. But if you don't need that cleanup then you can use an optimized version.

This is where the noexcept keywords comes in. Using template meta-programming we can check if these operations are safe and plant the appropriate code.

I can see the basics here. But my template meta programming is not something I can do of the top of my head for something like this. So watch this space.

Initializer Lists

Some obvious constructors missed. We are now in the land of C++14 and rapidly approaching the next version is supposed to be out next year in C++17. So we should allow at least std::initializer_list

 template<typename I>
 V(I begin, I end);
 V(std::initializer_list<T> const& list);

Container Semantics

Need to add the required types and methods for it to be considered a normal container.

Comparison Operators.

Most containers can be contained to other containers. So it may be worth defining those.

Answer 4

Suggestion for physical layout of members

A user of the class is most interested in the public section of the class. They are least interested in the private section of the class. Ideally, we would like to hide the private section of a class.

Hence, it makes sense to me to move the public section of the class to the top of the class and move the private section of the class to the bottom.

• Loki Astari: +1 That holds true if you are just interested in the interface (you only care about the public methods). When you are reviewing code you are also interested in all the members (so you can validate easily that they are being initialized in the constructor. I hate having to go find all the members of the class and validate them against the constructors, I want them there with the code that initializes them). All that changes of course if I don't provide the function definitions inline.