注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一路

To find the final symmetry & beauty

 
 
 

日志

 
 
 
 

SGI STL源码阅读笔记10 allocator[原创]  

2011-02-18 06:55:40|  分类: c++学习笔记 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

    STL中把内存分配与容器的元素管理通过这个allocator中间层分开,使得元素管理中是容器的事,而内存的分配等只要allocator负责就可以了。这个allocator也不一定是在内存上分配空间把对象放在内存上,如果你愿意你可以通过映射的方式把元素存储在硬盘,闪存甚至是网络服务器上。使用allocator使行内STL中内存的管理极有弹性。这个allocator一般都是做为容器的默认模版参数,除非在高级使用或是STL代码出错时会出现一堆与allocator有关的东西,它一般只是默默的工作。

    allocator的定义在<memory>标准头文件中可见,在SGI STL中它的真正实现代码是在stl_alloc.h文件中,SGI STL的这个allocator分为两级,一个是直接调用C语言的malloc函数族写成的allocator,另一个是使用的两级内池写成的allocator,在介绍allocator之前我们先看一下C++标准规定的allocator接口,这个接口十分简单。我自己写了一个符合规定的sm_allocator,代码如下:

 

//filename: sm_allocator.h< xmlnamespace prefix ="o" ns ="urn:schemas-microsoft-com:office:office" />

//written by saturnman

#ifndef _SM_ALLOCATOR_H_

#define _SM_ALLOCATOR_H_

#include<new>     //for placement new operator

#include<climits> //for UINT_MAX

#include<cstddef> //for size_t,ptrdiff_t

#include<iostream>//for cerr

#include<cstdlib> //for exit

using std::exit;

using std::cerr;

using std::endl;

using std::cout;

using std::size_t;

using std::ptrdiff_t;

using std::set_new_handler;

///using std::UINT_MAX;

//using std::new;

namespace saturnman

{

    //util function

    template <typename T>

    inline T* _allocate(ptrdiff_t size,T*)//allocating memory

    {

        set_new_handler(NULL);

        T* tmp = (T*)(::operator new((size_t)(size*sizeof(T))));

        if(tmp==NULL)

        {

            cerr<<"out of memory."<<endl;

            exit(1);

        }

    }

    template<typename T>

    inline void _deallocate(T* address)

    {

        ::operator delete(address);

    }

    template<typename T1,typename T2>

    inline void _construct(T1* address,T2 const& value)

    {

        new (address) T1(value);

        //construct T1 type var on address

    }

    template<typename T>

    inline void _destroy(T* obj_ptr)

    {

        obj_ptr->~T();

    }

    template <typename T> class allocator;//pre-declaration

    //void specialization

    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;

        template<typename _Tp1>

        class rebind

        { public:typedef allocator<_Tp1> other; };

    };

    template <typename T>                 //definition

    class allocator

    {

        public:

            typedef size_t size_type;

            typedef ptrdiff_t difference_type;

            typedef T* pointer;

            typedef const T* const_pointer;

            typedef T& reference;

            typedef const T& const_reference;

            typedef T value_type;

            template <class U>

            class rebind { public:typedef allocator<U> other; };

            allocator(){}

            allocator(const allocator<T>&){}

            template <typename U> allocator(const allocator<U>&){}

            ~allocator(){};//trival destructor

            pointer address(reference x) const{return (pointer)&x;}

            const_pointer address(const_reference x) const

            {return const_pointer(&x);}

            pointer allocate(size_type size, allocator<void>::const_pointer hint = 0)

            {

                _allocate(size,hint);

            }

            void deallocate(pointer p, size_type n)

            {

                _deallocate(p);

            }

            size_type max_size() const {return (size_type)(UINT_MAX/sizeof(T));}

            void construct(pointer address,T const& value){_construct(address,value);}

            void destroy(pointer p){_destroy(p);}

            /*c++0x use the following,my god,I can't read that*/

            //template<class U, class... Args>

            //void construct(U* p, Args&&... args);

            //template <class U>

            //void destroy(U* p);

           

    };

    //globals

template <class T1, class T2>

bool operator==(allocator<T1> const&,allocator<T2> const&)

{

    return true;

}

template <class T1, class T2>

bool operator!=(allocator<T1> const&,allocator<T2> const&)

{

    return false;

}

 

} //end namespace saturnman

#endif/*_SM_ALLOCATOR_H_*/

 

这份代码部分的接口是从C++标准文档copy过来的,其中allocate deallocate construct destroy是标准中规定的,至于其是成员函数还是类的静态成员函数标准中无规定。其中的operator=与operator!= rebind也是标准库要求。下面是一个测试程序,它可以很好的和STL的标准算法配合使用。我自己这个当然是很简单的了,性能不高,但是在这个接口上却可以做很多事情,SGI STL就在这里使用了两级内存分配机制,第一级是直接的使用C语言的内存处理函数包装的allocator,第二级是使用了内存池技术,具体代码可以参考SGI的stl_alloc.h文件,这个文件我有详细的注释,文件地址如下。

http://saturnman.blog.163.com/blog/static/557611201111715038911/

//filename allocator_test.cpp

//written by saturnman

#include<iostream>

#include<vector>

#include<algorithm>

#include<iterator>

#include "sm_allocator.h"

using namespace std;

int main()

{

    int arr[] = {1,2,3,5,6};

    vector<int,saturnman::allocator<int> > v(arr,arr+5);

    for(auto itor = v.begin();itor!=v.end();++itor)

    {

        cout<<*itor<<endl;

    }

    for_each(v.begin(),v.end(),[](int& value){value*=value;});

    for(auto itor = v.begin();itor!=v.end();++itor)

    {

        cout<<*itor<<endl;

    }

    copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));

    cout<<endl;

    return 0;

}

 

 

为了更加清楚的了解这个内存池式的配置器的工作方式,我绘制了一幅简图,是这个池工作一段时间后的状态。

注意到就算是同是一块内存池,其内部的自由表块也可能不是一样大小的,而所有的管理自由表的各块只能与自己同大小的块串联在一起,这个自由表有一个奇怪的特性,就是它中有申请内存的造作而没有释放的操作。SGI的人说这不会产生内存泄露,但是我想如果程序通过池分配了内存,那我以后的内存使用就会留着这个峰值的影子。例如第二块蓝色内存块就可以释放掉。如果我们采用amortized 分析方法可以把内存的分配平均时间是O(1),但是这个内存紧缩是十分耗时的,因为这要查找所有的自己表结点。估计这也是一般托管式内存分配要面对的问题吧,还没读过托管式内存虚拟机的内存管理代码,目前也没想到什么好的管理办法,等多读几份allocator的代码之后再说吧。

[1] http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch32.html

[2] 候捷 《STL源码剖析》

  评论这张
 
阅读(1183)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017