为C++标准库容器写自己的内存分配程序

2016-02-19 20:48 6 1 收藏

下面图老师小编要向大家介绍下为C++标准库容器写自己的内存分配程序，看起来复杂实则是简单的，掌握好技巧就OK，喜欢就赶紧收藏起来吧！

【 tulaoshi.com - 编程语言】

根据sgi 的STL源码的二级分配算法改写的内存池分配程序，只要稍微修改就可以实现共享内存方式治理，使用C++标准库容器中的map，set，multimap，multiset测试通过，vector测试通不过，原因是在内存回收的时候考虑的比较简单，vector每次分配内存个数不固定，回收也不固定，这样的话，程序还需要继续完善。　　内存池治理程序源码如下：？XML:namespace prefix = std />？xml:namespace prefix = sizeof(Cookie)<以下是引用片段：
　　#ifndef MY_ALLOCATOR_H_
　　#define MY_ALLOCATOR_H_
　　#include "stdafx.h"
　　#include limits
　　#include iostream
　　namespace happyever
　　{
　　  enum { NODENUMS = 2 };
　　  union _Obj
　　  {
　　    union _Obj* M_free_list_link;
　　    char M_client_data[1];
　　  } ;
　　  typedef union _Obj Obj;
　　  strUCt _Cookie
　　  {
　　    int iShmKey;        /* 共享内存键值 */
　　    int iShmID;         /* iShmKey对应的shmid */
　　    int iSemKey;        /* 锁信号键值 */
　　    int iSemID;         /* 锁信号标识 */
　　    int iTotalsize;    /* 容器总容量 */
　　    void* pStartall;   /* 共享内存自身地址 */
　　    char* pStartfree;  /* 自由空间的开始地址*/
　　    char* pEndfree;    /* 自由空间的结束地址*/
　　    int iUseNum[NODENUMS];
　　    /*用来存放free_list中节点的size*/
　　    short sFreelistIndex[NODENUMS];
　　    /*存放分配内存节点的链表*/
　　    Obj* uFreelist[NODENUMS];
　　  };
　　  typedef struct _Cookie Cookie;
　　  //Obj;
　　  //Cookie;
　　  static Cookie *pHead = NULL;
　　  template class T
　　  class MyAlloc
　　  {
　　  private:
　　    static const int ALIGN = sizeof(Obj);
　　    int round_up(int bytes);
　　    int freelist_index(int bytes);
　　    int freelist_getindex(int bytes);
　　    char* chunk_alloc(int size, int *nobjs);
　　    void* refill(int num,int n);
　　  public:
　　    // type definitions
　　    typedef T        value_type;
　　    typedef T*       pointer;
　　    typedef const T* const_pointer;
　　    typedef T&       reference;
　　    typedef const T& const_reference;
　　    typedef std::size_t    size_type;
　　    typedef std::ptrdiff_t difference_type;
　　    template class U
　　    struct rebind
　　    {
　　      typedef MyAllocU other;
　　    };
　　    pointer address (reference value) const
　　    {
　　      return &value;
　　    }
　　    const_pointer address (const_reference value) const
　　    {
　　      return &value;
　　    }
　　    MyAlloc() throw()
　　    {
　　      std::cout"MyAlloc"std::endl;
　　    }
　　    MyAlloc(const MyAlloc& x) throw()
　　    {
　　      std::cout"const MyAlloc"std::endl;
　　    }
　　    template class U
　　    MyAlloc (const MyAllocU& x) throw()
　　    {
　　      std::cout"const MyAllocU"std::endl;
　　    }
　　    ~MyAlloc() throw()
　　    {
　　      std::cout"~MyAlloc"std::endl;
　　    }
　　    size_type max_size () const throw()
　　    {
　　      return std::numeric_limitsstd::size_t::max() / sizeof(T);
　　    }
　　    //void PrintFreelistAndCookie();
　　    pointer allocate (size_type num, const void* = 0)
　　    {
　　      pointer ret = 0;
　　      Obj** my_free_list;
　　      Obj* result;
　　      int index;
　　      // print message and allocate memory with global new
　　      std::cerr  "allocate "  num  " element(s)"
　　         " of size "  sizeof(T)  std::endl;
　　      index = freelist_index(sizeof(T));
　　      if(index = NODENUMS)
　　      {
　　        return NULL;
　　      }
　　      my_free_list = pHead-uFreelist + index;
　　      //Lock(semid,LOCK_NUM);
　　      result = *my_free_list;
　　      if (result == 0)
　　      {
　　        ret = (pointer)refill((int)num, round_up(sizeof(T)));
　　      }
　　      else
　　      {
　　        *my_free_list = result-M_free_list_link;
　　        ret = (pointer)result;
　　      }
　　      //UnLock(semid,LOCK_NUM);
　　      pHead-iUseNum[index] = pHead-iUseNum[index] + (int)num;
　　      if(0 == ret)
　　      {
　　        std::cerr  "alloc memory fail!"  std::endl;
　　        exit(1);
　　      }
　　      std::cerr  " allocated at: "  (void*)ret  std::endl;
　　      PrintFreelistAndCookie();
　　      return ret;
　　    }
　　    void construct (pointer p, const T& value)
　　    {
　　      // initialize memory with placement new
　　      new((void*)p)T(value);
　　    }
　　    void destroy (pointer p)
　　    {
　　      // destroy objects by calling their destructor
　　      p-~T();
　　    }
　　    void deallocate (pointer p, size_type num)
　　    {
　　      Obj** my_free_list;
　　      Obj* q ;
　　      int index;
　　      index = freelist_getindex(sizeof(T));
　　      if(index = NODENUMS)
　　      {
　　        std::cerr  "deallocate memory fail!"  std::endl;
　　        exit(1);
　　      }
　　      my_free_list = pHead-uFreelist + index;
　　      q = (Obj*) p;
　　      //Lock(semid,LOCK_NUM);
　　      /*这个地方可能会有问题*/
　　      //for(int i=0 ;i(int)num ; i++)
　　      {
　　        q-M_free_list_link = *my_free_list;
　　        *my_free_list = q;
　　      }
　　      //UnLock(semid,LOCK_NUM);
　　      pHead-iUseNum[index] = pHead-iUseNum[index] - (int)num;
　　
　　      std::cerr  "deallocate "  num  " element(s)"
　　         " of size "  sizeof(T)
　　         " at: "  (void*)p  std::endl;
　　      PrintFreelistAndCookie();
　　    }
　　  };
　　  template class T
　　  int MyAllocT::round_up(int bytes)
　　  {
　　    int i;
　　    i = bytes;
　　    if(bytes  ALIGN)
　　    {
　　      i = ALIGN;
　　    }
　　    std::cout"round_up:bytes="bytes" , return="istd::endl;
　　    return i;
　　  };
　　  template class T
　　  int MyAllocT::freelist_index(int bytes)
　　  {
　　    int i;
　　    for(i=0 ; i NODENUMS ; i++)
　　    {
　　      if(pHead-sFreelistIndex[i] == bytes)
　　        break;
　　    }
　　    if(i = NODENUMS)
　　    {
　　      for(i=0 ; i NODENUMS ; i++)
　　      {
　　        if(pHead-sFreelistIndex[i] == 0)
　　        {
　　          pHead-sFreelistIndex[i] = bytes;
　　          std::cout"freelist_index:bytes="bytes" , return="istd::endl;
　　          return i;
　　        }
　　      }
　　    }
　　    std::cout"freelist_index:bytes="bytes" , return="istd::endl;
　　    return i;
　　  };
　　  template class T
　　  int MyAllocT::freelist_getindex(int bytes)
　　  {
　　    int i;
　　    for(i=0 ; i NODENUMS ; i++)
　　    {
　　      if(pHead-sFreelistIndex[i] == bytes)
　　        break;
　　    }
　　    std::cout"freelist_getindex:bytes="bytes" , return="istd::endl;
　　    return i;
　　  };
　　  template class T
　　  char* MyAllocT::chunk_alloc(int size, int *nobjs)
　　  {
　　    char* result;
　　    int counts = *nobjs;
　　    int total_bytes = size * counts;
　　    int bytes_left = int(pHead-pEndfree - pHead-pStartfree);
　　    std::cout"chunk_alloc:total_bytes = "total_bytes
　　      ",bytes_left = "bytes_leftstd::endl;
　　    if (bytes_left = total_bytes)
　　    {
　　      result = pHead-pStartfree;
　　      pHead-pStartfree += total_bytes;
　　      std::cout"chunk_alloc:total_bytes = "total_bytes
　　        ",result = "*result",start_free = "&(pHead-pStartfree)std::endl;
　　    }
　　    else if (bytes_left = size)
　　    {
　　      counts = bytes_left/size;
　　      total_bytes = size * counts;
　　      result = pHead-pStartfree;
　　      pHead-pStartfree += total_bytes;
　　      *nobjs = counts;
　　      std::cout"chunk_alloc:total_bytes = "total_bytes",nobjs = "nobjs
　　        ",result = "*result",start_free = "&(pHead-pStartfree)std::endl;
　　    }
　　    else
　　    {
　　      /*还需要处理回收其他空闲freelist里面的空间*/
　　      result = NULL;
　　    }
　　    return(result);
　　  };
　　  template class T
　　  void* MyAllocT::refill(int num,int n)
　　  {
　　    int counts = num;
　　    int *nobjs = &counts;
　　    char* chunk;
　　    Obj** my_free_list;
　　    Obj* result;
　　    Obj* current_obj;
　　    Obj* next_obj;
　　    int i;
　　    chunk = chunk_alloc(n, nobjs);
　　    if(chunk == NULL)
　　    {
　　      return(chunk);
　　    }
　　    counts = *nobjs;
　　    if (1 == counts)
　　    {
　　      return(chunk);
　　    }
　　    my_free_list = pHead-uFreelist + freelist_index(n);
　　    result = (Obj*)chunk;
　　    *my_free_list = next_obj = (Obj*)(chunk + n*num);
　　    for (i = 1; ; i++)
　　    {
　　      current_obj = next_obj;
　　      next_obj = (Obj*)((char*)next_obj + n);
　　      if (counts - 1 == i)
　　      {
　　        current_obj-M_free_list_link = 0;
　　        break;
　　      }
　　      else
　　      {
　　        current_obj-M_free_list_link = next_obj;
　　      }
　　    }
　　    return(result);
　　  };
　　/*这个函数可以改写成自己的共享内存分配函数*/
　　static void InitShm()
　　  {
　　    int i,size=1000;
　　    pHead = (Cookie*)malloc(sizeof(Cookie)+size);
　　    pHead-iTotalsize = sizeof(Cookie)+size;
　　    pHead-pStartall  = pHead;
　　    pHead-pStartfree = (char*)pHead + sizeof(Cookie);
　　    pHead-pEndfree   = (char*)pHead + pHead-iTotalsize;
　　    for(i=0 ; i NODENUMS ; i++)
　　    {
　　      pHead-sFreelistIndex[i]=0;
　　      pHead-uFreelist[i]=0;
　　      pHead-iUseNum[i]=0;
　　    }
　　  }
　　  static void PrintFreelistAndCookie()
　　  {
　　    int i,j;
　　    Obj* my_free_list;
　　    std::cout"Cookie info :"std::endl;
　　    std::cout"sizeof(struct Cookie) = "sizeof(Cookie)std::endl;
　　    std::cout"Totalsize     = "pHead-iTotalsizestd::endl;
　　    std::cout"UsedSize      = "int(pHead-pStartfree-(char*)pHead)std::endl;
　　    std::cout"FreepoolSize  = "int(pHead-pEndfree - pHead-pStartfree)std::endl;
　　    std::cout"Startall      = "&(pHead-pStartall)std::endl;
　　    std::cout"Startfree     = "&(pHead-pStartfree)std::endl;
　　    std::cout"Endfree       = "&(pHead-pEndfree)std::endl;
　　    std::cout"nFreelist info :"std::endl;
　　    for(i=0 ; iNODENUMS ; i++)
　　    {
　　      j=0;
　　      std::cout"iUseNum["i"] = "pHead-iUseNum[i]std::endl;
　　      std::cout"FreelistIndex["i"] = "pHead-sFreelistIndex[i]std::endl;
　　      my_free_list = pHead-uFreelist[i];
　　      if(my_free_list-M_client_data != 0)
　　      {
　　        while(my_free_list-M_client_data != 0)
　　        {
　　          j++;
　　          my_free_list = my_free_list-M_free_list_link;
　　        }
　　        std::cout"free_list["i"]; node counts="jstd::endl;
　　      }
　　    }
　　  }
　　  template class T1, class T2
　　  bool operator== (const MyAllocT1&,const MyAllocT2&) throw()
　　  {
　　    return true;
　　  }
　　  template class T1, class T2
　　  bool operator!= (const MyAllocT1&,const MyAllocT2&) throw()
　　  {
　　    return false;
　　  }
　　}
　　#endif /*MY_ALLOCATOR_H_*/
　　测试程序的源码如下：
　　
　　// MyStl.cpp : 定义控制台应用程序的入口点。
　　//
　　#include "stdafx.h"
　　#include map
　　#include vector
　　#include string
　　#include utility
　　#include iostream
　　#include "MyAlloc.h"
　　using namespace std;
　　int _tmain(int argc, _TCHAR* argv[])
　　{
　　  happyever ::InitShm();
　　  multimapstring,int,lessstring,happyever ::MyAllocstring  m;
　　  m.insert(make_pair(string("Harry"), 32));
　　  m.insert(make_pair(string("Mary"), 59));
　　  m.insert(make_pair(string("Roger"), 18));
　　  m.insert(make_pair(string("Nancy"), 37));
　　  m.insert(make_pair(string("Mary"), 23));
　　
　　  typedef multimapstring,int,lessstring,happyever ::MyAllocstring ::iterator Iter;
　　  for (Iter p = m.begin(); p != m.end(); p++)
　　  {
　　    cout  p-first  ","  p-second  endl;
　　  }
　　  Iter p = m.find("Harry");
　　  m.erase(p);
　　  /*p = m.find("Harry");
　　  cout  "Harry is: "  p-second  "."  endl;*/
　　
　　  for (Iter p = m.begin(); p != m.end(); p++)
　　  {
　　    cout  p-first  ","  p-second  endl;
　　  }
　　
　　  return 0;
　　}
　　以上程序在vs2005，vc6上测试通过。使用MinGW编译的时候只需要去掉vc的预编译头文件
　　#include "stdafx.h"
　　　　即可。　　以上程序只要稍微修改，就可以实现共享内存的治理，可以方便的使用标准库提供的容器。加上信号量的锁机制。　　以上为了学习而改写的SGI的stl二级分配算法实现的。以上代码存在一定的局限性。我另外完整实现了共享内存治理的STL标准的alloctor程序，使用posix信号量加锁。目前应用在aix的xlC编译环境下。因为源码涉及公司的商业秘密，所以不能公开。但基本上以上源码已经体现了自己治理内存的完整思路，供这方面需求的朋友一起学习研究用。

