How does vector use default allocator?

Question

When I have studied the STL i have been through the Allocator, I have found a lot of stuff on internet and more or less i have understood what they do. I have seen a Custom Allocator to see how they are implemented, but my question is how they are used by containers, let's say into the Vector ?

They always said vector is using DEFAULT Allocator. For example the empty vector constructor is :

   explicit vector (const allocator& alloc = allocator());

But how vector uses allocator ?

When and where, vector, behind the scene, is using Allocator::allocate() and Allocator::construct() ?

Knowing that, why one needs a custom allocator, what does it change ?

Answer 1

As @BenjaminLindley mentioned, there are many places that allocators may be used inside containers. One example is push_back, which uses allocator traits to construct a copy of its argument inside the container.

The standard (23.2.3) describes push_back as:

a.push_back(t)

Appends a copy of t. Requires: T shall be CopyInsertable into X.

Later, the term CopyInsertable is defined as:

T is CopyInsertable into X means that, in addition to T being MoveInsertable into X, the following expression is well-formed:

allocator_traits<A>::construct(a, p, t)

...which can be turned into:

a.construct(p, t)

...which effectively uses the allocator a to construct a copy of t at location p.

Answer 2

Different compilers use different implementations of the STL, and it is up to these implementations to determine how they use the Allocators. This can lead to some unfortunate results.

For example, I work primarily with embedded systems based on the ARM architecture, and at one point, I tried to implement my own Allocator based on fixed-size memory blocks for use with list, map, and set (I wasn't expecting it to work for vector, since a large-enough vector would exceed the size of the blocks). In the process, I discovered that the ARM compiler v3.1 uses a version of the RogueWave implementation of the STL in which some containers made certain assumptions about the behavior of Allocators. In the case of map and set, for instance:

• It never called Allocator::max_size() - it assumed that it returned something big enough that it didn't have to worry about it.
• It assumed that allocate() was slow, and tried to optimize it by allocating several objects at once (vector is designed to do this, but I wasn't expecting the same behavior to apply to containers like map and set that don't use contiguous memory). Basically, instead of calling allocate(sizeof(T)), it called allocate(sizeof(T) * 20) to get a pool of memory that it could then re-allocate internally as new objects were created.

These assumptions pretty much torpedoed my attempts to use the STL in that project - I eventually wound up using boost::intrusive containers instead.