What does it mean for an allocator to be stateless?

Question

What does it mean for an allocator to be stateless? I realize that std::allocator is a wrapper around malloc, and has no state of its own. At the same time, malloc does its own bookkeeping, so one could say that all std::allocator instances make use of a single state.

How would I go about implementing a pool allocator without state? If not the allocator, what would keep the current state of memory?

Could someone formally define what state means in this context?

Answer 1

State means that the instances of class have mutable information in them. Stateless means that they do not have it. Stateless classes do not have non-static data members.

You can make pool allocator to be stateless by using some mutual external state (a pool) that is same for all pool allocators of that type.

Answer 2

The allocator object himself is discouraged to be stateful. This means if you create an instance of std::allocator (or your own), this instance should not contain any info about allocated blocks etc - this info must be static and shared across all std::allocator instances. Breaking this rule may lead to undefined behavior in STL libraries.

For example, look at std::list::splice: it removes and interval of elements from one std::list and insert into other. Really nothing done with contained elements (no copying etc) - this method just rearranges internal pointers. So, if std::allocator instance #1 (in list #1) know something, what dont know std::allocator instance #2 (in list #2) ? These elements will be lost, memleaked, spontaneously deleted or whatever..

A good reading about such things on STL is "Effective STL", Scott Meyers