[c++][STL][Note] Allocator

Most of the standard containers never ask their associated allocator for memory.

In the C++ standard, the default allocator for objects of type T (cunningly known as allocator<T>) offers the typedefs allocator<T>::pointer and allocator<T>::reference, and it is expected that user-defined allocators will provide these typedefs, too.


The Standard says that an implementation of the STL is permitted to assume that all allocator objects of the same type are equivalent and always compare equal.



there's certainly good motivation for it:
template<typename T> // a user-defined allocator class SpecialAllocator {...}; // template typedef SpecialAllocator<Widget> SAW; // SAW = "SpecialAllocator // for Widgets" list<Widget, SAW> L1; list<Widget, SAW> L2: … L1.splice(L1 .begin(), L2); // move L2's nodes to the //front of L1





Recall that when list elements are spliced from one list to another, nothing is copied. Instead, a few pointers are adjusted, and the list nodes that used to be in one list find themselves in another. 

This makes splicing operations both fast and exception-safe. In the example above, the nodes that were in L2 prior to the splice are in L1 after the splice.




When L1 is destroyed, of course, it must destroy all its nodes (and deallocate their memory), and because it now contains nodes that were originally part of L2. L1's allocator must deallocate the nodes that were originally allocated by L2's allocator. 

Now it should be clear why the Standard permits implementers of the STL to assume that allocators of the same type are equivalent. It's so memory allocated by one allocator object (such as L2's) may be safely deallocated by another allocator object (such as L1's). 

Without being able to make such an assumption, splicing operations would be more difficult to implement.


STL implementations may assume that allocators of the same type are equivalent. 

It means that portable allocator objects — allocators that will function correctly under different STL implementations — may not have state.

Let's be explicit about this: it means that portable allocators may not have any nonstatic data members, at least not any that affect their behavior.

That means, for example, you can't have one SpecialAllocator that allocates from one heap and a different SpecialAllocator that allocates from a different heap. Such allocators wouldn't be equivalent, and STL implementations exist where attempts to use both allocators could lead to corrupt runtime data structures.

Notice that this is a runtime issue. Allocators with state will compile just fine. They just may not run the way you expect them to.

The responsibility for ensuring that all allocators of a given type are equivalent is yours. Don't expect compilers to issue a warning if you violate this constraint.
programmers concerned about portability will limit themselves to custom allocators with no state.


1.operator new and allocator:allocate differ in return types. operator new returns a void*, which is the traditional C++ way of representing a pointer to uninitialized memory. allocator::allocate returns a T* (via the pointer typedef), which is not only untraditional, it's premeditated fraud. The pointer returned from allocator::allocate doesn't point to a T object, because no T has yet been
constructed!

2.Implicit in the STL is the expectation that allocator::allocate's caller will eventually construct one or more T objects in the memory it returns (possibly via allocator::construct, via uninitialized_fill, or via some application of raw_storage_iterators), though in the case of vector::reserve or string::reserve, that may never happen.

3. Most of the standard containers never make a single call to the allocators with which they are instantiated.

list<int> L; // same as list<int, allocator<int> >; // allocator<int> is never asked to // allocate memory! set<Widget, SAW> s; // recall that SAW is a typedef for //SpecialAllocator<Widget>; no // SAW will ever allocate memory!

This oddity is true for list and all the standard associative containers (set. Multiset, map. and multimap).


That's because these are node-based containers, i.e., containers based on data structures in which a new node is dynamically allocated each time a value is to be stored. In the case of list, the nodes are list nodes.

In the case of the standard associative containers, the nodes are usually tree nodes, because the standard associative containers are typically implemented as balanced binary search trees.


Now , code says more than words:

template<typename T, // possible list typename Allocator = allocator<T> > // implementation class list{ private: Allocator alloc; // allocator for objects of type T struct ListNode{ // nodes in the linked list T data: ListNode *prev; ListNode *next; }; … }; template<typename T> // the standard allocator is declared class allocator { // like this, but this could be a userpublic: // written allocator template, too template<typename U> struct rebind{ typedef allocator<U> other; } … } Allocator::rebind<ListNode>::other;


What you do need to know is that if you choose to write allocators and use them with the standard containers, your allocators must provide the rebind template, because standard containers assume it will be there. (For debugging purposes, it's also helpful to know why node-based containers of T objects never ask for memory from the allocators for T objects.)

Summary:
Make your allocator a template, with the template parameter T representing the type of objects for which you are allocating memory.
Provide the typedefs pointer and reference, but always have pointer be T* and reference be T&.
Never give your allocators per-object state. In general, allocators should have no nonstatic data members.
Remember that an allocator's allocate member functions are passed the number of objects for which memory is required, not the number of bytes needed. Also remember that these functions return T* pointers Ma the pointer typedef), even though no T objects have yet been constructed.
Be sure to provide the nested rebind template on which standard containers depend.



---------------


template <class T> class malloc_allocator { public: typedef T value_type; typedef value_type* pointer; typedef const value_type* const_pointer; typedef value_type& reference; typedef const value_type& const_reference; typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; ... };

It's no accident that these types are so similar to those in an STL container: a container class usually gets those types directly from its allocator.

so the first thing a container has to do before using an allocator is create allocator objects.

any two malloc_allocator objects are interchangeable; if a1 and a2 are both of type malloc_allocator<int>, we can freely allocate memory through a1 and deallocate it through a2. We therefore define a comparison operator that says all malloc_allocator objects are equal:

template <class T> inline bool operator==(const malloc_allocator<T>&, const malloc_allocator<T>&) { return true; } template <class T> inline bool operator!=(const malloc_allocator<T>&, const malloc_allocator<T>&) { return false; }

Would you ever want to have an allocator where different objects weren't interchangeable? Certainly — but simple and useful examples are hard to come by. One obvious possibility is memory pools.

malloc_allocator<int>::pointer is int*, malloc_allocator<int>().allocate(1) returns enough memory for one int object.

Containers, like allocators, start with nested types: value_type, reference, const_reference, size_type, difference_type, iterator, and const_iterator. In general, most of those types can be taken directly from the container's allocator — thus illustrating why the container's value type and the allocator's must match.

The iterator types, of course, don't usually come from the allocator; usually an iterator is some kind of class, closely tied to the container's internal representation.

It's illegal to instantiate an allocator with an incomplete type. //Template issue



The only question is what happens when you perform an operation that requires two containers to cooperate on memory management. There are exactly two such operations in the standard library: swap (all containers) and std::list::splice. In principle, an implementation could handle them in several different ways:

Forbid swap or splice between two containers whose allocators aren't equal.
Put a test for allocator equality in swap and splice. If the allocators aren't equal, then fall back to some other operation like copying and assignment.
For swap only: swap the containers' allocators as well as their data. (It's hard to see how we could generalize this to splice. It also presents a problem: how do you swap things that don't have assignment operators?)



A sample allocator based on malloc
template <class T> class malloc_allocator { public: typedef T value_type; typedef value_type* pointer; typedef const value_type* const_pointer; typedef value_type& reference; typedef const value_type& const_reference; typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; template <class U> struct rebind { typedef malloc_allocator<U> other; }; malloc_allocator() {} malloc_allocator(const malloc_allocator&) {} template <class U> malloc_allocator(const malloc_allocator<U>&) {} ~malloc_allocator() {} pointer address(reference x) const { return &x; } const_pointer address(const_reference x) const { return x; } pointer allocate(size_type n, const_pointer = 0) { void* p = std::malloc(n * sizeof(T)); if (!p) throw std::bad_alloc(); return static_cast<pointer>(p); } void deallocate(pointer p, size_type) { std::free(p); } size_type max_size() const { return static_cast<size_type>(-1) / sizeof(T); } void construct(pointer p, const value_type& x) { new(p) value_type(x); } void destroy(pointer p) { p->~value_type(); } private: void operator=(const malloc_allocator&); }; template<> class malloc_allocator<void> { typedef void value_type; typedef void* pointer; typedef const void* const_pointer; template <class U> struct rebind { typedef malloc_allocator<U> other; }; }; template <class T> inline bool operator==(const malloc_allocator<T>&, const malloc_allocator<T>&) { return true; } template <class T> inline bool operator!=(const malloc_allocator<T>&, const malloc_allocator<T>&) { return false; }

Reference:
The Standard Librarian: What Are Allocators Good For?