5

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 ?

genpfault
  • 51,148
  • 11
  • 85
  • 139
MaxMarcucci
  • 175
  • 9
  • Take a look at [this](http://en.cppreference.com/w/cpp/memory/allocator) it might help – aaronman Sep 19 '13 at 16:26
  • 1
    Related : [this](http://stackoverflow.com/q/17848186/1870232) & [this](http://stackoverflow.com/q/826569/1870232) – P0W Sep 19 '13 at 16:27
  • thank you aaroman, I have already checked cppreference, if you look at the example in the main. it allocates and deallocate memory, my question is when and where vector or others container do that. – MaxMarcucci Sep 19 '13 at 16:37
  • 3
    @MaxMarcucci: Any function that has the potential to increase the capacity (`reserve`, `insert`, `resize`, `push_back`, etc...) will either use the allocator, or call another function which uses the allocator. It's up to the implementation exactly how they structure the code that does this. – Benjamin Lindley Sep 19 '13 at 16:41
  • 1
    The STL is implemented as inline code in header files, so you have it source code. You can look at the source code for `std::vector` and see for yourself how it uses the allocator. – Remy Lebeau Sep 19 '13 at 17:40

3 Answers3

2

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.

Nate Kohl
  • 35,264
  • 10
  • 43
  • 55
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.

Ben S.
  • 1,133
  • 7
  • 7
0

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

  • A custom allocator may optimize allocations of small objects
  • optimize allocations of objects having a common size
  • squeeze the last bit out of memory
  • ...

The default one has one strategy, only (likely).