11.3.1 矢量類
1、矢量類的概念：
矢量（vector）類提供具有連續(xù)內(nèi)存地址的數(shù)據(jù)結(jié)構(gòu)，可通過下標(biāo)運算符[ ]直接有效地訪問矢量的任何元素。
與數(shù)組不同，vector的內(nèi)存用盡時，vector自動分配更大的連續(xù)內(nèi)存區(qū)，將原先的元素復(fù)制到新的內(nèi)存區(qū)，并釋放舊的內(nèi)存區(qū)。這是矢量類的優(yōu)點。
內(nèi)存分配由分配子（Allocator）完成。分配子也是類，它運用了new和delete運算符，本教材不作進一步討論。
2、矢量類的迭代子：
每個容器都有自己所支持的迭代子類型，迭代子決定了可采用哪種算法。vector支持隨機訪問迭代子，具有最強的功能。vector的迭代子通常實現(xiàn)為vector元素的指針。所謂選擇容器類，實際上很大部分是選擇所支持的迭代子。
3、矢量容器的聲明例：
#include<vector>
……
vector<int> vi;
//定義存放整形序列的向量容器對象vi，長度為0的空vector
vector<float> vf; //存放實型序列的向量容器
vector<char> vch; //存放字符序列的向量容器
vector<char*>vstr; //存放字符串序列的向量容器
4、矢量容器的構(gòu)造函數(shù)：
vector(size_t n);
//構(gòu)造一個有n個元素的矢量，每個元素都是由默認的構(gòu)造函數(shù)所建立的
vector(size_t n,T& V);
//T表示矢量的基本類型，如int；為每個元素用同一個對象V來賦初值
vector(first,last);
//元素的初值由區(qū)間[first,last)指定的序列中的元素復(fù)制而來
vector(vector<T>& X)
//復(fù)制構(gòu)造函數(shù)
這些構(gòu)造函數(shù)還可以顯式給出分配子(allocator)對象。
5、對矢量的操作包含了第六章在順序表中所列出的操作，甚至更豐富。每種操作都是成員函數(shù)。對用戶自定義的元素類，要重載“= =”和“<”等比較運算符。
6、特殊類型迭代子：
*它們本身也具有五種四級迭代子屬性之一
反轉(zhuǎn)型迭代子（Reverse Iterator）：
它是把一切都顛倒過來。正向遍歷一個第一類容器時，如果用了反轉(zhuǎn)迭代子，實際上實現(xiàn)的是反向遍歷。
插入型迭代子（Insertion Iterator）：
當(dāng)用普通輸出迭代子來產(chǎn)生一個元素序列時，一旦添加一些元素就得完全重寫。例如普通輸出迭代子可以把一個矢量a的內(nèi)容復(fù)制到另一個矢量b中，復(fù)制可以從矢量b任一元素開始，矢量b對應(yīng)位置上的元素被覆蓋，相當(dāng)于改寫。插入迭代子則可以添加元素，復(fù)制時它可以把矢量a插入到矢量b任一位置。同一個copy()算法用不同類型迭代子，結(jié)果是不同的。
流迭代子(Stream Iterator)：
包括輸入流迭代子（Istream_Iterator）和輸出流迭代子（Ostream_Iterator）
簡介：
vector是一種簡單高效的容器，在尾端插入和刪除元素，算法時間復(fù)雜度為O(1)常數(shù)階，其他元素的插入和刪除為O(n)線性階，其中n為vector容器的元素個數(shù)。vector具有自動的內(nèi)存管理功能，對于元素的插入和刪除，可動態(tài)調(diào)整所占用的內(nèi)存空間。
vector應(yīng)用基礎(chǔ)：
創(chuàng)建vector對象：
1、vector(const A& a=A()) 創(chuàng)建一個空的vector對象。
如：vector<int> v;
2、vector(size_type n) 創(chuàng)建一個具有n個元素的vector對象，每個vector元素具有它的類型下的默認值。
如：vector<int> v(10);
3、vector(size_type n, const T& value) 創(chuàng)建一個具有n個元素的vector對象，每個元素具有初始值value。
如：vector<int> v(10, 5);
4、vector(const vector&) 通過拷貝一個vector對象的各個元素值，創(chuàng)建一個新的vector對象。
如：vector<int> v1(10, 5); vector<int> v2(v1);
5、vector(const InputIterator first, const InputIterator last, const A& a=A()) 通過拷貝迭代器區(qū)間[first, last)的元素值，創(chuàng)建一個新的vector對象中，內(nèi)存分配器可省略。
如：int iArray[] = {1,2,3}; vector<int> v(iArray, iArray+3);
初始化賦值：
vector提供的push_back函數(shù)常用來進行vector容器的初始化，push_back函數(shù)在容器的尾端插入新元素value。
void push_back(const T& value)
元素的遍歷訪問：
vector的元素可采用數(shù)組或迭代器的方式進行遍歷訪問。
元素的插入：
insert函數(shù)可在任意位置插入元素，由于插入時需要先將插入位置后面的元素移位，以空出一個位置進行插入，因此insert函數(shù)的執(zhí)行比push_back函數(shù)稍為耗時。insert函數(shù)的一個常用模板原型為：
iterator insert(iterator pos, const T& x)
元素的刪除：
iterator erase(iterator pos) 刪除迭代器pos所指的元素
iterator erase(iterator first, iterator last) 刪除迭代器區(qū)間[first, last)的所有元素
void clear() 調(diào)用erase函數(shù)，清除所有元素
元素的反向遍歷：
reverse_iterator rbegin()
reverse_iterator rend()
vector的交換：
void swap(vector&)
其它常用函數(shù)：
bool empty()
size_type size()
size_type max_size()
size_type capacity()
reference front()
reference back()
void pop_back()
舉例分析：
1、
//用數(shù)組方式訪問vector
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
vector<int> v;
v.push_back(20);
v.push_back(26);
v.push_back(39);
for (int i=0; i<v.size(); i++)
{
cout << "v[" << i << "] = " << v[i] << endl;
}
return 0;
}
2、
//用迭代器訪問vector元素
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
vector<int> v;
v.push_back(20);
v.push_back(26);
v.push_back(39);
vector<int>::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 <vector>
#include <iostream>
using namespace std;
int main(void)
{
vector<int> 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<v.size(); i++)
{
cout << "v[" << i << "] = " << v[i] << endl;
}
return 0;
}
4、
//利用erase和clear函數(shù)刪除vector元素
#include <iostream>
#include <vector>
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<MyAnimal*> 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<MyAnimal*>::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 <vector>
#include <iostream>
using namespace std;
int main(void)
{
vector<int> v;
v.push_back(1);
v.push_back(3);
v.push_back(5);
v.push_back(7);
v.push_back(9);
vector<int>::reverse_iterator ri, riend;
riend = v.rend();
for (ri=v.rbegin(); ri!=riend; ri++)
{
cout << *ri << endl;
}
return 0;
}
6、
//兩個vector容器元素的交換
#include <vector>
#include <iostream>
using namespace std;
void print(vector<int>& v)
{
for (int i=0; i<v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
}
int main(void)
{
vector<int> v1;
v1.push_back(11);
v1.push_back(12);
v1.push_back(13);
cout << "v1 = ";
print(v1);
vector<int> 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容器的一些統(tǒng)計函數(shù)的使用
#include <vector>
#include <iostream>
using namespace std;
void print(vector<int>& 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<int> 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);
//調(diào)整vector數(shù)據(jù)空間大小
v.reserve(30);
print(v);
return 0;
}
