关于Vector的常见使用总结

前言：

vector 容器是 STL 中最常用的容器之一，记录一些常用操作与方法，谨防遗忘！

1、vector特性：

擅长在尾部插入或删除元素，在常量时间内就可以完成，时间复杂度为O(1)；

在容器头部或者中部插入或删除元素，则花费时间要长一些（移动元素需要耗费时间），时间复杂度为线性阶O(n)

2、创建vector

（1）创建空的 vector 容器：

        如：vector<double> values;

因为容器中没有元素，所以没有为其分配空间。当添加第一个元素时，vector 会自动分配内存

（2） 创建的同时指定初始值以及元素个数：

比如：vector<int> primes {2, 3, 5, 7, 11, 13, 17, 19};

这样就创建了一个含有 8 个素数的 vector 容器。

(3) 在创建 vector 容器时，也可以指定元素个数：

比如：vector<double> values(20);

如此，values 容器开始时就有 20 个元素，它们的默认初始值都为 0。

注意，圆括号 () 和大括号 {} 是有区别的，前者（例如 (20) ）表示元素的个数，而后者（例如 {20} ） 则表示 vector 容器中只有一个元素 20。

如果不想用 0 作为默认值，也可以指定一个其它值：

例如：vector<double> values(20, 1.0);

第二个参数指定了所有元素的初始值，因此这 20 个元素的值都是 1.0。

值得一提的是，圆括号 () 中的 2 个参数，既可以是常量，也可以用变量来表示

（４）通过存储元素类型相同的其它 vector 容器，也可以创建新的 vector 容器，例如：

int array[]={1,2,3};
std::vector<int>values(array, array+2);//values 将保存{1,2}
std::vector<int>value1{1,2,3,4,5};
std::vector<int>value2(std::begin(value1),std::begin(value1)+3);//value2保存{1,2,3}

由此，value2 容器中也具有 5 个字符 'c'。在此基础上，如果不想复制其它容器中所有的元素，可以用一对指针或者迭代器来指定初始值的范围，例如

由此，value2 容器中就包含了 {1,2,3} 这 3 个元素。

3、添加元素方法push_back()和emplace_back()的比较：

C++ STL vector添加元素（push_back()和emplace_back()）详解 (biancheng.net)http://c.biancheng.net/view/6826.html

emplace_back()该函数是 C++ 11 新增加的，其功能和 push_back() 相同，都是在 vector 容器的尾部添加一个元素。

emplace_back()和push_back()的区别

emplace_back() 和 push_back() 的区别，就在于底层实现的机制不同。

push_back() 向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）；

 emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程。

 显然完成同样的操作，push_back() 的底层实现过程比 emplace_back() 更繁琐，换句话说，emplace_back() 的执行效率比 push_back() 高。因此，在实际使用时，建议大家优先选用 emplace_back()。

由于 emplace_back() 是 C++ 11 标准新增加的，如果程序要兼顾之前的版本，还是应该使用 push_back()。

4、vector支持的函数 

５、 vector容器迭代器用法 

除此之外，C++ 11 新添加的 begin() 和 end() 全局函数也同样适用于 vector 容器。即当操作对象为 vector 容器时，其功能分别和表 1 中的 begin()、end() 成员函数相同，具体用：

如：

auto first = std::begin(values);
auto end = std::end (values);

等价于

 auto first = values.begin();
 auto end = values.end();

表 1 中这些成员函数的具体功能如图 2 所示。

图 2 迭代器的具体功能示意图
从图 2 可以看出，这些成员函数通常是成对使用的，即 begin()/end()、rbegin()/rend()、cbegin()/cend()、crbegin()/crend() 各自成对搭配使用。其中，begin()/end() 和 cbegin/cend() 的功能是类似的，同样 rbegin()/rend() 和 crbegin()/crend() 的功能是类似的。

