• STL——vector

    目录

    1. vector的介绍

    2. vector的各个函数

    3. vector 迭代器失效问题

    4. vector模拟实现及注意

    C语言总结在这常见八大排序在这

    作者和朋友建立的社区：非科班转码社区-CSDN社区云💖💛💙

    期待hxd的支持哈🎉 🎉 🎉

    最后是打鸡血环节：你只管努力，剩下的交给天意🚀 🚀 🚀  

    1. vector的介绍

    vector - C++ Reference (cplusplus.com)

    vector与string 理论上应该是一样的，但其实操作上有些不同，没有string方便。而且string和c有相关联，所以后面要有'\0'

    1. vector 是表示可变大小数组的序列容器。
    2. 就像数组一样， vector 也采用的连续存储空间来存储元素。也就是意味着可以采用下标对 vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
    3. 本质讲， vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小， 为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是 一个相对代价高的任务，因为每当一个新的元素加入到容器的时候， vector 并不会每次都重新分配大 小。
    4. vector 分配空间策略： vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存 储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是 对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数（O1）时间的复杂度完成的。
    5. 因此， vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
    6. 与其它动态序列容器相比（ deque, list and forward_list ）， vector在访问元素的时候更加高效，在末 尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起 list 和 forward_list 统一的迭代器和引用更好。

    PS:

    在C++里面因为模板存在的原因，所以内置类型也是有构造函数的，析构也有，这样才能更好支持模板

    2. vector的各个函数

    以下列出常见的

    vector 的定义
    (constructor) 构造函数声明
    接口说明
    vector() （重点）
    无参构造
    vector （ size_type n, const value_type& val = value_type() ）
    构造并初始化 n 个 val
    vector (const vector& x); （重点）
    拷贝构造
    vector (InputIterator fifirst, InputIterator last);
    使用迭代器进行初始化构造
    vector iterator 的使用
    iterator 的使用
    接口说明
    begin +
    end （重点）
    获取第一个数据位置的 iterator/const_iterator ， 获取最后一个数据的下一个位置的iterator/const_iterator
    rbegin + rend
    获取最后一个数据位置的 reverse_iterator ，获取第一个数据前一个位置的reverse_iterator

    vector 空间增长问题 

    容量空间
    接口说明
    size
    获取数据个数
    capacity
    获取容量大小
    empty
    判断是否为空
    resize （重点）
    改变 vector 的 size
    reserve （重点）
    改变 vector 的 capacity
    vs 下 capacity 是按 1.5 倍增长的， g++ 是按 2 倍增长的。
    但是不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义
    的。vs是PJ版本STL，g++是SGI版本STL。
    reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
    resize在开空间的同时还会进行初始化，同时影响size。
    如果已经确定vector中要存储元素大概个数，可以提前将空间设置足够
    就可以避免边插入边扩容导致效率低下的问题了
    vector 增删查改
    vector 增删查改
    接口说明
    push_back （重点）
    尾插
    pop_back （重点）
    尾删
    find
    查找。（注意这个是算法模块实现，不是 vector 的成员接口）
    insert
    在 position 之前插入 val
    erase
    删除 position 位置的数据
    swap
    交换两个 vector 的数据空间
    operator[] （重点）
    像数组一样访问

    3. vector 迭代器失效问题

    迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。

    对于 vector 可能会导致其迭代器失效的操作有：
    会引起其底层空间改变的操作，都有可能是迭代器失效 ，比如： resize 、 reserve 、 insert 、 assign 、push_back等。
    以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，
    而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的空间，而引起代码运行时崩溃。
    解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新赋值即可。
    问题：
    1.  

    2.

    扩容的时候也会有迭代器失效的问题，因为pos是值传递，外面的it没有改变

    3.

    往前插入时，然后++指向同一个值，会死循环 

    解决：

     

     

    综合上面有两种失效，一个是野指针，一个是指向的意义变了 

    指定位置元素的删除操作 - -erase
    删除pos位置的数据，导致pos迭代器失效。
    erase 删除 pos 位置元素后， pos 位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos 刚好是最后一个元素，删完之后 pos 刚好是 end 的位置，而 end 位置是没有元素的，那么pos 就失效了。因此删除 vector 中任意位置上元素时， vs 就认为该位置迭代器失效了。
    1. erase的失效都是意义变了，或者不在访问数据的有效范围。
    2.一般不会使用缩容的方案，那么erase的失效，一般也不存在野指针的失效 
    SGI STL中，迭代器失效后，代码并不一定会崩溃，但是运行结果肯定不
    对，如果it不在begin和end范围内，肯定会崩溃的。
    与 vector 类似， string 在插入 + 扩容操作 +erase 之后，迭代器也会失效
    扩容之后，it指向之前旧空间已经被释放了，该迭代器就失效了
    后序打印时，再访问it指向的空间程序就会崩溃
    迭代器失效解决办法：在使用前，对迭代器重新赋值即可。
    PS:
    Linux 下， g++ 编译器对迭代器失效的检测并不是非常严格，处理也没有 vs 下极端。
    SGI STL 中，迭代器失效后，代码并不一定会崩溃，但是运行结果肯定不对，如果it 不在 begin 和 end 范围内，肯定会崩溃的。
    问题：错误匹配的时候
    解决：多增加一个重载版本

    4. vector模拟实现及注意

    注意: 对于浅拷贝的问题要多加注意，如用memcpy

    1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中。
    2. 如果拷贝的是自定义类型的元素， memcpy 既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy 的拷贝实际是浅拷贝。 
    1. #pragma once
    2. #include
    3. #include
    4.  
    5. using std::cin;
    6. using std::cout;
    7. using std::endl;
    8.  
    9.  
    10. template<class T=int>
    11. class my_vector
    12. {
    13. public:
    14.     // Vector的迭代器是一个原生指针
    15.         typedef T* iterator;
    16.         typedef const T* const_iterator;
    17.         iterator begin()
    18.         {
    19.             return _start;
    20.         }
    21.         iterator end()
    22.         {
    23.             return _finish;
    24.         }
    25.         const_iterator cbegin()const                    //注意这里的两个const
    26.         {                                               //前面限制返回值不可被修改
    27.             return _start;                              //后面限制传入this const修饰来调用此次函数
    28.         }
    29.         const_iterator cend() const
    30.         {
    31.             return _finish;
    32.         }
    33.         // construct and destroy
    34.         //默认构造
    35.         my_vector()
    36.             :_start(nullptr),
    37.             _finish(nullptr),
    38.             _endOfStorage(nullptr)
    39.         {}
    40.         //n个值构造
    41.         my_vector(int n, const T& value = T())                  // value = T() 默认构造 内置类型也有
    42.             :_start(nullptr),
    43.             _finish(nullptr),
    44.             _endOfStorage(nullptr)
    45.         {
    46.             reserve(n);
    47.             for (int i = 0; i < n; i++)
    48.             {
    49.                 push_back(value);
    50.             }
    51.         }
    52.         //迭代器区间构造
    53.         template<class InputIterator>
    54.         my_vector(InputIterator first, InputIterator last)
    55.             :_start(nullptr),
    56.             _finish(nullptr),
    57.             _endOfStorage(nullptr)
    58.         {
    59.             while (first != last)
    60.             {
    61.                 push_back(*first);
    62.                 first++;
    63.             }
    64.         }
    65.         //拷贝构造
    66.         my_vector(const my_vector& v)
    67.             :_start(nullptr),
    68.             _finish(nullptr),
    69.             _endOfStorage(nullptr)
    70.         {
    71.             const_iterator first = v.cbegin();
    72.             while (first != v.cend())
    73.             {
    74.                 push_back(v[first]);
    75.                 first++;
    76.             }
    77.         }
    78.         my_vector& operator= (my_vector v)
    79.         {
    80.             swap(v);
    81.             return *this;
    82.         }
    83.         ~my_vector()
    84.         {
    85.             if (_start)
    86.             {
    87.                 delete _start;
    88.                 _start = _endOfStorage = _finish = nullptr;
    89.             }
    90.         }
    91.         // capacity.
    92.         size_t size() const
    93.         {
    94.             return _finish - _start;
    95.         }
    96.         size_t capacity() const
    97.         {
    98.             return _endOfStorage - _start;
    99.         }
    100.         void reserve(size_t n)
    101.         {
    102.             size_t sz = size();
    103.             if (n > capacity())
    104.             {
    105.                 //注意是新new了个对象
    106.                 //避免浅拷贝的问题
    107.                 T* tmp = new T[n];
    108.                 if (_start)
    109.                 {
    110.                     for (size_t i = 0; i < size(); i++)
    111.                     {
    112.                         tmp[i] = _start[i];
    113.                     }
    114.                     delete _start;
    115.                 }
    116.                 _start = tmp;
    117.             }
    118.             _finish = _start + sz;
    119.             _endOfStorage = _start + n;
    120.         }
    121.         void resize(size_t n, const T& value = T())
    122.         {
    123.             if (n > capacity())
    124.             {
    125.                 reserve(n);
    126.             }
    127.             if (n > size())
    128.             {
    129.                 //1 2 3     8     5
    130.                 while (_finish != _start + n)
    131.                 {
    132.                     *_finish = value;
    133.                     _finish++;
    134.                 }
    135.             }
    136.             else
    137.             {
    138.                 _finish = _start + n;
    139.             }
    140.         }
    141.         ///access///
    142.         T& operator[](size_t pos)
    143.         {
    144.             assert(pos<size());
    145.  
    146.             return *(_start + pos);
    147.             //return _start[pos];
    148.         }
    149.         const T& operator[](size_t pos)const
    150.         {
    151.             assert(pos < size());
    152.  
    153.             return *(_start + pos);
    154.         }
    155.         ///modify/
    156.         void push_back(const T& x)
    157.         {
    158.             if (_finish == _endOfStorage)
    159.             {
    160.                 size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
    161.                 reserve(newCapacity);
    162.             }
    163.             *_finish = x;
    164.             ++_finish;
    165.         }
    166.         void pop_back()
    167.         {
    168.             assert(_finish > _start);
    169.             _finish--;
    170.         }
    171.  
    172.         void swap(my_vector& v)
    173.         {
    174.             std::swap(_start, v._start);
    175.             std::swap(_finish, v._finish);
    176.             std::swap(_endOfStorage, v._endOfStorage);
    177.         }
    178.         iterator insert(iterator pos, const T& x)
    179.         {
    180.             assert(pos >= _start && pos <= _finish);
    181.             //这样就不用判断扩容，反正这个值也会被覆盖
    182.             push_back(0);
    183.  
    184.             size_t end = size()+1;
    185.             while (end != (pos-_start))
    186.             {
    187.                 _start[end] = _start[end-1];
    188.                 end--;
    189.             }
    190.             _start[end] = x;
    191.             return &_start[end];
    192.         }
    193.  
    194.         iterator erase(iterator pos)
    195.         {
    196.             assert(pos >= begin() && pos < end());
    197.  
    198.             iterator end = pos + 1;
    199.             while (end!=_finish)
    200.             {
    201.                 *(end - 1) = *end;
    202.                 end++;
    203.             }
    204.             _finish--;
    205.             return pos;
    206.         }
    207.  
    208. private:
    209.     //1 2 3 (空间大小为4)
    210.     iterator _start; // 指向数据块的开始
    211.     iterator _finish; // 指向有效数据的尾          end是\0 
    212.     iterator _endOfStorage; // 指向存储容量的尾    
    213. };
    214.  
    215. //
    216. //int main()
    217. //{
    218. //    my_vector v;
    219. //
    220. //    return 0;
    221. //}

    最后的最后，创作不易，希望读者三连支持💖

    赠人玫瑰，手有余香💖

  • 相关阅读:
    代码随想录算法训练营第十三天|239. 滑动窗口最大值、 347.前 K 个高频元素
    进程地址空间
    EN 14915实木镶板和包层—CE认证
    Flask 学习-21. 项目配置通过.env环境变量启动开发/生产环境
    Vue的路由使用，Node.js下载安装及环境配置教程 （超级详细）
    python库sqlalchemy使用教程
    与开发斗智斗勇的日子
    HTTP 响应的格式和响应代码
    软考 系统架构设计师系列知识点之特定领域软件体系结构DSSA（4）
    邦芒支招：求职自荐的五条技巧
  • 原文地址：https://blog.csdn.net/weixin_62700590/article/details/125831049