1.0vector的介绍及使用

vector的介绍

vector的文档介绍

可改变size的顺序表！

1.2 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 s("hello world");//string 结尾有\0
 vector<char> v5(s.begin(), s.end());//vector 结尾没有\0
 }

2 迭代器

迭代器遍历

operator[] 遍历

 //遍历:
 for (size_t i = 0;i<v.size();++i)
 {
     v[i] += 1;
     cout << v[i] << ' ';
 }
 cout << endl;

iterator 遍历

 //遍历：迭代器
 vector<int>::iterator it = v.begin();
 while (it != v.end())
 {
     *it -= 1;
     cout << *it << " ";
     ++it;
 }
 cout << endl;

范围for 遍历

 //遍历：范围for
 for (auto e : v)
 {
     cout << e << " ";
 }
 cout << endl;

指针 遍历

 int a[] = { 1,2,3 };
 //原生指针就是天然的迭代器，数组支持范围for，会被替换成指针
 for (int* p = a; p < a + sizeof(a) / sizeof(int); ++p)
 {
     //
 }

迭代器分类

查看迭代器类型

迭代器失效

一般发生在insert/erase中

 void test_vector4()
 {
     //场景
     //1 2 3 4 5 -> 正常
     //1 2 4 5   -> 没删除完
 
         //1245 -> it指向2  2删除后得到145 然后直接++it  it指向了5 跳过了4；
         //所以不能直接++；
         //或者erase有的编译器会缩容，缩容后it也会失效，跟insert类似
         //SGI版本和PJ版本的vector都没有采用缩容的做法。避免了频繁申请空间。
     //1 2 3 4   -> 崩溃
         //最后一个是偶数，当删除完，_finish指向了it的位置，然后it++了，则it永远不可能等于v1.begin()
         //所以崩溃了，while (it != v1.end())，可以改成小于吗？ 小于只能用在 随机迭代器身上，物理空间连续
                                             //而list呢？，所以!=是通用的！
     //上述单中问题，本质都是erase(it)以后it的意义变了，再去++it是不对的。(it失效了)
     vector<int> v1;
     v1.push_back(1);
     v1.push_back(2);
     //v1.push_back(3);
     v1.push_back(4);
     //v1.push_back(5);
     //vector<int>::iterator it = find(v1.begin(), v1.end(), 2);
     //if (it != v1.end())
     //{
     ////如果insert中发生了扩容，那么会导致it指向空间被释放
     ////it本质就是一个野指针，这种问题，我们就叫做迭代器失效
     //v1.erase(it);
     //}
     //vector<int>::iterator it = v1.begin();
     //while (it != v1.end())
     //{
     //if (*it % 2 == 0)
     //{
     //v1.erase(it);
     //}
 
     //++it;
     //}
     //正确写法
     vector<int>::iterator it = v1.begin();
     while (it != v1.end())
     {
         if (*it % 2 == 0)
         {
             it = v1.erase(it);
             //erase 以后it失效 返回it的下一个位置  下一个位置已更新，已经向前挪动，所以返回的看起来还是当前位置
         }
         else
         {
             ++it;
         }
     }
 
     for (auto e : v1)
     {
         cout << e << " ";
     }
     cout << endl;
 }

Q：string的insert/erase迭代器是否会失效？

A：会 ， string什么事后会失效，参考vector，跟vector完全类似。sting的insert 一般用下下标size_t参数，所以很少会失效

结论：只要使用迭代器访问的容器都可能会涉及迭代器失效

3 增删查改

增删：扩容

 void test_vector3()
 {
 vector<int> v;
 v.push_back(1);
 v.push_back(2);
 v.push_back(3);
 v.push_back(4);
 cout << v.max_size() << endl;//char42亿
 
 v.reserve(100);//只扩容 capacity = 100  size不变
 v.resize(100,5);//扩容后还 将有效数字加到100   capacity = 100 size = 100  
 v.resize(4);//还可以删除  但capacity不变，size = 4;
 //v[5];//断言越界
 //v.at(5);//抛异常
 }

