【C++】vector使用 & 经典题型讲解-阿里云开发者社区

一. 构造和析构

💦构造函数

胡不多说，测试：

vector<int> v1;//无参构造
vector<int> v2(10, 1);//构造10个val，初始化为1
vector<int> v3(v2);//拷贝构造
vector<int> v3(++v2.begin(), --v2.end()); //迭代器区间初始化

那vector可以代替string吗？不可以！因为有'\0'，在操作上+=、find、<<、>>，因为vector是针对T 泛型，一般针对其他类型（int、double）,所以vector无法替代string

💦析构函数

还是老规矩，不用管，系统自己会调用

二. 遍历

⚡operator[]

//下标+[]      可读可写
for (size_t i = 0; i < v1.size(); ++i)
{
  v1[i]++;
  cout << v1[i] << endl;
}

⚡迭代器 & 范围for

✨ iterator 内嵌类型

iterator的使用接口说明

begin + end（重点）获取第一个数据位置的，获取最后一个数据的下一个位置的

rbegin + rend 获取最后一个数据位置，获取第一个数据前一个位置

// 遍历 - 可读可写
  vector<int>::iterator it = v.begin();
  while (it != v.end())
  {
  (*it) --;
  cout << *it << " ";
  it++;
  }
  cout << endl;

支持迭代器就支持范围for🍬(底层就是迭代器)

//范围for
  for (auto e : v1)
  {
    cout << e << " ";
  }
  cout << endl;

三.增删查改

🌈reserve & resize

resize初始化可以自己指定值

测试vector的默认扩容机制

#include<iostream>
#include<vector>
using namespace std;
int main()
{
  size_t sz;
  vector<int> foo;
  sz = foo.capacity();
  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';
  }
  }
}

vs：运行结果：vs下使用的STL基本是按照1.5倍方式扩容

g++以标准的2倍增长 ——

🌈push_back & pop_back

尾插尾删，不多赘述了

vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4);

🌈find

vector类中并没有find，这是因为算法库中就提供了一个模板函数，在迭代器区间中查找(左闭右开)，若查找到了，就返回迭代器；没找到就返回s.end()

vector<int> v1;
  v1.push_back(1);
  v1.push_back(2);
  v1.push_back(3);
  v1.push_back(4);
  vector<int>::iterator pos = find(v1.begin(), v1.end(), 3);
  if (pos != v1.end())
  {
      cout << "找到了！" << *pos << endl;
  }

🌈insert & erase

可头插头删

insert & erase 可以搭配 find 使用。string类的insert和erase通常支持下标，因为它find也刚好返回下标

// 头插
     v.insert(v.begin(), 0);
  vector<int>::iterator pos = find(v1.begin(), v1.end(), 3);
  if (pos != v1.end())
  {
    v1.insert(pos, 30);
  }
  pos = find(v1.begin(), v1.end(), 3);
  if (pos != v1.end())
  {
    v1.erase(pos);
  }

注意vector没有重载流提取和流插入<<、>>,遍历有迭代器和[],所以就不需要了

四. 排序

函数模板排序，对迭代器区间进行排序，默认是升序

vector<int> v1;
  v1.push_back(1);
  v1.push_back(2);
  v1.push_back(10);
  v1.push_back(4);
  sort(v1.begin(), v1.end());
  for (auto e : v1)
  {
    cout << e << " ";
  }
  cout << endl;

那我们想实现降序这么办呢？仿函数（后面栈细细分说），现在先会用

vector<int> v1;
  v1.push_back(1);
  v1.push_back(2);
  v1.push_back(10);
  v1.push_back(4);
  sort(v1.begin(), v1.end());
  for (auto e : v1)
  {
    cout << e << " ";
  }
  cout << endl;
  less<int> ls;//升序
  greater<int> gt;//降序
  sort(v1.begin(), v1.end(), greater<int>());//匿名对象~ 传参
  for (auto e : v1)
  {
    cout << e << " ";
  }
  cout << endl;

不仅仅可以排vector，string也能排（按照ascll码排序）

五. 小细节

举例：

vcctor<string> strV;
string str1("张三");
strV.push_back(str1);
strV.push_back(string("李四"));
strV.push_back("王五");//这个为什么能实现呢？？
答：会构造一个临时对象，然后被引用

因为构造函数是一个单参数，支持隐式类型转换

string(const char* str)//构造函数
{}

如果要使用范围for的时候，要谨慎小心再小心

for(const auto& str:: strV)
{
    cout<<str<<endl;
}

此处会被替换成迭代器，迭代器会依次取数据去赋值，如果不加引用就是就会调用拷贝构造，此时还是深拷贝，如果多次赋值就会浪费很多空间，所以要加&引用，拷贝别名，更加高效

经典题型讲解

0️⃣易错课后题

下面这个代码输出的是( C )

#include <iostream>       
#include <vector>
using namespace std;
int main(void)
{
  vector<int>array;
  array.push_back(100);
  array.push_back(300);
  array.push_back(300);
  array.push_back(300);
  array.push_back(300);
  array.push_back(500);
  vector<int>::iterator itor;
  for(itor=array.begin();itor!=array.end();itor++)
  {
  if(*itor==300)
  {
    itor=array.erase(itor);
  }
  }
  for(itor=array.begin();itor!=array.end();itor++)
  {
    cout<<*itor<<"";
  }
  return 0;
}

A.100 300 300 300 300 500

B.100 3OO 300 300 500

C.100 300 300 500

D.100 300 500

E.100 500

F.程序错误