值得一提的是，以上函数在实际使用时，其返回值类型都可以使用auto 关键字代替，编译器可以自行判断出该迭代器的类型。

 （1）最常用的功能：遍历访问容器中存储的元素；

使用begin() 和 end()遍历 vector 容器并输出其中的元素：

    vector<int>values{1,2,3,4,5};
    auto first = values.begin();
    auto end = values.end();
    while (first != end)
    {
        cout << *first << " ";
        ++first;
    }

vector 模板类中提供的 rbegin() 和 rend()成员函数，分别表示指向最后一个元素和第一个元素前一个位置的随机访问迭代器，又称它们为反向迭代器（如图 2 所示）。

需要注意的是，在使用反向迭代器进行 ++ 或 -- 运算时，++ 指的是迭代器向左移动一位，-- 指的是迭代器向右移动一位，即这两个运算符的功能也“互换”了。

反向迭代器用于以逆序的方式遍历容器中的元素 

注意： 

1、对于空的 vector 容器来说，begin() 和 end() 成员函数返回的迭代器是相等的，即它们指向的是同一个位置；

2、vector 容器在申请更多内存的同时，容器中的所有元素可能会被复制或移动到新的内存地址，这会导致之前创建的迭代器失效：

values 容器在增加容量之后，首个元素的存储地址发生了改变，此时再使用先前创建的迭代器，显然是错误的。因此，为了保险起见，每当 vector 容器的容量发生变化时，我们都要对之前创建的迭代器重新初始化一遍：

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int>values{1,2,3};
    cout << "values 容器首个元素的地址：" << values.data() << endl;
    auto first = values.begin();
    auto end = values.end();
    //增加 values 的容量
    values.reserve(20);
    cout << "values 容器首个元素的地址：" << values.data() << endl;
    first = values.begin();
    end = values.end();
    while (first != end) {
        cout << *first ;
        ++first;
    }
    return 0;
}

６、获取（修改）容器中存储的元素

 （1）下标访问单个元素：注意不要越界！

（2）vector 容器还提供了 2 个成员函数，即front() 和 back()，它们分别返回 vector 容器中第一个和最后一个元素的引用，通过利用这 2 个函数返回的引用，可以访问（甚至修改）容器中的首尾元素

７、指定位置插入元素

 1、insert() 函数：在 vector 容器的指定位置插入一个或多个元素。该函数的语法格式有多种，如表 1 所示。

2、emplace() ： C++ 11 标准新增加的成员函数，用于在 vector 容器指定位置之前插入一个新的元素。

再次强调，emplace() 每次只能插入一个元素，而不是多个。

该函数的语法格式如下：

iterator emplace (const_iterator pos, args...);

其中，pos 为指定插入位置的迭代器；args... 表示与新插入元素的构造函数相对应的多个参数；该函数会返回表示新插入元素位置的迭代器。

简单的理解 args...，即被插入元素的构造函数需要多少个参数，那么在 emplace() 的第一个参数的后面，就需要传入相应数量的参数。

 两者比较：emplace() 在插入元素时，是在容器的指定位置直接构造元素，而不是先单独生成，再将其复制（或移动）到容器中。因此，emplace()运行效率更高，所以在实际使用中，推荐大家优先使用 emplace()。

８、删除元素的几种方式 

 基于不同场景的需要，删除 vecotr 容器的元素，可以使用表 1 中所示的函数（或者函数组合）。

使用案例：

1、erase() 成员函数：

删除 vector 容器中指定位置处的元素，

该函数的语法格式为：iterator erase (pos);

其中，pos 为指定被删除元素位置的迭代器，同时该函数会返回一个指向删除元素所在位置下一个位置的迭代器。
如：demo.erase(demo.begin() + 1);

 删除容器中某个指定区域内的所有元素

iterator erase (iterator first, iterator last);

其中 first 和 last 是指定被删除元素区域的迭代器，同时该函数会返回指向此区域之后一个位置的迭代器。 

如：demo.erase(demo.begin()+1, demo.end() - 2);

