从零开始学C++之STL（二）：实现简单容器模
首先，vector 在VC 2008 中的实现比较复杂，虽然vector 的声明跟VC6.0 是一致的，如下：
template < class _Ty, class _Ax = allocator<_Ty> >class vector;但在VC2008 中vector 还有基类，如下：
// TEMPLATE CLASS vectortemplate < class _Ty,
class _Ax >class vector
: public _Vector_val<_Ty, _Ax>
{
};稍微来看一下基类_Vector_val：
// TEMPLATE CLASS _Vector_valtemplate < class _Ty,
class _Alloc >class _Vector_val
: public _CONTAINER_BASE_AUX_ALLOC<_Alloc>
{
// base class for vector to hold allocator _Alvalprotected:
_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++