關(guān)鍵字： vector容器? deque容器
3.2 vector容器
3.2.1基本概念
功能：vector數(shù)據(jù)結(jié)構(gòu)和數(shù)組非常相似，也稱為單端數(shù)組，在尾端可以進(jìn)行插入刪除操作；
vector與普通數(shù)組區(qū)別：數(shù)組為靜態(tài)空間，vector可以動態(tài)擴(kuò)展
注：vector容器的迭代器是支持隨機(jī)訪問的迭代器
動態(tài)擴(kuò)展
并不是在原空間之后續(xù)接新空間，而是找更大的內(nèi)存空間，然后將原數(shù)據(jù)拷貝新空間，釋放原空間；
vector容器的迭代器是支持隨機(jī)訪問的迭代器
3.2.2 vector構(gòu)造函數(shù)
函數(shù)原型：
1 vector<T> v;//采用模板實現(xiàn)類實現(xiàn)，默認(rèn)構(gòu)造函數(shù)
2 vector(v.begin(),v.end());//將v[begin(),end()）區(qū)間中的元素拷貝給本身
3 vector(n,elem);//構(gòu)造函數(shù)將n個elem拷貝給本身
4 vector(const vector &vec);//拷貝構(gòu)造函數(shù)
示例：
void test01()
{
vector<int> v1;
vector<int> v2(v1.begin(), v1.end());
vector<int> v3(10, 100);
vector<int> v4(v3);
}
3.2.3 vector賦值操作
函數(shù)原型：
1 vector &operator=(const vector &vec);
2 assign(beg,end);//左開右閉
3 assign(n,elem);
示例：
void test01()
{
vector<int> v1;
for (int i = 0; i < 10; ++i)
{
v1.push_back(i);
}
vector<int> v2 = v1;
vector<int> v3;
v3.assign(v1.begin(), v1.end());
vector<int> v4;
v4.assign(10, 100);
}
3.2.4 vector容量和大小
函數(shù)原型：
1 empty();//判空
2 capacity();//容量
3 size();//返回容器中元素個數(shù)
4 resize(int num);//重新指定容器長度，若容器變長，以默認(rèn)值填充；若變短，則末尾元素被刪除；
5 resize(int num, elem);//重新指定容器長度，若容器變長，以elem值填充；
3.2.5 vector插入和刪除
函數(shù)原型：
1 push_back(ele);//尾插
2 pop_back()；//刪除最后一個元素
3 insert(const_iterator pos, ele);//迭代器指向位置pos插入元素ele)
4 insert(const_iterator pos, int count, ele);//迭代器指向位置pos插入count個元素ele)
5 erase(const_iterator pos);//刪除迭代器指向元素
6 erase(const_iterator start, const_iterator end);//刪除迭代器從start到end之間的元素
7 clear();//刪除容器中所有元素
3.2.6 vector數(shù)據(jù)存取
函數(shù)原型：
1 at(int idx);//返回索引idx所指的數(shù)據(jù)
2 operator[];//返回索引idx所指的數(shù)據(jù)
3 front();//返回容器中第一個數(shù)據(jù)元素
4 back();//返回容器中最后一個數(shù)據(jù)元素
3.2.7 vector互換容器
功能：實現(xiàn)兩個容器內(nèi)元素進(jìn)行互換
函數(shù)原型：swap(vec);
用途：收縮內(nèi)存
示例：
void test02()
{
vector<int> v;
for (int i = 0; i < 1000; ++i)
{
v.push_back(i);
}
cout << "capacity: " << v.capacity()<< endl;
cout << "size: " << v.size() << endl;
v.resize(3);//重新指定大小 容量不變
cout << "capacity: " << v.capacity() << endl;
cout << "size: " << v.size() << endl;
//巧用swap收縮內(nèi)存
vector<int>(v).swap(v);
//vector<int>(v)//匿名對象 調(diào)用拷貝構(gòu)造函數(shù)
//按照v目前所用元素個數(shù)初始化該匿名對象
//匿名對象當(dāng)前行結(jié)束系統(tǒng)自動回收
cout << "capacity: " << v.capacity() << endl;
cout << "size: " << v.size() << endl;
}
3.2.8 vector預(yù)留空間
功能：減少vector動態(tài)擴(kuò)展容量時的擴(kuò)展次數(shù)
函數(shù)原型：reserve(int len);//容器預(yù)留len個元素長度，預(yù)留位置不初始化，元素不可訪問
示例：
void test01()
{
//統(tǒng)計擴(kuò)展（開辟空間）次數(shù)
int num = 0;
int *p = NULL;
vector<int> v1;
//利用reserve預(yù)留空間
v1.reserve(100000);
for (int i = 0; i < 100000; ++i)
{
v1.push_back(i);
if (p != &v1[0])
{
p = &v1[0];
++num;
}
}
cout << "num = " << num << endl;
}
3.3 deque容器
3.3.1 deque容器基本概念
功能：雙端數(shù)組，可以對頭端進(jìn)行插入刪除操作
deque和vector區(qū)別：
1 vector對于頭部的插入刪除效率低，數(shù)據(jù)量越大，效率越低
2 deque相對而言，對頭部的插入刪除速度比vector快
3 vector訪問元素的速度會比deque快，這和兩者內(nèi)部實現(xiàn)有關(guān)
deque內(nèi)部工作原理：
deque內(nèi)部有個中控器，維護(hù)每段緩沖區(qū)中的內(nèi)容，緩沖區(qū)中存放真實數(shù)據(jù)
中控器維護(hù)的是每個緩沖區(qū)的地址，使得使用deque時像一片連續(xù)的內(nèi)存空間
注：deque容器迭代器也是支持隨機(jī)訪問的
3.3.2 deque構(gòu)造函數(shù)
函數(shù)原型：
1 deque<T> deqT;//默認(rèn)構(gòu)造
2 deque(beg,end);//構(gòu)造函數(shù)將[begin,end)區(qū)間中的元素拷貝給本身
3 deque(n,elem);//構(gòu)造函數(shù)將n個elem拷貝給本身
4 deque(const deque &deq);//拷貝構(gòu)造函數(shù)
3.3.3 deque賦值操作
函數(shù)原型
1 deque &operator=(const deque &deq);
2 assign(beg,end);
3 assign(n,ele);
3.3.4 deque大小操作
函數(shù)原型
1 deque.empty();
2 deque.size();
3 deque.resize(num);//以默認(rèn)值0填充
4 deque.resize(num,elem);//以elem填充
注：deque容器不存在容量的概念，因為容量不受限制，
可以無限開辟新空間，中控器只需增加地址；
3.3.5 deque插入和刪除
函數(shù)原型：
兩端操作：
1 push_back(elem);
2 push_front(elem);
3 pop_back();
4 pop_front();
指定位置操作：
1 insert(pos,elem);//在pos位置插入一個elem元素的拷貝，返回新數(shù)據(jù)位置
2 insert(pos,n,elem);//在pos位置插入n個elem，無返回值
3 insert(pos,beg,end);//插入一個區(qū)間數(shù)據(jù)。無返回值
4 clear();
5 erase(beg,end);//刪除區(qū)間數(shù)據(jù)，返回下一個數(shù)據(jù)位置
6 erase(pos);//刪除pos位置數(shù)據(jù)，返回下一數(shù)據(jù)的位置
3.3.6 deque數(shù)據(jù)存取
函數(shù)原型
1 at(int idx);
2 operator[];
3 front();
4 back();
3.3.7 deque排序
函數(shù)原型
sort(iterator beg,iterator end);//對區(qū)間內(nèi)的元素進(jìn)行排序
注：頭文件 <algorithm>
