Hello and welcome to C++ Weekly. I'm your host, Jason Turner.
In this episode I want to talk about vector. If you've been around C++
at all you know that people think this thing is really weird, so let's discuss why it's weird.
Be sure to check out the video description for links to my ebooks, printed books, Patreon
and Github's sponsor page, as well as news about upcoming events that you might be interested in.
Okay, so why it's weird? Well, let's look at the standard description of vector for a moment.
Now the standard explicitly gives a specialization for vector - it lists it in its own
category, it's "Class vector", and it says, "To optimize space allocation,
a specialization of vector for 'bool' elements is provided," and that's all that it really says.
It says down here "there is no requirement that the data be stored as a contiguous
allocation of bool values. A space-optimized representation of bits is recommended instead,"
and it also has a few things with, like, flipping of bits, whatever. What does that mean? Why a
space optimized version? Now a 'bool' can be represented as a single bit. A single bit is,
you know, just zero or one. The 'bool' type however takes up one byte generally speaking.
If I just do this "returnsize(bool)," I'm going to get 1 returned from main,
so if I've got an array of these 'bools',
I'm going to get 15 bytes returned. Now that's 15 boolean values takes 15 bytes. Those should take 2
bytes that can be stored as 15 bits, and generally speaking, we're going to say a byte is 8 bits that
should be stored in two bytes. So vector tries to be the space optimized thing.
We're going to try to kind of peek behind the curtain here
and see what vector is doing for us, so I'm going to look at 'capacity' and 'size'.
So I have pushed back a single value and I get that the size is 1, but the capacity is
64. Well that kind of makes sense if each block of data that it's going to hold is a 64-bit integer
that it can pack these bits into; and so that means I'm going to have to pack in a whole lot
of bits if I want to actually see the capacity of this thing grow and change in any meaningful way.
Now what we'll see instead if I were to take this from vector to say, vector (and this
code should compile) is we see this geometric growth. So I've got 3 elements in here and a
capacity of 4. If I comment out these, then I should see a size of 1 and a capacity of 1.
It's not going to allocate a bunch more memory than it needs to. So when we go to vector
we are observing (and I just noticed that I was pushing integers back into a vector - I
really should not have been doing), we are observing the fact that it is packing these things
into a 64-bit integer. Let's do something slightly more reasonable. Interestingly, we did not get any
warnings from the compiler about that whatsoever, so that is incredibly helpful. So say I want to
get a pointer to the front of this thing - now I'm going to print out the first value also.
Okay so the size is 3, capacity is 64, the value of the first thing is 1. Now if this were
a vector of integers it would be perfectly reasonable to say, "I want a reference
to the front thing," and we're going to get this "cannot bind non-const lvalue reference" nonsense.
Let's go ahead and take this back to integer again,
and if I reassign the first thing to equal to 0, then we should see 1, 1,
0 printed now. Sorry - we have three elements in here, so 3,
4, 0. Okay so 3, 4, 0 have been printed, and I can assign this to any value that I want to,
and we can observe this last thing change. So if I take this back to a 'bool',
there's no way in the C++ standard to get a reference to a single bit.
That just simply doesn't exist. It would... and if you think about it it doesn't make sense.
All right. How would I even represent this? How would I say, "Give me a reference to...?"
I don't even know, like, how would I represent this? I could
do a bitmask. That doesn't make sense - I can only reason about
values and bytes. There's just simply nothing for me to type here. Now I could create a bit field.
Now if you're not used to the syntax it's going to look very strange to you,
but what I have said is that there are three objects in this struct called b1, b2, b3. They are
all booleans, and they are represented by one bit. In this case I have it represented by three bits,
so this is a bit-field. So you might think I could initialize this object
and then say, "Okay, I will use this to get a reference to one of the bits
like that," and we get a different error here - "cannot bind bit-field to a bool
reference." So there's just no way to use a single bit in C++. So what the standard
implementers have done for us is they've created this proxy object, so now things start to behave
quite a bit differently than we would expect. I have this thing which looks like it's a copy - in
fact it is a copy, it should be a copy, and I can assign to it. If I assign it to it this value 0,
we expect 0 to get printed here in a moment, and it did right here in the bottom right because
this is a proxy object that internally contains a function that knows how to set the appropriate bit
in this packed set of bits that we want. So that's weird, and then where it starts to get annoying -
If I want to write code like this I can't because this thing that's returned - these begin and end
iterators, these proxy objects, are temporary objects. I cannot bind a non-const lvalue
reference to a temporary object. So I can do this, but then I can't assign through it because it is a
const object. So now we just moved the error down here to line 14. And... I can do this,
but this starts to look really weird. You're like, "Well I'm assigning to this thing. Is that
actually doing anything?" and it is. Line 14 is doing something because it's assigning through the
proxy object itself. So what you end up finding is people who will write something like this, which
is a forwarding reference, and it says, "You know, you can bind to anything, so I'll just do that."
Now this use case is extremely rare. It's very few different types of objects that
return back a proxy object to you, so for that reason I recommend that you only use
this forwarding reference syntax for your arranged for loops in the cases where you
need it. I would say in a normal situation you should do something like this if you intend to
mutate the value - use a non-const reference and then you can mutate the value in an expected way,
and you can fall back to using rvalue references
in the case where you've got a proxy object involved; but that's, like, why vector is
weird. We can dig into this a little bit more - so I've jumped in here in GCC's version of 'bvector',
which is their vector, we can see in here this 'bit_reference' type; and when you do an
assignment of it it actually has to check which byte you are currently trying to access (or which
value inside this packed bit structure) and then it does some of these bit set versus bit clear
against and the value that it needs to mask on, and there you go. It's got a mask that's stored in
here so it knows which bit to access, and it knows how to set it or clear it appropriately. So that's
what makes vector weird. It's not just a collection of data like every other vector type,
it is a vector of packed bits, or at least it's encouraged to be. It's still not required
to be by the standards rules, so that's just an interesting note. Also interesting to note
that this specialization is in fact enabled for constexpr use in C++20 if you have a need for
such a thing, although I think most people agree that it might not be the best tool in your toolbox
for working with bits if that's what you need. So thanks for watching this episode of C++ Weekly.
I hope you found it at least slightly enlightening and be sure to subscribe.