STL源码分析之vector(一) 基本数据类型及构造函数

2017-09-13 20:38:36来源:CSDN作者:jmh1996人点击

分享

说明:
STL源码分析系列博客的使用的是https://www.sgi.com/tech/stl/download.html 里面的STL v2.03版.不同的STL或许会有所不同。工程文件可下载。

前言

C++ STL的vector 源码分析!vector是十分常用的stl容器,它支持动态增长,是静态数组的很好的替代品!本博客主要介绍基本数据类型和构造函数!

0. 主要成员变量及数据类型:

template <class T, class Alloc = alloc>//模板参数的第二个是内存分配器,但是它有默认值,我们一般不改动class vector {public:    typedef T value_type;    typedef value_type* pointer;//指针类型    typedef value_type* iterator;//迭代器类型    typedef const value_type* const_iterator;//常迭代器,所指对象不变    typedef value_type& reference;//引用类型    typedef const value_type& const_reference;//常引用类型    typedef size_t size_type;//size_type类型typedef ptrdiff_t difference_type;    ······protected:    typedef simple_alloc<value_type, Alloc> data_allocator;//定义一个value_type为T的内存分配器    iterator start;    iterator finish;iterator end_of_storage;···}

由代码可知,核心的成员变量有三个:start,finish,end_of_storage.
start指向有效元素的第一个
finish指向最后一个有效元素的后一个元素
end_of_storage指向当前动态内存块的尾部
且end_of_storage>=finish!
他们都是value_type 类型的指针,而value_type其实就是模板类里面传入的类型参数。
比如vector< int >···那么这个三个变量都是int * 类型的指针。
需要注意里面的size_type,它有size_t 定义,而size_t定义如下:

#ifdef _WIN64typedef unsigned __int64    size_t;#else  /* _WIN64 */typedef _W64 unsigned int   size_t;#endif  /* _WIN64 */

是根据机器位数变化的 无符号32位或64位整数.

1. 构造函数

一共有6个构造函数:

    vector();    vector(size_type n, const T& value);    vector(int n, const T& value) ;    vector(long n, const T& value);    explicit vector(size_type n);    vector(const vector<T, Alloc>& x) ;

我们一个个的来看:

1.1 vector()默认构造函数

vector() : start(0), finish(0), end_of_storage(0) {}

在初始化列表初始化三个成员变量为NULL指针:start(0),finish(0),end_of_storage(0)

1.2 vector(size_type n,const T & value);

这个函数接受一个无符号size_type,同时接受一个初值value.
内部实现:

vector(size_type n, const T& value) { fill_initialize(n, value); }

调用fill_initialize(n,value);
我们再看fill_initialize(n,value)实现:

      void fill_initialize(size_type n, const T& value) {      start = allocate_and_fill(n, value);//分配内存,同时完成初始化      finish = start + n;//finish偏移n个指针      end_of_storage = finish;//内存结束标记}

首先是start=allocate_and_fill(n,value);
我们看allocate_and_fill():

   iterator allocate_and_fill(size_type n, const T& x) {      iterator result = data_allocator::allocate(n);//分配n个字节的空间#         ifdef __STL_USE_EXCEPTIONS      try {#         endif /* __STL_USE_EXCEPTIONS */        uninitialized_fill_n(result, n, x);//往刚刚申请的内存填入初值x。        return result;#         ifdef __STL_USE_EXCEPTIONS      }      catch(...) {        data_allocator::deallocate(result, n);        throw;      }#         endif /* __STL_USE_EXCEPTIONS */    }

具体一点我们看data_allocator::allocate(n)实现:

  static T *allocate(size_t n)    { return 0 == n? 0 : (T*) Alloc::allocate(n * sizeof (T)); }

就是在分配n*sizeof(T)个字节的内存,allocate()本质是调用了malloc.h的malloc()函数!
再看uninitialized_fill_n(result,n,x):

inline ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n,                                            const T& x) {  return __uninitialized_fill_n(first, n, x, value_type(first));}
template <class ForwardIterator, class Size, class T>inline ForwardIterator__uninitialized_fill_n_aux(ForwardIterator first, Size n,                           const T& x, __true_type) {  return fill_n(first, n, x);}
template <class OutputIterator, class Size, class T>OutputIterator fill_n(OutputIterator first, Size n, const T& value) {  for ( ; n > 0; --n, ++first)    *first = value;  return first;}

上面fill_n完成了最终的初始化。
因此,vector(size_type n ,const T & value)的过程是:
1. 动态分配n*sizeof(T)个字节的内存单元,同时给这些内存单位设置成为value的值
2. 将动态分配的指针给start,finish 偏移n个单位(其实是n*sizeof(T)个字节)
3. 将end_of_storage设置为finish的值

1.3 vector(int n,const T& value);和vector(long n,const T & value);

内部是一致的,区别在于n是int,long,还是无符号的int。

1.4 explicit vector(size_type n);

显示构造函数,需要指定申请多少个元素的。实现:

explicit vector(size_type n) { fill_initialize(n, T()); }

也是调用了fill_initialize(),不过初值的调用了T的默认构造函数,至于初值是什么就要看T()把自己初始化成什么了。

1.5 vector(const vector

     vector(const vector<T, Alloc>& x) {      start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());//深复制      finish = start + (x.end() - x.begin());      end_of_storage = finish;}

我们可以看到,其中使用的是深复制,先申请x.end()-x.begin()个元素的动态内存,再把x的值拷贝到刚刚申请到的内存中去。

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台