【C++初阶：STL —— vector】vector的介绍及使用 | 迭代器失效问题 | vector的深度剖析及模拟实现 上

//这里的模板给的是缺省参数,也就意味着不传也行。Alloc是空间配置器,是一个内存池去申请和释放空间,我们直接用new也行,只不过内存池的效率要高一点
template <class T, class Alloc = alloc>
class vector {
public:
  typedef T value_type;
  typedef value_type* iterator;
protected:
  //这里为啥没有看到指针、size、capacity之类的东西? ———— 我们可以先看下iterator是啥(在public里已经指明了)
  //所以这里就给了三个T*的指针
  iterator start;
  iterator finish;
  iterator end_of_storage;
public:
  //其次还可以去看下它的构造函数,它完成了对3个成员变量的初始化工作
  vector() : start(0), finish(0), end_of_storage(0) {}
  //其次再看下push_back的实现
  //现阶段我们看源码还是有些难度的,等到后期我们会深挖
  void push_back(const T& x) {
  //说明没满
    if (finish != end_of_storage) {
    //这里不是直接赋值,而是调用construct,原因这里要对一块已有的空间显示调用构造函数初始化,我们在stl_vector.h里并没有找到有关实现
    //其实这里就要结合vector来看了,上面我们不是有一堆头文件嘛,那么它的实现肯定就在stl_vector.h上面的头文件中————stl_construct.h
      construct(finish, x);//怎么实现的?
      ++finish;
    }
    //满了,增容
    else
      insert_aux(end(), x);//怎么实现的?
  }
}

#include<iostream>
#include<vector>
#include<string>
using namespace std;
void test_vector1()
{
  vector<int> v;   
  //在C实现数据结构中我们的代码风格是驼峰法，而STL整体的风格是小写和下划线分隔的风格
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4);
  v.push_back(5);
  //遍历vector
  //1、operator[]
  for(size_t i = 0; i < v.size(); ++i)
  {
    v[i] -= 1;
    cout << v[i] << " ";  
  }
  cout << endl;
  //2、迭代器
  vector<int>::iterator it = v.begin();
  while(it != v.end())
  {
    *it += 1;
    cout << *it << " "; 
    ++it;
  }
  cout << endl;
  //3、范围for
  for(auto& e : v)
  {
    ++e;
    cout << e << " "; 
  }
  cout << endl;
  //为什么有了vector,还要有string呢
  //vector里给char，虽然它们底层都是数组中存储char,但是还是不一样的
  //相比T是char的vector,s对象中指向的空间结尾有\0,这样符合很多规范,比如需要去玩strstr、strcpy等,而vector不能玩+=字符串等
  //所以说T是char的vector不能去替代string 
  string s("111111");
  vector<char> vc(6, '1');
  //可以使用一段迭代器区间去构造,也可以控制这一段区间,且这里属于深拷贝(所有自己有独立空间的都要深拷贝)
  vector<int> v1(v.begin(), v.end());
  vector<int> v2(++v.begin(), --v.end());
  //可以使用其它容器的迭代器去构造,只要数据类型可以匹配上(*iterator对象的类型跟vector中存的数据类型是一致的)
  string s1("hello world");
  vector<char> v3(s1.begin(), s1.end());
  //vector<char*> v3(s1.begin(), s1.end());//err,无法从char转换到char*
  //怎么实现的
  /*template<class InputIterator>
  vector(InputIterator first, InputIterator last)
  {
     while(first != last)
     {
      push_back(*first);
      ++first;  
     }  
  }*/
  //拷贝构造
  vector<int> v4(v);
}
int main()
{
  test_vector1();
  return 0;
}

#include<iostream>
#include<vector>
using namespace std;
void test_vector1()
{
  vector<int> v;   
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4);
  v.push_back(5);
  //begin+end,这里和string非常相似，可以说迭代器就是指针
  vector<int>::iterator it = v.begin();
  while(it != v.end())
  {
    cout << *it << " "; 
    ++it;
  }
  cout << endl;
  //rbegin+rend,rbegin(rit)指向5,rend指向1,++rit怎么会倒着走呢
  //这里rit其实不再是原生指针了,它是一个被封装的类对象,重载operator++,才能实现++rit时是反向走,具体细节后面会说明
  //所以这就是之前为什么说迭代器不一定是(原生)指针的原因
  vector<int>::reverse_iterator rit = v.rbegin();
  while(rit != v.rend())
  {
    cout << *rit << " ";
    ++rit; 
  }
  cout << endl;
}
int main()
{
  test_vector1();
  return 0;
}

