从零开始学C++之STL(二):实现简单容器模板类Vec(vector capacity 增长问题、allocator 内存分配器)

首先,vector 在VC 2008 中的实现比较复杂,虽然vector 的声明跟VC6.0 是一致的,如下:

template < class _Ty, class _Ax = allocator<_Ty> >
class vector;

但在VC2008 中vector 还有基类,如下:

// TEMPLATE CLASS vector
template < class _Ty,
         class _Ax >
class vector
    : public _Vector_val<_Ty, _Ax>
{
};

稍微来看一下基类_Vector_val:

// TEMPLATE CLASS _Vector_val
template < class _Ty,
         class _Alloc >
class _Vector_val
    : public _CONTAINER_BASE_AUX_ALLOC<_Alloc>
{
    // base class for vector to hold allocator _Alval
protected:
    _Vector_val(_Alloc _Al = _Alloc())
        : _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Al), _Alval(_Al)
    {
        // construct allocator from _Al
    }

    typedef typename _Alloc::template
    rebind<_Ty>::other _Alty;

    _Alty _Alval;   // allocator object for values
};

为了理解_Alty 的类型,还得看一下allocator模板类:

template<class _Ty> class allocator
{

    template<> class _CRTIMP2_PURE allocator<void>
    {
        // generic allocator for type void
    public:
        template<class _Other>
        struct rebind
        {
            // convert an allocator<void> to an allocator <_Other>
            typedef allocator<_Other> other;
        };
        ....
    };
    ...
};

typedef typename _Alloc::template rebind<_Ty>::other _Alty; 整体来看是类型定义,假设现在我们这样使用

vector<int>, 那么_Ty 即 int, _Ax 即 allocator<int>,由vector 类传递给 基类_Vector_val,则_Alloc 即

allocator<int> ;可以看到 allocator<void> 是allocator 模板类的特化, rebind<_Ty> 是成员模板类,other是成员模板类

中自定义类型,_Ty 即是int , 那么other 类型也就是allocator<int>, 也就是说_Alty 是类型 allocator<int> 。

_Alty _Alval; 即 基类定义了一个allocator<int> 类型的成员,被vector 继承后以后用于为vector 里面元素分配内存等操作。

如 iterator new_data  = alloc.allocate(new_size); 注意,标准的vector::iterator 是以模板类实现的,下面的实现简单地将其等同为指

针,实际上真正的iterator 类的实现是内部有一个指针成员,指向容器元素。

对比list 的实现,继承它的基类_List_nod 的一个成员 allocator<_Node>   _Alnod;  如下:

typename _Alloc::template rebind<_Node>::other  _Alnod;   // allocator object for nodes

其中 _Node有三个成员,如下:

_Nodeptr _Next;  // successor node, or first element if head

_Nodeptr _Prev; // predecessor node, or last element if head

_Ty _Myval; // the stored value, unused if head

如果是list<int> ,那么_Ty 即是int 类型。双向链表在创建一个新结点时,这样实现:

_Nodeptr _Pnode = this->_Alnod.allocate(1); // 即分配一个节点的空间,返回指向这个节点的指针。

实际上list 还继承另外两个基类的两个成员,如下:

typename _Alloc::template rebind<_Nodeptr>::other  _Alptr;// allocator object for pointers to nodes

typename _Alloc::template rebind<_Ty>::other _Alty  _Alval;  // allocator object for values stored in nodes

在VC6.0 vector 的实现,_Alval 是直接作为vector 自身的成员存在的。此外还有一个比较大的不同点在于,两个版本对于capacity 也就是容量的

计算方式不同,接下去的测试可以看到这种不同,在这里可以先说明一下:

VC2008:容量每次增长为原先容量 + 原先容量 / 2;

VC6.0 :容量每次增长为原先容量的2倍。

容量跟vector 大小的概念是不一样的,capacity 》= size,如下图所示:

size 指的是avail  - data 的区间;capacity 指的是 limit - data 的区间;也就是说存在尚未使用的空间。

data, avail 和 limit 是vector 类的三个指针成员,对比list 的实现,自身也许只有两个成员,如下:

Nodeptr _Myhead; // pointer to head node

size_type _Mysize; // number of elements

