vector容器、迭代器、基于范围的for循环

vector 容器封装了动态数组。
包含头文件： #include<vector>
vector 类模板的声明：

template<class T, class Alloc = allocator<T>>
class vector{
private:
T *start_;
T *finish_;
T *end_;
......
};

分配器
各种 STL 容器模板都接受一个可选的模板参数，该参数指定使用哪个分配器对象来管理内存
如果省略该模板参数的值，将默认使用 allocator<T>，用 new 和 delete 分配和释放内存。

一、构造函数

1）vector(); // 创建一个空的 vector 容器。
2）vector(initializer_list<T> il); // 使用统一初始化列表。
3）vector(const vector<T>& v); // 拷贝构造函数。
4）vector(Iterator first, Iterator last); // 用迭代器创建 vector 容器。
5）vector(vector<T>&& v); // 移动构造函数（C++11 标准）。

不重要的已省略。

析构函数~vector()释放内存空间。

二、特性操作

1）size_t max_size() const; // 返回容器的最大长度，此函数意义不大。
2）size_t capacity() const; // 返回容器的容量。
3）size_t size() const; // 返回容器的实际大小（已使用的空间）。
4）bool empty() const; // 判断容器是否为空。
5）void clear(); // 清空容器。
6）void reserve(size_t size); // 将容器的容量设置为至少 size。
7）void shrink_to_fit(); // 将容器的容量降到实际大小（需要重新分配内存）。
8）void resize(size_t size); // 把容器的实际大小置为 size。

三、元素操作

1）T &operator[](size_t n);
2）const T &operator[](size_t n) const; // 只读。
3）T &at(size_t n);
4）const T &at(size_t n) const; // 只读。

以上均为返回第n个元素
5）T *data(); // 返回容器中动态数组的首地址。
6）const T *data() const; // 返回容器中动态数组的首地址。
7）T &front(); // 第一个元素。
8）const T &front(); // 第一个元素，只读。
9）const T &back(); // 最后一个元素，只读。

10）T &back(); // 最后一个元素。

四、赋值操作

给已存在的容器赋值，将覆盖容器中原有的内容。
1）vector &operator=(const vector<T> &v); // 把容器 v 赋值给当前容器。
2）vector &operator=(initializer_list<T> il); // 用统一初始化列表给当前容器赋值。
3）void assign(initializer_list<T> il); // 使用统一初始化列表赋值。
4）void assign(Iterator first, Iterator last); // 用迭代器赋值。
5）void assign(const size_t n, const T& value); // 把 n 个 value 给容器赋值

vector<int> v1;
v1 = { 1,2,3,4,5 }; // 使用统一初始化列表赋值。
for (int ii = 0; ii < v1.size(); ii++) cout << v1[ii] << " ";
cout << endl;
vector<int> v2;
v2 = v1; // 把容器 v1 赋值给当前容器。
for (int ii = 0; ii < v2.size(); ii++) cout << v2[ii] << " ";
cout << endl;
vector<int> v3;
v3.assign({ 1,2,3,4,5 }); // 用 assign()函数给当前容器赋值，参数是统一初始化列表。
for (int ii = 0; ii < v3.size(); ii++) cout << v3[ii] << " ";
cout << endl;

五、交换操作

void swap(vector<T> &v); // 把当前容器与 v 交换。
交换的是动态数组的地址。

六、比较操作

bool operator == (const vector<T> & v) const;
bool operator != (const vector<T> & v) const;

七、插入和删除

1）void push_back(const T& value); // 在容器的尾部追加一个元素。
2）void emplace_back(...); // 在容器的尾部追加一个元素，...用于构造元素。C++11
3）iterator insert(iterator pos, const T& value); // 在指定位置插入一个元素，返回指向插入元
素的迭代器。
4）iterator emplace (iterator pos, ...); // 在指定位置插入一个元素，...用于构造元素，返回指向
插入元素的迭代器。C++11
5）iterator insert(iterator pos, iterator first, iterator last); // 在指定位置插入一个区间的元素，
返回指向第一个插入元素的迭代器。
6）void pop_back(); // 从容器尾部删除一个元素。
7）iterator erase(iterator pos); // 删除指定位置的元素，返回下一个有效的迭代器。
8）iterator erase(iterator first, iterator last); // 删除指定区间的元素，返回下一个有效的迭代器。

强烈建议使用emplace.

八、嵌套使用

vector<vector<int>> vv; // 创建一个 vector 容器 vv，元素的数据类型是 vector<int>。
vector<int> v; // 创建一个容器 v，它将作为容器 vv 的元素。

九、迭代器失效的问题

resize()、reserve()、assign()、push_back()、pop_back()、insert()、erase()等函数会引起 vector
容器的动态数组发生变化，可能导致 vector 迭代器失效。

十、补充

1.什么是迭代器？

