STL源码解析之vector源码(一)
前置条件
- 由于Visual Studio版本中带的STL源码中有大量的宏定义和非标准, 丑拒.
- 由于SGI STL是权威实现, 本文仅跟踪SGI STL
- SGI STL版本3.3, 可在下方下载.
代码跟踪
默认构造函数
首先, 我们找到 stl_vector.h 文件, 可以找到 vector 类.
vector类的定义如下(我直接写上注释):
// vector是一个模板类, 有两个模板参数, 一个类型_Tp, 一个分配器 _Alloc
// 分配器_Alloc 有个默认的值 __STL_DEFAULT_ALLOCATOR(_Tp)
// 这个__STL_DEFAULT_ALLOCATOR 是一个宏定义, 如下:
# ifndef __STL_DEFAULT_ALLOCATOR
# ifdef __STL_USE_STD_ALLOCATORS
# define __STL_DEFAULT_ALLOCATOR(T) allocator< T >
# else
# define __STL_DEFAULT_ALLOCATOR(T) alloc
# endif
# endif
// 意思是如果没定义宏 __STL_USE_STD_ALLOCATORS 就用 alloc, 否则用 allocator<T>
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
// vector类protected继承自 _Vector_base 类
class vector : protected _Vector_base<_Tp, _Alloc>
{
// 依赖 生成一个static变量
__STL_CLASS_REQUIRES(_Tp, _Assignable);
private:
// 简化类型名称为 _Base
typedef _Vector_base<_Tp, _Alloc> _Base;
public:
// ====== 以下都是 STL标准 要求的, 必须有 ======
// 定义 value_type, 其实就是我们自己传递的 _Tp
typedef _Tp value_type;
// 将我们的 _Tp* 定义为 pointer
typedef value_type* pointer;
// 定义我们的 const _Tp* 定义为 const_pointer
typedef const value_type* const_pointer;
// 将 _Tp* 定义为 iterator
typedef value_type* iterator;
// 将 const _Tp* 定义为 iterator
typedef const value_type* const_iterator;
// 将 _Tp& 定义为 reference
typedef value_type& reference;
// 将 const _Tp& 定义为 const_reference
typedef const value_type& const_reference;
// 将 size_t 定义为 size_type
typedef size_t size_type;
// 将 ptrdiff_t 定义为 difference_type
// ptrdiff_t 是 一个 int
typedef ptrdiff_t difference_type;
// 注意此处的typedef后边跟了一个typename
// 因为如果不加typename的话, 编译器就会认为 _Base::allocator_type 是本类中的一个静态成员对象
// 而实际上, 它并不是, 我们只是需要 _Base 中的某个, 所以要加typename
// 这是来定义我们的 allocator_type, 分配器类型
typedef typename _Base::allocator_type allocator_type;
allocator_type get_allocator() const { return _Base::get_allocator(); }
// 如果有偏特化定义
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
// 定义常量反向迭代器
typedef reverse_iterator<const_iterator> const_reverse_iterator;
// 定义反向迭代器
typedef reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
typedef reverse_iterator<const_iterator, value_type, const_reference,
difference_type> const_reverse_iterator;
typedef reverse_iterator<iterator, value_type, reference, difference_type>
reverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
// ====== 以上都是 STL标准 要求的, 必须有 ======
protected:
// 如果有命名空间 就进行using指令
#ifdef __STL_HAS_NAMESPACES
// 我们知道 _Base 是一个 typedef的东西, 它其实是 _Vector_base<_Tp, _Alloc>
using _Base::_M_allocate;
using _Base::_M_deallocate;
using _Base::_M_start;
using _Base::_M_finish;
using _Base::_M_end_of_storage;
#endif /* __STL_HAS_NAMESPACES */
protected:
// 两个成员模板, 等用到的时候我们在细看
void _M_insert_aux(iterator __position, const _Tp& __x);
void _M_insert_aux(iterator __position);
public:
// ......
// 省略....
// ......
};
我们从类中, 得到vector的默认构造函数:
explicit vector(const allocator_type& __a = allocator_type())
: _Base(__a) {}我们来分析一下这个构造函数:
- allocator_type 是一个类型, 是 _Base::alloctor_type 的类型
- 这个构造函数拥有默认实参
- 默认实参就是 allocator_type 的默认构造函数出来的对象
- 它会首先去调用 _Base 的构造, 传递了我们的分配器.
我们在看来一下 _Base 类.
// 类模板
template <class _Tp, class _Alloc>
class _Vector_base {
public:
// 将 _Alloc 定义为 allocator_type
typedef _Alloc allocator_type;
// 返回一个默认的分配器
allocator_type get_allocator() const { return allocator_type(); }
// 构造函数
// 必须传递一个 分配器 过来
_Vector_base(const _Alloc&)
: _M_start(0), _M_finish(0), _M_end_of_storage(0) {}
// 构造函数
// 按照指定的空间大小和指定的分配器分配内存
_Vector_base(size_t __n, const _Alloc&)
: _M_start(0), _M_finish(0), _M_end_of_storage(0)
{
// 我们注意到, 这里有一个函数是 _M_allocate
_M_start = _M_allocate(__n);
_M_finish = _M_start;
_M_end_of_storage = _M_start + __n;
}
// 析构函数
~_Vector_base()
{
// 这里又有一个 _M_deallocate 函数
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
}
protected:
// 可被继承的成员变量, 是我们指定类型的指针类型
// 开始
_Tp* _M_start;
// 结束
_Tp* _M_finish;
// 空间结尾
_Tp* _M_end_of_storage;
// 定义一个 分配器
typedef simple_alloc<_Tp, _Alloc> _M_data_allocator;
// 这个函数, 可以看到, 是调用上面我们定义的分配器
// 来进行allocate方法的操作
_Tp* _M_allocate(size_t __n)
{ return _M_data_allocator::allocate(__n); }
// 调用我们上面定义的分配器
// 来进行deallocate方法的操作
void _M_deallocate(_Tp* __p, size_t __n)
{ _M_data_allocator::deallocate(__p, __n); }
};
根据以上分析, 我们可以知道, 在我们的 _Base 类中, 有分配内存和回收内存的两个方法.
分配器
在我们的 _Base 类中, 我们知道存在 分配内存 和 释放内存 两个方法, 这两个方法存在于 simple_alloc 这个类中.
这个类位于 stl_alloc.h 中.
所有的SGI STL的内存管理函数, 都在 stl_alloc.h 中定义.
它只负责内存的分配和释放, 不负责元素的构造和析构.
它的本质就是operator new 和 operator delete 的操作.
我们看一看这个类
// 类模板
template<class _Tp, class _Alloc>
class simple_alloc {
public:
// 静态方法 分配指定大小 __n 个内存
static _Tp* allocate(size_t __n)
{ return 0 == __n ? 0 : (_Tp*) _Alloc::allocate(__n * sizeof (_Tp)); }
// 静态方法, 分配一个_Tp类型的内存
static _Tp* allocate(void)
{ return (_Tp*) _Alloc::allocate(sizeof (_Tp)); }
// 静态方法, 释放从 __p 处 指定 __n 大小的内存
static void deallocate(_Tp* __p, size_t __n)
{ if (0 != __n) _Alloc::deallocate(__p, __n * sizeof (_Tp)); }
// 静态方法, 释放 __p 的指针
static void deallocate(_Tp* __p)
{ _Alloc::deallocate(__p, sizeof (_Tp)); }
};经过这个简单的类, 我们可以知道, 我们的allocate和deallocate都来自我们的 _Alloc
而这个是我们进行指定的, 我们在回过头去看一下调用我们 simple_alloc 类方法的地方:
// .......
// 定义一个 分配器
typedef simple_alloc<_Tp, _Alloc> _M_data_allocator;
// 这个函数, 可以看到, 是调用上面我们定义的分配器
// 来进行allocate方法的操作
_Tp* _M_allocate(size_t __n)
{ return _M_data_allocator::allocate(__n); }
// 调用我们上面定义的分配器
// 来进行deallocate方法的操作
void _M_deallocate(_Tp* __p, size_t __n)
{ _M_data_allocator::deallocate(__p, __n); }
// .......
可以看到, 我们的 _Alloc 来自于我们的指定类型.
我们溯源而去, 发现我们的 _Alloc 是在vector进行构造的时候
如果我们没有传递, 就是我们默认的 __STL_DEFAULT_ALLOCATOR(_Tp)
还记得我们的这个宏是什么吗?
在定义 __STL_USE_STD_ALLOCATORS 的时候, 就是 allocator< T >, 否则就是 alloc.
我们现在没有定义 __STL_USE_STD_ALLOCATORS, 所以我们去看一下 alloc
template <bool threads, int inst>
class __default_alloc_template {
private:
// Really we should use static const int x = N
// instead of enum { x = N }, but few compilers accept the former.
#if ! (defined(__SUNPRO_CC) || defined(__GNUC__))
// 对齐位数
enum {_ALIGN = 8};
// 最大分配字节
enum {_MAX_BYTES = 128};
// 可最多分配几次
enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN
# endif
// 内存对齐
static size_t
_S_round_up(size_t __bytes)
{ return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }
__PRIVATE:
// 一个联合体, 用来形成一个"链表", 存储内存池的内存
union _Obj {
union _Obj* _M_free_list_link;
char _M_client_data[1]; /* The client sees this. */
};
private:
# if defined(__SUNPRO_CC) || defined(__GNUC__) || defined(__HP_aCC)
static _Obj* __STL_VOLATILE _S_free_list[];
// Specifying a size results in duplicate def for 4.1
# else
static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS];
# endif
// 获得可用内存的下标
static size_t _S_freelist_index(size_t __bytes) {
return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
}
// Returns an object of size __n, and optionally adds to size __n free list.
static void* _S_refill(size_t __n);
// Allocates a chunk for nobjs of size size. nobjs may be reduced
// if it is inconvenient to allocate the requested number.
// 二级分配器 内存池的分配
// 参数1 大小 参数2 nObjs, 对象个数, 调用的时候 nObjs默认 = 20
static char* _S_chunk_alloc(size_t __size, int& __nobjs)
// 如下代码 是我从实现处贴过来的, 本身这里是没有这段代码的
// 但是这是一个很经典的内存池, 可以进行学习
{
char* __result;
// 计算待分配的总大小
size_t __total_bytes = __size * __nobjs;
// 未分配的内存池的大小
size_t __bytes_left = _S_end_free - _S_start_free;
// 如果未分配的内存池的大小 >= 待分配的总大小
if (__bytes_left >= __total_bytes) {
// 空间足够 直接返回内存地址
__result = _S_start_free;
_S_start_free += __total_bytes;
return(__result);
// 如果未分配的内存池的大小 < 待分配的总大小, 但是 >= 需要分配的一个元素的大小
// 即 内存池可以分配一个元素出来
} else if (__bytes_left >= __size) {
// 求出可以分配的元素个数
__nobjs = (int)(__bytes_left/__size);
// 在算出可以分配的元素所占用的总大小
__total_bytes = __size * __nobjs;
// 将空闲内存池地址给返回
__result = _S_start_free;
// 置内存池的利用状态
_S_start_free += __total_bytes;
return(__result);
// 连一个元素都分配不出了
} else {
// 计算出所需要多少空间
size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
// Try to make use of the left-over piece.
// 尝试利用剩下的一小块内存池
// 如果还有空闲内存池
if (__bytes_left > 0) {
// 将头指向剩余空间地址
_Obj* __STL_VOLATILE* __my_free_list =
_S_free_list + _S_freelist_index(__bytes_left);
((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
*__my_free_list = (_Obj*)_S_start_free;
}
// 开始进行malloc的内存分配
_S_start_free = (char*)malloc(__bytes_to_get);
// 如果分配失败了
if (0 == _S_start_free) {
size_t __i;
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __p;
// Try to make do with what we have. That can't
// hurt. We do not try smaller requests, since that tends
// to result in disaster on multi-process machines.
// 应该就是重新遍历内存池, 找到一个空闲的内存块然后进行操作.
// 不是特别确定
for (__i = __size;
__i <= (size_t) _MAX_BYTES;
__i += (size_t) _ALIGN) {
// 计算一个 __size 的内存池空间地址
__my_free_list = _S_free_list + _S_freelist_index(__i);
// 解引用这个地址
__p = *__my_free_list;
// 如果这个地址是有效的
if (0 != __p) {
// 重定位内存池分配地址
*__my_free_list = __p -> _M_free_list_link;
// 做好内存池的各个参数
_S_start_free = (char*)__p;
_S_end_free = _S_start_free + __i;
// 递归, 重新进行分配
return(_S_chunk_alloc(__size, __nobjs));
// Any leftover piece will eventually make it to the
// right free list.
// 任何剩下的内存片段最终都会使其成为正确的可用内存池列表
}
}
// 如果一个循环完成, 都没有进行重新分配
_S_end_free = 0; // In case of exception. 例外的情况
// 调用一级分配器
_S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
// This should either throw an
// exception or remedy the situation. Thus we assume it
// succeeded.
// 这应该抛出异常或补救这种情况。 因此，我们假设它成功了。
}
_S_heap_size += __bytes_to_get;
_S_end_free = _S_start_free + __bytes_to_get;
return(_S_chunk_alloc(__size, __nobjs));
}
}
// Chunk allocation state. 内存池分配状态
// 空闲内存池开始的指针
static char* _S_start_free;
// 空闲内存池结束的指针
static char* _S_end_free;
// 内存大小
static size_t _S_heap_size;
# ifdef __STL_THREADS
static _STL_mutex_lock _S_node_allocator_lock;
# endif
// It would be nice to use _STL_auto_lock here. But we
// don't need the NULL check. And we do need a test whether
// threads have actually been started.
class _Lock;
friend class _Lock;
class _Lock {
public:
_Lock() { __NODE_ALLOCATOR_LOCK; }
~_Lock() { __NODE_ALLOCATOR_UNLOCK; }
};
public:
/* __n must be > 0 */
// 内存分配
static void* allocate(size_t __n)
{
void* __ret = 0;
// 如果需要分配的内存 > 128Byte, 就去调用一级分配器(malloc)
if (__n > (size_t) _MAX_BYTES) {
__ret = malloc_alloc::allocate(__n);
}
// 否则进行内存池的分配
else {
// 找到当前内存池的空闲的首地址
_Obj* __STL_VOLATILE* __my_free_list
= _S_free_list + _S_freelist_index(__n);
// Acquire the lock here with a constructor call.
// This ensures that it is released in exit or during stack
// unwinding.
# ifndef _NOTHREADS
/*REFERENCED*/
_Lock __lock_instance;
# endif
// 将得到的空闲地址进行判定
_Obj* __RESTRICT __result = *__my_free_list;
// == 0 说明没有足够的内存池了 开始调用 _S_refill来进行重新分配
if (__result == 0)
__ret = _S_refill(_S_round_up(__n));
// 分配成功了 返回内存地址
else {
*__my_free_list = __result -> _M_free_list_link;
__ret = __result;
}
}
return __ret;
};
/* __p may not be 0 */
// 释放空间
static void deallocate(void* __p, size_t __n)
{
// 如果是 > 128Byte 的内存空间释放, 直接调用一级内存分配器进行释放
if (__n > (size_t) _MAX_BYTES)
malloc_alloc::deallocate(__p, __n);
// 否则进行内存池的内存释放
else {
_Obj* __STL_VOLATILE* __my_free_list
= _S_free_list + _S_freelist_index(__n);
_Obj* __q = (_Obj*)__p;
// acquire lock
# ifndef _NOTHREADS
/*REFERENCED*/
_Lock __lock_instance;
# endif /* _NOTHREADS */
// 直接将 __p 的空间加入空闲列表中
__q -> _M_free_list_link = *__my_free_list;
*__my_free_list = __q;
// lock is released here
}
}
// 重新分配
static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz);
} ;
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;可以看到, alloc分为两级, 二级分配器就是SGI实现的一个内存池
而我们的一级分配器, 本质上是我们的 __default_alloc_template.
我们继续跟踪其中的 allocate 和 deallocate 函数, 可以看到,
它们调用的是 malloc_alloc 类的函数, 我们继续跟入 malloc_alloc
template <int __inst>
class __malloc_alloc_template {
private:
static void* _S_oom_malloc(size_t);
static void* _S_oom_realloc(void*, size_t);
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
static void (* __malloc_alloc_oom_handler)();
#endif
public:
static void* allocate(size_t __n)
{
void* __result = malloc(__n);
if (0 == __result) __result = _S_oom_malloc(__n);
return __result;
}
static void deallocate(void* __p, size_t /* __n */)
{
free(__p);
}
static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
{
void* __result = realloc(__p, __new_sz);
if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
return __result;
}
static void (* __set_malloc_handler(void (*__f)()))()
{
void (* __old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = __f;
return(__old);
}
};
// 一些特化已经省略.....
typedef __malloc_alloc_template<0> malloc_alloc;
此时, 我们知道, alloc::deallocate 是调用的free函数.
而我们的 alloc:allocate 调用的是 _S_oom_malloc
_S_oom_malloc 是一个内部使用的非暴露的函数, 我们找到定义:
template <int __inst>
void*
__malloc_alloc_template<__inst>::_S_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);
}
}
可以看到, 最核心的是调用了 malloc 函数.
根据我们的分析, 我们重新回到 vector 的构造函数.
我们知道了, 当我们在进行 vector 的初始化的时候, 会根据我们传递的类型
然后使用我们的分配器进行空间的分配, 这样, 一个 vector 对象就构造完毕了.
其他构造函数
在上面, 我们跟踪了默认构造函数, 我们在来看另外的构造函数:
vector(size_type __n, const _Tp& __value,
const allocator_type& __a = allocator_type())
: _Base(__n, __a)
{ _M_finish = uninitialized_fill_n(_M_start, __n, __value); }
explicit vector(size_type __n)
: _Base(__n, allocator_type())
{ _M_finish = uninitialized_fill_n(_M_start, __n, _Tp()); }
vector(const vector<_Tp, _Alloc>& __x)
: _Base(__x.size(), __x.get_allocator())
{ _M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start); }
#ifdef __STL_MEMBER_TEMPLATES
// Check whether it's an integral type. If so, it's not an iterator.
template <class _InputIterator>
vector(_InputIterator __first, _InputIterator __last,
const allocator_type& __a = allocator_type()) : _Base(__a) {
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
_M_initialize_aux(__first, __last, _Integral());
}
template <class _Integer>
void _M_initialize_aux(_Integer __n, _Integer __value, __true_type) {
_M_start = _M_allocate(__n);
_M_end_of_storage = _M_start + __n;
_M_finish = uninitialized_fill_n(_M_start, __n, __value);
}
template <class _InputIterator>
void _M_initialize_aux(_InputIterator __first, _InputIterator __last,
__false_type) {
_M_range_initialize(__first, __last, __ITERATOR_CATEGORY(__first));
}
#else
vector(const _Tp* __first, const _Tp* __last,
const allocator_type& __a = allocator_type())
: _Base(__last - __first, __a)
{ _M_finish = uninitialized_copy(__first, __last, _M_start); }
#endif /* __STL_MEMBER_TEMPLATES */从以上构造函数中, 我们捕获到了如下函数
- uninitialized_fill_n
- uninitialized_copy
uninitialized_fill_n
首先分析一下 uninitialized_fill_n 函数, 它在 stl_uninitialized.h 中.
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter
uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x)
{
return __uninitialized_fill_n(__first, __n, __x, __VALUE_TYPE(__first));
}
// ...
template <class _ForwardIter, class _Size, class _Tp, class _Tp1>
inline _ForwardIter
__uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x, _Tp1*)
{
typedef typename __type_traits<_Tp1>::is_POD_type _Is_POD;
return __uninitialized_fill_n_aux(__first, __n, __x, _Is_POD());
}
// ...
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter
__uninitialized_fill_n_aux(_ForwardIter __first, _Size __n,
const _Tp& __x, __true_type)
{
return fill_n(__first, __n, __x);
}
template <class _ForwardIter, class _Size, class _Tp>
_ForwardIter
__uninitialized_fill_n_aux(_ForwardIter __first, _Size __n,
const _Tp& __x, __false_type)
{
_ForwardIter __cur = __first;
__STL_TRY {
for ( ; __n > 0; --__n, ++__cur)
_Construct(&*__cur, __x);
return __cur;
}
__STL_UNWIND(_Destroy(__first, __cur));
}
// ...
// --------------------------------------------------------------------
// stl_construct.h
template <class _T1, class _T2>
inline void _Construct(_T1* __p, const _T2& __value) {
new ((void*) __p) _T1(__value);
}
template <class _T1>
inline void _Construct(_T1* __p) {
new ((void*) __p) _T1();
}
// --------------------------------------------------------------------
// ...
// --------------------------------------------------------------------
// stl_algobase.h
template <class _OutputIter, class _Size, class _Tp>
_OutputIter fill_n(_OutputIter __first, _Size __n, const _Tp& __value) {
__STL_REQUIRES(_OutputIter, _OutputIterator);
for ( ; __n > 0; --__n, ++__first)
*__first = __value;
return __first;
}
// --------------------------------------------------------------------很简单, 通过层层调用后, 我们发现:
- 在_Tp是基本类型的时候, 它最终调用了
算法中的fill_n函数, 直接进行值的赋值操作. - 在_Tp不是基本类型的时候, 它调用了 _Construct 方法进行元素的构造, 实质上是进行 plancement new.
uninitialized_copy
我们在分析一下 uninitialized_copy 函数, 它在 stl_uninitialized.h 中.
template <class _InputIter, class _ForwardIter>
inline _ForwardIter
uninitialized_copy(_InputIter __first, _InputIter __last,
_ForwardIter __result)
{
return __uninitialized_copy(__first, __last, __result,
__VALUE_TYPE(__result));
}
// ...
template <class _InputIter, class _ForwardIter, class _Tp>
inline _ForwardIter
__uninitialized_copy(_InputIter __first, _InputIter __last,
_ForwardIter __result, _Tp*)
{
typedef typename __type_traits<_Tp>::is_POD_type _Is_POD;
return __uninitialized_copy_aux(__first, __last, __result, _Is_POD());
}
// ...
template <class _InputIter, class _ForwardIter>
inline _ForwardIter
__uninitialized_copy_aux(_InputIter __first, _InputIter __last,
_ForwardIter __result,
__true_type)
{
return copy(__first, __last, __result);
}
template <class _InputIter, class _ForwardIter>
_ForwardIter
__uninitialized_copy_aux(_InputIter __first, _InputIter __last,
_ForwardIter __result,
__false_type)
{
_ForwardIter __cur = __result;
__STL_TRY {
for ( ; __first != __last; ++__first, ++__cur)
_Construct(&*__cur, *__first);
return __cur;
}
__STL_UNWIND(_Destroy(__result, __cur));
}
// ...
同样的, 通过分析我们发现:
- 在_Tp是基本类型的时候, 它最终调用了
算法中的copy函数. - 在_Tp不是基本类型的时候, 它调用了 _Construct 方法进行元素的构造, 实质上是进行 plancement new.
stl_uninitialized.h和stl_construct.h
stl_uninitialized.h 是进行元素值拷贝的.
stl_construct.h 是用来进行容器内元素的构造和析构的.
根据规范, stl_uninitialized.h共暴露如下四个函数:
- uninitialized_copy
- uninitialized_copy_n
- uninitialized_fill
- uninitialized_fill_n
它们进行直接值的赋值, 或者通过调用 stl_construct.h 中的函数进行元素的构造.
这四个函数都不涉及内存的分配, 只负责元素的值的拷贝/赋值/填充
stl_construct.h 只负责元素的构造和析构, 并不包括内存的分配和释放
它的本质就是 placement new 和 placement delete 的操作.
push_back函数
来一个常用的 push_back 函数进行跟踪.
void push_back(const _Tp& __x) {
// 如果当前的vector的Finish != 当前vector所分配内存空间的 End
if (_M_finish != _M_end_of_storage) {
// 利用现有空间进行元素的构造, 执行 placement new
construct(_M_finish, __x);
// 将当前vector的Finish后移.
++_M_finish;
}
// 如果内存不够了, 则进行空间重新分配
else
_M_insert_aux(end(), __x);
}
template <class _Tp, class _Alloc>
void
vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
{
// 如果当前vector的元素结尾 != vector的内存空间结尾
if (_M_finish != _M_end_of_storage) {
// 直接构建一个元素到 end() 的位置
// 注意, end()始终指向最后一个元素的后一个!
// 所以这里使用 _M_finish - 1 的值来进行构建
construct(_M_finish, *(_M_finish - 1));
// 指针后移
++_M_finish;
_Tp __x_copy = __x;
// 从后面进行复制, 从最后的元素开始复制，直到首元素复制出来
// 复制操作是从 last-1 开始, 直到first结束.
// 这些元素也被从后向前复制到目标容器中, 从 result-1 开始, 一直复制 last-first 个元素
// 比如 vector 是一个 {1, 2, 3, 4, 5, 6}
// 我们想得到 { 4, 5, 6, 4, 5, 6 }
// 可以写如下代码:
// copy_backward (v.begin() + 3, v.end(), v.begin() + 3);
copy_backward(__position, _M_finish - 2, _M_finish - 1);
*__position = __x_copy;
}
// 否则
else {
const size_type __old_size = size();
const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
// 重新分配内存
iterator __new_start = _M_allocate(__len);
iterator __new_finish = __new_start;
__STL_TRY {
// 进行元素的拷贝
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
// 构造新元素
construct(__new_finish, __x);
++__new_finish;
__new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
}
// 如果发生异常, 则进行元素的析构, 不会构造出实质性的东西
// 析构完元素后, 进行空间的释放
__STL_UNWIND((destroy(__new_start,__new_finish),
_M_deallocate(__new_start,__len)));
// 销毁原有的vector的元素
destroy(begin(), end());
// 释放原有的vector的内存
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
// 重新设置 begin() end() 等
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_start + __len;
}
}
template <class _Tp, class _Alloc>
void
vector<_Tp, _Alloc>::_M_insert_aux(iterator __position)
{
if (_M_finish != _M_end_of_storage) {
construct(_M_finish, *(_M_finish - 1));
++_M_finish;
copy_backward(__position, _M_finish - 2, _M_finish - 1);
*__position = _Tp();
}
else {
const size_type __old_size = size();
const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
iterator __new_start = _M_allocate(__len);
iterator __new_finish = __new_start;
__STL_TRY {
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
construct(__new_finish);
++__new_finish;
__new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
}
__STL_UNWIND((destroy(__new_start,__new_finish),
_M_deallocate(__new_start,__len)));
destroy(begin(), end());
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_start + __len;
}
}
由此可知, 当我们在需要大量push_back的时候, 还是需要预先分配足够多的内存.
当我们进行push_back后, 我们的迭代器需要更新.
小结
typedef后跟typename
typedef typename _Alty0::template rebind<_Ty>::other _Alty;
- typename一定要加
- 如果不加, 编译器会认为typedef后的`是一个类的静态成员对象`
- 而我们是这个类型中的一个类型, 所以`一定要加typename`
- 简言之, 在typedef后边有作用域的时候, 一般都需要加上typename
vector在使用 push_back 后, 需要更新
迭代器- 因为会使内部空间发生改变
需要注意 end()
- _M_finish 永远指向一个无效的元素
- 它是最后一个元素的后一个位置.
- 所以end()在使用的时候要小心.
注意STL的浅拷贝问题
- 如果vector中都装的是指针, 则需要自己管理指针的内存
- 比如在erase操作的时候, 会擦除指针, 但是不会释放其中的值.
STL中所有的容器都是 值语义(浅拷贝) 的, 它不会负责元素的生命周期.
- 因为 值语义可以转换成对象语义(深拷贝)
可以做一个包装, 比如智能指针.
- 它就是将指针包装成一个类.
进行继承, 包装析构函数
- 不能特化
- 因为STL不能修改.
善用模板的继承
继承可以减少代码膨胀.
- 模板会生成大量代码, 使用继承可以规避代码膨胀.
示例:
struct _List_node_base { _List_node_base* _M_next; _List_node_base* _M_prev; }; template <class _Tp> struct _List_node : public _List_node_base { _Tp _M_data; };C++中的new和delete
C++中有3个new
new operator
int* p = new int;
- 1.分配内存
- 2.调用构造函数
operator new
string* sz = operator new(sizeof(string));
- 分配内存
placement new
- new ((void*) p) ClassDemo();
- new ((ClassDemo*) p) ClassDemo("123");
同样, C++也有3个delete
- delete operator
- operator delete
- placement delete
示例:
class Demo { public: Demo() { std::cout << "Demo()" << std::endl; } ~Demo() { std::cout << "~Demo()" << std::endl; } } int main() { // 不会调用构造函数 Demo* pDemo = (Demo*)(operator new (sizeof(Demo))); // 等同于: // Demo* pDemo = (Demo*)malloc(sizeof(Demo)); // 不会调用析构函数的构造 operator delete(pDemo); // ================= // 如下两步之后才能delete Demo* pDemo1 = (Demo*)(operator new (sizeof(Demo))); new((void*)pDemo1) Demo(); delete pDemo1; }学习SGI STL的异常处理机制
构造失败后立即析构
- 构造过程中try
- 如果异常就进行catch
- 在catch中进行析构.
SGI STL的内存分配机制
- 分配内存
- 在现有内存中构建对象
- 构建对象后去填充值
- 填充完了可以使用
- 使用完成, 进行析构
- 析构完成后进行内存释放
资料下载
未完待续....
如有错误,请提出指正!谢谢.
本文由 花心胡萝卜 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: 2017-04-05 at 04:22 pm