Space Allocator

1. Why introduce a space configurator?

When we use the STL standard template library, all objects that need to be operated are stored in containers. When we operate on objects in a container, such as adding an element, deleting an element, or initializing a container, memory allocation will be involved. Therefore, the spatial configurator is introduced to store the objects in the container and configure the memory. (the space is not only memory, but also disk or other auxiliary storage media. In STL, the configuration object of the space allocator allocator is memory.)

2. Role of space configurator & what functions need to be implemented?

The space adapter described earlier is mainly used to configure memory space. When considering which configurator functions the space needs to implement, the focus is on how we want to use the container. What points should we consider when using containers to consider what functions the space adapter needs to implement:

1) First, you need to be able to initialize a container, and the configurator needs to support memory that can allocate a custom space.

• Then there will be a situation. What should we do when the existing memory space is less than the size of the allocated space?
• When C++ uses malloc for space configuration, in addition to allocating the required memory space, it also carries other information (such as the starting position of the currently allocated memory space). These information also occupy a certain amount of memory. If the allocated memory space is too small, a large number of other information will occupy memory, affecting efficiency. Can we optimize this situation?
• The programming idea of STL is mainly GP (generalized programming idea), which is different from OOP (object-oriented programming idea). For object-oriented programming, data and operations on data are encapsulated in one class. But for GP, the programming idea is different. GP divides the data into container modules, and the data operations are placed in the algorithm. The two are separated and belong to different modules. The two modules interact through iterators. Then there is a problem. When we configure the memory, we do not know the type of the current container class data. Therefore, we need to be able to accept different data types and allocate memory for them.
• STL is implemented in the way of traits (see another blog for details). The main idea of this method is "extraction". The container operates the space adapter through the iterator? The programming idea of traits is that the spatial adapter tells the iterator the information it needs? For example, the type of element currently stored, the distance between two elements, the element address, and the element reference.

Use of iterators: when we use iterators, there are two situations when the iterator calls the spatial adapter. One is that the data object needs to be operated as a class object, so the element operation is no longer a simple pointer++ operation. However, there is also a way to operate data objects. The operation space is continuous. You can use the pointer to execute + + or -- operations. At this time, partial specialization and full specialization in generalized programming are used, that is, operations similar to if else are used to process different data types respectively, and the algorithm module is told through trais if the operation.

[todo]: what is trais used for? Why quote? For iterators? Or space configurator? Who do you want to tell?

2) Can support the release of allocated memory space

• In addition to supporting the allocation of memory space, STL also needs to support the release of allocated memory space.

3. How to implement spatial configurator in STL

The spatial adapters in STL are constructed according to different types
1. The SGI space configurator contains two levels of space configurators. The first level of space configuration essentially uses malloc for space allocation. For the space configuration (>128bytes) that needs to allocate a large area, this kind of user with a large space Configurator

2. The second level space configurator adopts a more ingenious method to avoid the additional overhead caused by malloc when allocating space. aim at

4. Build a simple space configurator by yourself

Source: the book "STL source code analysis", which has been reproduced by myself

#include "allocate_Test.hpp"
#include <new>       //for placement new
#include <cstddef>   //for ptrdiff_t, size_t
#include <cstdlib>   //for exit()
#include <climits>   //for UINT_MAX
#include <iostream>  //for cerr

namespace STL_allocate{

//Global functions defined here
template <class T>
inline T* _allocate(ptrdiff_t size, T*){
    //Global space allocation function
    std::set_new_handler(0);//This is the operation to be performed before throwing an exception when the memory is insufficient
    //Use operator new to allocate a space. The space size is size * sizeof(T)
    T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));
    if(0 == tmp){ //If there is no space to allocate
        std::cerr<<"out of memory"<<std::endl;
        //In the whole program, just call exit
        //exit(1) returns 1, indicating that the process exits normally. If exit(0), it indicates an abnormal exit
        exit(1);
    }
    return tmp;
}

//Functions that reclaim allocated space globally
template <class T>
inline void _deallocate(T* buffer){
    ::operator delete(buffer);
}

//Global constructor
template <class T1, class T2>
inline void _construct(T1 *p, const T2& value){ //T2& reference
    //placement new calls the constructor only on a pointer to the allocated memory
    //It is to put the address pointed to by the pointer p back into the value of T2. Reduces the time-consuming allocation of space.
    //Advantages: compared with using new directly, it reduces the time to find the appropriate memory in the heap
    new(p) T1(value);
}

//Global destructor
template <class T>
inline void _destory(T* ptr){
    ptr->~T();
}


template <class T>
class allocator{
public:
    typedef T value_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    
    template <class U> //Template nested template
    struct rebind{
        typedef allocator<U> others;
    };
    
    
    //size_type is the number of elements to be allocated
    pointer allocate(size_type n, const void* hint = 0){
        return _allocate((difference_type)n, (pointer)0);
    }
    
    void deallocate(pointer buffer, size_type n){
        _deallocate(buffer);
    }
    
    void construce(pointer p, const T& value){
        _construct(p, value);
    }
    
    void destory(pointer p){
        _destory(p);
    }
    
    pointer address(reference T1){
        return (pointer)&T1;
    }
    
    const_pointer const_address(const_reference T1){
        return (const_pointer)&T1;
    }
    
    size_type max_size(){
        return size_type(UINT_MAX/sizeof(T));
    }
};

}

Build a space adapter by yourself