C++ layout of an object containing containers

Question

As someone with a lot of assembler language experience and old habits to lose, I recently did a project in C++ using a lot of the features that c++03 and c++11 have to offer (mostly the container classes, including some from Boost). It was surprisingly easy - and I tried wherever I could to favor simplicity over premature optimization. As we move into code review and performance testing I'm sure some of the old hands will have aneurisms at not seeing exactly how every byte is manipulated, so I want to have some advance ammunition.

I defined a class whose instance members contain several vectors and maps. Not "pointers to" vectors and maps. And I realized that I haven't got the slightest idea how much contiguous space my objects take up, or what the performance implications might be for frequently clearing and re-populating these containers.

What does such an object look like, once instantiated?

Answer 1

Formally, there aren't any constraints on the implementation other than those specified in the standard, with regards to interface and complexity. Practically, most, if not all implementations derive from the same code base, and are fairly similar.

The basic implementation of vector is three pointers. The actual memory for the objects in the vector is dynamically allocated. Depending on how the vector was "grown", the dynamic area may contain extra memory; the three pointers point to the start of the memory, the byte after the last byte currently used, and the byte after the last byte allocated. Perhaps the most significant aspect of the implementation is that it separates allocation and initialization: the vector will, in many cases, allocate more memory than is needed, without constructing objects in it, and will only construct the objects when needed. In addition, when you remove objects, or clear the vector, it will not free the memory; it will only destruct the objects, and will change the pointer to the end of the used memory to reflect this. Later, when you insert objects, no allocation will be needed.

When you add objects beyond the amount of allocated space, vector will allocate a new, larger area; copy the objects into it, then destruct the objects in the old space, and delete it. Because of the complexity constrains, vector must grow the area exponentially, by multiplying the size by some fixed constant (1.5 and 2 are the most common factors), rather than by incrementing it by some fixed amount. The result is that if you grow the vector from empty using push_back, there will not be too many reallocations and copies; another result is that if you grow the vector from empty, it can end up using almost twice as much memory as necessary. These issues can be avoided if you preallocate using std::vector<>::reserve().

As for map, the complexity constraints and the fact that it must be ordered mean that some sort of balanced tree must be used. In all of the implementations I know, this is a classical red-black tree: each entry is allocated separately, in a node which contains two or three pointers, plus maybe a boolean, in addition to the data.

I might add that the above applies to the optimized versions of the containers. The usual implementations, when not optimized, will add additional pointers to link all iterators to the container, so that they can be marked when the container does something which would invalidate them, and so that they can do bounds checking.

Finally: these classes are templates, so in practice, you have access to the sources, and can look at them. (Issues like exception safety sometimes make the implementations less straight forward than we might like, but the implementations with g++ or VC++ aren't really that hard to understand.)

Answer 2

A map is a binary tree (of some variety, I believe it's customarily a Red-Black tree), so the map itself probably only contains a pointer and some housekeeping data (such as the number of elements).

As with any other binary tree, each node will then contain two or three pointers (two for "left & right" nodes, and perhaps one to the previous node above to avoid having to traverse the whole tree to find where the previous node(s) are).

In general, vector shouldn't be noticeably slower than a regular array, and certainly no worse than your own implementation of a variable size array using pointers.

Answer 3

A vector is a wrapper for an array. The vector class contains a pointer to a contiguous block of memory and knows its size somehow. When you clear a vector, it usually retains its old buffer (implementation-dependent) so that the next time you reuse it, there are less allocations. If you resize a vector above its current buffer size, it will have to allocate a new one. Reusing and clearing the same vectors to store objects is efficient. (std::string is similar). If you want to find out exactly how much a vector has allocated in its buffer, call the capacity function and multiply this by the size of the element type. You can call the reserve function to manually increase the buffer size, in expectation of the vector taking more elements shortly.

Maps are more complicated so I don't know. But if you need an associative container, you would have to use something complicated in C too, right?

Answer 4

Just wanted to add to the answers of others few things that I think are important.

Firstly, the default (in implementations I've seen) sizeof(std::vector<T>) is constant and made up of three pointers. Below is excerpt from GCC 4.7.2 STL header, the relevant parts:

template<typename _Tp, typename _Alloc>
struct _Vector_base
{
 ...
 struct _Vector_impl : public _Tp_alloc_type
 {
  pointer _M_start;
  pointer _M_finish;
  pointer _M_end_of_storage;
  ...
 };
 ...
 _Vector_impl _M_impl;
 ...
};

template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class vector : protected _Vector_base<_Tp, _Alloc>
{
 ...
};

That's where the three pointers come from. Their names are self-explanatory, I think. But there is also a base class - the allocator. Which takes me to my second point.

Secondly, std::vector< T, Allocator = std::allocator<T>> takes second template parameter that is a class that handles memory operations. It's through functions of this class vector does memory management. There is a default STL allocator std::allocator<T>>. It has no data-members, only functions such as allocate, destroy etc. It bases its memory handling around new/delete. But you can write your own allocator and supply it to the std::vector as second template parameter. It has to conform to certain rules, such as functions it provides etc, but how the memory management is done internally - it's up to you, as long as it does not violate logic of std::vector relies on. It might introduce some data-members that will add to the sizeof(std::vector) through the inheritance above. It also gives you the "control over each bit".

Answer 5

Basically, a vector is just a pointer to an array, along with its capacity (total allocated memory) and size (actually used elements):

struct vector {
    Item* elements;
    size_t capacity;
    size_t size;
};

Of course thanks to encapsulation all of this is well hidden and the users never get to handle the gory details (reallocation, calling constructors/destructors when needed, etc) directly.

As to your performance questions regarding clearing, it depends how you clear the vector:

• Swapping it with a temporary empty vector (the usual idiom) will delete the old array: std::vector<int>().swap(myVector);
• Using clear() or resize(0) will erase all the items and keep the allocated memory and capacity unchanged.

If you are concerned about efficiency, IMHO the main point to consider is to call reserve() in advance (if you can) in order to pre-allocate the array and avoid useless reallocations and copies (or moves with C++11). When adding a lot of items to a vector, this can make a big difference (as we all know, dynamic allocation is very costly so reducing it can give a big performance boost).

There is a lot more to say about this, but I believe I covered the essential details. Don't hesitate to ask if you need more information on a particular point.

---

Concerning maps, they are usually implemented using red-black trees. But the standard doesn't mandate this, it only gives functional and complexity requirements so any other data structure that fits the bill is good to go. I have to admit, I don't know how RB-trees are implemented but I guess that, again, a map contains at least a pointer and a size.

And of course, each and every container type is different (eg. unordered maps are usually hash tables).