        vector是C++标准模板库中的部分内容，中文偶尔译作"容器"，但并不准确。它是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。vector之所以被认为是一个容器，是因为它能够像容器一样存放各种类型的对象，简单地说，vector是一个能够存放任意类型的动态数组，能够增加和压缩数据。

        1. vector是表示可变大小数组的序列容器。

        2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自 动处理。

        3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是 一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大 小。

        4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是 对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。

        5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。

        6. 与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和 forward_lists统一的迭代器和引用更好

二、vector常用接口

1.vector初始化操作

1.构造函数


void test_vector1()
{
	vector<int> v1;        //无参构造
	vector<int> v2(10, 8); //用10个8初始化
	vector<int> v3(v2.begin(), v2.end()); //迭代器区间初始化
	vector<int> v4(v3);    //拷贝构造
 
	string s1("hello world");
	vector<char> v5(s1.begin(), s1.end()); //用string的迭代器区间初始化
}

2.析构函数

系统会自动调用析构函数

3.赋值重载函数


int main ()
{
    std::vector<int> v1 (3,0);
    std::vector<int> v2 (5,0);
 
    //赋值前
    cout << int(v1.size()) << '\n'; // v1 = 3
    cout << int(v2.size()) << '\n'; // v2 = 5
 
    v2 = v1;
 
    //赋值后
    cout << int(v1.size()) << '\n'; // v1 = 3
    cout << int(v2.size()) << '\n'; // v2 = 3
    return 0;
}

2.vector容量相关接口

函数接口	说明
size	当前有效存储的数据个数，并不是容量
capacity	当前为vector分配的存储空间大小
reserve	如果n（增容的数量）大于当前vector容器的容量，该函数会使容器重新分配存储空间，将容量增加到n(或更大)。
resize	1.如果n（增容的数量）小于当前容器的大小，则内容会减少到其前n个元素，并删除(并销毁它们)。 2.如果n（增容的数量）大于当前容器的大小，则通过在末尾插入尽可能多的元素来扩展内容，使容器的大小达到n。如果指定了val，则新元素被初始化为val的副本，否则被初始化为值
empty	判断容器是否为空
max_size	返回vector容器所能容纳的最大元素个数

1.基本使用方法


void test_vector3()
{
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(5);
    
    v1.size();         // 计算当前数据个数
    v1.capacity();     // 计算当前的空间容量
    v1.max_size();     // 查看最大容量
    v1.empty();        // 判断容器是否为空
	v1.reserve(100);   // 扩容
	v1.resize(100, 5); // 扩容+初始化 或 删除数据
 
}

reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。

resize在开空间的同时还会进行初始化，影响size。

2.vector增容机制


//检查容量递增情况
void test_vector4()
{
	size_t sz;
	std::vector<int> foo;
	sz = foo.capacity();
	std::cout << "making foo grow:\n";
	for (int i = 0; i < 100; i++)
	{
		foo.push_back(i);
		if (sz != foo.capacity())
		{
			sz = foo.capacity();
			std::cout << "capacity changed: " << sz << '\n';
		}
	}
}

capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，顺序表增容都是2倍，具体增长多少是根据具体的需求定义的。vs是 PJ 版本STL，g++是 SGI 版本STL。

3.vector访问及遍历操作

这三种遍历方式大致上和string类是一样的

1.元素访问——下标

常用函数	说明
operator[ ]	支持下标访问，返回对位于字符串中pos位置的元素的引用。
front	返回对vector容器中第一个元素的引用。
back	返回对vector容器中最后一个元素的引用。
at	支持下标访问，返回对位于字符串中pos位置的元素的引用。


void test_vector2()
{
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
 
	//方式1  -----  operator[ ]
	for (size_t i = 0; i < v1.size(); i++)
	{
		cout << v1[i] << " ";//  v1[i] 等价于 v1.operator[](i)
		v1[i] += 1;//修改
	}
	cout << endl;
 
	for (size_t i = 0; i < s1.size(); ++i)
	{
		s1.at(i) += 1;
	}
 
}

operator[ ] 和 at 的效果是一样的，两者区别在于检查机制：

operator[ ]：当发生越界访问时，会直接assert报错；

at：当发生越界访问时，会直接抛异常

2. 元素访问——迭代器


void test_vector2()
{
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
 
    //方式2  ----- 迭代器（在C++中凡是使用迭代器，都是左闭右开区间）
	vector<int>::iterator it = v1.begin();
	while (it != v1.end())
	{
		*it -= 1;
		cout << *it << " ";
		++it;
	}
	cout << endl;
 
}

3.元素访问——范围for


void test_vector2()
{
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
 
	//方式3 ----- 范围for
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;;
 
}

4.vector的增删查改

函数	说明
assign	将新内容赋给vector，替换其当前内容，并相应地修改其大小。
push_back	在vector的最后一个元素之后添加一个新元素。
pop_back	移除vector中的最后一个元素，有效地将容器大小减少1。
insert	1.在指定位置插入一个元素 2.在指定位置插入多个 3.在指定位置插入插入某迭代器区间的元素
erase	从vector中移除单个元素或一组元素（迭代器区间）。
swap	交换两个数据
clear	将数据清空


void test_vector3()
{
	vector<int> v1;
	vector<int> v2(4,8);
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(5);
	v1.push_back(6);
 
 
	//查找---在vector里没有find函数
	vector<int>::iterator ret = find(v1.begin(), v1.end(), 3);
	//auto ret = find(v1.begin(), v1.end(), 3);
 
	if (ret != v1.end())
	{
		cout << "找到了" << endl;
		v1.insert(ret, 30);                     //在ret的前面插入30
		v1.insert(ret, 3, 40);                  //在ret的前面插入3个40
		v1.insert(ret, v2.begin(), v2.end());   //在ret前面插入v2的迭代器区间
	}
 
	v1.insert(v1.begin(), 10);  //在v1的起始迭代器前插入10（相当于头插）
	v1.insert(v1.end(), 20);    //在v1的末尾迭代器前插入10（相当于尾插）
 
	vector<int>::iterator pos = find(v1.begin(), v1.end(), 3);
	if (pos != v1.end())
	{
		v1.erase(pos); // 删除pos位置的元素
	}
 
    v1.erase(v1.begin() + 2, v1.end() - 3); // 删除一部分元素
 
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;
	v1.clear(); //清空数据
}

在vector中并没有find函数，但是在string类当中却有，这是为什么呢？

因为vector本身作为数组，对于查找的需求比较简单，不想string类那样需要查找子串，我们可以直接使用算法库当中的find函数（使用前需要包#include <algorithm>头文件）。

库中的代码实现：

返回范围[first,last]中第一个与val比较相等的元素的迭代器，如果没有找到这样的元素，则返回last。


template<class InputIterator, class T>
  InputIterator find (InputIterator first, InputIterator last, const T& val)
{
  while (first!=last) {
    if (*first==val) return first;
    ++first;
  }
  return last;
}

三、牛刀小试

链接：https://leetcode.cn/problems/single-number/


class Solution {
public:
    int singleNumber(vector<int>& nums) {
            int n = 0;
            for(auto e : nums) 
            {
                n ^= e; //让数组中的每个数异或一下，相同的数异或为0
            }
            return n;
 
            //或
            /*
            for(int i = 0;i < nums.size();++i)
            {
                n ^= nums[i];
            }
            return n;
            */
    }
};

本篇博客还一个比较重要的知识点：迭代器试下的问题。将会在下一期的博客中更新，对于vector的相关练习也会陆续更新

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/452806