C++ STL空间配置源码分析以及实现二

bear_fish

发布于 2018-09-14 09:52:58

6280

发布于 2018-09-14 09:52:58

文章被收录于专栏：用户2442861的专栏

本文主要内容如下：

1. 在上篇文章的基础上，通过实现简单的vector来说明空间配置对容器的作用。

2. c++中在已经分配好的内存上面构造对象(调用对象的构造函数)，一般C++中new object会同时分配内存调用对象的构造函数。但是容器是在空间配置器已经分配好的内存上面直接构建对象(等价于调用对象的构造函数)

3. C++11判断类型是否是pod（std::is_pod的使用），以及从迭代器中萃取类型std::iterator_traits

allocator类的定义

STL中容器定义的时候都会带上：

template <class T, class Alloc = allocator<T>>
class SimpleVec{.....}

其中allocator<T>主要是用来为容器分配管理内存，我们看下allocator<T>的定义：

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;
    public:
       static T *allocate();// 分配sizeof(T)大小的内存
       static T *allocate(size_t n);// 分配size n 大小的内存
       static void deallocate(T *ptr);//内存返回给空间配置器alloc回收
       static void deallocate(T *ptr, size_t n);

};

注意的是allocator的所有成员都是static（程序运行结束会自动释放内存）

对应的allocate函数(向alloc中获取内存)的定义如下：

template<class T>
T *allocator<T>::allocate(){
   return static_cast<T *>(alloc::allocate(sizeof(T)));
}

template<class T>
T *allocator<T>::allocate(size_t n){
   if (n == 0) return 0;
   return static_cast<T *>(alloc::allocate(sizeof(T) * n));
}

deallocate函数(内存由alloc回收)的定义如下：

template<class T>
void allocator<T>::deallocate(T *ptr){
   alloc::deallocate(static_cast<void *>(ptr), sizeof(T));
}
template<class T>
void allocator<T>::deallocate(T *ptr, size_t n){
   if (n == 0) return;
   alloc::deallocate(static_cast<void *>(ptr), sizeof(T)* n);
}

精简版本的vector实现

接下来通过实现精简vector来说明allocator在容器中的使用。

template <class T, class Alloc = allocator<T>>
class SimpleVec{
    public:
        typedef T          value_type;
        typedef T*         iterator;
        typedef T*         pointer;
        typedef ptrdiff_t  difference_type;
    private:
        pointer start_;
        pointer finish_;
        pointer end_of_storage_;

        typedef Alloc dataAllocator;

    public:
        SimpleVec():start_(0), finish_(0), end_of_storage_(0){}
        explicit SimpleVec(size_t n);//创建n个对象(默认值)
        SimpleVec(size_t n, const T& value);//创建n个对象(指定值)

        ~SimpleVec();

        size_t size()const{return finish_ - start_;}
        size_t capacity()const{return end_of_storage_ - start_;}
};

我们重点分析SimpleVec的构造函数，来说明allocator内存分配，以及如何在内存中构造对象。

// 首先看构造函数
// explicit SimpleVec(size_t n);

//===========================================================
template <typename T, typename Alloc>
SimpleVec<T, Alloc>::SimpleVec(size_t n){
    start_ = dataAllocator::allocate(n);//获取内存
    // value_type like int, int() = 0
    xy_stl::initialized_fill_n(start_, n, value_type());//内存填充数据
    finish_ = end_of_storage_ = start_ + n;
    std::cout<<"SimpleVec(n), start_: "<<start_<<" finish_: "<<finish_<<std::endl;
}

重点看initialized_fill_n的原理，initialized_fill_n在以及分配好的内存上面构造对象（调用对象的构造函数）。在C++11中我们可以通过std::is_pod<T>::value来判断类T是否是pod类型。

下面给出initialized_fill_n的实现：

template<typename Iterator, typename Size, typename T>
void initialized_fill_n(Iterator it, Size n, const T& value){
    // typedef typename std::iterator_traits<Iterator>::value_type value_type;
    bool b_pod = std::is_pod<T>::value;
    if (b_pod){//旧类型,例如value_type=int, 则int()=0,初始化为0
        std::cout<<"pod type: "<< typeid(value).name()<<std::endl;
        fill_n(it, n, value);//填充普通对象例如int, char
    } else{
        initialized_n_with_ctor(it, n, value);//填充含有构造函数的类
    }
}

注意的是在已经分配的内存上面构建对象

// 普通的类 直接赋值即可
template<typename It, typename Size, typename T>
void fill_n(It first, Size n, const T& value){
    while (n--){
        *first++ = value;//指针直接赋值即可
    }
    std::cout<<std::endl;
}

// 含有构造函数的则需要显示的调用构造函数
template<typename Iterator, typename Size, typename T>
void initialized_n_with_ctor(Iterator it, Size n, const T& value){
    for (int i = 0; i < n; ++i) {
        construct((T*)(it + i), value);
    }
}

接下来看construct（已经分配的内存上，调用对象的构造函数）：

template<typename T1, typename T2>
inline void construct(T1* ptr, const T2& value){
    new(ptr)T1(value);
}

我们看下如何在C++分配好的内存上面创建对象：

char* ptr = new char[sizeof(T)]; // allocate memory
T* tptr = new(ptr) T;            // construct in allocated storage ("place")
tptr->~T();                      // destruct
delete[] ptr;                    // deallocate memory

具体测试如下：

class TestNewPlacement{
    private: int n; char c;
    public:
        TestNewPlacement(){cout<<"TestNewPlacement ctor"<<endl;}
        ~TestNewPlacement(){cout<<"TestNewPlacement dtor"<<endl;}
};

