• 软件:1160
  • 资讯:41601|
  • 收录网站:97880|

IT精英团

三张图片带你了解stl内存分配器 你不再害怕面试官的提问

三张图片带你了解stl内存分配器 你不再害怕面试官的提问

浏览次数:
评论次数:
编辑: 泽洋
信息来源: 51CTO博客
更新日期: 2021-06-11 01:09:39
摘要

三张图带你弄懂stl内存分配器,再也不怕面试官问了,本篇文章基于源码来剖析标准库中内存分配器的实现原理及使用。说明一下,我用的是gcc7.1.0编译器,标准库源代码也是这个版本的。还是来先通过思维导图来看一下本篇文章会从哪些方面来讲解stl中内存分配器和萃取器,如下:其实stl中有关内存申请的操作是包含两个内容的:内存分配器、内存萃取器。一、vector容器中对内存分配器的使用前面的文章中说了,vector容器本质上是个动态数组

  • 资讯详情

从源代码出发,分析了标准库中内存分配器的实现原理和使用方法。

解释一下,我用的是gcc7.1.0编译器,标准库的源代码也是这个版本。

让我们首先看一下这篇文章的各个方面,通过思维导图解释stl中的内存分配器和提取器,如下所示:

在这里插入图片描述

实际上,stl中内存应用程序的操作包括两个内容:内存分配器和内存提取器。

一、vector容器中对内存分配器的使用

如前一篇文章所述,向量容器本质上是一个动态数组,它实际上是通过使用标准库的内存分配器来实现的。让我们先看看代码,如下所示:

templatetypename _Tp,typename _Alloc

结构_矢量_基础

{

typedef typename _ _ GNU _ cxx : _ _ alloc _ traits _ alloc :模板

rebind _ Tp :3360 OThER _ Tp _ alloc _ type;

typedef typename _ _ GNU _ cxx : _ _ alloc _ traits _ Tp _ alloc _ type :3:指针

指针;

结构_向量_impl

: public _Tp_alloc_type

{

.

};

.

public:

_ Vector _ impl _ M _ impl

指针

_M_allocate(size_t __n)

{

typedef _ _ GNU _ cxx : _ _ alloc _ traits _ Tp _ alloc _ type _ Tr;

return __n!=0 ?_Tr:allocate(_M_impl,__n) :指针();

}

.

};

class Vector : protected _ Vector _ base _ Tp,_Alloc

{.};

向量继承自_Vector_base,而_Vector_base中内存分配是由_Vector_impl结构实现的,它继承自_Tp_alloc_type。type _Tp_alloc_type的完整类型是_ _ GNU _ cxx :3360 _ _ alloc _ traits _ alloc :3360 template rebind _ Tp 33603360 other,按照function _M_allocate的最终内存分配是这样实现的:

_ _ GNU _ cxx : _ _ alloc _ traits _ Tp _ alloc _ type : allocate(_ Tp _ alloc _ type,_ _ n);

如果不知道这一行代码中发生了什么,我们就不能知道这个内存是如何分配的,并且stl中的许多其他容器也是用这个分配器实现的,所以如果不知道这个分配器发生了什么,我们就不能解释容器的使用。

二、stl内存分配器和萃取器介绍

1. 分配器和萃取器类关系

要知道它们到底是什么,首先要了解它们之间的关系。我追踪了stl的源代码到它的来源。

说实话,为了了解这段感情,我浪费了很多脑细胞。毕竟这些类型真的太长了,我看着晕晕的。最后我画了一张图如下:

在这里插入图片描述

用文字描述这么难的类型会很疯狂,或者用图片描述会更好。哈哈哈,这个类继承关系应该是一目了然的,包括每种类型标注清楚的是哪个头文件。自然,我们也对提取器和分配器有了初步的概念。比如我们知道第一章中的type _ _ alloc _ traits是提取器,type _ TP _ alloc是提取器。

哦。

不过这里有一点,我们需要说明一下,先看头文件allocator.h里面这段代码:

template<typename _Tp>
    class allocator: public __allocator_base<_Tp>

这里allocator的基类明明是__allocator_base<_Tp>,为啥我们图片里面不是呢,这就需要头文件new_allocator_base.h里面的第二段代码啦,如下:

template<typename _Tp>
    using __allocator_base = __gnu_cxx::new_allocator<_Tp>;

原来类型__allocator_base是类new_allocator的别名,所以就有了我们图片里面的这个继承关系啦。

2. 分配器和萃取器到底是啥

我们接着第一章的内容,截取stl_vector.h头文件中部分代码如下:

template<typename _Tp, typename _Alloc>
struct _Vector_base
{
	typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Tp>::other _Tp_alloc_type;
	struct _Vector_impl: public _Tp_alloc_type
	{
	...
	};
	_Vector_impl _M_impl;
    //调用函数_M_allocate分配大小为__n的空间
    pointer _M_allocate(size_t __n)
	{
		typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
		return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer();
	}
    ...
};
template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
    class vector : protected _Vector_base<_Tp, _Alloc>;

