雅安的旅游景点:C++ STL 容器技术之 vector向量容器

11.3.1 矢量类

1、矢量类的概念：
矢量（vector）类提供具有连续内存地址的数据结构，可通过下标运算符[ ]直接有效地访问矢量的任何元素。

与数组不同，vector的内存用尽时，vector自动分配更大的连续内存区，将原先的元素复制到新的内存区，并释放旧的内存区。这是矢量类的优点。

内存分配由分配子（Allocator）完成。分配子也是类，它运用了new和delete运算符，本教材不作进一步讨论。

2、矢量类的迭代子：
每个容器都有自己所支持的迭代子类型，迭代子决定了可采用哪种算法。vector支持随机访问迭代子，具有最强的功能。vector的迭代子通常实现为vector元素的指针。所谓选择容器类，实际上很大部分是选择所支持的迭代子。

3、矢量容器的声明例：
#include
……
vector vi; 
//定义存放整形序列的向量容器对象vi，长度为0的空vector
vector vf; //存放实型序列的向量容器
vector vch; //存放字符序列的向量容器
vectorvstr; //存放字符串序列的向量容器

4、矢量容器的构造函数：
vector(size_t n); 
//构造一个有n个元素的矢量，每个元素都是由默认的构造函数所建立的
vector(size_t n,T& V); 
//T表示矢量的基本类型，如int；为每个元素用同一个对象V来赋初值
vector(first,last); 
//元素的初值由区间[first,last)指定的序列中的元素复制而来 
vector(vector& X) 
//复制构造函数
这些构造函数还可以显式给出分配子(allocator)对象。

5、对矢量的操作包含了第六章在顺序表中所列出的操作，甚至更丰富。每种操作都是成员函数。对用户自定义的元素类，要重载“= =”和“<”等比较运算符。

【例11.2】寻找vector容器元素。

6、特殊类型迭代子：
*它们本身也具有五种四级迭代子属性之一

反转型迭代子（Reverse Iterator）：
它是把一切都颠倒过来。正向遍历一个第一类容器时，如果用了反转迭代子，实际上实现的是反向遍历。

插入型迭代子（Insertion Iterator）：
当用普通输出迭代子来产生一个元素序列时，一旦添加一些元素就得完全重写。例如普通输出迭代子可以把一个矢量a的内容复制到另一个矢量b中，复制可以从矢量b任一元素开始，矢量b对应位置上的元素被覆盖，相当于改写。插入迭代子则可以添加元素，复制时它可以把矢量a插入到矢量b任一位置。同一个copy()算法用不同类型迭代子，结果是不同的。

流迭代子(Stream Iterator)：
包括输入流迭代子（Istream_Iterator）和输出流迭代子（Ostream_Iterator）

简介：

vector是一种简单高效的容器，在尾端插入和删除元素，算法时间复杂度为O(1)常数阶，其他元素的插入和删除为O(n)线性阶，其中n为vector容器的元素个数。vector具有自动的内存管理功能，对于元素的插入和删除，可动态调整所占用的内存空间。

vector应用基础：

创建vector对象：

1、vector(const A& a=A()) 创建一个空的vector对象。

如：vector v;

2、vector(size_type n) 创建一个具有n个元素的vector对象，每个vector元素具有它的类型下的默认值。

如：vector v(10);

3、vector(size_type n, const T& value) 创建一个具有n个元素的vector对象，每个元素具有初始值value。

如：vector v(10, 5);

4、vector(const vector&) 通过拷贝一个vector对象的各个元素值，创建一个新的vector对象。

如：vector v1(10, 5);        vector v2(v1);

5、vector(const InputIterator first, const InputIterator last, const A& a=A()) 通过拷贝迭代器区间[first, last)的元素值，创建一个新的vector对象中，内存分配器可省略。

如：int iArray[] = {1,2,3};      vector v(iArray, iArray+3);

初始化赋值：

vector提供的push_back函数常用来进行vector容器的初始化，push_back函数在容器的尾端插入新元素value。

void push_back(const T& value)

元素的遍历访问：

vector的元素可采用数组或迭代器的方式进行遍历访问。

元素的插入：

insert函数可在任意位置插入元素，由于插入时需要先将插入位置后面的元素移位，以空出一个位置进行插入，因此insert函数的执行比push_back函数稍为耗时。insert函数的一个常用模板原型为：

