C++标准库笔记四:用户定义分配器
下面的代码用gcc version 3.4.5 (mingw-vista special r3)测试。
注意,代码摘自《C++程序设计语言(特别版)》(略加修改),
里面的内存池和分配器实现都不是完整的。
// 编译命令行:
// g++ test008.cpp
//《C++程序设计语言(特别版)》
// 19.4.2 一个用户定义分配器
//演示标准库分配器allocator接口的简单实现
#include <cstddef>
#include <vector>
#include <iostream>
#include <iterator>
//class Pool定义一个简单接口的小内存块内存池
//这个内存池一次只能分配恒定大小的小内存块(由构造函数参数指定)
class Pool
{
private:
//用于分配和释放内存的链表
//比Chunk的粒度小,多个Link分割一个Chunk
//分配前Link的next域用于计算下一个分配位置
//分配后Link只是void*内存块的头部
struct Link
{
Link *next;
};
// 底层内存分配区的分区块
// 一个Pool内有多个依次链接的Chunk
//每个Chunk被多个Link分割成更小的内存块
//(但所有Link的排列次序不一定依照其所在Chunk块的排列次序),
//但因为内存是连续的,所以在增量分配和全体释放时速度会较快
struct Chunk
{
//让一个Chunk不超过8K且略小于8K
enum { SIZE = 8 * 1024 - 16 };
unsigned char mem[SIZE];
Chunk *next; //next应该不会超过16个字节
};
//多个Chunk前后组成一个链表(好像一个栈)
Chunk *chunks;
//每次alloc()返回的内存块最大大小,
//但不能比sizeof(Link)小,也不能比Chunk::SIZE大
const unsigned int esize;
//当前空闲Chunk块内的空闲Link头部
Link *head;
//禁用默认的复制构造函数和复制赋值,
//所以这里不需要定义方法体
private:
Pool(Pool& sz);
void operator=(Pool&);
private:
void grow();
public:
Pool(unsigned int n);//指定每次alloc()返回的内存块大小
~Pool();
void* alloc(); //不需要指定内存块大小(在构造函数中指定)
void free(void* b);
};
//从head链表的头部取出一个Link
//如果空闲Chunk块用完,需要分配新的Chunk块,
//然后用Link链表分割这个新的空闲Chunk块。
inline void* Pool::alloc()
{
if (head == 0)
{
grow();
}
Link *p = head;
head = p->next;
std::cout << "Pool::alloc(): p == " << p << ", head == " << head << std::endl;
return p;
}
//把要释放的b放回head链表的头部
inline void Pool::free(void* b)
{
Link* p = static_cast<Link*>(b);
p->next = head;
std::cout << "Pool::free(): p == " << p << ", head == " << head << std::endl;
head = p;
}
Pool::Pool(unsigned int sz)
: esize(sz < sizeof(Link) ? sizeof(Link) : sz)
{
head = 0;
chunks = 0;
}
Pool::~Pool()
{
Chunk *n = chunks;
while (n)
{
Chunk *p = n;
n = n->next;
delete p;
}
}
//增量分配内存
//虽然Link*所在的小内存块是连续的,
//但alloc的分配次序不一定是连续的
//(因为free()可能放回旧的内存块)
void Pool::grow()
{
Chunk *n = new Chunk();
n->next = chunks;
chunks = n;
std::cout << "Pool::grow(): esize == " << esize << std::endl;
const int nelem = Chunk::SIZE / esize;
unsigned char *start = n->mem;
unsigned char *last = &start[(nelem - 1) * esize];
for (unsigned char *p = start; p < last; p += esize)
{
reinterpret_cast<Link*>(p)->next = reinterpret_cast<Link*>(p + esize);
}
reinterpret_cast<Link*>(last)->next = 0; //见alloc()的if (head == 0)
head = reinterpret_cast<Link*>(start);
}
//template Pool_alloc把class Pool适配到C++标准库的分配器接口
//不完整,因为有些接口没有实现,而有些接口只实现部分功能
template<class T>
class Pool_alloc
{
private:
static Pool mem; //全局,以提高效率
public:
typedef T value_type;
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;
Pool_alloc();
T* allocate(size_type n, void*);
void deallocate(pointer p, size_type n);
};
//构造静态的mem域
//因为Pool只能分配固定大小的小内存块,
//而且Pool_alloc没有实现rebind方法
//所以这里指定每次分配的连续内存区都必须是sizeof(T) * 128,
//虽然造成浪费,但确保分配的内存是连续的。
//没有超过Chunk块的8K上限,所以是安全的。
template <class T>
Pool Pool_alloc<T>::mem(sizeof(T) * 128);
template <class T>
Pool_alloc<T>::Pool_alloc()
{
}
template<class T>
T* Pool_alloc<T>::allocate(size_type n, void* = 0)
{
if (n <= 128)
{
void *p = mem.alloc();
std::cout << "allocate : " << n << ", " << p << std::endl;
return static_cast<T*>(p);
} else {
//TODO:
std::cout << "allocate : " << n << std::endl;
throw "allocate error"; //出错
}
}
template<class T>
void Pool_alloc<T>::deallocate(pointer p, size_type n)
{
if (n <= 128)
{
std::cout << "deallocate : " << n << ", " << p << std::endl;
mem.free(p);
return;
} else {
//TODO:
std::cout << "deallocate : " << n << std::endl;
throw "deallocate error"; //出错
}
}
int main(int argc, const char *argv[])
{
{
std::vector<int> V1;
V1.push_back(1);
V1.push_back(2);
V1.push_back(3);
V1.push_back(4);
std::cout << "V1:"<< std::endl;
std::copy(V1.begin(), V1.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
}
{
std::cout << "==================="<< std::endl;
try
{
std::vector< int, Pool_alloc<int> > V2;
std::cout << "V2.push_back(1);" << std::endl;
V2.push_back(1);
std::cout << "V2.push_back(2);" << std::endl;
V2.push_back(2);
std::cout << "V2.push_back(3);" << std::endl;
V2.push_back(3);
V2.push_back(4);
std::cout << "V2:"<< std::endl;
std::copy(V2.begin(), V2.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
}
catch (const char *&str)
{
std::cout << str << std::endl;
}
}
return 0;
}
/**
运行结果:
$ g++ -g test008.cpp
$ ./a.exe
V1:
1 2 3 4
===================
V2.push_back(1);
Pool::grow(): esize == 512
Pool::alloc(): p == 0x3e4d68, head == 0x3e4f68
allocate : 1, 0x3e4d68
V2.push_back(2);
Pool::alloc(): p == 0x3e4f68, head == 0x3e5168
allocate : 2, 0x3e4f68
deallocate : 1, 0x3e4d68
Pool::free(): p == 0x3e4d68, head == 0x3e5168
V2.push_back(3);
Pool::alloc(): p == 0x3e4d68, head == 0x3e5168
allocate : 4, 0x3e4d68
deallocate : 2, 0x3e4f68
Pool::free(): p == 0x3e4f68, head == 0x3e5168
V2:
1 2 3 4
deallocate : 4, 0x3e4d68
Pool::free(): p == 0x3e4d68, head == 0x3e4f68
*/
分享到:
相关推荐
【Visual C++】游戏编程笔记四:透明动画实现 配套代码
C++Primer中文第三版(C++从入门到精通)第一章的读书笔记,主要是C++程序、预处理器指示符、iostream库等的基础知识点读书笔记。
C++标准库实现简介 C++标准库是一组C++模板类,提供了通用的编程数据结构和函数,如链表、堆、数组、算法、迭代器等C++组件。C ++标准库包含了C标准库,并在C++标准中进行了定义。 C++编译器开发厂商根据C++标准委员会...
《C++标准库——自学教程与参考手册(第2版)英文版》涵盖了所有的新的C++11库组件,包括:并发性、分数计算、时钟和计时器、元组、新STL容器、新STL算法、新智能指针、新local方面、随机数字和分布、类型特性和通用...
[超越C++标准库:Boost库导论].(美)卡尔森.著.张杰良.译.扫描版.pdf
c++标准库第二版高清影印版pdf,侯捷译,230M,c++程序员必看
更明确地说,《C++标准程序库:自修教程与参考手册》将焦点放在标准模板库身上,检验其中的容器、迭代器、仿函数和算法。你还可以找到特殊容、字串、数值类别、国际化议题、IOStream。每一个元素都有深刻的呈现,包括...
C++标准程序库自修参考手册
C++标准库——自学教程与参考手册(第2版)英文版.pdf
它是标准c++所支持的标准库头文件,包括标准库所支持的。
Boost程序库完全开发指南:深入C++“准”标准库+Boost程序库完全开发指南:深入C++“准”标准库+Boost程序库完全开发指南:深入C++“准”标准库+Boost程序库完全开发指南:深入C++“准”标准库+Boost程序库完全开发...
超越C++标准库:Boost库导论 美)卡尔森.著.张杰
《C++标准程序库:自修教程与参考手册》PDF 中文 The C++ Standard Library - A Tutorial and Reference CHM 英文原版
大名鼎鼎的Nicolai M. Josuttis著,侯捷/孟岩翻译,初高级C++程序员的必备参考书
QT 4 c++ 笔记 QT 4 c++ 笔记 QT 4 c++ 笔记 QT 4 c++ 笔记 QT 4 c++ 笔记 QT 4 c++ 笔记
C++标准库源代码
C++程序员案前必备 C++ Standard Library provides a set of common classes and interfaces that greatly extend the core C++ language. The library, however, is not self-explanatory. To make full use of its...
C++标准程序库—自修教程与参考手册 《C++标准程序库自修教程与参考手册》是2002年华中科技大学出版社出版的图书。 [1] 书 名 C++标准程序库:自修教程与参考手册 ISBN 7560927823 页 数 800页 出版社 华中科技...
C++学习笔记C++学习笔记C++学习笔记C++学习笔记C++学习笔记
C++标准库代码,都是分开的程序文件,可供学习参考,很完整,对深入学习C++很有帮助!