思维导图（建议收藏，复习小宝贝）

一、vector容器简介

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容量相关接口

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的增删查改

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的相关练习也会陆续更新

【C++】STL —— vector基本使用