实际上 list不仅是一个双向链表,而且还是一个环状双向链表。另外,插入操作和结合操作都不会造成原有的list迭代器失效,这在vector是不成立的。

因为vector的插入操作可能造成存储空间重新配置,导致原有的迭代器全部失效。list的元素删除操作(erase),也只有“指向被删除元素”的那个

迭代器失效,其他迭代器不受任何影响。

下面是模仿VC6.0 中vector 的实现写的Vec 类,程序主要参考《Accelerated C++》 ,略有修改,比如将接口修改成与VC6.0 一致,

这样做的好处是可以传递第二个参数,也就是说可以自己决定内存的分配管理方式;实现capacity() 函数等;

Vec.h:

/*************************************************************************
> File Name: template_class_Vec.h
> Author: Simba
> Mail: dameng34@163.com
> Created Time: Thu 07 Feb 2013 06:51:12 PM CST
************************************************************************/

#include<iostream>
#include<cstddef>
#include<memory>
#include<algorithm>

template < class T, class A_ = std::allocator<T> >
class Vec
{

public: // interface
    typedef T *iterator;
    typedef const T *const_iterator;
    typedef size_t size_type;
    typedef T value_type;
    typedef std::ptrdiff_t difference_type;
    typedef T &reference;
    typedef const T &const_reference;

    Vec()
    {
        create();    // default constructor
    }
    // const T & t = T();意思是默认参数,当没有传递 参数时,T() 即定义一个类型为T的无名对象(参数为空会调用默认构造函数)
// 也就是 t 引用着这个无名对象。
    //explicit表示不允许构造函数进行隐式类型转换
    explicit Vec(size_type n, const T &val = T())
    {
        create(n, val);
    }
    Vec(const Vec &v)
    {
        create(v.begin(), v.end());    // copy constructor
    }
    Vec &operator=(const Vec &);  // assigment operator
    ~Vec()
    {
        uncreate();    // destructor
    }

    size_type size() const
    {
        return avail - data;    // a value of ptrdiff_t
    }
    size_type capacity() const
    {
        return (data == 0 ? 0 : limit - data);
    }
    T &operator[](size_type i)
    {
        return data[i];
    }
    /* because their left operand is different(const), we can overload the operation */
    const T &operator[](size_type i) const
    {
        return data[i];
    }

    iterator begin()
    {
        return data;
    }
    const_iterator begin() const
    {
        return data;
    }
    iterator end()
    {
        return avail;
    }
    const_iterator end() const
    {
        return avail;
    }

    void push_back(const T &val)
    {
        if (avail == limit) // get space if needed
            grow();
        unchecked_append(val); // append the new element
    }
    void clear()
    {
        uncreate();
    }
    bool empty()
    {
        return data == avail;
    }

private:
    iterator data; // first element in the Vec
    iterator avail; // one past the last constructed element in the Vec
    iterator limit; // one past the last available element

    A_ alloc; // object to handle memory allocation
    // allocate and initialize the underlying array
    void create();
    void create(size_type, const T &);
    void create(const_iterator, const_iterator);

    // destory the element in the array and free the memory
    void uncreate();
    // support functions for push_back
    void grow();
    void unchecked_append(const T &);

};

template < class T, class A_>
Vec<T, A_> &Vec<T, A_>::operator=(const Vec<T, A_> &rhs)
{
    // check for self-assigment
    if (&rhs != this)
    {
        uncreate();
        create(rhs.begin(), rhs.end());
    }

    return *this;
}

template < class T, class A_>
void Vec<T, A_>::create()
{
    data = avail = limit = 0;
}

template < class T, class A_>
void Vec<T, A_>::create(size_type n, const T &val)
{
    data = alloc.allocate(n);
    limit = avail = data + n;
    std::uninitialized_fill(data, limit, val);
}

template < class T, class A_>
void Vec<T, A_>::create(const_iterator i, const_iterator j)
{
    data = alloc.allocate(j - i);
    limit = avail = std::uninitialized_copy(i, j, data);
    /* return a pointer to (one past) the last element that it initialized */
}

template < class T, class A_>
void Vec<T, A_>::uncreate()
{
    if (data)
    {
        // destroy(in reverse order) the elements that were constructed
        iterator it = avail;
        while (it != data)
            // destory runs T's destructor for that object, rendering the storage uninitialized again
            alloc.destroy(--it);

        alloc.deallocate(data, limit - data);
    }
    // reset pointers to indicate that Vec is empty again
    data = limit = avail = 0;
}

