C++中的vector使用与实现

一、vector的使用

1.1 vector的定义

是一种类模板

template < class T, class Alloc = allocator<T> > 
class vector;

其中的模板参数Alloc是在使用空间配置器（内存池），并给了缺省值，暂时不深究

1.2遍历方式

1.2.1下标+[]遍历

与sting类似，得益于其物理连续结构

1.2.2迭代器遍历

在书写迭代器类型的时候要注意加上模板类型

vector<int>::iterator it1=v1.begin();

1.2.2补：string也可以放到模板里

对应类型vector<string>

此时若要尾插一个string可以用上匿名对象的方法

如要尾插一个:

//①
string s1("张三");
v1.push_back(s1);//②
v1.push_back(string("李四"));//③
v1.push_back("王五");

这里的②就是用了匿名对象，而③用了单参数构造函数的隐式类型转换加匿名对象。

1.2.3范围for遍历

普通类型的用法与string类似，但是string的话最好

for(const string& e:v)
{//...}

这样可以避免string频繁地进行深拷贝，消耗时间

1.3数据的控制

1.3.1插入删除的操作

使用push_back和pop_back来完成，头插头删需要配合insert和erase来使用

void push_back (const value_type& val);void pop_back();iterator insert (iterator position, const value_type& val);iterator erase (iterator position);

1.3.2resize的操作

比原来短就缩小，比原来长就默认补齐，这里填补的数字有缺省值，可以选择补默认的（如0）或者自行指定

void resize (size_type n, value_type val = value_type());

1.4顺序表的嵌套

即顺序表的顺序表，如

vector<vector<int>>

此时顺序表中存的就是一个个地址，访问的时候可以采用类似二维数组的访问方式

vv[i][j];//实质上是
vv.operator[](i).operator[](j);

1.5顺序表常常配合算法sort使用，但排序的方式可能是自定义类型，怎么解决？

sort添加了一个重载，这个重载中有第三个参数

Compare comp

这是一种仿函数的应用，我们只要知道默认排升序，如果要改降序可以采用这一操作：

greater<int> gt;
sort(s1.begin(),s1.end(),gt);

greator这一模板属于std库，于它对应的还有一个less，传过去可以排升序。

二、vector的实现

2.1实现时的分文件问题

对于模板的声明与定义分离我们需要准备多行代码，因此建议都在一个文件.h中实现

2.1补：阅读源码的过程

①先看成员变量

②再看核心成员函数，如构造函数，vector中的尾插等等

③大致了解以后再展开看

2.2reserve实现时的陷阱

我们实现vector的时候有三个成员变量

_start _finish _end_of_storage

分别存储初始位置，最后一个元素下一个位置，当前空间结束的下一个位置三处的迭代器

size依靠指针相减得出大小，因此申请新空间以后size（）会失效，需要提前记录size的大小方便使用。

2.3vector中的find问题

vector不再提供find，而是在算法algorithm头文件下有find函数来让stl统一使用。

2.4insert与erase涉及到的迭代器失效问题

2.4.1insert中

迭代器失效是扩容导致的，在插入时扩容后，_start和_finish会转移到新空间，那么原来标识插入位置的参数pos就会失效

直接在参数列表加引用可不可以？

答：不可以，例如当我们调用函数的语句写为

v1.insert(v1.begin(),0);

这样的时候，因为begin()是传值返回，而传值返回意味着会进行拷贝生成临时对象，临时对象具有常性，不可被修改

为此，我们以iterator作为返回值，出现类似

it=v1.insert(it,0);

这样的形式，更新一下it对应的迭代器。

2.4.2erase中

因为有时会erase最后一个数据，造成野指针，所以我们统一认为pos位置迭代器已失效，在VS中会在类型层面对它标识，不允许访问；在Linux中没有进行强制处理

此时我们的解决方案依旧是iterator作为返回值，更新一下来去除标识

2.4.2补：Linux中隐藏的陷阱

虽然在Linux中没有进行强制处理，但是也不能抱有侥幸心理，因为可能出现野指针问题和其他编译器无法运行的问题。

2.5实现拷贝构造时的问题

在自行实现vector的时候我们习惯直接用默认构造函数，但是因为拷贝构造也属于一种构造，所以在显示写完拷贝构造以后，编译器不会默认生成构造函数，这时可以用

2.5补：default关键字

vector()=default;

可以强制生成默认构造函数。

2.6迭代器区间进行构造中的问题

类模板的成员函数也可以写成函数模板，这里我们就用到了这一说法

template <class InputIterator>vector (InputIterator first, InputIterator last,const allocator_type& alloc = allocator_type());

我们之所以要写成函数模板，就是为了可以支持所有类型的迭代器进行区间初始化，它的实现逐步尾插即可

2.7缺省值T()与C++对内置类型的更新

对于泛型编程来说，有时我们需要给一种缺省值：来达到模板类型是什么，就给什么类型的值这一效果，为此出现了T()，

如vector的一种特殊构造：用n个val初始化vector就用到了

explicit vector (size_type n, const T& val = T(),const allocator_type& alloc = allocator_type());

其中，T()本质是自动调用构造函数，自定义类型完美解决，可是这样一来内置类型也需要构造了

2.7补：内置类型的构造

其实就是简单的赋值，如以下几种写法：

int a1=0;
int a2(1);
int a3=int();
int a4=int(1);

分别赋值0，1，0，1

2.8 vector(size_t n,const T& value)与vector(int n,const T& value)同时存在的原因

因为函数调用的冲突问题，

当

template <class InputIterator>vector (InputIterator first, InputIterator last);

与

vector (size_type n, const T& val = T())

同时存在的时候，我们的代码（int类型的特殊问题）

vector<int> v1(10,1);

本意是用10个1来初始化，却被上面的模板读取导致目的无法达到，因此重载一个函数来避免这种“抢调用”的情况。

2.9C++中{}的问题（initializer_list列表构造vector）

{}的功能不少，有

//多参数的隐式类型转换
A aa1={1,2};//单参数也可以用{}来隐式类型转换
B aa2={1};

要区分

std::vector<int> v1={1,2,3,4,5,6};

这里的隐式类型转换因为参数个数不固定，与上面不同，隐式类型转换到的新类型是属于C++11新支持的initializer_list类型

它有两种表示方法：

auto li={1,2,3,4,5,6};initializer_list<int> li={1,2,3,4,5,6};

此处li的类型为initializer_list

要想支持上述v1的顺利构造，需要写一个传参为initializer_list<T>类型的构造函数

库中：

vector (initializer_list<value_type> il,const allocator_type& alloc = allocator_type());

之后如

vector<int> v1({1,2,3});vector<int> v2={10,20,30};

都可以支持了。

2.10关于reverse对于含有资源管理的自定义类型的拷贝

对于内置类型和无资源管理的自定义类型，我们在实现reverse的时候进行memcpy对应的浅拷贝即可，但是对于如string类型的含有资源管理的自定义类型，我们在需要申请空间的时候会进行浅拷贝，delete销毁会导致原空间内容一并销毁,导致析构多次。

为此我们可以用下标+[]循环赋值来深拷贝解决。