解析：

vector::erase()：从指定容器删除指定位置的元素或某段范围内的元素 vector::erase()方法有两种重载形式如下：

iterator erase( iterator _Where); iterator erase( iterator _First,iterator _Last);

如果是删除指定位置的元素时：返回值是一个迭代器，指向删除元素下一个元素;

如果是删除某范围内的元素时：返回值也表示一个迭代器，指向最后一个删除元素的下一个元素;

在本题中，当 itor==300成立时，删除第一个值为300的元素，同时itor指向下一个元素（即是第二个值为300的元素）；在for(;;itor++)执行itor，itor指向第三个值为300的元素，进入下一个循环。

所以整个过程中，只删除了2个值为300的元素

💛T是一个数据类型，关于std::vector::at 和 std::vector::operator[] 描述正确的是( C )

A.at总是做边界检查， operator[] 不做边界检查.

B.at 不做边界检查， operator[] 做边界检查.

C.at和operator[] 都是会做边界检查的

D.以上都不对

at() 函数和 [] 运算符的重载，两者都可以得到相应下标的值，并且两者都会去做边界检查。当发生越界行为时，at 是抛异常，operator[] 是报出 assert 错误

1️⃣只出现一次的数字（单身狗）

题目链接：136. 只出现一次的数字

著名的单身狗问题，异或解法最经典：相同为0, 不同为1

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret =0;
        for(auto& i : nums)
        {
            ret^=i;
        }
        return ret;
    }
};

2️⃣只出现一次的数字ii（进阶）

题目链接：137. 只出现一次的数字 II

巧妙的思路：如下图所示，考虑数字的二进制形式，对于出现三次的数字，各二进制位出现的次数都是 3 的倍数

因此，统计所有数字的各二进制位中 1 的出现次数，并对 3 求余，结果则为只出现一次的数字

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret =0;
        size_t sum =0;//统计个数
        for(size_t i = 0; i< 32 ;++i)
        {
            sum = 0;
            for(auto& ch : nums)
            {
                sum += (ch>>i)&1;
            }
            sum %=3;
            ret += (sum<<i);
        }
        return ret;
    }
};

3️⃣只出现一次的数字iii（两只单身狗）

题目链接：260. 只出现一次的数字 III

著名的两只单身狗的故事

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        //全员异或
        int ret =0;
        for(auto e: nums)
        {
            ret ^= e;
        }
        //找到两个单身狗数字不同的一位(二进制)
        size_t pos = 0;
        while(pos < 32)
        {
            if((ret >> pos)&1 == 1 )
                break;
            pos++;
        }
        //分组异或
        vector<int> retArr(2);
        for(size_t i=0;i<nums.size();++i)
        {
            if((nums[i] >> pos)&1 == 1)
            {
                retArr[0] ^= nums[i];
            }
            else
            {
                retArr[1] ^= nums[i];
            }
        }
        return retArr;
    }
};

4️⃣删除有序数组中的重复项

题目链接：26. 删除有序数组中的重复项

解题思路：双指针移动，fast指针遍历，fast！=slow时候，fast赋值给++slow，不断遍历，最后返回长度。

ps：返回是要求长度，slow+1，不加就漏了最开始的那个数据

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        //慢指针、快指针
        int slow = 0, fast =0;
        while(fast < nums.size())
        {
            if(nums[slow] == nums[fast])
            {
                ++fast;
            }  
            else
            {
                nums[++slow] = nums[fast++];
            }
        }
      return slow + 1;
    }
};

5️⃣杨辉三角OJ

题目链接：118. 杨辉三角

用c语言做相当的麻烦，要动态开辟二维数组，所以我们学了vector之后就简单多了

vv[i][j]本质上是两次的[]函数调用~

💗核心思想：找出杨辉三角的规律，发现每一行头尾都是1，中间第[j]个数等于上一行[j-1]+[j]

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv;
        vv.resize(numRows);
        //初始化
        for(size_t i = 0; i < vv.size() ; ++i)
        {
            vv[i].resize(i + 1, 0);
            vv[i].front() = vv[i].back() = 1;
        }
        //遍历
        for(size_t i =0; i< vv.size() ; ++i)
        {
            for(size_t j = 0; j <vv[i].size(); ++j)
            {
                if(vv[i][j] == 0)
                {
                    vv[i][j] = vv[i-1][j] + vv[i-1][j-1];
                }
            }
        }
        return vv;
    }
};

6️⃣电话号码组合（中等）

题目链接：17. 电话号码的字母组合

本题是一道多路递归的深度遍历，简单的映射&回溯，递归深度取决于数字串长度，数字串映射多长就是，几路递归！！

class Solution {
    //单参数构造
    char* numTok[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:
    void Combine(string digits, int di, vector<string>& retV, string combineStr)
    {
        if(di == digits.size())
        {
            retV.push_back(combineStr);
            return ;
        }
        //先取数字字符映射的字符串
        int num = digits[di] - '0';
        string str = numTok[num];
        for(auto ch: str)
        {
            Combine(digits, di+1, retV, combineStr + ch);
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> v;
        if(digits.empty())
            return v;
        string str;
        Combine(digits, 0, v , str);
        return v;
    }
};

ps:

建立映射的时候，不需要用vector，因为是固定长度，并且可以想string("abc")那样初始化，因为支持隐式类型转化

思路不清晰的可以自己画画递归展开图：

📢写在最后

慢慢要开始笔试强化了，每天坚持写完并且博客输出易错知识点

【C++】vector使用 & 经典题型讲解