How to explain the value of sizeof(std::vector<int>)?

Question

In order to understand the memory consumption of std::vector<int> I wrote:

std::cout << sizeof(std::vector<int>) << std::endl;

This yields 32. I tried to understand where this value comes from. Some look in the source code revieled that std::vector stores pointers _MyFirst, _MyLastand _MyEnd which explaines 24 bytes of memory consumption (on my 64 bit system).

What about the last 8 byte? As I understand, the stored allocator does not use any memory. Also this might be implementation defined (is it?), so maybe this helps: I am working with MSVC 2017.5. I do not guarantee to have found all the members by looking into the code; the code looks very obfuscated to me.

Everything seems to be nicely aligned, but may the answer be the following?: Why isn't sizeof for a struct equal to the sum of sizeof of each member?. But I tested it with a simple struct Test { int *a, *b, *c; }; which satisfiessizeof(Test) == 24.

---

Some background

In my program, I will have a lot of vectors and it seems that most of them will be empty. This means that the ciritical memory consumption comes from there empty-state, i.e. the heap allocated memory is not so very important.

A simple "just for this usecase"-vector is implemented pretty quickly, so I wondered if I am missing anything and I will need 32 bytes of memory anyway, even with my own implementation (note: I will most probably not implement my own, this is just curiosity).

---

Update

I tested it again with the following struct:

struct Test
{
    int *a, *b, *c;
    std::allocator<int> alloc;
};

which now gave sizeof(Test) == 32. It seems that even though std::allocator has no memory consuming members (I think), its presence raises Test's size to 32 byte.

I recognized that sizeof(std::allocator<int>) yields 1, but I thought this is how a compiler deals with empty structs and that this is optimized away when it is used as a member. But this seems to be a problem with my compiler.

Printable

Why do you want an explanation? Did you dive into the source code of your <vector> headers (and the internal headers included from it)? Do you really care? Are you willing to spend weeks of work to understand all the gory details? On my Linux/GCC system, #include <vector> expands to more than ten thousand lines of C++, and I did not took time to read all of them. BTW, most of the memory used by your vector is some data in the heap... – Peggie

@BasileStarynkevitch Partly curiosity. Party because I have to use std::vector in a memory critical environment and I wondered "if I would implement it myself, would I be able to do any better?". I will most probably not implement anything myself, so mostly curiosity. I know about that most memory is on the heap. The problem is that it seems that I have a lot vectors, and most of them will be empty. So the empty-memory consumption is the important number here. – Printable

Your question doesn't seem to be about vector at all. It can pretty much be summed in, "on a 64 bit system, why does struct {void *_1; void *_2; void *_3; }; take up 32 bytes instead of 24?". If these are indeed the only member in the structure as you say. – Nadean

@StoryTeller Is it so? So it is all about alignment? – Printable

@M.Winter - According to you the implementation you looked at has only 3 members and no bases. So yeah, that would sum up the question. – Nadean

You might re-implement your vector, but consider that it will take you a lot of time (weeks or months of work), which means money, and that it might be less optimized than standard containers. In practice, <vector> is coded by the same guys coding your compiler.... and they might improve that compiler to optimize it better. – Peggie

@StoryTeller The implementation is very confusing (almost obfuscated) for me. I do not guarantee that I found every member. I do not know what is standardized about the members and what is up to implementation. – Printable

@M.Winter - No data member is standardized. So you can rest assured that is implementation specific – Nadean

@BasileStarynkevitch As I said, it is more about curiosity and an answer to this question will not motivate me to implement my own. But it never was a bad thing to understand the used language better. – Printable

@BasileStarynkevitch: vector can actually be implemented in an hour or so. It won't have all the stl functionality, like different kinds of iterators, tons of assignment variants and etc., but it will have what is necessary, and have the needed memory layout. – Abroad

@valdo: I am not that sure (remember that on my system #include <vector> expands to more than 10KLOC). In particular, because most compilers have some optimization passes related to their particular implementation of <vector>. BTW, bravo if you can code the 10KLOC lines of <vector> in one hour. Please teach me your tricks. I need several months of work to code good, debugged, documented, tested, optimized 10KLOC – Peggie

BTW, on my Linux/GCC/x86-64/Debian/Sid sizeof(std::vector<int>) is 24. So you might consider changing your compiler! – Peggie

@BasileStarynkevitch Same with clang/libc++, same with MSVC, both tested online. – Flagwaving

@BasileStarynkevitch: as I said, I didn't mean implementation of all the vector functionality that exists in STL. But specific subset of it can be implemented easily, and it will be suited for the needs. In particular in a described situation, where memory size of an empty vector is important - this is the way to go. – Abroad

@M.Winter: yes, if you're optimizing for sizeof(vector), and for the empty case, you can do better. Much better. The idea would be that your custom vector will only contain a pointer. If the vector is empty, then it will be nullptr. If not, then this pointer will point to a memory, for which size/capacity/vector_contents stored. – Arbiter

Answer 1

The compiler cannot optimise away an empty member. It is explicitly forbidden by the standard.

Complete objects and member subobjects of an empty class type shall have nonzero size

An empty base class subobject, on the other hand, may have zero size. This is exactly how GCC/libstdc++ copes with the problem: it makes the vector implementation inherit the allocator.

Norbertonorbie

Answer 2

There doesn't to be something standarized about the data members of std::vector, thus you can assume it's implementation defined.

You mention the three pointers, thus you can check the size of a class (or a struct) with three pointers as its data members.

I tried running this:

std::cout << sizeof(classWith3PtrsOnly) << " " << sizeof(std::vector<int>) << std::endl;

on Wandbox, and got:

24 24

which pretty much implies that the extra 8 bytes come from "padding added to satisfy alignment constraints".

Necktie

Thank you. So it seems to be an artifact of my compiler, implementation, operating system, ... !?! But it seems to be possible to do it with 24 bytes. – Printable

I would try another compiler @M.Winter. if I was curious enough! ;) – Necktie

Answer 3

If you ran the above test with Windows at DEBUG level, then be aware that "vector" implementation inherits from "_Vector_val" which has an additional pointer member at its _Container_base class (in addition to Myfirst, Mylast, Myend):

_Container_proxy* _Myproxy

It increases the vector class size from 24 to 32 bytes in DEBUG build only (where _ITERATOR_DEBUG_LEVEL == 2)

Ikeikebana

Answer 4

I've occurred the same question recently. Though I still not figure out how std::vector does this optimization, I found out a way get through by C++20.

C++ attribute: no_unique_address (since C++20)

struct Empty {};
struct NonEmpty {
    int* p;
};

template<typename MayEmpty>
struct Test {
    int* a;
    [[no_unique_address]] MayEmpty mayEmpty;
};

static_assert(sizeof(Empty) == 1);
static_assert(sizeof(NonEmpty) == 8);

static_assert(sizeof(Test<Empty>) == 8);
static_assert(sizeof(Test<NonEmpty>) == 16);

Erdda