iterator insert(iterator pos, const T& x)

元素的删除：

iterator erase(iterator pos) 删除迭代器pos所指的元素

iterator erase(iterator first, iterator last) 删除迭代器区间[first, last)的所有元素

void clear() 调用erase函数，清除所有元素

元素的反向遍历：

reverse_iterator rbegin()

reverse_iterator rend()

vector的交换：

void swap(vector&)

其它常用函数：

bool empty()

size_type size()

size_type max_size()

size_type capacity()

reference front()

reference back()

void pop_back()

举例分析：

1、

//用数组方式访问vector
#include
#include
using namespace std;

int main(void)
{
vector v;
v.push_back(20);
v.push_back(26);
v.push_back(39);
for (int i=0; i{
   cout << "v[" << i << "] = " << v[i] << endl;
}

return 0;
}

2、

//用迭代器访问vector元素
#include
#include
using namespace std;

int main(void)
{
vector v;
v.push_back(20);
v.push_back(26);
v.push_back(39);
vector::iterator i, iend;
iend = v.end();
int j;
for(i=v.begin(), j=0; i!=iend; i++, j++)
{
   cout << "v[" << j << "] = " << *i << endl;
}

return 0;
}

3、

//在任意位置插入vector元素
#include
#include
using namespace std;

int main(void)
{
vector v;
v.push_back(6);
v.push_back(7);
v.push_back(8);
v.push_back(10);
v.insert(v.begin()+3, 9);
v.insert(v.begin(), 5);
v.insert(v.end(), 11);
for (int i=0; i{
   cout << "v[" << i << "] = " << v[i] << endl;
}

return 0;
}

4、

//利用erase和clear函数删除vector元素
#include
#include
using namespace std;

class MyAnimal
{
public:
MyAnimal(char* name, int age) { this->name = name; this->age = age; }
~MyAnimal() {}

char* name;
int age;
};

int main(void)
{
MyAnimal* pDog = new MyAnimal("Dog", 1);
MyAnimal* pMonkey = new MyAnimal("Monkey", 2);
MyAnimal* pChicken = new MyAnimal("Chicken", 3);
MyAnimal* pSnake = new MyAnimal("Snake", 4);

vector v;
v.push_back(pDog);
v.push_back(pMonkey);
v.push_back(pChicken);
v.push_back(pSnake);

delete pMonkey;
v.erase(v.begin() + 1);
vector::iterator i, iend;
iend = v.end();
for (i=v.begin(); i!=iend; i++)
{
   cout << (*i)->name << " " << (*i)->age << endl;
}
v.clear();

return 0;
}

5、

//反向遍历vector元素
#include
#include
using namespace std;

int main(void)
{    
vector v;
v.push_back(1);
v.push_back(3);
v.push_back(5);
v.push_back(7);
v.push_back(9);
vector::reverse_iterator ri, riend;
riend = v.rend();
for (ri=v.rbegin(); ri!=riend; ri++)
{
   cout << *ri << endl;
}

return 0;
}

6、

//两个vector容器元素的交换
#include
#include
using namespace std;

void print(vector& v)
{
for (int i=0; i{
   cout << v[i] << " ";
}
cout << endl;
}

int main(void)
{
vector v1;
v1.push_back(11);
v1.push_back(12);
v1.push_back(13);
cout << "v1 = ";
print(v1);

vector v2;
v2.push_back(90);
v2.push_back(92);
cout << "v2 = ";
print(v2);

v1.swap(v2);
cout << "v1与v2交换后" << endl;
cout << "v1 = ";
print(v1);
cout << "v2 = ";
print(v2);

return 0;
}

7、

//vector容器的一些统计函数的使用
#include
#include
using namespace std;

void print(vector& v)
{
cout << "empty = " << v.empty() << endl;
cout << "size = " << v.size() << endl;
cout << "max_size = " << v.max_size() << endl;
cout << "capacity = " << v.capacity() << endl;
cout << endl;
}

int main(void)
{ 
vector v;
print(v);

//添加5个元素
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5); 
print(v);

//再添加4个元素
v.push_back(6);
v.push_back(7);
v.push_back(8);
v.push_back(9);
print(v);

//调整vector数据空间大小
v.reserve(30);
print(v);

return 0;
}