2、remove() 函数：删除容器中和指定元素值相同的所有元素，

该函数定义在 <algorithm> 头文件中 

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    vector<int>demo{ 1,3,3,4,3,5 };
    //交换要删除元素和最后一个元素的位置
    auto iter = std::remove(demo.begin(), demo.end(), 3);

    cout << "size is :" << demo.size() << endl;
    cout << "capacity is :" << demo.capacity() << endl;
    //输出剩余的元素
    for (auto first = demo.begin(); first < iter;++first) {
        cout << *first << " ";
    }
    return 0;
}//在对容器执行完 remove() 函数之后，由于该函数并没有改变容器原来的大小和容量，因此无法使用之前的方法遍历容器，而是需要向程序中那样，借助 remove() 返回的迭代器完成正确的遍历。

remove() 的实现原理是，在遍历容器中的元素时，一旦遇到目标元素，就做上标记，然后继续遍历，直到找到一个非目标元素，即用此元素将最先做标记的位置覆盖掉，同时将此非目标元素所在的位置也做上标记，等待找到新的非目标元素将其覆盖。因此，如果将上面程序中 demo 容器的元素全部输出，得到的结果为 1 4 5 4 3 5。

另外还可以看到，既然通过 remove() 函数删除掉 demo 容器中的多个指定元素，该容器的大小和容量都没有改变，其剩余位置还保留了之前存储的元素。我们可以使用 erase() 成员函数删掉这些 "无用" 的元素。

比如，修改上面的程序：

1. #include <vector>
2. #include <iostream>
3. #include <algorithm>
4. using namespace std;
6. int main()
7. {
8. vector<int>demo{ 1,3,3,4,3,5 };
9. //交换要删除元素和最后一个元素的位置
10. auto iter = std::remove(demo.begin(), demo.end(), 3);
11. demo.erase(iter, demo.end());
12. cout << "size is :" << demo.size() << endl;
13. cout << "capacity is :" << demo.capacity() << endl;
14. //输出剩余的元素
15. for (int i = 0; i < demo.size();i++) {
16. cout << demo[i] << " ";
17. }
18. return 0;
19. }

运行结果为：

size is :3
capacity is :6
1 4 5

remove()用于删除容器中指定元素时，常和 erase() 成员函数搭配使用。

3、clear() 成员函数：删除容器中所有的元素 

９、vector作为函数的形式参数的使用：

c++中常用的vector容器作为参数时，有三种传参方式，分别如下：

function1(vector vec)，传值
function2(vector &vec)，传引用
function3(vector *vec)，传指针

注意，三种方式分别有对应的const形式，不在此讨论。

三种方式对应的调用形式分别为：

function1(vec)，传入值
function2(vec)，传入引用
function3(&vec),传入地址
三种方式的效果分别为：

会发生拷贝构造——不能修改原始实际的vector元素的值，这一点与普通数组名的传值参数不一样，数组名的参数传递时可以修改到实际数组元素值的；
不会发生拷贝构造
不会发生拷贝构造

例子：在DFS算法中使用visited标记数组

#include<iostream>
#include<vector>
using namespace std;
int n, e, s;
void DFS(vector<vector<int>>G, int N,vector<int>&V) //此处vector不能设置为传值参数！！否则在递归的过程中之前的标记改动无效！！
{
	V[N] = 1;
	if (N != s)cout << " ";
	cout << N;
	for (int v = 0; v < n;v++)if (!V[v]&&G[N][v])DFS(G, v, V);
}
int main() {
	int m;
	cin >> m; 

	while (m--) {
			 cin >> n >> e >> s;
			int u, v;
			vector<vector<int>>graph(n,vector<int>(n,0));
			vector<int>visited(n, 0);
			while (e--) {
				cin >> u >> v;
				graph[u][v]=1, graph[v][u]=1;
			}
			DFS(graph, s,visited);
			cout << endl;
	}
}