Welcome back! I hope you’re enjoying quarantine. I know for me, not being able to get out climb has definitely had an impact on my mental health. Oh, and my waistline. That being said, I’ve had more time to get into the code, which is a piece of my own little paradise.
As I mentioned in my last write-up, I’m trying to bring these posts back to basics, and give people more of what they’re interested in reading. Though, it’s very likely that the people find those posts more interesting, because I had more fun writing them. Reverse engineering the C++ unit test framework brought me immense joy, because I was really excited by it, and to write about it. With that in mind, I spent a good long while trying to figure out what I should post next. I haven’t had the itch to deconstruct anything lately. I decided to rack my brain, and remember what the original intent of my blog was. To demystify code, to remove the “magic” behind it. I’ve always been curious about the way things worked. As developers, we shouldn’t be afraid of the magic behind libraries, we should embrace it. We should strive to understand at least peripherally how the code we use works. I once made a comment on Reddit, to a untrained junior developer looking for tips on how to further his career. The tip was that they should take their work code home, and try to recreate it. For me, recreating code I didn’t understand was always the best tool to further my understanding. You start small, and you build, as you run into problems you start to understand why the author did the things they did. You can start to form opinions about the decisions they made, as you understand the problems they faced. Needless to say, this comment was down-voted into oblivion, and someone even suggested that I was instructing OP to steal their employer’s code. (Spoiler: I wasn’t.) Reddit not agreeing with me didn’t change my mind. I still think that reverse engineering something is the best way to understand it. If you’ve got access to the code on a laptop, I’m sure your boss wouldn’t mind if you took the initiative to understand company code better. Just don’t go selling your companies code.
So, that’s sort of what inspired this series, Don’t try this at work. In my personal experience, I’ve noticed a commonly occurring problem, people experimenting at work. I’m sure we can all agree that writing code, is as much an art, as it is a science. The problem is, that often times if people don’t have an outlet outside of work, they’ll use the company code base as their canvas. This can be problematic for smaller companies, who don’t always have the capacity and resources of a larger company to catch these things. These “works of art” can sometimes make it into production code, thus needing to be maintained for the lifetime of the application. This type of exploratory code is often coined “toy” code, it’s code you definitely shouldn’t be using at work. Hence, Don’t try this at work. In the Don’t try this at work series, I want to demystify the one of the most commonly used classes, in the most common library, used by almost all C++ developers. The Standard Template Library.
In this, the first of the Don’t try this at work series, I’m going to be looking at something every C++ developer, regardless of experience, uses (or at least knows of). Just because we all use it, doesn’t mean we understand it. So without further ado, let’s dive into the vector!
You can find all the code I write for this series here, if you have any questions or comments feel free to shoot me an email.
The STL vector is the probably the most ubiquitous container used in C++. If you need a generic dynamically sized container, the vector is the first tool you should grab from the STL’s bag of tricks. It’s a thin wrapper over contiguous memory, providing immense usability with little overhead over a raw array. It can easily be used with STL algorithms, and fits most cases where a dynamically sized container is required. It features constant time random access, amortized constant appending and removal to the end, and linear insertions and deletions. In short, if you don’t use vectors, you should.
Warning: Because a vector is a generic container, we’re going to be doing template programming. So if you’re faint of heart, stop reading now.
Where do we start? Well, the vector is essentially a wrapper over an array, that will expand when the array runs out of space. So, something simple probably looks like this.
template <typename T>
class vector
{
T* data_;
size_t size_;
size_t cap_;
public:
vector()
:data_(new T[10]),size_(0),cap_(10)
{
}
void push_back(const T& value)
{
if (size_ == cap_)
{
grow();
}
data_[size_++] = value;
}
private:
void grow()
{
T* tmp = new T[cap_ * 2];
for (int i = 0; i < size_; ++i)
tmp[i] = data_[i];
cap_ = cap_ * 2;
auto data = data_;
data_ = tmp;
delete data;
}
};
Pretty simple right? The basics of a vector are that, we have an array, the count of objects (size), and the capacity. When we push a new object, we check to see if we have space, if not we’ll grow, and then push that item on the end. When we do have to grow, we allocate double the capacity, copy all the items over, and then delete the old array. Neat huh? The problem is, that this is toy code. It’s inefficient, it requires that objects be default constructible, and not to mention it isn’t at all safe. It gets the point across, but it’s not really rocket science, or STL science for that matter. This code is a Fisherprice vector. It’s light-years away from being a real vector. This is your 3 year old’s vector. We want a real vector. We want a vector that looks and feels like the vector you use from your compiler writer.
Where do we even start? Well, the first thing would be to maybe look at a real vector implementation. Cooking is also an art form, and when you’re learning how to cook something new, you generally use a recipe. So, let’s start with a recipe.
I’m a Microsoft guy, through and through. So naturally, my first thought was to go look at the files in VS 2019. So I cracked open Visual Studio, opened a new C++ file, typed #include <vector>, right-clicked “Go to Document <vector>”, and voila. Sorry vim folks, I’m not sure if you can do that, BUT BASICALLY I RIGHT CLICKED AND OPENED THE VECTOR FILE. Have you ever looked at the MSVC’s implementation of anything STL? Well, be thankful when “Just my code” works when you’re debugging. Here’s a snippet. (I didn’t write this code, it’s directly from MSVC vector)
Note: If you don’t use Visual Studio to code and debug. I truly feel sorry for you.
// vector standard header
// Copyright (c) Microsoft Corporation.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// ...
template <class _Ty, class _Alloc = allocator<_Ty>>
class vector { // varying size array of values
private:
template <class>
friend class _Vb_val;
friend _Tidy_guard<vector>;
using _Alty = _Rebind_alloc_t<_Alloc, _Ty>;
using _Alty_traits = allocator_traits<_Alty>;
public:
static_assert(!_ENFORCE_MATCHING_ALLOCATORS || is_same_v<_Ty, typename _Alloc::value_type>,
_MISMATCHED_ALLOCATOR_MESSAGE("vector<T, Allocator>", "T"));
using value_type = _Ty;
using allocator_type = _Alloc;
using pointer = typename _Alty_traits::pointer;
using const_pointer = typename _Alty_traits::const_pointer;
using reference = _Ty&;
using const_reference = const _Ty&;
using size_type = typename _Alty_traits::size_type;
using difference_type = typename _Alty_traits::difference_type;
private:
using _Scary_val = _Vector_val<conditional_t<_Is_simple_alloc_v<_Alty>, _Simple_types<_Ty>,
_Vec_iter_types<_Ty, size_type, difference_type, pointer, const_pointer, _Ty&, const _Ty&>>>;
public:
using iterator = _Vector_iterator<_Scary_val>;
using const_iterator = _Vector_const_iterator<_Scary_val>;
using reverse_iterator = _STD reverse_iterator<iterator>;
using const_reverse_iterator = _STD reverse_iterator<const_iterator>;
vector() noexcept(is_nothrow_default_constructible_v<_Alty>) : _Mypair(_Zero_then_variadic_args_t()) {
_Mypair._Myval2._Alloc_proxy(_GET_PROXY_ALLOCATOR(_Alty, _Getal()));
}
// ..
Mmhmmm. Yup. Feast your eyes. If the code I wrote was Fisherprice, this is Dewalt. It’s safe, efficient, and it works. The reason that we never question much about things in the STL, is because they almost always work the way we expect them to work. The authors of these libraries deserve praise. So if you’re an STL developer, you have my sincerest thank you. The problem is, that this code is so dense, and I for one am not smart enough to understand what’s going on at a glance.
Shout out to @StephanTLavavej, and all others on the Visual C++ team for making our lives easier.
What do you think a _Scary_val is? I actually have no idea.
Okay — so that recipe might as well be in Cuneiform, or French. Neither of which I’m particularly talented at reading. We need a recipe we can understand. Thankfully, I did some digging, and I was able to find something. Located in the depths of the internet, here, I found Alexander Stepanov’s implementation of the STL. If you don’t know who Alex is, he’s the father of the STL. The man is a living legend, to him we owe a massive thanks. Anyways, his implementation of vector, is clean, simple, and readable. It’s something we can easily consume. The only problem is, that it’s from 1994. Do you know what this means? It means it was written when mullets were popular. I would know, I had one. It also means, that it was written before any of the cool modern C++ existed. It was written before C++ was even standardized!! Talk about using Grandma’s recipe. It’s fine, we’ll make due, things haven’t changed that much, have they? Until I find a better resource, this is the best I’ve got. (Edit: I actually found another good resource, a bit into my experiment, the EASTL). I’m going to use a hybrid between Stepanov’s vector, the CPP reference standard, and whatever I can figure out from MSVC. Then I’ll sprinkle a little bit of my knowledge, and bingo, we’ll have a real working vector.
Let’s start by defining what we’re working towards. First, we want a standard vector. This means we want it to fulfill the standard for what a vector is. It needs to work with standard algorithms, which we’ll eventually test. Lastly, we’re going to compare it performance wise to MSVC’s implementation.
From cppreference.com, a vector is a sequence container that encapsulates dynamic sized arrays. It’s declaration looks like this.
template <typename T, typename Allocator = std::allocator<T>>
class vector;
So, the template declaration is a bit different from the toy code we looked at earlier, and Stepanov’s vector. It has this weird thing called an Allocator. So you might be asking, “what’s an allocator, and why is it a template argument?” Let’s address the first question, an allocator encapsulates your allocation mechanism. This means, it hides away how the memory is getting allocated, behind a constant interface. To answer the second question, it’s a template argument, so that you can supply what type of allocator your vector will use. A huge part of what makes the STL so nice, is that it’s very very flexible. It works against all your custom hand rolled classes, and it allows you to control how allocations happen for standard containers. It does this through the Allocator template argument. Why would anyone use a custom allocator? Well — a few reasons come to mind. If you’ve got memory constraints. Or maybe you have a highly optimized use for your vector. You might want to use a custom allocator for these cases. Maybe you noticed that Stepanov’s vector implementation doesn’t have the allocator template either. However, if you read deeper, he uses a static member allocator that’s defined at the top section of the code.
If you recall back to the toy code, we used “new T[]” directly to allocate our array. This is problematic for two reasons. It forces the user of our toy vector, to use the runtime’s default allocation mechanism and it will call the default constructor on all of the items in the array. So we force our library user to have a default constructor on all their objects and use the default allocation heap. No bueno. The Allocator interface breaks the responsibility of allocation and construction, into two separate calls. This way we can control when the memory gets allocated for our objects, and when our objects get constructed. The member functions of an allocator are:
template <typename T>
struct allocator
{
allocator()=default;
~allocator()=default;
// return the address of an object
T* address(T&);
// allocates sizeof(T) * count
T* allocate(size_t count);
// deallocates the storage pointed to by p, must have been obtained by a call to allocate
void deallocate(T *p);
// construct - a given object in place of p (deprecated C++17, removed C++20)
template <typename ...Args>
void construct(T *p, Args &&args);
// destroy - destruct the object pointed to by p (deprecated C++17, remove C++20)
void destroy(T *p);
};
Note: I’ve chosen to use the deprecated functions construct / destroy. They’ve been replaced by allocator_traits, and honestly, I just didn’t want to go that far down the rabbit hole for this first post. So my vector takes advantage of them. For now.
So given that we can’t have a vector, without an allocator, we should probably start our journey there.
For brevity, I’m not going to write out the entire implementation, but I will write out one of the important functions, allocate. Taking a look at Stepanov’s implementation.
/*
* Copyright (c) 1994
* Hewlett-Packard Company
*/
template <class T>
inline T* allocate(ptrdiff_t size, T*) {
set_new_handler(0);
T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));
if (tmp == 0) {
cerr << "out of memory" << endl;
exit(1);
}
return tmp;
}
It’s pretty simple, we just use ::operator new, to allocate some space of the size multiplied by the size of our type. If we fail (returns 0), we write to the standard error, and exit the application. We what? We write to the standard error, and exit the application. Hmmm. I would’ve expected this to use exceptions, but my best guess is that in 1994, exceptions were not yet widely accepted. Also, at the time, if you ran out of memory, what was a guy to do? Other than to print to standard error, and crap itself. Well — in this day and age, that isn’t appropriate. We’ve got something up our sleeves known as exceptions. Exceptions are a fundamental piece of the STL, and they’re perfect for this very thing. The only problem is that, in this little experiment we’re doing, we have to implement everything that isn’t bare metal C++ (mostly). So, we’ve gotta implement standard exceptions.
Thankfully, exceptions aren’t that complicated. They’re basically a wrapper over a constant character array, or in other words, an immutable string.
class exception
{
const char * const message_;
public:
exception()
:message_(nullptr)
{
}
exception(const char* message)
:message_(reinterpret_cast<const char *>(::operator new(strnlen(message,256))))
{
if (message_ == nullptr)
exit(-1);
strncpy_s(const_cast<char *const>(message_), 256, message, 256);
}
exception(const exception& e)
:exception(e.message_)
{
}
~exception()
{
::operator delete(const_cast<void*>(reinterpret_cast<const void*>(message_)));
}
virtual const char* what()
{
return message_;
}
};
class bad_alloc : public exception
{
public:
bad_alloc()
:exception("bad_alloc")
{
}
bad_alloc(const char *message)
:exception(message)
{
}
};
So, now that we have an exception to throw, we can use it in our allocator and have the allocation look something like this.
pointer allocate(size_t count)
{
T* temp = static_cast<T*>(::operator new(count*sizeof(T)));
if (temp == nullptr)
{
throw bad_alloc();
}
return temp;
}
Once we have our allocation function, the rest of the allocator is pretty self explanatory. Mine came out looking something like this.
template <typename T>
struct allocator
{
using pointer = T*;
using const_pointer = const T*;
using reference = T&;
using const_reference = const T&;
using size_type = size_t;
allocator() = default;
~allocator() = default;
// address
pointer address(reference x) const
{
return &x;
}
const_pointer address(const_reference x) const
{
return &x;
}
pointer allocate(size_t count)
{
T* temp = static_cast<T*>(::operator new(count*sizeof(T)));
if (temp == nullptr)
{
throw bad_alloc();
}
return temp;
}
void deallocate(pointer p, size_type n)
{
::operator delete(p, n * sizeof(T));
}
size_type max_size() const
{
return max(size_type(1), size_type(UINT_MAX / sizeof(T)));
}
template <typename ...Args>
void construct(reference dest, Args&&... args)
{
::new (static_cast<void*>(&dest)) T(htk::forward<Args>(args)...);
}
void destroy(pointer p)
{
p->~T();
}
};
Basically, the calls are thin shims into the default C++ mechanism for allocation (new) and deallocation (delete). Then the construction uses placement new to construct the object in a given destination, and the destroy call explicitly calls the destructor.
If you’re still following along, before we even started writing our vector, we needed to create some foundations. I searched and searched, but I couldn’t find instructions on how to implement an STL. What I mean by that, is where do you even start? Obviously classes in the STL depend on other classes in the STL, but where’s the leaves? I wish I could say I found that. So my best bet it to just pick a common class, and implement. So thus far, we have the basic exception, we have a bad_alloc exception, and we have the default allocator. All so we can start on our vector.
In order to keep this post from becoming my first novel, we’re just going to focus on implementing one method on the vector. We’ll leave the default construction for now, and we’ll look at the emplace_back function. This is a function that allows for argument forwarding, into direct construction at the back of the vector. It’s a really nice starting point. It seems rather straightforward. I’ll soon find out, it isn’t.
So the signature of emplace_back is something like this. It takes a variadic set of arguments, and returns the object it created. The decltype(auto) specifies that the compiler is to figure out the return type based on what we’ve returned.
template <typename ...Args>
decltype(auto) emplace_back(Args&&...args)
{
ensure_space_at_least(1);
allocator_.construct(*(data_.last++), htk::forward<Args>(args)...);
return back();
}
This code though, is pretty straightforward. We first ensure we have enough space for 1 element. Then, we use our allocator to construct the element in the last position, and increment the pointer.
You might be asking about this strange htk::forward<Args>(args)…? Well, I debated going into it, and going down that rabbit hole. But decided against it. What std::forward or htk::forward does, is passes arguments exactly as they were passed into the function. This means that if we’re passing r-value references into emplace_back, we’re forwarding those as-is to the allocator construct call.
What does ensure_space_at_least(1) do? In our toy vector had some code to grow and copy our existing objects. That’s effectively what this is doing. We’re going to ensure we have space for at least one element. If we do we can just create the new item, right at the end of that memory we allocated earlier. This illustrates separating allocation from construction. We allocate space which hasn’t been initialized, then when someone pushes into our vector, we just initialize that memory!
void ensure_space_at_least(size_t count)
{
if (initialize(count))
return;
// we need to see if we have enough space.
if (freespace() < count)
{
const auto cap = calculate_growth(count);
grow(cap);
}
// we good.
}
So the first line, is just to initialize the vector. Since with this vector, we’re starting out with no memory allocation. The first call will just allocate some memory, and return. If we have enough memory allocated, we don’t do anything. Where we’re really interested, is when we don’t have enough memory available. Our growth algorithm, is just going to keep doubling the capacity until we can fit the count. So that’s what calculate_growth(count) will do. Just return us the next capacity that’ll fit our count. Then we need to grow our memory.
In order to grow the memory, we need to do a couple things. First, we need to allocate a contiguous block for our new capacity. Then we need to transfer all existing items into the new memory block. Then we need to free our old memory.
void grow(size_type cap)
{
pointer new_vec = allocator_.allocate(cap);
move_items(data_.first, data_.last, new_vec);
auto old = data_;
auto curs = size();
data_ = data{ new_vec,dest, new_vec + cap };
// destroy the old stuff
destroy(old.first, old.last);
allocator_.deallocate(old.first, old.capacity());
}
void move_items(pointer first, pointer last, pointer dest)
{
while (first != last)
allocator_.construct(*(dest++), *(first++));
}
First thing we do, is to allocate the size of our capacity. Then we call move_items, which takes the first, and last element, and a pointer to the new destination. Then in move_items, we just iterate from first to last, and construct the old item into the destination, and increment it. Then, we’ll assign our new vector pointer to our internal data pointer, then destroy all the old items, and deallocate the memory. With that, we have a pretty simple growth algorithm that copies from our old vector into the new space, and frees up the old items.
My initial thought was to type “we’ve got a problem here“, like we only have one. There’s a boatload more than one problem in this code. This folks, is why being a library developer is hard. At this point, we’re still only writing the basic algorithm. We haven’t taken into account safety, or optimization. Just thank your god, that you don’t have be a library developer. (unless you want to be, you masochist.)
The first problem we’re going to address, is the fact that we only support copying items. This means, that every time our vector expands, we’re going to copy all the items over. For large types, this can be costly, and as of C++11 we don’t need to copy the items. We want to take advantage of move semantics. Move semantics are a pivotal part of smart pointers, and optimizations for things like the vector, because they effectively allow you to move the guts from one object to another. This is primarily useful when you have a temporary, or an item you know will be going out of scope, and do not want to copy. It’s done by defining a “move constructor” (see Rule of 5).
If you think about an object like a vector, that has an internal pointer to some array of objects. In C++98, when we pass that object by value (a copy), to be correct, we would need to allocate enough space, and copy all the items over into the new vector. This means then, we would have two copies of our vector. If you were passing this into a function, that vector you copied would then be destroyed. This is very wasteful. This also would happen when you would return by value. It’s obvious today, that we need a way to say “I’m only temporary”, and when it’s a temporary, we can commandeer that temporaries pointer as our own, set his pointer to nullptr, and let him go out of scope. This way we’ve moved the object. Before we had move semantics we had a lot different techniques, like reference out parameters, and copy-on-modify semantics. With move, those workarounds aren’t necessary.
Obviously, we want to take advantage of move semantics when we copy our vector. That way, if the class we’re holding is optimized for move, we will use that and not copy it. As well, we can hold on to classes that have only move semantics, and not copy. Things like resource holders. So how do we do that?
In order to take advantage of move semantics, we need to use std::move (or in our case htk::move), which will convert an object reference into an r-value reference.
void grow(size_type cap)
{
pointer new_vec = allocator_.allocate(cap);
if(has_move_semantics())
{
move_items(data_.first, data_.last, new_vec);
}
else
{
copy_item(data_.first, data_.last, new_vec);
}
auto old = data_;
auto curs = size();
data_ = data{ new_vec,dest, new_vec + cap };
// destroy the old stuff
destroy(old.first, old.last);
allocator_.deallocate(old.first, old.capacity());
}
void move_items(pointer first, pointer last, pointer dest)
{
while (first != last)
allocator_.construct(*(dest++), htk::move(*(first++)));
}
void copy_items(pointer first, pointer last, pointer dest)
{
while (first != last)
allocator_.construct(*(dest++), *(first++));
}
It’s that simple! Pfft. Library implementation is easy…. Just kidding. This probably is not that easy. If this way did work, we would be doing the check at runtime! Because whether or not a type can be moved, is based on the class definition (does the class implement a move constructor?). We can do this check at compile time. This means, that when the vector code is generated for contained type i.e. <T>, we know whether we want to move or copy it.
If you’ve ever programmed in a language that doesn’t have function overloading. You’ll know how important it is. Because it lets you specify a function with the same name, but different arguments, and then the compiler can choose the best function to call, based on the type you’ve provided it. This is great, because then we can write one algorithm, and based on the type the compiler can select the best function to call. When we’re talking template code, the compiler will only call the required function. This may seem like a digression, but it’s not, and let me show you why.
template <typename T>
class adder
{
T value_;
public:
adder(const T &value)
:value_(value)
{
}
void add(const T& value)
{
add_internal(value);
}
const T& get() const
{
return value_;
}
private:
void add_internal(const std::string &s)
{
value_ += " + " + s;
}
void add_internal(int val)
{
value_ += val;
}
};
This code isn’t really useful at all, but it’s just to illustrate the point, that based on the type of our template, we can call different functions. I made a compiler explorer here. You can see in the compiler explorer, that when we use a std::string, we call the appropriate add_internal. Can you see where this is going? We want to call different functions based on traits of the class we’re containing. So back to our grow code.
void grow(size_type cap)
{
pointer new_vec = allocator_.allocate(cap);
move_items(data_.first, data_.last, new_vec, /* something here */);
auto old = data_;
auto curs = size();
data_ = data{ new_vec,dest, new_vec + cap };
// destroy the old stuff
destroy(old.first, old.last);
allocator_.deallocate(old.first, old.capacity());
}
void move_items(pointer first, pointer last, pointer dest, /* argument when movable */)
{
while (first != last)
allocator_.construct(*(dest++), htk::move(*(first++)));
}
void move_items(pointer first, pointer last, pointer dest, /* argument when copyable */)
{
while (first != last)
allocator_.construct(*(dest++), *(first++));
}
We want to take advantage of overloading, and the template system, to call the right call based on our type. This is a technique called “tag_dispatching“, we want to get the compiler to pick the right function, based on the template type we’re using. Or, at least that’s what we’re trying to do. 🙂
I’ve been eluding to “traits about a type” without outright calling it what it is. To a library author, I can only assume that type_traits are a bit like paint, to a painter, or gasoline, to an internal combustion engine. (or arsonist?) Type traits (type_traits) are part of the STL, and they allow you to get compile time answers to questions about the types that the template code is working on. In our case, we want to ask the question “is this class moveable”? and based on the answer, we’ll have the compiler call the right move_items call.
In the STL, these “questions” are generally answered by small helper structs called type_traits. In general, they take a type argument (or a few), and give back a compile time constant boolean value. You can ask questions like:
std::is_reference<T>;
std::is_pointer<T>;
std::is_member_pointer<T>;
Honestly, there’s a lot, if you can think to ask it about a class, it’s probably a type_trait. Type traits are a build up of little tiny structs, that enable huge possibilities. The root of most type traits, is this thing called a bool_constant. It’st just a small struct that has a boolean as a compile time constant. With this, we can define two types (obvs) std::true_type && std::false_type. These classes are aliases of bool_constant<true> and bool_constant<false> respectively. So let’s go back to the code.
void grow(size_type cap)
{
pointer new_vec = allocator_.allocate(cap);
move_items(data_.first, data_.last, new_vec, /* something here */);
auto old = data_;
auto curs = size();
data_ = data{ new_vec,dest, new_vec + cap };
// destroy the old stuff
destroy(old.first, old.last);
allocator_.deallocate(old.first, old.capacity());
}
void move_items(pointer first, pointer last, pointer dest, htk::true_type /* is moveable */)
{
while (first != last)
allocator_.construct(*(dest++), htk::move(*(first++)));
}
void move_items(pointer first, pointer last, pointer dest, htk::false_type /* is not moveable */)
{
while (first != last)
allocator_.construct(*(dest++), *(first++));
}
You can start to see how we can get the compiler to choose which function to call. If we want to move the object, we use htk::true_type as the tag that we want to move, and htk::false_type when we want to copy. The last piece is asking the question! Thankfully, in the STL’s bag of tricks there’s a helpful trait called std::is_move_constructible<T>.
Since this blog is about demystification, this is the last piece (for now) of wool we need to lift off our eyes. How do we implement is_move_constructible<T>? I’ll be totally honest with you. I had 0 idea. My first thought was I needed to some how have the compiler test call the move constructor with the arguments, and see if that could compile, if not fallback to false_type, this is something called SFINAE. (I’m definitely not an expert, and I have little confidence I could explain it without a significant amount of research.) So after some thinking, I decided I need to phone a friend. So I pulled up VS again and dove into type_traits.
// STRUCT TEMPLATE is_move_constructible
template <class _Ty>
struct is_move_constructible : bool_constant<__is_constructible(_Ty, _Ty)> {
// determine whether _Ty can be direct-initialized from an rvalue _Ty
};
That’s it. No crazy template magic. Just 3 little lines. Wemp. Womp.
But wait! What the heck is that __is_constructible(_Tv, _Ty)? Yeah. That had me too. I actually spent longer than I’d like to admit, trying to figure that *expletive deleted* out. It wasn’t until I found the EASTL, that it dawned on me. Well, there’s a line that gives it away.
#if EASTL_COMPILER_INTRINSIC_TYPE_TRAITS_AVAILABLE && (defined(_MSC_VER) || (defined(EA_COMPILER_CLANG) && EA_COMPILER_HAS_FEATURE(is_constructible)))I’ll let you see their code when the compiler doesn’t do it, for yourself here. It’s really quite fascinating and very impressive. Thank goodness for Microsoft and the compiler writers, because they made that job easy. We basically have a compiler intrinsic function, that will answer that question for us! Let’s go back to our code, so we can finish this off.
void grow(size_type cap)
{
pointer new_vec = allocator_.allocate(cap);
move_items(data_.first, data_.last, new_vec, htk::is_move_constructible<T>::value);
auto old = data_;
auto curs = size();
data_ = data{ new_vec,dest, new_vec + cap };
// destroy the old stuff
destroy(old.first, old.last);
allocator_.deallocate(old.first, old.capacity());
}
void move_items(pointer first, pointer last, pointer dest, htk::true_type /* is moveable */)
{
while (first != last)
allocator_.construct(*(dest++), htk::move(*(first++)));
}
void move_items(pointer first, pointer last, pointer dest, htk::false_type /* is not moveable */)
{
while (first != last)
allocator_.construct(*(dest++), *(first++));
}
With that we’ve got our vector growing, and choosing the correct function for copying the old items, based on the type specified to the vector. Cool!
It’s been a journey, we waded (deeper than we may have wanted) into the world of the STL. We uncovered things like allocators, exceptions, and type_traits. We also looked at how we can leverage tag dispatching to ensure we’re doing the right thing based on the type at hand. We saw that library development past a toy, is hard. We didn’t even get into exception safety. Which admittedly complicates things passed something that’s understandable without writing a novel. I can only hope to be able to dig into that one day, until then we can let it remain magic. For now, we have the start of a vector, and some other useful tools in our just heavier than a toy STL.
I hope you enjoyed the opener in this vector series. Next up, we’ll be making our vector work with the STL algorithms. Then lastly, we’ll pit our vector against Microsoft’s, in a battle of the…. Well battle of the vectors. To see just how poorly this vector performs against the professionals.
Until then, stay healthy, and happy coding!
“Life is really simple, but we insist on making it complicated.”
― Confucius
References
https://en.cppreference.com/w/cpp/container/vector
http://stepanovpapers.com/butler.hpl.hp/stl/stl/VECTOR.H
https://github.com/microsoft/STL/blob/master/stl/inc/vector
https://github.com/electronicarts/EASTL
https://foonathan.net/2015/11/overload-resolution-3/
Unparalleled Adventure 