template < class T, class A_>
void Vec<T, A_>::grow()
{
    // when growing, allocate twice as much space as currently in use
    size_type new_size = std::max(2 * (limit - data), ptrdiff_t(1));

    // allocate new space and copy elements to the new space
    iterator new_data = alloc.allocate(new_size);
    iterator new_avail = std::uninitialized_copy(data, avail, new_data);

    // return the old space
    uncreate();

    // reset pointers to point to the newly allocated space
    data = new_data;
    avail = new_avail;
    limit = data + new_size;
}

template < class T, class A_>
// error C4519: 仅允许在类模板上使用默认模板参数
void Vec<T, A_>::unchecked_append(const T &val)
{
    alloc.construct(avail++, val);
}

先介绍一下用到的一些类和函数:

allocator 模板类:

#include <memory>
template <class T> class allocator
{
public:
    T *allocate(size_t);
    void deallocate(T *, size_t);
    void construct(T *, size_t);
    void destroy(T *);
    //.......
};

当然实际的接口没实现没那么简单,但大概实现的功能差不多:

allocate 调用operator new ;deallocate 调用 operator delete; construct 调用placement new (即在分配好的内

存上调用拷贝构造函数),destroy 调用析构函数。

两个std函数:

template < class In, class For>
For uninitialized_copy(In, In, For);

template < class For, class T>
void uninitialized_fill(For, For, const T &);

如 std::uninitialized_copy(i, j, data); 即将i ~ j 指向区间的数值都拷贝到data 指向的区间,返回的是最后一个初始化值的下一个位置。

std::uninitialized_fill(data, limit, val);  即将 data ~ limit 指向的区间都初始化为val 。

为了理解push_back 的工作原理,写个小程序测试一下:

#include <iostream>
#include "Vec.h"

using namespace std;

class Test
{
public:
    Test()
    {
        cout << "Test ..." << endl;
    }
    Test(const Test &other)
    {
        cout << "copy Test ..." << endl;
    }
    ~Test()
    {
        cout << "~Test ..." << endl;
    }
};

int main(void)
{
    vector<Test> v2;
    Test t1;
    Test t2;
    Test t3;
    v2.push_back(t1);
    v2.push_back(t2);
    v2.push_back(t3);

    return 0;
}

从输出可以看出,构造函数调用3次,拷贝构造函数调用6次,析构函数调用9次,下面来分析一下,首先看下图:

首先定义t1, t2, t3的时候调用三次构造函数,这个没什么好说的;接着第一次调用push_back,调用grow进而调用alloc.allocate,

allocate 函数调用operator new 分配一块内存,第一次uncreate 没有效果,接着push_back 里面调用uncheck_append,进而调用

alloc.construct,即调用placement new(new (_Vptr) _T1(_Val); ),在原先分配好的内存上调用一次拷贝构造函数。

接着第二次调用push_back,一样的流程,这次先分配两块内存,将t1 拷贝到第一个位置,调用uncreate(),先调用alloc.destroy,即

调用一次析构函数,接着调用alloc.deallocate,即调用operator delete 释放内存,最后调用uncheck_append将t2 拷贝到第二个位置。

第三次调用push_back,也一样分配三块内存,将t1, t2 拷贝下来,然后分别析构,最后将t3 拷贝上去。

程序结束包括定义的三个Test 对象t1, t2, t3 ,析构3次,Vec<Test> v2;  v2是局部对象,生存期到则调用析构函数~Vec(); 里面调用

uncreate(), 调用3次Test 对象的析构函数,调用operator delete 释放3个对象的内存。故总共析构了6次。

在VC2008 中换成 vector<Test> v2; 来测试的话,输出略有不同,如下:

输出的次数是一致的,只是拷贝的顺序有所不同而已,比如第二次调用push_back 的时候,VC2008 中的vector 是先拷贝t2, 接着拷

贝t1, 然后将t1 释放掉。

最后再来提一下关于capacity 的计算,如下的测试程序:

#include <iostream>
#include "Vec.h"

using namespace std;