删查改：

• erase 删除
• find 查找
• insert 插入修改

 void test_vector4()
 {
 vector<int> v;
 v.push_back(1);
 v.push_back(2);
 v.push_back(3);
 v.push_back(4);
 //v.assign(10, 5);//10个5 覆盖原来的数据，或者给区间
 
 //在区间中查找3 ，找到返回3，没找到返回end()//类型可以auto
 vector<int>::iterator ret = find(v.begin(), v.end(),3);
 if (ret != v.end())
 {
 cout << "找到了！"<<endl;
 v.insert(ret, 30);//在ret的前面位置插入30
 //v.erase(ret);//不能在这删除，因为ret被insert使用后会失效，会报错
 }
 //插入 insert
 v.insert(v.begin(), -1);//在头部插入-1
 //删除 erase
 //在begin - end 区间找到3 赋值给 pos迭代器
 vector<int>::iterator pos = find(v.begin(), v.end(), 3);
 if (pos != v.end())
 {
 v.erase(pos);//删除pos
 }
 //打印删除后的数据
 for (auto e : v)
 {
 cout << e << ' ';
 }
 
 //string 为什么有独立的find? 因为 sting还要查找子串，不仅仅查某个字符
 }

4.套娃

• 二维数组 vector<vector < type >> vv

void test_vector5()
{
    vector<vector<int>> vv;
    //开空间+初始化，默认0
    vv.resize(5);
    for (size_t i = 0; i < 5; ++i)
    {
        //先开空间
        vv[i].resize(i + 1);
        //每行第一个和最后一个置1
        vv[i][0] = vv[i][vv[i].size() - 1] = 1;
    }
    //sort(vv.begin(), vv.end());
}

5.其他补充

const

修饰的匿名对象，生命周期会延长

当没有构造函数，只有析构函数，对象出了这一行会直接析构，程序结束后 也可能再次调用析构函数。

当构造、析构函数同时存在，对象出了这一行则不会析构，直到出了当前函数作用域，才会析构。

swap

sawp(v1,v3) 3个深拷贝

v1.swap(v3) 仅交换成员变量指针

1.3 习题

118.杨辉三角

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        //定义vv
        vector<vector<int>> vv;
        //开空间+初始化，默认0
        vv.resize(numRows);
        for(size_t i = 0;i<numRows;++i)
        {
            //先开空间
            vv[i].resize(i+1);
            //每行第一个和最后一个置1
            vv[i][0] = vv[i][vv[i].size()-1] = 1;
        }
        //访问第一层vector
        for(size_t i = 0;i<vv.size();++i)
        {
            //访问第一层vector里的vector
            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];
                }
            }
        }
        //返回vv
        return vv;
    }
};

17. 电话号码的字母组合

