一. vector概述
1. vector的数据安排以及操作方式与数组非常的相似。数组是静态空间,一旦配置了就无法改变其大小。但是vector是动态的,随着元素的加入它的内部机制会自动扩充空间以容纳新元素,所以不用担心vector的空间问题。
2. vector的内部实现机制:定义一个vector的时候,如果不指定大小默认会开辟一块大小为n(n是默认值)的空间,如果指定大小就会为其开辟相应大小的空间。当vector的空间容纳了所有的元素之后,这个时候系统会为vector开辟一个当前空间两倍的内存空间(如果两倍还不足则会开辟一个足够大的容量),然后把当前vector的所有元素拷贝到新开辟的空间中,再把原来的空间释放。(注意只要有重新配置空间,那么指向原来vector的所有迭代器都会失效)
所以实际上vector的动态是这样的过程“配置新空间->数据拷贝->释放旧空间”,所以如果不断动态的分配空间其实是很耗时间的。
二. vector的数据结构
1. vector所采用的数据结构非常简单就是线性连续空间,它以两个迭代器start和finish分别指向配置得来的连续空间中目前已经使用的范围,并用迭代器end_of_storage用来表示整个连续空间的尾端.
注意在STL中所有的区间都是采用前闭后开区间,实际上finish是当前最后一个元素的下一个位置。
template <class T, class Alloc = alloc> class vector{ ... protected: iterator start; //表示目前使用空间的头 iterator finish; //表示目前使用空间的尾 iterator end_of_storage; //表示目前可用空间的尾 ... };
2. 有了start、finish、end_of_storage三个迭代器,我们可以很容易的实现以下各种方法
template <class T, class Alloc = alloc> class vector{ public: iterator begin() { return start;} iterator end() { return finish;} size_type size() { return size_type(end()-begin());} size_type capacity() const { return size_type(end_of_storage()-begin());} bool empty() const { return begin() == end();} reference operator[](size_type n) { return *(begin()+n);} reference front() { return *begin();} reference back() { return *(end()-1)} ... };
3. vector动态空间配置如图所示
(1)初始化后vector的状态,目前不用开辟新空间
(2)当前vector空间已经满了,需要开辟新的空间
三. vector的使用样例
//vector的使用 void TestVector(void){ //定义个vector vector<int> v; cout<<v.size()<<endl; //输出0:元素个数为0 //插入元素 for(int i = 1; i <= 5; i++){ v.push_back(i); } cout<<v.size()<<endl; //输出5:元素个数为5 cout<<v.front()<<endl; //输出1:vector的头元素为1 cout<<v.back()<<endl; //输出5:vector的尾元素为5 //迭代器使用 vector<int>::iterator it; for(it = v.begin(); it != v.end(); it++){ cout<<*it<<endl; //输出1 2 3 4 5 } //删除元素 v.pop_back(); //删除最后一个元素 cout<<v.size()<<endl; //输出4:元素个数为4 //清空vector v.clear(); cout<<v.size()<<endl; //输出0:vector此时为空 }
四.vector的方法