测试：

void test_new_placement(){
    char* ptr = new char[sizeof(TestNewPlacement)];
    cout<<"after create memory"<<endl;
    TestNewPlacement* ptrT = new(ptr) TestNewPlacement;
    ptrT->~TestNewPlacement();
    delete ptrT;
}

输出如下：

//after create memory
//TestNewPlacement ctor
//TestNewPlacement dtor
//TestNewPlacement dtor

上面有个问题delete 类指针，会调用类的析构函数（因此上面调用了两次析构函数，一次显示）可以吧delete ptrT -> delete[] ptr

或者测试如下（std空间配置器里面也是这样做的）：

void test_new_placement(){
    char* ptr = (char*)malloc(sizeof(TestNewPlacement));
    cout<<"after create memory"<<endl;
    TestNewPlacement* ptrT = new(ptr) TestNewPlacement;
    ptrT->~TestNewPlacement();
    free(ptr);
}

输出如下：

//after create memory
//TestNewPlacement ctor
//TestNewPlacement dtor

还有就是int a1 = int(); // a1 will be zero

下面看析构函数`~SimpleVec`：

template <typename T, typename Alloc>
SimpleVec<T, Alloc>::~SimpleVec(){
    if(capacity()){
        //调用析构函数, 析构每个对象
        destroy(start_, finish_);
        //内存归回空间配置器>128 bytes直接释放，小于则二级空间配置器回收
        dataAllocator::deallocate(start_, capacity());
    }
}

1. 显示在分配的内存上，调用对象的析构函数
2. 内存返回给空间配置处理

下面给出destory的定义：

析构单个对象：

template<typename T>
inline void destory(T* ptr){
    ptr->~T();
}

按照迭代器范围析构，这里主要是判断T是否是pod，如果是int等类型则没有必要显示调用析构函数：

template<typename Iterator>
inline void destory(Iterator first, Iterator last){
    // using type = typename std::iterator_traits<Iterator>::value_type;
    // bool b_pod = std::is_pod<type>::value;
    typedef typename std::iterator_traits<Iterator>::value_type type;
    bool b_pod = std::is_pod<type>::value;
    if (!b_pod){ // 只显示调用含有析构函数的类型
        _destory(first, last);
    }
}

显示析构每个对象：

template<typename Iterator>
inline void _destory(Iterator first, Iterator last){
    while(first != last){
        destory(first++);
    }
}

测试代码如下：

struct TestVec{
    int a;       char c1;
    TestVec():a(1), c1('\0'){  std::cout<<"TestVec ctor"<<std::endl;  }

    TestVec(const TestVec& tv):a(tv.a), c1(tv.c1){
        std::cout<<"TestVec copy ctor"<<std::endl;
    }

    ~TestVec(){   std::cout<<"~TestVec dtor"<<std::endl; }
};

void test_allocator(){
    SimpleVec<int> intVec(10);
    SimpleVec<int> intVec2(10);
    SimpleVec<int> intVec3(10);

    std::cout<<"============ test struct vector"<<std::endl;
    SimpleVec<TestVec> intTestVec(10);
}

上面的示例：主要是测试pod类型如int，以及含有构造函数的类验证allocator，同时也可以大致理解std::vector的实现。输出如下：

第一个对象SimpleVec<int> intVec(10)：

第二个对象SimpleVec<int> intVec2(10)：

直接使用1中的空闲节点{8, 16, 24, 32, 40, …..} 40的index=4

第三个对象：

SimpleVec(n), start_: 0x60005aa58 finish_: 0x60005aa80
allocate size: 40. after round up size is: 40 
free_list has free node, index is: 4

第四个对象SimpleVec<TestVec> intTestVec(10)：

SampleVec会调用TestVec的默认构造函数创建一个临时对象，以此临时对象调用TestVec的默认copy 构造函数

因此上面首先输出一个构造函数的运行输出，然后是10次copy ctor。

但是问题在于，临时的对象显然是没有必要的，而且创建10个TestVec调用copy构造函数语义上也说不过去。

对比下std::vector我们发现， vector使用的是默认构造函数，而且没有创建临时对象。

std::cout<<"============ test std::vector struct vector"<<std::endl;
std::vector<TestVec> vecTest(10);

输出如下：

因此我们需要对SampleVec做一定的修改：

修改如下,直接从迭代器中萃取类型信息：

template<typename Iterator, typename Size>
void initialized_fill_n(Iterator it, Size n){
    typedef typename std::iterator_traits<Iterator>::value_type value_type;
    bool b_pod = std::is_pod<value_type>::value;
    if (b_pod){//旧类型,例如value_type=int, 则int()=0,初始化为0
        std::cout<<"pod type: "<< typeid(value_type).name()<<std::endl;
        fill_n(it, n, value_type());
    } else{
        initialized_n_with_ctor(it, n);
    }
}

initialized_n_with_ctor修改如下：

template<typename Iterator, typename Size>
void initialized_n_with_ctor(Iterator it, Size n){
    typedef typename std::iterator_traits<Iterator>::value_type value_type;
    for (int i = 0; i < n; ++i) {
        std::cout<<" initialized_n_with_ctor first++ addr: "<<(it + i);
        construct((value_type*)(it + i));
    }
    std::cout<<std::endl;
}

对应的construct：

template<typename T>
inline void construct(T* ptr){
    new(ptr)T;
}

测试输出如下：

可以看到没有使用类的copy构造函数。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018年06月04日，如有侵权请联系 cloudcommunity@tencent.com 删除

其他

http

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

其他

http

登录后参与评论

0 条评论

热度