STL源码分析 # vector #
下面是一个使用vector的demo:
#include <iostream>
#include <vector>
using namespace std;
int main()
{
/*
** To create a vector which contain 10 elements and the value
** of each element is 1
*/
vector<int> vec(10, 1);
vector<int>::iterator iter = vec.begin();
for (iter = vec.begin(); iter != vec.end(); iter++)
{
cout << *iter << endl;
}
return 0;
}
首先要知道class vector是 struct _Vector_base的衍生类．我们看看后者．
又包含一个基类struct _Vector_impl, 这里有三个指针，_M_start, _M_finish, _M_end_of_storage.
默认的初始化为0.
vector采用的数据结构非常简单，就是线性储存空间，它以两个迭代器_M_start, _M_finish分别指向配置得来的连续空间中目前已经使用的范围．并以迭代器_M_end_of_storage指向整块连续空间的尾部（包含备用空间）
_M_start 表示目前使用空间的头
_M_finish 表示目前使用空间的尾
_M_end_of_storage 表示目前可用空间的尾．
至于最后这里的不是很清楚，到现在都没找到如何在一大堆C++代码中快速的定位函数定义的位置．
我们测试一下这种内存构造布局．写个小demo:
/*
Programmer : EOF
Date : 2015.03.31
file : 4vector-test.cpp
Code description:
This is a demo to show how the vector works.
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int i = 0;
vector<int> iv(2, 9);
cout << "size" << iv.size() << endl; // size = 2
cout << "capacity = " << iv.capacity() << endl; // capacity = 2
iv.push_back(1);
cout << "size" << iv.size() << endl; // size = 3
cout << "capacity = " << iv.capacity() << endl; // capacity = 4
iv.push_back(2);
cout << "size" << iv.size() << endl; // size = 4
cout << "capacity = " << iv.capacity() << endl; // capacity = 4
iv.push_back(3);
cout << "size" << iv.size() << endl; // size = 5
cout << "capacity = " << iv.capacity() << endl; // capacity = 8
iv.push_back(4);
cout << "size" << iv.size() << endl; // size = 6
cout << "capacity = " << iv.capacity() << endl; // capacity = 8
for (i = 0; i < iv.size(); i++)
{
cout << iv.at(i) << ' ';
}
cout << endl;
iv.push_back(5);
cout << "size" << iv.size() << endl; // size =
cout << "capacity = " << iv.capacity() << endl; // capacity =
for (i = 0; i < iv.size(); i++)
{
cout << iv.at(i) << ' ';
}
cout << endl;
iv.pop_back();
iv.pop_back();
cout << "size" << iv.size() << endl; // size =
cout << "capacity = " << iv.capacity() << endl; // capacity =
iv.pop_back();
cout << "size" << iv.size() << endl; // size =
cout << "capacity = " << iv.capacity() << endl; // capacity =
vector<int>::iterator ivite = find(iv.begin(), iv.end(), 1);
if (ivite != iv.end())
{
iv.erase(ivite);
}
cout << "size" << iv.size() << endl; // size =
cout << "capacity = " << iv.capacity() << endl; // capacity =
for (i = 0; i < iv.size(); i++)
{
cout << iv.at(i) << ' ';
}
cout << endl;
ivite = find(iv.begin(), iv.end(), 2);
if( ivite != iv.end())
{
iv.insert(ivite, 3, 7);
}
cout << "size" << iv.size() << endl; // size =
cout << "capacity = " << iv.capacity() << endl; // capacity =
for (i = 0; i < iv.size(); i++)
{
cout << iv.at(i) << ' ';
}
cout << endl;
iv.clear();
cout << "size" << iv.size() << endl; // size =
cout << "capacity = " << iv.capacity() << endl; // capacity =
return 0;
}size2
capacity = 2
size3
capacity = 4
size4
capacity = 4
size5
capacity = 8
size6
capacity = 8
9 9 1 2 3 4
size7
capacity = 8
9 9 1 2 3 4 5
size5
capacity = 8
size4
capacity = 8
size3
capacity = 8
9 9 2
size6
capacity = 8
9 9 7 7 7 2
size0
capacity = 8
[Finished in 0.6s]
vector用起来很像C语言的数组，但是这家伙又不是数组，而且比数组快更有效率．
而且还提供下标访问操作．
一下接口供用户访问查看当前vector占用的内存大小
值得注意的是max_size那里，好奇怪为嘛是-1．．．这里还不是很清楚．
这里应该是一个理论值，vector占满整个内存能装载几个_Tp类型的对象．
begin() end()返回迭代器，其实对于vector来说
我们注意到下标索引实质上是由指针运算实现的．返回引用
reference operator[](size_type __n) { return *(begin() + __n); }
const_reference operator[](size_type __n) const { return *(begin() + __n); }
reference at(size_type __n)
{ _M_range_check(__n); return (*this)[__n]; }
const_reference at(size_type __n) const
{ _M_range_check(__n); return (*this)[__n]; }
vector的构造函数们～
explicit vector(const allocator_type& __a = allocator_type()) //缺省参数，构造一个空的vector
: _Base(__a) {}
vector(size_type __n, const _Tp& __value,
const allocator_type& __a = allocator_type()) //创建n个值为 __value的_Tp类型的vector
: _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) //用别的vector初始化自己这个vector
: _Base(__x.size(), __x.get_allocator())
{ _M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start); } ~vector() { destroy(_M_start, _M_finish); }
如果内存空间还富余的话(_M_finish 小于 _M_end_of_storage)，利用构造函数在_M_finish处构造一个值为__x的vector元素．
如果内存空间不足了，就调用_M_insert_aux在尾部进行插入操作．push_back是没有返回值的！
很多函数都牵扯到_M_insert_aux,而这家伙的实现感觉又找不到，很奇怪．．．
有一个实现，但是第二个参数是bool在bvector.h里面
front() back()分别返回第一个元素的引用和最后元素的引用．
insert有各种重载，这里贴出一个
在迭代器指向的位置__position插入类型为_Tp的元素__x
erase会删除__first到__last之间的所有元素，而clear()则是调用erase删除所有元素．但是不缩减容量！！
只对_M_start, _M_end进行操作．
原文：http://blog.csdn.net/cinmyheart/article/details/44767215
