Vector

So, the C++ standard specifies a set of requirements for containers. Very few requirements are specified in terms of containers, so adhering to these strictly is not required (unless you want to be considered for the standard). But they provide an insight into what can be done with them, and if you support them, it will allow your container to be more easily used with some features of the language and standard library. I am not going to go over all of them here (that is left as an exercise for the reader), but I will go over the ones I would expect to see in a simple implementation (the kind you would see in a university project). ...

Now that we have used std::is_nothrow_move_constructible, we can also examine a couple of other types available in the template utility library. Optimized Destruction Since we have to manually call the destructor on all objects in the container (because we are using placement new), we can look to see if we can optimize that. The type std::is_trivially_destructible detects if the type is Trivially destructible. This basically means that there will be no side effects from the destructor (See: Section 12.4 Paragraph 5 of the standard). For types we don’t need to call the destructor of the object. For the Vector class, this means we can eliminate the call to the destructor but, more importantly, the loop. ...

Because resizing a vector is expensive, the std::vector class uses exponential growth to minimize the number of times that the vector is resized: a technique we replicate in this version. But every now and then, you still need to resize the internal buffer. In the current version, resizing the vector requires allocating a new buffer and copying all the members into it. We use the copy and swap idiom to provide the strong exception guarantee (If an exception is thrown, all resources are cleaned up, and the object remains unchanged). ...

In the previous article, I went over basic allocation for a Vector like class. In this article, I want to put some detail around the copy assignment operator and resizing the underlying Vector. Unlike the other methods previously discussed, these methods have to deal with both construction and destruction of elements and the potential of exceptions interrupting the processes. The goal is to provide exception safe methods that provide the strong exception guarantee for the object and do not leak resources. ...

Many new developers of C++ attempt to build a Vector like container as a learning process. Getting a simple version of this working for POD types (like int) is not that complicated. The next step in getting this working for arbitrary data types takes a significant leap forward in thinking in C++, especially when you start looking at efficiency and exception safety. This set of five articles looks at building an efficient Vector implementation. I show some of the common mistakes and explain why and how to resolve the problems: ...