更多内容请看C/C++技术专题 C/C++进阶技术文档专题，或

来源:http://www.tulaoshi.com/n/20160219/1624574.html

上一篇：使用break与continue语句和for与continue语句
下一篇： Dreamweaver 4 简明教程(八、为网页增添互动效果3)

看过《为C++标准库容器写自己的内存分配程序》的人还看了以下文章更多>>

C++程序的异常处理技巧

标签：编程语言网络编程

处理 C++ 中的异常会在语言级别上碰到少许隐含限制，但在某些情况下，您可以绕过它们。学习各种利用异常的方法，您就可以生产更可靠的应用程序。保留异常

让C/C++图形程序独立运行

标签：编程语言网络编程

C/C＋＋语言提供了十分丰富的图形函数，图形函数文件为Graphics.h，使用图形函数前须先将屏幕设置为图形模式，C/C＋＋语言提供了下面的函数： void far initgraph(int far ＊GD,int far ＊GM,char ＊P); 其中，GD和GM分别表示图形驱动程序和图形模式，P指图形驱动程序所在的目录路径。图形驱动程序由Borland公司(对于Turbo C和Bo...

程序宝典：C++学习感想

标签：编程语言网络编程

在一些论坛上经常会看到一些各语言的优劣比较，知道自己所学语言的优劣也好，但是假如一味停留在这个层面就没有用了。任何语言都只是工具而已。重要的是使用工具的人！就我个人的经验来讲，真正处于业界搞开发的人都愿意使用成熟的、为自己所熟知的技术来完成工作。 !-- frame contents -- !-- /frame contents -- 而新手都喜欢用一...

C++的iostream标准库介绍(3)

标签：编程语言网络编程

C语言提供了格式化输入输出的方法，C++也同样，但是C++的控制符使用起来更为简单方便，在c++下有两中方法控制格式化输入输出。１.有流对象的成员函数。例如，下列程序以成员函数的方式控制输出的精度://程序作者:管宁 //站点:www.cndev-lab.com //所有稿件均有版权,如要转载,请务必闻名出处和作者 ...

C++的iostream标准库介绍(1)

标签：编程语言网络编程

我们从一开始就一直在利用C++的输入输出在做着各种练习，输入输出是由iostream库提供的，所以讨论此标准库是有必要的，它与C语言的stdio库不同，它从一开始就是用多重继续与虚拟继续实现的面向对象的层次结构，作为一个c++的标准库组件提供给程序员使用。 !-- frame contents -- !-- /frame contents -- iostream为内置类型类...

查看更多精彩>>