class Solution {
    string arr[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

public:
    void _letterCombinations(const string& digits,size_t i,string combinStr,vector<string>& strV)
    {                       //数字字符串      //标识数字字符串  //取到的字母组合 // 返回的 string类型的vector
        if(i == digits.size())
        {
            strV.push_back(combinStr);// i = 3 后，将 "akt" 存进strV里，
                                    //然后回到 k的那一层(j = 0),这层循环完成，j++，则取到"aku"
            return;
        }
        //例如 digits = "258"
        //取2对应的位置 ,绝对映射 arr的2的校标
        //i 标识 数字字符串
        string str = arr[digits[i] - '0'];//i = 0(0:2)取到"abc" //i+1 = 1 (1:5)后取到"kjl"// i:1+1 = 2 (2:8)后取到"tuv"
        //j标识数字对应的字符串  取到的字符串多长，就递归多少次
        for(size_t j = 0; j<str.size();++j)
        {
            _letterCombinations(digits,i+1,combinStr + str[j],strV);
                                        //取到的"a"因为j是0 // 下一层进来取到 "k" j是0 // 再下一层是 "t" j是0
        }
    }
    vector<string> letterCombinations(string digits) {
        string combinStr;
        vector<string> strV;

        if(digits.empty())
        {
            return strV;
        }
        _letterCombinations(digits,0,combinStr,strV);

        return strV;
    }
};

！！！画一下递归展开图，总结后写题解！！！

？？？

2.0 ?vector 模拟实现

?练习

?写一个简单的vector

namespace uaena
{
    template<class T>
    class vector
    {
    public:
        typedef T* iterator;
        typedef const T* const_iterator;
        //构造函数
        vector()
            :_start(nullptr)
            , _finish(nullptr)
            , _endofstorage(nullptr)
        {}
        //析构函数
        ~vector()
        {
            if (_start)
            {
                delete[] _start;
                _start = _finish = _endofstorage = nullptr;
            }
        }
private:
        iterator _start;//指向起始位置
        iterator _finish;//指向数据个数的下一个
        iterator _endofstorage;//指向空间的最后位置的下一个
    };
}

?vector类实现

?构造函数

?s2(v1)

深拷贝_传统写法

v2(v1)
vector(const vector<T>& v)
{
    //给v2开辟和v1相同的空间
    _start = new T[v.capacity()];
    _finish = _start + v.size();
    _endofstorage = _start + v.capacity();

    memcpy(_start, v._start, v.size() * sizeof(T));
 //这里也要 更改浅拷贝  跟reserve一样。
    size_t sz = v.size();
    T* tmp = new T[n];
    if (_start)
    {
        //memcpy(tmp, _start, sizeof(T) * size());//浅拷贝，test6测试中会出错。
        for (size_t i = 0; i < sz; i++)
        {
            //T是int，一个一个拷贝没问题
            //T是string，一个一个调用的是T的深拷贝赋值，也没问题
            tmp[i] = _start[i];
        }
        delete[] _start;
    }
    _start = tmp;
    _finish = _start + sz;
    _endofstorage = _start + n;
}

现代写法

//一个类模板的成员函数，又可以是一个杉树模板
//构造
template <class InputIterator>//迭代器模板，自动推 迭代器类型
vector(InputIterator first, InputIterator last)
    :_start(nullptr)
    ,_finish(nullptr)
    ,_endofstorage(nullptr)
{
    while (_finish != last)
    {
        push_back(*_finish);
        ++first;
    }
}
void swap(vector<T>& v)
{
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_endofstorage, v._endofstorage);
}
//深拷贝_现代写法
//v2(v1)
vector(const vector<T>& v)
{
    vector<T> tmp(v.begin(),v.end());
    //this->swap(tmp)
    swap(tmp);
}

?v2 = v1

//v2 = v1
vector<T>& operator=(vector<T> v)
{
    swap(v);
    return *this;
}

?析构函数

?~vector()

~vector()
{
    if (_start)
    {
        delete[] _start;
        _start = _finish = _endofstorage = nullptr;
    }
}

?迭代器

?begin()

返回指向向量中第一个元素的迭代器。

迭代器返回的是 迭代器(iterator)类型

//迭代器
iterator begin()
{
    return _start;
}
const_iterator begin() const
{
    return _start;
}

?end()

指向序列末尾之后的元素的迭代器

//迭代器
iterator end()
{
    return _finish;
}
const_iterator end() const
{
    return _finish;
}

?成员函数

?swap

迭代器、引用和指针的交换

void swap(vector<T>& v)
{
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_endofstorage, v._endofstorage);
}

?size()

返回元素个数

size_t size() const
{
    return _finish - _start;
}

?capacity()

返回当前为vector分配的存储空间的大小

size_t capacity() const
{
    return _endofstorage - _start;
}

?reserve()

扩容，当n小于原来的容量，没有任何效果