#include<iostream>
#include<vector>
using namespace std;
void test_vector1()
{
  vector<int> v;   
  //开空间,改变容量,如果确定知道需要多少空间,reserve可以缓解vector增容所带来的代价
  v.reserve(10);
  /* err,错误访问,在之前string里就说明了operator[]会去检查下标是否小于size,[]只能去对size范围内的数据使用
  for(size_t i = 0; i < 10; ++i)
  {
    v[i] = i; 
  }
  */
  //ok,正确访问
  for(size_t i = 0; i < 10; ++i)
  {
    v.push_back(i); 
  }
  //开空间+默认初始化,resize会影响size
  v.resize(20); 
  //开空间+指定初始化
  v.resize(20, 1);
}
int main()
{
  test_vector1();
  return 0;
}

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;
void test_vector1()
{
  std::vector<int> first;
  std::vector<int> second;
  std::vector<int> third;
  //assign可以分配新内容，替换其当前内容，并相应地修改其size
  //n个val
  first.assign(7, 100);
  //迭代器区间
  std::vector<int>::iterator it;
  it = first.begin() + 1;
  second.assign(it, first.end() - 1);
  //指针区间,这里myints指向1,myints+3指向4,为什么只输出1 2 3
  //这里的两个参数myints,myints+3分别传给迭代器区间first,last。迭代器一定是一个左闭右开的区间[first, last),因为迭代器的循环条件是first!=last
  int myints[] = { 1, 2, 3, 4, 5 };
  third.assign(myints, myints + 3);
  for(auto e : third)
  {
    std::cout << e << " ";  
  }
  std::cout << "Size of first:" << int(first.size()) << '\n';
  std::cout << "Size of second:" << int(second.size()) << '\n';
  std::cout << "Size of third:" << int (third.size()) << '\n';
}
void test_vector2()
{
  int a[] = { 1, 2, 3, 4, 5 };
  vector<int> v(a, a + 5);
  //头插
  v.insert(v.begin(), 0);
  //在2的前面插入,可以先find 2,但是vector没有提供find,但是算法里提供了函数模板的find
  //之所以算法里提供find的原因是vector要find,list要find,所以这里的find提供一个模板就解决了,你可以是vector的迭代器,也可以是list的迭代器,string的迭代器没必要,当然string里自己提供了,为什么string要自己提供呢
  //因为string不仅要支持find一个字符,还要支持查找一个字符串,使用find要包algorithm
  vector<int>::iterator pos = find(v.begin(), v.end(), 2);
  if(pos != v.end())//找不到返回last
  {
    v.insert(pos, 20);  
  }
}
void test_vector3()
{
  //讲了算法里的find后,顺道再讲一下比较常用的sort
  int a[] = { 1, 20, 2, 3, 4, 5 };
  vector<int> v(a, a + 6);
  //升序
  sort(v.begin(), v.end());
  //降序,这里需要传一个比较器对象,这里就涉及仿函数,具体在后面优先级队列会详细介绍,使用它需要包functional
  /*greater<int> gt;
  sort(v.begin(), v.end(), gt);*/
  sort(v.begin(), v.end(), greater<int>());//同上,更推荐使用匿名对象
  //sort不仅可以对容器排序,还可以对数组排序,因为指向数组空间的指针是天然的迭代器
  //也就是说从现在开始就可以把C语言的qsort放弃了 
  int b[] = { 30, 4, 50, 6, 7 };
  sort(b, b + 5);
}
void test_vector4()
{
  int a[] = { 1, 20, 2, 3, 4, 5 };
  vector(int> v(a, a + 6);
  //头删
  v.erase(v.begin());
  //删除2
  vector<int>::iterator pos = find(v.begin, v.end(), 2);
  if(pos != v.end))
  {
    v.erase(pos);
  } 
}
int main()
{
  test_vector1();
  test_vector2();
  test_vector3();
  test_vector4();
  return 0;
}

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void test_vector1()
{
  vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4):
  vector<int>::iterator pos = find(v.begin(), v.end(), 2);
  if(pos != v.end())
  {
    v.insert(pos, 20);  
  }
  //在insert以后,pos有可能就失效了,失效了程序有可能就会崩溃，迭代器失效问题就类似于野指针问题
  //如下分别进行访问和修改,注意不同的编译器结果有可能不同,在VS下连访问都过不了(insert时增容导致的)
  cout << *pos << endl;
  *pos = 100;
}
void test_vector2()
{
  vector<int> v;
  //提前增容下面就不会增容了,所以就不会失效了?
  v.reserve(6);
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4):
  vector<int>::iterator pos = find(v.begin(), v.end(), 2);
  if(pos != v.end))
  {
    v.insert(pos, 20);
  }
  //在VS下运行程序后没有报错,这里我们就可以认定只要发生了增容,那么它一定就会失效
  //这里虽然没有发生增容,但严格来说还是失效了,这里的失效指的是pos的意义变了,它不再指向原来的值2,而是指向20,所以说迭代器失效并不一定是野指针,还有意义变了
  cout << *pos << endl;
  *pos = 100;
}
void test_vector3()
{
  vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4);
  vector<int>::iterator pos = find(v.begin(), v.end(), 2);
  if(pos != v.end()）
  {
    v.erase(pos); 
  }
  //这里erase后,导致pos失效了,失效的原因是pos的意义被改变了,且虽然pos没有野指针,但是意义变了,vs(p.j)版本下进行了强制检查,所以这里*pos就会报错
  cout << *pos << endl;
  *pos = 100; 
}
int main()
{
  //insert
  test_vector1();
  test_vector2();
  //erase
  test_vector3();
  return 0;
}

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        //1、operator[]
        /*for(size_t i = 0; i < nums.size(); ++i)
        {
            ret ^= nums[i];
        }*/
        //2、迭代器
        /*vector<int>::iterator it = nums.begin();
        while(it != nums.end())
        {
            ret ^= *it;
            ++it;
        }*/
        //3、范围for
        for(auto e : nums)
        {
            ret ^= e;
        }
        return ret;
    }
};

class Solution {
public:
    //vector<vector<int>>就是一个二维数组,这里在vector模拟实现的时候也会细讲
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv;
        vv.resize(numRows);
        //生成
        for(size_t i = 0; i < vv.size(); ++i)
        {
          //每行有多少个,并初始化为0
            vv[i].resize(i + 1, 0);
            //每一行的第一个和最后一个赋值为1
            /*vv[i].front() = 1;
            vv[i].back() = 1;*/
            vv[i][0] = 1;
            vv[i][vv[i].size() - 1] = 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;
    }
};