很显然,这里首先要清楚类型_Tp_alloc_type到底是个怎么回事,这又是一个比较漫长的套娃过程,看下图:

在这里插入图片描述

所以最后这个other类型实际上就是allocator<_Tp1>这个类型,注意它是先取了allocator<void>这个,继而才走到带模板的allocator那里去的,而结合vector实现代码和上面图片可知模板实参_Tp1这个就是我们定义一个vector的时候指定的模板形参,这里以vector<int>为例,那么这个other其实就是allocator<int>类型了,所以_Tp_alloc_type实际上是allocator<int>类型,有些书上把这个套娃的过程称为萃取,所以我这里称__alloc_traits这个为萃取器,它取到了一个分配器。

把上面调用过程转换一下,就是这样了:

allocator<int> _M_impl;
__gnu_cxx::__alloc_traits<allocator<int>>::allocate(_M_impl, __n);

看一下__gnu_cxx::__alloc_traits::allocate的实现,如下:

static pointer
    allocate(_Alloc& __a, size_type __n)
    { return __a.allocate(__n); }

所以实际上是调用了allocator<int>.allocate这个函数来实现的内存分配,而class allocator本身是没有这个函数的,只有它的基类new_allocator才有这个函数,实现如下:

pointer
      allocate(size_type __n, const void* = 0)
      {
	if (__n > this->max_size())
	  std::__throw_bad_alloc();
#if __cpp_aligned_new
	if (alignof(_Tp) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
	  {
	    std::align_val_t __al = std::align_val_t(alignof(_Tp));
	    return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp), __al));
	  }
#endif
	return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
      }

到最后,其实就是直接调用了::operator new这个函数进行了内存的分配,所以allocator叫做内存分配器。

呼,总算把这个分配器和萃取器的运作过程讲完啦,举一反三,那么释放这个动态内存其实也是一样的过程哈,这里不再多说。

三、内存分配器的使用
1. 内存分配器construct和destroy函数的说明

对于内存分配器,前面也说了,分配调用allocate函数,最终是调用了operator new,释放内存是调用了operator delete这个函数,所以这里不再多说。

接下来我们看一下给分配的这个动态内存中构造数据和析构数据是怎么操作的,截取代码如下:

//这里入参__p是一个指向当前内存的指针,而入参__val是待存入内存中的值
//这里对new的使用不太好理解,我理解可以转换成:__p = new _Tp(__val);
void construct(pointer __p, const _Tp& __val)
      { ::new((void *)__p) _Tp(__val); }
//销毁就比较好理解一些了,直接调用了元素的析构函数
void destroy(pointer __p) { __p->~_Tp(); }

具体怎么操作的,注释已经写得很清楚了,这里不再多说,同时get到了new的新用法呀,如下:

#include <iostream>
using namespace std;
int main()
{
	int *p = new int;
	new (p) int(10);
	cout << "*p=" << *p << endl;
}

这样也是可以滴。

2. max_size函数

这里为什么要把max_size这个函数拿出来说明了,因为在使用内存分配器的容器中,往往这些容器的最大元素个数都是不能超过这个函数返回值的,所以要拿出来说明以下,实现如下:

size_type max_size() const _GLIBCXX_USE_NOEXCEPT
      { return size_t(-1) / sizeof(_Tp); }

首先看size_t,之所以用size_t,是为了跨平台,每个平台定义的size_t类型可能都不一样,但一般来讲size_t是一个无符号整型的数字,假设它是一个unsigned long,那就是4294967295 ,再除以这个元素的大小,就得出了一个容器能保存的最大的元素个数了

3. 直接使用allocator类

我们直接使用一下这个类看下,简单使用代码如下:

#include <iostream>
#include <bits/allocator.h>
using namespace std;
int main()
{
	allocator<int> alloc;
	allocator<int>::size_type size = 5;
	allocator<int>::pointer ptr = alloc.allocate(size);
	for (int i = 0; i< size; i++)
	{
		alloc.construct(ptr+i, i+1);
	}
	for (int i = 0; i< size; i++)
	{
		cout << "alloc[" << i << "]=" << ptr[i] << endl;
	}
    //这里销毁内存一定要手动调用,因为allocator类的析构函数啥事也没干
	alloc.deallocate(ptr, size);
	return 0;
}

四、标准库为什么要使用内存分配器

其实我也不知道呀,我猜是为了保持各个容器分配都有一个统一的接口,也就是标准化。

标签: vector STL
超细化STL中数组容器的使用和实现原理分析
« 上一篇
返回列表
下一篇 »
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表
你会是第一个来这里评论的人吗?
最近发布资讯
更多