迭代器是访问容器中元素的通用方法。
如果使用迭代器，不同的容器，访问元素的方法是相同的。
迭代器支持的基本操作：赋值（=）、解引用（*）、比较（==和!=）、从左向右遍历（++）。
一般情况下，迭代器是指针和移动指针的方法。

迭代器一般有五种：

1）正向迭代器

只能使用++运算符从左向右遍历容器，每次沿容器向右移动一个元素。
容器名<元素类型>::iterator 迭代器名; // 正向迭代器。
容器名<元素类型>::const_iterator 迭代器名; // 常正向迭代器。
相关的成员函数：
iterator begin();
const_iterator begin();
const_iterator cbegin(); // 配合 auto 使用。
iterator end();
const_iterator end();
const_iterator cend();

2）双向迭代器

具备正向迭代器的功能，还可以反向（从右到左）遍历容器（也是用++），不管是正向还是反向遍历，都可以用--让迭代器后退一个元素。

容器名<元素类型>:: reverse_iterator 迭代器名; // 反向迭代器。
容器名<元素类型>:: const_reverse_iterator 迭代器名; // 常反向迭代器。
相关的成员函数：
reverse_iterator rbegin();
const_reverse_iterator crbegin();
reverse_iterator rend();
const_reverse_iterator crend();

3）随机访问迭代器
具备双向迭代器的功能，还支持以下操作：
? 用于比较两个迭代器相对位置的关系运算（<、<=、>、>=）。
? 迭代器和一个整数值的加减法运算（+、+=、-、-=）。
? 支持下标运算（iter[n]）。
数组的指针是纯天然的随机访问迭代器。

4）输入和输出迭代器
这两种迭代器比较特殊，它们不是把容器当做操作对象，而是把输入/输出流作为操作对象。

#include <iostream>
#include <vector>
#include <list>
using namespace std;
struct Node // 单链表的结点。
{
int item;
Node* next;
};
int* find_(int* arr, int n, const int& val) // 在整型数组 arr 中查找值为 val 的元素。
{
for (int ii = 0; ii < n; ii++) // 遍历数组。
if (arr[ii] == val) return &arr[ii]; // 如果找到了，返回数组中元素的地址。
return nullptr;
}
int* find_(int* begin, int* end, const int& val) // 在整型数组的区间中查找值为 val 的元素。
{
for (int* iter = begin; iter != end; iter++) // 遍历查找区间。
if (*iter == val) return iter; // 如果找到了元素，返回区间中的
位置。
return nullptr;
}
Node* find_(Node* begin, Node* end, const Node& val) // 在单链表中查找值为 val
的元素。
{
for (Node * iter = begin; iter != end; iter = iter->next) // 遍历链表。
if (iter->item == val.item) return iter; // 如果找到了，返回链表中结点的地址。
return nullptr;
}
// 查找元素的算法。
template<typename T1, typename T2>
// begin-查找区间开始的位置；end-查找区间结束的位置；val-待查找的值。
T1 find_(T1 begin, T1 end, const T2 &val)
{
for (T1 iter = begin; iter != end; iter++) // 遍历查找区间。
if (*iter == val) return iter; // 如果找到了元素，返回区间中的位
置。
return end;
}
int main()
{
// 在 vector 容器中查找元素。
vector<int> vv = { 1,2,3,4,5 }; // 初始化 vector 容器。
vector<int>::iterator it2 = find_(vv.begin(), vv.end(), 3);
if (it2 != vv.end()) cout << "查找成功。\n";
else cout << "查找失败。\n";
// 在 list 容器中查找元素。
list<int> ll = {1,2,3,4,5}; // 初始化 vector 容器。
list<int>::iterator it3 = find_(ll.begin(), ll.end(), 3);
if (it3 != ll.end()) cout << "查找成功。\n";
else cout << "查找失败。\n";
}

2.基于范围的for循环

对于一个有范围的集合来说，在程序代码中指定循环的范围有时候是多余的，还可能犯错误。
C++11 中引入了基于范围的 for 循环。
语法：

for (迭代的变量 : 迭代的范围)
{
// 循环体。
}

vector<int> vv = { 1,2,3,4,5,6,7,8,9,10 };
//for (auto it = vv.begin(); it != vv.end(); it++) // 用迭代器遍历容器 vv。
//{
// cout << *it << " ";
//}
//cout << endl;
for (auto &val : vv) // 用基于范围的 for 循环遍历数组 vv。
{
cout << val << " ";
vv.push_back(10);
}
cout << endl;

注意：
1）迭代的范围可以是数组名、容器名、初始化列表或者可迭代的对象（支持 begin()、end()、++、
==）。
2）数组名传入函数后，已退化成指针，不能作为容器名。
3）如果容器中的元素是结构体和类，迭代器变量应该申明为引用，加 const 约束表示只读。
4）注意迭代器失效的问题。

强烈建议加引用。