一、SGI STL配置器简介
如果要了解STL的实现,必须要了解空间配置器,因为整个STL的操作对象都放在容器之内,而容器一定需要配置空间以存放数据等资料。allocator叫做空间配置器而不是内存配置器,因为空间不一定是内存,也可以是磁盘或者其他辅助存储介质。可以写一个allocator直接向硬盘取空间。当然这里介绍的allocator配置的是内存。
二、SGI标准的空间配置器
其实SGI也定义了一个符合部分标准,名为allocator的配置器,但是它自己不使用,也不建议我们使用,主要原因是效率不佳。它只是把C++的操作符::operator new和::operator delete做了一层简单的封装而已。下面是代码,可以看出空间配置器的标准接口,提供了默认的构造器、复制、析构等接口。另外这里的SGI版本的allocator仅仅对底层的内存配置/释放行为(::operator new和::operator delete)做了一层简单的包装,没有效率上的强化。
#ifndef DEFALLOC_H
#define DEFALLOC_H
#include <new.h>
#include <stddef.h>
#include <stdlib.h>
#include <limits.h>
#include <iostream.h>
#include <algobase.h>
template <class T>
inline T* allocate(ptrdiff_t size, T*) {
set_new_handler(0);
T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));
if (tmp == 0) {
cerr << "out of memory" << endl;
exit(1);
}
return tmp;
}
template <class T>
inline void deallocate(T* buffer) {
::operator delete(buffer);
}
template <class T>
class allocator {
public:
typedef T value_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
pointer allocate(size_type n) {
return ::allocate((difference_type)n, (pointer)0);
}
void deallocate(pointer p) { ::deallocate(p); }
pointer address(reference x) { return (pointer)&x; }
const_pointer const_address(const_reference x) {
return (const_pointer)&x;
}
size_type init_page_size() {
return max(size_type(1), size_type(4096/sizeof(T)));
}
size_type max_size() const {
return max(size_type(1), size_type(UINT_MAX/sizeof(T)));
}
};
class allocator<void> {
public:
typedef void* pointer;
};
#endif
三、SGI特殊的空间配置器alloc
一般而言,我们所习惯的C++内存配置操作和释放操作是这样的:
class Foo{...};
Foo* pf = new Foo; //配置内存,然后构造对象
delete //将对象析构,释放内存
通常,C++中用new操作符来分配内存都包括两个阶段(如上):
(1)调用::operator new配置内存
(2)调用构造函数Foo::Foo()来构造对象内容
同理,delete操作也包括两个阶段:
(1)调用析构函数Foo::~Foo()将对象析构
(2)调用::operator delete释放内存
为了精密分工,SGI allocator将两个阶段分开:
内存配置操作由alloc:allocate负责,内存释放由alloc:deallocate负责;对象构造操作由::contructor()负责,对象析构由::destroy()负责。
配置器定义在头文件中,它里面又包括两个文件:
#include <stl_alloc.h> // 负责内存空间的配置和器释放
#include <stl_construct.h> // 负责对象的构造和析构
下图显示了其结构:
1、对象的建构和结构函数construct()和destroy()
下图显示了这两个函数的结构和功能。他们被包含在头文件stl_construct.h中。
函数construct()使用了定位new操作符,其源代码:
template <class T1, class T2>
inline void construct(T1* p, const T2& value) {
new (p) T1(value); // 定为new操作符placement new; 在指针p所指处构造对象
}
函数destroy则有两个版本。
第一个版本较简单,接受一个指针作为参数,直接调用对象的析构函数即可,其源代码:
template <class T>
inline void destroy(T* pointer) {
pointer->~T(); // 调用析构函数
}
第二个版本,其参数接受两个迭代器,将两个迭代器所指范围内的所有对象析构掉。而且,它采用了trivial编程技法(这里有介绍http://blog.csdn.net/mmshixing/article/details/51657168):依据元素的型别,判断其是否有trivial destructor(无用的析构函数)进行不同的处理。这也是为了效率考虑。因为如果每个对象的析构函数都是trivial的,那么调用这些毫无作用的析构函数会对效率造成影响。
下面看其源代码:
//destroy()第二个版本,接受两个迭代器。此函数设法找出元素的数值型别
//然后利用__type_trivial<>求取最适当措施。
Template <class ForwardInterator>
Inline void destroy(ForwardInterator first,ForwardInterator last, T*)
{
Typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;
__destroy_aux(first, last, trivial_destructor());
}
//下面是对__destroy_aux的重载,第三个参数分别为__true_type、__false_type
//如果元素的数值型别(value type)有non-trivial 函数
Template <class ForwardIterator>
Inline void
__destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) {
for( ; first < last ; ++first)
destroy(&*first); //对[first, last)范围的多有对象析构掉!
}
//如果元素的数值型别(value type)有trivial 函数
Template <class ForwardIterator>
Inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {}//什么也不做
2、空间的配置和释放,std::alloc
对象构造前的空间分配和析构后的空间释放,定义在头文件
template<class T, class Alloc>
class simple_alloc {
public:
static T *allocate(size_t n)
{ return 0 == n? 0 : (T*) Alloc::allocate(n * sizeof (T)); }
static T *allocate(void)
{ return (T*) Alloc::allocate(sizeof (T)); }
static void deallocate(T *p, size_t n)
{ if (0 != n) Alloc::deallocate(p, n * sizeof (T)); }
static void deallocate(T *p)
{ Alloc::deallocate(p, sizeof (T)); }
};
SGI STL容器全部是使用这个simple_alloc接口。
第一级和第二级配置器之间的关系如下图所示:
第一级和第二级配置器的包装接口和运用方式如下:
第一级配置器__malloc_alloc_template剖析
第一级配置器直接使用malloc(),free(),realloc()等C函数执行实际的内存配置、释放、重配置操作,并实现出类似C++ new handler机制。它有独特的out-of-memory内存处理机制:在抛出std::bad_alloc异常之前,调用内存不足处理例程尝试释放空间,如果用户没有定义相应的内存不足处理例程,那么还是会抛出异常。详细实现见函数oom_malloc(),oom_realloc()。
内存不足处理例程保存在函数指针__malloc_alloc_oom_handler里面。内存不足处理函数,由程序猿自己通过new-handler自己设计,在头文件中这样定义
typedef void (*new_handler)();
这个在《effctive c++》第二版条款7中有详细说明。
new_handler set_new_handler(new_handler p) throw();
下面列出第一级配置器__malloc_alloc_template代码:
#if 0
# include <new>
# define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(__THROW_BAD_ALLOC)
# include <iostream.h>
# define __THROW_BAD_ALLOC cerr << "out of memory" << endl; exit(1)
#endif
// malloc-based allocator. 通常比稍后介绍的 default alloc 速度慢,
//一般而言是 thread-safe,并且对于空间的运用比较高效(efficient)。
//以下是第一级配置器。
//注意,无「template 型别参数」。至于「非型别参数」inst,完全没派上用场。
template <int inst>
class __malloc_alloc_template {
private:
//以下都是函式指标,所代表的函式将用来处理内存不足的情况。
// oom : out of memory.
static void *oom_malloc(size_t);
static void *oom_realloc(void *, size_t);
static void (* __malloc_alloc_oom_handler)();
public:
static void * allocate(size_t n)
{
void *result =malloc(n);//第一级配置器直接使用 malloc()
// 以下,无法满足需求时,改用 oom_malloc()
if (0 == result) result = oom_malloc(n);
return result;
}
static void deallocate(void *p, size_t /* n */)
{
free(p); //第一级配置器直接使用 free()
}
static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)
{
void * result =realloc(p, new_sz);//第一级配置器直接使用 rea
// 以下,无法满足需求时,改用 oom_realloc()
if (0 == result) result = oom_realloc(p, new_sz);
return result;
}
//以下模拟 C++的 set_new_handler(). 换句话说,你可以透过它,
//指定你自己的 out-of-memory handler
static void (* set_malloc_handler(void (*f)()))()
{
void (* old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = f;
return(old);
}
};
// malloc_alloc out-of-memory handling
//初值为 0。有待客端设定。
template <int inst>
void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;
template <int inst>
void * __malloc_alloc_template<inst>::oom_malloc(size_t n)
{
void (* my_malloc_handler)();
void *result;
for (;;) {
//不断尝试释放、配置、再释放、再配置…
my_malloc_handler = __malloc_alloc_oom_handler;
if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }
(*my_malloc_handler)();//呼叫处理例程,企图释放内存。
result = malloc(n); //再次尝试配置内存。
if (result) return(result);
}
}
template <int inst>
void * __malloc_alloc_template<inst>::oom_realloc(void *p, size_t n)
{
void (* my_malloc_handler)();
void *result;
for (;;) { //不断尝试释放、配置、再释放、再配置…
my_malloc_handler = __malloc_alloc_oom_handler;
if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }
(*my_malloc_handler)();//呼叫处理例程,企图释放内存。
result = realloc(p, n);//再次尝试配置内存。
if (result) return(result);
}
}
//注意,以下直接将参数 inst指定为 0。
typedef __malloc_alloc_template<0> malloc_alloc;
以上为STL空间配置器及第一级配置器__malloc_alloc_template详细内容,大部分是《STL源码剖析》这本书上的,自己捋一下,思路更加清晰。
文章浏览阅读565次。求链式线性表的倒数第K项给定一系列正整数,请设计一个尽可能高效的算法,查找倒数第K个位置上的数字。输入格式:输入首先给出一个正整数K,随后是若干非负整数,最后以一个负整数表示结尾(该负数不算在序列内,不要处理)。输出格式:输出倒数第K个位置上的数据。如果这个位置不存在,输出错误信息NULL。输入样例:4 1 2 3 4 5 6 7 8 9 0 -1输出样例:7标程 单链表版#include<map>#include<list>#include<cm_c语言 求链式线性表的倒数第k项 分数 12 作者 ds课程组 单位 浙江大学 给定一系列
文章浏览阅读1.4k次。YOLOX 是旷视开源的高性能检测器。旷视的研究者将解耦头、数据增强、无锚点以及标签分类等目标检测领域的优秀进展与 YOLO 进行了巧妙的集成组合,提出了 YOLOX,不仅实现了超越 YOLOv3、YOLOv4 和 YOLOv5 的 AP,而且取得了极具竞争力的推理速度。其中YOLOX-L版本以 68.9 FPS 的速度在 COCO 上实现了 50.0% AP,比 YOLOv5-L 高出 1.8% AP!还提供了支持 ONNX、TensorRT、NCNN 和 Openvino 的部署版本,本文将详细介绍如_yolox 刀具
文章浏览阅读2.9k次,点赞27次,收藏45次。统一建模语言UML类图是一种用于描述系统结构的图形化工具。它以类和对象为基础,主要用于表示系统中的类、接口、继承关系、关联关系等元素,以及它们之间的静态结构和关系。在本文中,将深入介绍UML类图的基本元素关系类型以及如何创建一个简单而有效的类图。类图以反映类的结构(属性、操作)以及类之间的关系为主要目的,描述了软件系统的结构,是一种静态建模方法。类图用来描述系统中有意义的概念,包括具体的概念、抽象的概念、实现方面的概念等,是对现实世界中事物的抽象。_uml类图
文章浏览阅读4.2k次,点赞4次,收藏26次。pandas-datareader背景介绍当熟悉了Pandas的两个主要数据结构:Series和DataFrame之后,我们就可以使用pandas-datareader进行金融财经数据的导入和初步分析了。pandas-datareader是基于Python的专门从一系列的公开在线数据库获取数据的工具库,该接口在urllib3库基础上实现了以客户端身份访问在线数据库的各类金融财经股票数据。相关参考网站官网官方文档GIT源码安装pandas-datareader可以使用标准的pip进_pandas-datareader
文章浏览阅读860次。原标题:计算机专业的职业发展方向有哪些很多人都知道计算机是最近几年 比较热门的专业之一,其中薪资高待遇好是很多年轻人加入该行业的原因,但还有一些人会担心计算机专业的未来,毕竟这股“热潮”在互联网行业大裁员中变成让互联网人感觉压力山大的“寒潮”。究竟计算机的未来如何,小编不敢吹嘘说很好,但我相信计算机行业的未来肯定不会差,而且对计算机人才会越来越重视。 我们经常会听到有人说程序员是吃青春饭的,真是这..._机算机职业发展
文章浏览阅读3.2k次,点赞4次,收藏27次。一、基本思想用指向早期曾经出现过的字符串的指针来表示当前被编码的字符串,如:二、LZ77算法算法伪码:示意图:举例:三、C\C++实现#include <iostream>#include <vector>#include <string>using namespace std;struct code { int off; i..._lz77编码例题详解
文章浏览阅读6k次,点赞6次,收藏30次。数据可视化——Matlab平台gramm工具箱绘制散点相关图概述:基于matlab平台的gramm工具箱绘制散点相关图使用的工具箱:gramm。gramm工具箱使得matlab平台的图形绘制能力更加强大,绘制出的图形更美观,同时,绘制图形需要设置的参数相对较少。gramm工具箱可在以下链接中下载:https://github.com/piermorel/gramm将下载好的工具箱解压之后,通..._gramm工具箱画图
文章浏览阅读3.9w次,点赞33次,收藏175次。一 Rxjava3简介RxJava是响应式编程(Reactive Extensions)的java实现,它基于观察者模式的实现了异步编程接口。Rxjava 3.x 的github官网RxJava2将被支持到2021年2月28日,错误的会同时在2.x和3.x修复,但新功能只会在3.x上添加。Rxjava 3.0的一些改变:官方WikiRxjava 3.x 文档可以在官方javad..._rxjava
文章浏览阅读124次。public class ExcelTest {/*** @param args*/public static void main(String[] args) throws IOException {try {HSSFWorkbook wb = new HSSFWorkbook();HSSFSheet sheet = wb.createSheet("new sheet");HSSFCellS..._hssfrow.setcellstyle
文章浏览阅读1.5k次。该篇内容由个人博客点击跳转同步更新!转载请注明出处!前言最近有一个需求需要频繁调用xx接口,但这个接口调用次数一多就会给你禁掉,而且一禁就是禁一天的那种,只能通过界面模拟用户操作抓取数据包,然后单独对这些数据包进行处理具体步骤首先看下需要格式化的数据包长什么样 数据包这就是完整的一个数据包,网上基本都是格式化json数据包的,但返回的内容中还包含了头信息等所以不能简单的通过json来格式化,..._python解析http.client.httpresponse
文章浏览阅读1.7k次。uni-app修改button按钮样式_uniapp按钮样式怎么改
文章浏览阅读200次。Flume配置安装Flume是Cloudera提供的一个高可用的,高可靠的、分布式的海量日志采集、聚合和传输的系统,Flume支持在日志系统中定制各类数据发送方,用于收集数据;同时,Flume提供对数据进行简单处理,并写到各种数据接受方(可定制)的能力。Flume特点如下:Flume可以高效率的将多个网站服务器中收集的日志信息存入HDFS/HBase中Flume可以将从多个服务器中获取的数..._修改文件,配置文件flume-env.sh