operator new() and malloc()
operator new() calls malloc to apply for memory space
All memory allocation operations will eventually fall on malloc. The actual memory allocated by malloc is larger than the applied memory, because there is additional information, which is usually fixed
allocators(VC6 BC5 G2.9 G4.9)
-
VC6 version
-
BC5 version
- G2.9 Version
G2.9 defines<defalloc. h>similar to the allocator in other versions, but does not use it. G2.9 uses an improved allocator, namely<stl_ alloc.h>
The goal of the allocator is to minimize the number of malloc and reduce the extra cost< stl_ Alloc. h>can reduce additional overhead:
Reduce additional overhead:
The extra cost comes from the description of the size of the block space (Cookie). G2.9 saves the extra cost by the following methods:
G2.9 The actual allocator is to maintain n linked lists. Each linked list is responsible for a block of a specific size. For example, the first linked list is responsible for the allocation of one byte, the second is responsible for the allocation of two bytes, and the third is responsible for the allocation of three bytes. When there is no time, it will apply for and cut with the operating system
Memory blocks on the same linked list can save some additional overhead, such as size and other information
- G4.9 version (latest version)
G4.9 discards the design of G2.9 and uses VC6 mode without special design, as follows
However, version G2.9 is also retained
How to use allocator
int main() {
std::allocator<std::string> alloc; // allocator object that can allocate string
int n{5};
auto const p = alloc.allocate(n); // Allocate n uninitialized string s
auto q = p;
alloc.construct(q++); // *q is an empty string
alloc.construct(q++, 10, 'o'); // *q is cccccccccc
alloc.construct(q++, "hello"); // *q is hello
std::cout << *p << std::endl; // Correct: Use the output operator of string
//std::cout << *q << std::endl; // Error: q points to unconstructed memory
std::cout << p[0] << std::endl;
std::cout << p[1] << std::endl;
std::cout << p[2] << std::endl;
while (q != p) {
alloc.destroy(--q); // Release the string we really constructed
}
alloc.deallocate(p, n);
return 0;
}
Detailed source code of allocator
Source file structure
There are still many underlying functions that have not been implemented. We can only look at them first
1. In QT5.8, vector is defined as follows
template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class vector : protected _Vector_base<_Tp, _Alloc>{}
template<typename _Tp, typename _Alloc>
struct _Vector_base{}
The std::allocator allocator is used by default
2. allocator Structure Description
(1) Take allocator.h of qt5.8 as an example. The top layer defines multiple allocators, one of which is as follows
(2) It can be seen that there are no standard functions such as deallocator s in the above allocator class. But it inherits the base class**__ allocator_base * *, and this base class appears in c++allocator.h, as follows:
template<typename _Tp> using __allocator_base = __gnu_cxx::new_allocator<_Tp>;
(3) Further find * *<new_ allocator. h> * * file. It can be found that all required classes for allocator are defined, including deallocator___ gnu_ cxx::new_ allocator<_ Tp>is the lowest layer of allocator implemented by most compilers
Allocator base class: new_allocator
reference resources: https://zhuanlan.zhihu.com/p/354191253
https://blog.csdn.net/mei_true/article/details/113951160
c++'s default memory allocator inherits from___ gnu_ cxx::new_ allocator<_ Tp>, it has two tasks
- Allocate object memory and initialize objects
- Deconstruct objects and free object memory
The source code is as follows:
//Use size in std_ T and ptrdiff_t definition, adapting to different platforms for the portability of programs
//size_t represents unsigned type, ptrdiff_ TSave the result of subtracting two pointers
using std::size_t;
using std::ptrdiff_t;
//1. Definition new_allocator template
template<typename _Tp>
class new_allocator{
public:
typedef size_t size_type;//Type definition__ allocator_ Introduced in traits
typedef ptrdiff_t difference_type;//Distance between elements
typedef _Tp* pointer;//Pointer type
typedef const _Tp* const_pointer;
typedef _Tp& reference;//Lvalue reference type (lvalue is a non temporary variable)
typedef const _Tp& const_reference;
typedef _Tp value_type;//Element Type
//2. rebind, structure template (important function)
template<typename _Tp1>
struct rebind{
typedef new_allocator<_Tp1> other;
};
//3. Check whether the C++11 standard is supported; The meaning of the variables will be explained in detail in the following memory learning
#if __cplusplus >= 201103L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 2103. propagate_on_container_move_assignment
typedef std::true_type propagate_on_container_move_assignment;
#endif
//4. No parameter structure_ GLIBCXX_USE_NOEXCEPT is define d as noexcept, indicating that no exception will be thrown
new_allocator() _GLIBCXX_USE_NOEXCEPT { }
//5. Copy constructor
new_allocator(const new_allocator&) _GLIBCXX_USE_NOEXCEPT { }
//6. Constructor template, generalized copy construction
template<typename _Tp1>
new_allocator(const new_allocator<_Tp1>&) _GLIBCXX_USE_NOEXCEPT { }
//7. Destructor
~new_allocator() _GLIBCXX_USE_NOEXCEPT { }
//8. Define the address member function, and reference is_ Tp&Type__ addressof is the address of the variable that can still be obtained when the overload of operator&exists
//Formula a.address(x) is equivalent to&x
pointer address(reference __x) const _GLIBCXX_NOEXCEPT {
return std::__addressof(__x);
}
//9. Similar to the above functions, but with const type
const_pointer address(const_reference __x) const _GLIBCXX_NOEXCEPT {
return std::__addressof(__x);
}
// NB: __n is permitted to be 0.
// The C++ standard says nothing about what the return value is when __n == 0.
//10. Allocate memory (important functions)
pointer allocate(size_type __n, const void* = 0){
if (__n > this->max_size())
std::__throw_bad_alloc();
return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
}
// __p is not permitted to be a null pointer.
//11. Free memory (important functions)
void deallocate(pointer __p, size_type){
::operator delete(__p);
}
//12. Return the maximum memory that can be allocated
//size_t is 32-bit for 32-bit machines, 64 bit for 64 bit machines, size_t(-1) can just express the maximum value it can represent (complement+1 just means all bits are 1)
//suze_t/sizeof(_Tp) can express the maximum returned under the current platform_ Number of Tp (4G in theory, but not in practice)
size_type max_size() const _GLIBCXX_USE_NOEXCEPT {
return size_t(-1) / sizeof(_Tp);
}
//13. construct and destory
#if __cplusplus >= 201103L
template<typename _Up, typename... _Args> void construct(_Up* __p, _Args&&... __args) {
::new((void *)__p) _Up(std::forward<_Args>(__args)...);
}
template<typename _Up> void destroy(_Up* __p) {
__p->~_Up();
}
#else
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 402. wrong new expression in [some_] allocator::construct
void construct(pointer __p, const _Tp& __val) {
::new((void *)__p) _Tp(__val);
}
void destroy(pointer __p) {
__p->~_Tp();
}
#endif
};
Some important members will be described in detail below
Member: rebind()
template<typename _Tp1>
struct rebind{
typedef new_allocator<_Tp1> other;
};
new_ The allocator is a memory allocator, and rebind() is used to bind memory allocators of different data types. A typical example is the list container.
typedef typename _Alloc::template rebind<_List_node<_Tp> >::other _Node_alloc_type; typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
The simplest list contains two members: int data and struct node *next; When we define a container, we pass the type to the allocator, but the allocator cannot recognize struct node *next;
rebind() is used to solve this problem. It allows the container to use an allocator_ Alloc defines multiple different allocators to ensure consistency. This setting also makes the new_ Parametric construction of allocator class is not needed
From the source code of vector and list, respectively:
(1)vector
The call sequence is c++/vector, c++/bits/stl_vector.h
class vector and its base class_ Vector_ The base is in the source file<stl_ Vector. h>, the file only serves as an import function
template<typename _Tp, typename _Alloc>
struct _Vector_base{
typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Tp>::other _Tp_alloc_type;
typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer pointer;
...;
}
(2)list
From the top to the bottom, c++/list, c++/bits/stl are include d in turn_ list.h，
class list and its base class_ List_ The base is in the source file<stl_ In list. h>
template<typename _Tp, typename _Alloc>
class _List_base{
protected:
typedef typename _Alloc::template rebind<_List_node<_Tp> >::other _Node_alloc_type;
typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
...;
}
- As you can see, both list and vector are executed once<_ rebind() of Tp>, which is equivalent to parametric construction. But the list has one rebind() more than the vector, because the list also needs a node memory allocator
- rebind mainly serves stl chained containers. The memory allocator of a vector serves the entire vector. When the vector capacity is insufficient and needs to be expanded, it will re use the allocator to request a vector space and then copy it. Taking int as an example, the allocator only needs to allocate int*n
- The difference between the list is that it also defines an int, but the allocator cannot assign an int type to it, because each linked list node also includes front and back pointers, so what needs to be allocated is<_ list_ Node>type. rebind() allows the list container to use listl like other containers
elementary analysis:
A list is also defined in the list_node node class. A node is a<_ list_node< _ Tp>>type data structure, use_ Tp type cannot be assigned correctly.
You can also add one allocator parameter to the container, that is, two allocator parameters. But to ensure that the two allocators are the same, it is better to use rebind(), that is, to avoid_ Tp uses std::allocator allocator, while nodes use other allocators, such as pool_allocator； (Because the allocation space size of different allocators may be different)
Rebind can re specify the type of allocator allocation space, which meets the requirement of using the same memory allocation strategy for different types. When the container needs to use the same allocation policy for different types, the meaning of rebind is reflected.
Member: allocate()
Configure memory space and return__ n (0 allowed) memory space of Tp type size
pointer allocate(size_type __n, const void* = 0){
if (__n > this->max_size())
std::__throw_bad_alloc();
return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
}
- __ n > this->max_ Size() checks whether the size of the request exceeds the maximum available memory of the current process, and throws an exception if it exceeds
- operator new is the actual space allocation operation, encapsulating malloc
- static_cast allows basic type conversion and uplink conversion (i.e., the son pointer is transferred to the parent pointer)
- Const void *=0: (No meaning found)
Member: deallocate()
void deallocate(pointer __p, size_type){
::operator delete(__p);
}
Release__ Memory space pointed by p
- __ p null pointer is not allowed
- operator delete encapsulates the free function to free memory
- Size here_ Type is not used because free() does not require a size parameter, but other allocators such as boost pool_ The allocator is used. To ensure the consistency of stl calls, this parameter is used
Member: construct()
allocate allocates memory, and construct initializes memory
template<typename _Up, typename... _Args> void construct(_Up* __p, _Args&&... __args) {
::new((void *)__p) _Up(std::forward<_Args>(__args)...);
}
Example of using construct
allocator<string> alloc;//The allocator object is of string type auto const p = alloc.allocate(3);//Allocate space for 3 string s, but not initialized auto q = p;//q points to the first uninitialized string alloc.construct(q++);//Initialize string, the first is an empty string alloc.construct(q++,5,'a');//The second is "aaaaa" alloc.construct(q++,"hi");//The third is "hi"
Construction involves forwarding forward. std::forward transfers the input parameters (left and right values) to the next function (in new) without changing them. Here, it can be regarded as a forward does not exist
Member: destory()
template<typename _Up> void destroy(_Up* __p) {
__p->~_Up();
}
Call_ Up destructor to free its space
class allocator
- Inherited new_allocator
- There are some overloads allocated, but the following functions are not very clear for the time being
#ifndef _ALLOCATOR_H
#define _ALLOCATOR_H 1
#include <bits/c++allocator.h> // Define the base class to std::allocator.
#include <bits/memoryfwd.h>
#if __cplusplus >= 201103L
#include <type_traits>
#endif
namespace std _GLIBCXX_VISIBILITY(default) {
_GLIBCXX_BEGIN_NAMESPACE_VERSION
//allocator without inheriting parent class
template<>
class allocator<void> {
public:
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef void* pointer;
typedef const void* const_pointer;
typedef void value_type;
//Define rebind
template<typename _Tp1>
struct rebind {
typedef allocator<_Tp1> other;
};
#if __cplusplus >= 201103L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 2103. std::allocator propagate_on_container_move_assignment
typedef true_type propagate_on_container_move_assignment;
#endif
};
//Inherit the allocator of the parent class__ allocator_base is actually new_allocator
template<typename _Tp>
class allocator: public __allocator_base<_Tp> {
public:
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef _Tp* pointer;
typedef const _Tp* const_pointer;
typedef _Tp& reference;
typedef const _Tp& const_reference;
typedef _Tp value_type;
//Override the rebind of the parent class
template<typename _Tp1>
struct rebind {
typedef allocator<_Tp1> other;
};
#if __cplusplus >= 201103L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 2103. std::allocator propagate_on_container_move_assignment
typedef true_type propagate_on_container_move_assignment;
#endif
//Nonparametric structure
allocator() throw() { }
//copy construction
allocator(const allocator& __a) throw() : __allocator_base<_Tp>(__a) { }
template<typename _Tp1>
allocator(const allocator<_Tp1>&) throw() { }
~allocator() throw() { }
// Inherit everything else.
// From new_ The allocator inherits important functions such as allocate, deallocate, construct, and destory
};
//Yes==and= The four overloaded functions here express that the objects instantiated with std::allocator must be the same, regardless of the type
template<typename _T1, typename _T2>
inline bool operator==(const allocator<_T1>&, const allocator<_T2>&) _GLIBCXX_USE_NOEXCEPT {
return true;
}
template<typename _Tp>
inline bool operator==(const allocator<_Tp>&, const allocator<_Tp>&) _GLIBCXX_USE_NOEXCEPT {
return true;
}
template<typename _T1, typename _T2>
inline bool operator!=(const allocator<_T1>&, const allocator<_T2>&) _GLIBCXX_USE_NOEXCEPT {
return false;
}
template<typename _Tp>
inline bool operator!=(const allocator<_Tp>&, const allocator<_Tp>&) _GLIBCXX_USE_NOEXCEPT {
return false;
}
/// @} group allocator
// Inhibit implicit instantiations for required instantiations,
// which are defined via explicit instantiations elsewhere.
#if _GLIBCXX_EXTERN_TEMPLATE
extern template class allocator<char>;
extern template class allocator<wchar_t>;
#endif
// Undefine.
#undef __allocator_base
// To implement Option 3 of DR 431.
template<typename _Alloc, bool = __is_empty(_Alloc)>
struct __alloc_swap {
static void _S_do_it(_Alloc&, _Alloc&) _GLIBCXX_NOEXCEPT { }
};
//If the distributor is different, exchange (application?)
template<typename _Alloc>
struct __alloc_swap<_Alloc, false> {
static void _S_do_it(_Alloc& __one, _Alloc& __two) _GLIBCXX_NOEXCEPT {
// Precondition: swappable allocators.
if (__one != __two)
swap(__one, __two);
}
};
// neq means inequality
// Optimize for stateless allocators.
template<typename _Alloc, bool = __is_empty(_Alloc)>
struct __alloc_neq {
static bool _S_do_it(const _Alloc&, const _Alloc&) {
return false;
}
};
template<typename _Alloc>
struct __alloc_neq<_Alloc, false> {
static bool _S_do_it(const _Alloc& __one, const _Alloc& __two) {
return __one != __two;
}
};
#if __cplusplus >= 201103L
template<typename _Tp, bool = __or_<is_copy_constructible<typename _Tp::value_type>,
is_nothrow_move_constructible<typename _Tp::value_type>>::value>
struct __shrink_to_fit_aux {
static bool _S_do_it(_Tp&) noexcept {
return false;
}
};
template<typename _Tp>
struct __shrink_to_fit_aux<_Tp, true> {
static bool _S_do_it(_Tp& __c) noexcept {
#if __cpp_exceptions
try {
_Tp(__make_move_if_noexcept_iterator(__c.begin()),
__make_move_if_noexcept_iterator(__c.end()),
__c.get_allocator()).swap(__c);
return true;
} catch(...) { return false; }
#else
return false;
#endif
}
};
#endif
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
#endif