浅谈vector

Posted on | In | Visitors:

目录：
1.vector概述
2.vector声明
3.vector迭代器
4.vector数据结构
5.vector常用成员函数
6.测试程序

概述

vector的数据安排以及操作方式与array非常类似，两者唯一的差别在于空间的运用的灵活性。array是静态空间，一旦配置了就不能改变，要换个大点（或者小点）的房子，需要客户端自己来搞：先申请一块空间，然后将旧array中的元素挨个拷贝到新的array中，再释放旧array。vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以适应新元素的插入。因此，vector的应用对于内存的合理利用有很大帮助。
vector的实现技术，关键在于对大小的控制和重新配置时数据的移动效率。一旦vector旧空间满载，此时客户端继续新增元素，如果vector内部只是扩充了一个元素的空间，实为不智之举。其配置步骤为：配置新空间->移动元素->释放旧空间。工程浩大，时间成本高，故需采取未雨绸缪的方案。

声明

1
2
vector<typename> vector_name
vector<typename> vector_name(size,element)    //大小为size，里面元素全部初始化为element

迭代器

`vector<typename>::iterator ite`
ite的类型就是 * typename

vector维护的是一个连续的线性空间，所有不论其元素类型如何，普通指针都可以作为vector的迭代器而满足所有必要条件因为vector所需要的操作行为如：operator->，operator*,operator++,operator–,operator+=，operator-=，普通指针天生就具备。vector支持随机存取，而普通指针正有这样的能力。

vector数据结构

vector所采用的数据结构非常简单：线性连续空间。它以两个迭代器start，和finish分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器end_of_storage指向整块连续空间（含备用空间）的尾端：

1
2
3
4
5
6
7
8
9
template <class T,class Alloc = alloc>
class vector{
	...
	protected:
		iterator start;
		iterator finish;
		iterator end_of_storage
	...
}

为了降低空间配置时的速度成本，vector实际配置的大小可能比客户端需求量更大一些，以备将来可能的扩充，这就是容量（capacity）。换句话说，vector的容量一定大于等于它的大小，如果满载并继续添加元素，则重新配置一块原来两倍空间的容量，然后复制原来元素，释放旧的空间

常用成员函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
reference front(){ return * begin; }      //获取头元素
reference back(){ return * (end) - 1;}    //获取尾元素
void insert(iterator position,（size_type n,）const T &x) {}    //在某位置前插入(n个)元素
void push_back(const T &x){ ... }         //尾部插入元素
void pop_back(){ ... }	                   //尾部弹出元素
void clear(){...}                         //清空vector
iterator erase(iterator position) { ... } //删除某位置元素
iterator erase(iterator first,iterator last){...}    //删除[first,last)区域内的元素
iterator begin() {return start;}          //第一个元素的位置
iterator end(){return finish;}            //最后一个元素的下一个位置
iterator find(iterator start_position,iterator end_position,size_type element){}
                                    	   //在指定区域内查找指定元素，找不到则返回位置end()
size_type size() {...}                    //元素个数
bool empty(){...}                         //判断vector是否为空

每次调用push_back()时，该函数检查是否还有备用空间，如果有则插入，否则扩充空间（重新配置，拷贝数据，释放原空间）。因此，对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就失效了！

测试程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	int i;
	vector<int> iv(2,9);
	cout<<iv.size()<<endl;		//size = 2;
	cout<<iv.capacity()<<endl;	//capacity = 2;

	iv.push_back(1);
	cout<<iv.size()<<endl;		//size = 3;
	cout<<iv.capacity()<<endl;	//capacity = 4;

	iv.push_back(2);
	cout<<iv.size()<<endl;		//size = 4;
	cout<<iv.capacity()<<endl;	//capacity = 4;

	iv.push_back(3);
	cout<<iv.size()<<endl;		//size = 5;
	cout<<iv.capacity()<<endl;	//capacity = 8;

	iv.push_back(4);
	cout<<iv.size()<<endl;		//size = 6;
	cout<<iv.capacity()<<endl;	//capacity = 8;

	
	for(int i = 0;i<iv.size();i++)
		cout<<iv[i]<<' ';		//9 9 1 2 3 4
	cout<<endl;

	iv.push_back(5);
	cout<<iv.size()<<endl;		//size = 7;
	cout<<iv.capacity()<<endl;	//capacity = 8;

	iv.pop_back();
	iv.pop_back();
	cout<<iv.size()<<endl;		//size = 5;
	cout<<iv.capacity()<<endl;	//capacity = 8;

	vector<int>::iterator ivite = find(iv.begin(),iv.end(),1);
	if(ivite != iv.end())	
		iv.erase(ivite);
	cout<<iv.size()<<endl;		//size = 4;
	cout<<iv.capacity()<<endl;	//capacity = 8;

	for(int i = 0;i<iv.size();i++)
		cout<<iv[i]<<' ';		//9 9 2 3 
	cout<<endl;	
	ivite = find(iv.begin(),iv.end(),2);
	if(ivite != iv.end())	
		iv.insert(ivite,3,7);

	cout<<iv.size()<<endl;		//size = 7;
	cout<<iv.capacity()<<endl;	//capacity = 8;

	
	for(int i = 0;i<iv.size();i++)
		cout<<iv[i]<<' ';		//9 9 7 7 7 2 3
	cout<<endl;

	iv.clear();
	cout<<iv.size()<<endl;		//size = 0;
	cout<<iv.capacity()<<endl;	//capacity = 8;	
}

参考书籍：《STL源码剖析 侯捷》
注：
书中关于find（）函数结果中，如果没有找到指定元素，应当返回ite == end(),并非 ite == 0 。博客中已进行修正