void reserve(size_t n)
{
    if (n > capacity())
    {
        size_t sz = size();
        T* tmp = new T[n];
        if (_start)
        {
            //memcpy(tmp, _start, sizeof(T) * size());//浅拷贝，test6测试中会出错。
            for (size_t i = 0; i < sz; i++)
            {
                //T是int，一个一个拷贝没问题
                //T是string，一个一个调用的是T的深拷贝赋值，也没问题
                tmp[i] = _start[i];
            }
            delete[] _start;
        }
        _start = tmp;
        _finish = _start + sz;
        _endofstorage = _start + n;
    }
}

?resize()

扩容+初始化+删除数据

当n大于已有空间，则扩容，如果设置初始化值，则原来的数据保留，扩容的数据初始化为val，未给val则默认赋值0；

当n小于原来空间，会删除多余数据，空间不变。

resize(100,5);//初始化100个5
void resize(size_t n, const T& val =T())
{
    //删除数据直接挪动_finish
    if (n<size())
    {
        _finish = _start + n;
    }
    else
    {
        //其他两种情况 是空间够，直接填数据，空间不够扩容，再填数据
        if (n > capacity)
        {
            //扩容
            reserve(n);
        }
        while (_finish != _start + n)
        {
            //填数据
            *_finish = val;
            ++_finish;
        }
    }
}

?insert()

在pos前插入，可指定迭代器范围，但是可能会导致迭代器失效。

//在pos位置插入数据
void insert(iterator pos, const T& x)
{
    assert(pos >= _start);
    assert(pos <= _finish);//可以等于_finish ,pos是这个位置就可以尾插
    //满了就扩容
    if (_finish == _endofstorage)//如果已存数据 == 已有空间
    {
        //扩容会导致pos失效，扩容后更新pos
        size_t len = pos - _start;//记录位置
        //扩容
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        pos = _start + len;//更新
    }
    //插入数据 从后往前挪动

    iterator end = _finish - 1;
    while (end >= pos)
    {
        *(end + 1) = *(end);
        --end;
    }
    *pos = x;
    ++_finish;
}

[?erase()]()

删除pos指向的数据，其他数据向前挪动！

//删除pos位置的数据 
iterator erase(iterator pos)
{
    assert(pos >= _start);
    assert(pos < _finish);

    iterator begin = pos + 1;
    while (begin < _finish)
    {
        *(begin - 1) = *(begin);
        ++begin;
    }
    --_finish;
    return pos;
}

?push_back()

尾插

//尾插
void push_back(const T& x)
{
    if (_finish == _endofstorage)//如果已存数据 == 已有空间
    {
        //扩容
        //size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;//算出要开辟空间的大小
        //size_t sz = size();//先记录原有数据个数
        //T* tmp = new T[newCapacity];
        ////旧数据拷贝到新空间
        //if (_start) //如果_start 不为空则转移数据
        //{
        //    memcpy(tmp, _start, sizeof(T) * size()); 
        //    //void * memcpy ( void * 目的地, const void * 源, size_t num );
        //    //将 源 的num个拷贝到目的地
        //    delete[] _start; //释放原来的空间
        //}
        //_start = tmp; //扩容，_start 等于 新开辟的空间
        //_finish = _start + sz;//起始位置+加原来的数据个数 = 已有数据
        //_endofstorage = _start + newCapacity;//空间大小等于 起始位置+新开辟空间的大小
        reserve(capacity() == 0 ? 4 : capacity() * 2);
    }
    *_finish = x;
    ++_finish;
}

?pop_back()

尾删

void pop_back()
{
    //检查是否有数据
    assert(_finish > _start);
    --_finish;
}

?赋值函数

?[operator[]](https://cplusplus.com/reference/vector/vector/operator%5B%5D/)

返回对向量容器 中位置n处元素的引用

      reference operator[] (size_type n);
const_reference operator[] (size_type n) const;

T& operator[](size_t i)
{
    assert(i < size());
    return _start[i];
}
const T& operator[](size_t i)const
{
    assert(i < size());
    return _start[i];
}

?operator=

将新内容分配给容器，替换其当前内容，并相应地修改其大小。

 vector& operator= (const vector& x);

vector<T>& operator=(vector<T> v)
{
    swap(v);
    return *this;
}