int main(void)
{
    Vec<int> v;

    v.push_back(1);
    cout << v.capacity() << endl;
    v.push_back(1);
    cout << v.capacity() << endl;
    v.push_back(1);
    cout << v.capacity() << endl;
    v.push_back(1);
    cout << v.capacity() << endl;
    v.push_back(1);
    cout << v.capacity() << endl;
    v.push_back(1);
    cout << v.capacity() << endl;
    v.push_back(1);
    cout << v.capacity() << endl;
}

 输出为 1 2 4 4 8 8 8 即在不够的情况下每次增长为原来的2倍。

如果换成 vs2008 下 vector<int> v; 测试,那么输出是 1 2 3 4 6 6 9,即在不够的情况每次增长为原来大小 + 原来大小 / 2;

看到这里,有些朋友会疑惑了,由1怎么会增长到2呢?按照原则不是还是1?其实只要看一下vector 的源码就清楚了:

void _Insert_n(const_iterator _Where,
               size_type _Count, const _Ty &_Val)
{
    // insert _Count * _Val at _Where

    .....
    size_type _Capacity = capacity();
    .....
    else if (_Capacity < size() + _Count)
    {
        // not enough room, reallocate
        _Capacity = max_size() - _Capacity / 2 < _Capacity
                    ? 0 : _Capacity + _Capacity / 2;    // try to grow by 50%
        if (_Capacity < size() + _Count)
            _Capacity = size() + _Count;
        pointer _Newvec = this->_Alval.allocate(_Capacity);
        pointer _Ptr = _Newvec;
        .....
    }
}

_Insert_n 是被push_back 调用的,当我们试图增长为_Capacity + _Capacity / 2;  时,下面还有一个判断:

if (_Capacity < size() + _Count)

            _Capacity = size() + _Count;

现在试图增长为 1 + 1/ 2 = 1; 此时因为 1 < 1 + 1 ; 所以 _Capacity = 1 + 1 = 2; 

其他情况都是直接按公式增长。

从上面的分析也可以看出,当push_back 的时候往往带有拷贝和析构多个操作,所以一下子分配比size() 大的空间capacity,可以减轻频繁操作造成的

效率问题。

参考:

C++ primer 第四版

Effective C++ 3rd

C++编程规范

Accelerated C++

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏逸鹏说道

Python3 与 C# 扩展之~基础衍生

在线编程: https://mybinder.org/v2/gh/lotapp/BaseCode/master

823
来自专栏青枫的专栏

【Java面试复习经典】传智播客Java就业班入学测试题及答案解析(2014年版)

582
来自专栏一枝花算不算浪漫

[读书笔记]C#学习笔记四: C#2.0泛型 可控类型 匿名方法和迭代器

41211
来自专栏代码世界

Python之面向对象四

面向对象进阶 一、关于面向对象的两个内置函数 isinstance   判断类与对象的关系    isinstance(obj,cls)检查obj是否是类 cl...

36213
来自专栏猿人谷

一个正则表达式测试(只可输入中文、字母和数字)

  在项目中碰到了正则表达式的运用,正则还是非常强大的,不管什么编程语言,基本上都可以用到。之前在用java时特别是对用户名或密码使用正则非常爽,写脚本上用正则...

2986
来自专栏逆向技术

C++反汇编第五讲,认识多重继承,菱形继承的内存结构,以及反汇编中的表现形式.

      C++反汇编第五讲,认识多重继承,菱形继承的内存结构,以及反汇编中的表现形式. 目录:   1.多重继承在内存中的表现形式     多重继承在汇编中...

1757
来自专栏Felix的技术分享

《一个操作系统的实现》笔记(2)--保护模式

1608
来自专栏风口上的猪的文章

.NET面试题系列[8] - 泛型

“可变性是以一种类型安全的方式,将一个对象作为另一个对象来使用。“ - Jon Skeet

973
来自专栏mukekeheart的iOS之旅

Java基础——异常体系

在Java中,异常对象都是派生于Throwable类的一个实例,Java的异常体系如下图所示: ?    所有的异常都是由Throwable继承而来,在下一层立...

2577
来自专栏圣杰的专栏

一道面试题的思考

在继承中new和override相同点和区别?看下面的代码,有一个基类A,B1和B2都继承自A,并且使用不同的方式改变了父类方法Print()的行为。测试代码...

2126

扫码关注云+社区