AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

STL中vector的用法以及模拟实现

2023-11-24 57
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： STL中vector的用法以及模拟实现

一、vector的介绍及使用

1、vector的介绍

vector文档

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

2、vector的使用

2.1 vector的定义

构造函数 说明
vector() 无参构造
vector（size_type n, const value_type& val = value_type()） 构造并初始化n个val
vector (const vector& x) 拷贝构造
vector (InputIterator first, InputIterator last) 利用迭代器区间构造


用法：

// constructing vectors
#include <iostream>
#include <vector>
int main ()
{
  // constructors used in the same order as described above:
  std::vector<int> first; // empty vector of ints
  std::vector<int> second (4,100); // four ints with value 100
  std::vector<int> third (second.begin(),second.end()); // iterating through second
  std::vector<int> fourth (third); // a copy of third
  // 下面涉及迭代器初始化的部分，我们学习完迭代器再来看这部分
  // the iterator constructor can also be used to construct from arrays:
  int myints[] = {16,2,77,29};
  std::vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );
  std::cout << "The contents of fifth are:";
  for (std::vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';
  return 0; 
}

2.2 vector iterator 的使用


1700807702308.png

  • begin和end图示：

  • rbegin和rend图示：

  • 用法举例：
#include <iostream>
#include <vector>
using namespace std;
void PrintVector(const vector<int>& v)
{
  // const对象使用const迭代器进行遍历打印
  vector<int>::const_iterator it = v.begin();
  while (it != v.end())
  {
    cout << *it << " ";
    ++it;
  }
  cout << endl;
}
int main()
{
  // 使用push_back插入4个数据
  vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4);
  // 使用迭代器进行遍历打印
  vector<int>::iterator it = v.begin();
  while (it != v.end())
  {
    cout << *it << " ";
    ++it;
    cout << endl;
    // 使用迭代器进行修改
    it = v.begin();
    while (it != v.end())
    {
      *it *= 2;
      ++it;
    }
    // 使用反向迭代器进行遍历再打印
    vector<int>::reverse_iterator rit = v.rbegin();
    while (rit != v.rend())
    {
      cout << *rit << " ";
      ++rit;
    }
    cout << endl;
    PrintVector(v);
    return 0;
  }
}


2.3 vector 空间增长问题

函数 说明
size 获取数据个数
capacity 获取容器容量
empty 判断容器是否为空

resize 改变vector的size
reserve 预留空间


值得一提的是：


  • capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，顺序表增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
  • reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
  • resize在开空间的同时还会进行初始化，影响size。

2.4 vector 增删查改

1700807796608.png

用法举例：

  • push_back/pop_back
#include <iostream>
#include <vector>
using namespace std;
int main()
{
  int a[] = { 1, 2, 3, 4 };
  vector<int> v(a, a+sizeof(a)/sizeof(int));
  vector<int>::iterator it = v.begin();
  while (it != v.end()) 
  {
    cout << *it << " ";
    ++it;
  }
  cout << endl;
  v.pop_back();
  v.pop_back();
  it = v.begin();
  while (it != v.end()) 
  {
    cout << *it << " ";
    ++it;
  }
  cout << endl;
  return 0;
}


  • find / insert / erase
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
  int a[] = { 1, 2, 3, 4 };
  vector<int> v(a, a + sizeof(a) / sizeof(int));
  // 使用find查找3所在位置的iterator
  vector<int>::iterator pos = find(v.begin(), v.end(), 3);
  // 在pos位置之前插入30
  v.insert(pos, 30);
  vector<int>::iterator it = v.begin();
  while (it != v.end()) 
  {
    cout << *it << " ";
    ++it;
  }
  cout << endl;
  pos = find(v.begin(), v.end(), 3);
  // 删除pos位置的数据
  v.erase(pos);
  it = v.begin();
  while (it != v.end()) 
  {
    cout << *it << " ";
    ++it;
  }
  cout << endl;
  return 0;
}


  • operator[]+index 和 C++11中vector的新式for+auto的遍历
#include <iostream>
#include <vector>
using namespace std;
int main()
{
  int a[] = { 1, 2, 3, 4 };
  vector<int> v(a, a + sizeof(a) / sizeof(int));
  // 通过[]读写第0个位置。
  v[0] = 10;
  cout << v[0] << endl;
  // 通过[i]的方式遍历vector
  for (size_t i = 0; i < v.size(); ++i)
    cout << v[i] << " ";
  cout << endl;
  vector<int> swapv;
  swapv.swap(v);
  cout << "v data:";
  for (size_t i = 0; i < v.size(); ++i)
    cout << v[i] << " ";
  cout << endl;
  cout << "swapv data:";
  for (size_t i = 0; i < swapv.size(); ++i)
    cout << swapv[i] << " ";
  cout << endl;
  // C++11支持的新式范围for遍历
  for(auto x : v)
    cout<< x << " ";
  cout<<endl;
  return 0;
}


二、vector 迭代器失效

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


对于vector可能会导致其迭代器失效的操作有：


1.会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、ush_back等

例如：

#include <iostream>
using namespace std;
#include <vector>
int main()
{
  vector<int> v{1,2,3,4,5,6};
  auto it = v.begin();
  // 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容
  // v.resize(100, 8);
  // reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变
  // v.reserve(100);
  // 插入元素期间，可能会引起扩容，而导致原空间被释放
  // v.insert(v.begin(), 0);
  // v.push_back(8);
  // 给vector重新赋值，可能会引起底层容量改变
  v.assign(100, 8);
  /*
  出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，
  而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的
  空间，而引起代码运行时崩溃。
  解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新
  赋值即可。
  */
  while(it != v.end())
  {
    cout<< *it << " " ;
    ++it;
  }
  cout<<endl;
  return 0;
}
  1. 指定位置元素的删除操作 ：erase
    例如：
#include <iostream>
using namespace std;
#include <vector>
int main()
{
  int a[] = { 1, 2, 3, 4 };
  vector<int> v(a, a + sizeof(a) / sizeof(int));
  // 使用find查找3所在位置的iterator
  vector<int>::iterator pos = find(v.begin(), v.end(), 3);
  // 删除pos位置的数据，导致pos迭代器失效。
  v.erase(pos);
  cout << *pos << endl; // 此处会导致非法访问
  return 0;
}

erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。


迭代器失效解决办法：在使用前，对迭代器重新赋值即可。

三、vector深度剖析及模拟实现

1、实现代码

#pragma once
#include<iostream>
#include<assert.h>
using std::cout;
using std::endl;
namespace my_vector
{
  template<class T>
  class vector
  {
  public:
    typedef T* iterator;
    typedef const T* const_iterator;
    vector()
      :_start(nullptr)
      , _finish(nullptr)
      , _endofstoage(nullptr)
    {}
    template <class InputIterator>
    vector(InputIterator first, InputIterator last)
      : _start(nullptr)
      , _finish(nullptr)
      , _endofstoage(nullptr)
    {
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }
    vector(size_t n, const T& val = T())
      : _start(nullptr)
      , _finish(nullptr)
      , _endofstoage(nullptr)
    {
      reserve(n);
      for (size_t i = 0; i < n; ++i)
      {
        push_back(val);
      }
    }
    vector(int n, const T& val = T())
      : _start(nullptr)
      , _finish(nullptr)
      , _endofstoage(nullptr)
    {
      reserve(n);
      for (int i = 0; i < n; ++i)
      {
        push_back(val);
      }
    }
    void swap(vector<T>& v)
    {
      std::swap(_start, v._start);
      std::swap(_finish, v._finish);
      std::swap(_endofstoage, v._endofstoage);
    }
    // 休息11：37继续
    //vector(const vector& v);
    vector(const vector<T>& v)
      : _start(nullptr)
      , _finish(nullptr)
      , _endofstoage(nullptr)
    {
      vector<T> tmp(v.begin(), v.end());
      swap(tmp);
    }
    //vector& operator=(vector v)
    vector<T>& operator=(vector<T> v)
    {
      swap(v);
      return *this;
    }
    // 资源管理
    ~vector()
    {
      if (_start)
      {
        delete[] _start;
        _start = _finish = _endofstoage = nullptr;
      }
    }
    iterator begin()
    {
      return _start;
    }
    iterator end()
    {
      return _finish;
    }
    const_iterator begin() const
    {
      return _start;
    }
    const_iterator end() const
    {
      return _finish;
    }
    size_t size() const
    {
      return _finish - _start;
    }
    size_t capacity() const
    {
      return _endofstoage - _start;
    }
    void reserve(size_t n)
    {
      size_t sz = size();
      if (n > capacity())
      {
        T* tmp = new T[n];
        if (_start)
        {
          memcpy(tmp, _start, size()*sizeof(T));
          delete[] _start;
        }
        _start = tmp;
      }
      _finish = _start + sz;
      _endofstoage = _start + n;
    }
    //void resize(size_t n, const T& val = T())
    void resize(size_t n, T val = T())
    {
      if (n > capacity())
      {
        reserve(n);
      }
      if (n > size())
      {
        while (_finish < _start + n)
        {
          *_finish = val;
          ++_finish;
        }
      }
      else
      {
        _finish = _start + n;
      }
    }
    void push_back(const T& x)
    {
      /*if (_finish == _endofstoage)
      {
        size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newCapacity);
      }
      *_finish = x;
      ++_finish;*/
      insert(end(), x);
    }
    void pop_back()
    {
      /*if (_finish > _start)
      {
        --_finish;
      }*/
      erase(end() - 1);
    }
    T& operator[](size_t pos)
    {
      assert(pos < size());
      return _start[pos];
    }
    const T& operator[](size_t pos) const
    {
      assert(pos < size());
      return _start[pos];
    }
    iterator insert(iterator pos, const T& x)
    {
      // 检查参数
      assert(pos >= _start && pos <= _finish);
      // 扩容
      // 扩容以后pos就失效了,需要更新一下
      if (_finish == _endofstoage)
      {
        size_t n = pos - _start;
        size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newCapacity);
        pos = _start + n;
      }
      // 挪动数据
      iterator end = _finish - 1;
      while (end >= pos)
      {
        *(end + 1) = *end;
        --end;
      }
      *pos = x;
      ++_finish;
      return pos;
    }
    iterator erase(iterator pos)
    {
      assert(pos >= _start && pos < _finish);
      iterator it = pos + 1;
      while (it != _finish)
      {
        *(it - 1) = *it;
        ++it;
      }
      --_finish;
      return pos;
    }
    void clear()
    {
      _finish = _start;
    }
  private:
    iterator _start;
    iterator _finish;
    iterator _endofstoage;
  };
}

2、使用memcpy拷贝问题

假设模拟实现的vector中的reserve接口中，使用memcpy进行的拷贝，以下代码会发生什么问题？

int main()
{
  my_vector::vector<my_vector::string> v;
  v.push_back("1111");
  v.push_back("2222");
  v.push_back("3333");
  return 0;
}

问题分析：

  1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
  2. 如果拷贝的是自定义类型的元素，memcpy即高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。


  1. 结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

3、使用模拟实现的vector实现杨辉三角中的深层次拷贝问题

3.1 vector的深层次拷贝问题

构造一个杨辉三角，打印一下并返回构造完成后的杨辉三角：

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);
      // 第一个和最后一个初始化成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)
        {
          // 中间位置等于上一行j-1 和 j个相加
          vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];
        }
      }
    }
    for (size_t i = 0; i < vv.size(); ++i)
    {
      for (size_t j = 0; j < vv[i].size(); ++j)
      {
        cout << vv[i][j] << " ";
      }
      cout << endl;
    }
    cout << endl;
    return vv;
  }
};

接收构造完成后的杨辉三角并打印：

void test()
{
  vector<vector<int>> ret = Solution().generate(5);
  for (size_t i = 0; i < ret.size(); ++i)
  {
    for (size_t j = 0; j < ret[i].size(); ++j)
    {
      cout << ret[i][j] << " ";
    }
    cout << endl;
  }
  cout << endl;
}


结果：程序崩溃

调试可知：利用memcpy扩容，造成扩容前和扩容后杨辉三角的前四排的元素指向同一地址，发生的浅拷贝，当delete_start的时候导致tmp也被释放了。想要解决这个问题就必须使用深拷贝的方法去替代memcpy即可。

3.2 解决方法——更新reserve函数

使用深拷贝的方法去替代memcpy：

    void reserve(size_t n)
    {
      size_t sz = size();
      if (n > capacity())
      {
        T* tmp = new T[n];
        if (_start)
        {
          //memcpy(tmp, _start, size()*sizeof(T));
          for (size_t i = 0; i < size(); ++i)
          {
            tmp[i] = _start[i];
          }
          delete[] _start;
        }
        _start = tmp;
      }
      _finish = _start + sz;
      _endofstoage = _start + n;
    }

此时，问题便得到了完美的解决。


文章标签：
C++
容器
存储
算法
求知.
目录
相关文章
戊子仲秋
|
程序员 编译器 C++
【STL】 模拟实现简易 vector
【STL】 模拟实现简易 vector
戊子仲秋
36 0
ephemerals__
|
16天前
|
存储 编译器 C语言
【c++丨STL】vector模拟实现
本文深入探讨了 `vector` 的底层实现原理，并尝试模拟实现其结构及常用接口。首先介绍了 `vector` 的底层是动态顺序表，使用三个迭代器（指针）来维护数组，分别为 `start`、`finish` 和 `end_of_storage`。接着详细讲解了如何实现 `vector` 的各种构造函数、析构函数、容量接口、迭代器接口、插入和删除操作等。最后提供了完整的模拟实现代码，帮助读者更好地理解和掌握 `vector` 的实现细节。
ephemerals__
27 0
stackY
|
7月前
|
存储 算法 Linux
【STL】：vector用法详解
【STL】：vector用法详解
stackY
91 1
stackY
|
7月前
|
C++
【STL】：vector的模拟实现
【STL】：vector的模拟实现
stackY
58 0
烽起黎明
|
安全 C++ 容器
【C++】STL之vector类模拟-1
【C++】STL之vector类模拟
烽起黎明
39 0
烽起黎明
|
Linux 编译器 测试技术
【C++】STL之vector类模拟-3
【C++】STL之vector类模拟
烽起黎明
54 0
烽起黎明
|
C++ 容器
【C++】STL之vector类模拟-2
【C++】STL之vector类模拟
烽起黎明
46 0
Hayaizo
|
C++
【C++ STL】vector模拟实现
【C++ STL】vector模拟实现
Hayaizo
55 0
【C++ STL】vector模拟实现
诚酱
|
存储 C++ 容器
C++【STL】之vector模拟实现
C++ STL vector类模拟实现，常用接口详细讲解，干货满满！
诚酱
72 0
C++【STL】之vector模拟实现
枫叶先生_
|
存储 机器学习/深度学习 算法
【C++初阶】七、STL---vector模拟实现
目录 一、模拟实现接口总览 1.1 接口总览 1.2 vector整体框架 1.3 vector成员变量介绍 二、vector模拟实现 2.1 构造函数 2.1.1 无参构造 2.1.2 迭代器区间构造 2.1.3 n个val构造 2.1.4 拷贝构造 2.2 赋值运算符重载 2.2.1 传统写法 2.2.2 现代写法 2.3 析构函数 2.4 Iterator 2.4.1 begin 2.4.2 end 2.5 Capacity 2.5.1 size 2.5.2 capacity 2.5.3 empty 2.5.4 resize 2.5.5 re
枫叶先生_
82 0
【C++初阶】七、STL---vector模拟实现

热门文章

最新文章

  • 1
    跟阿里云技术专家阙寒一起深度了解视频直播CDN技术
  • 2
    流批一体的近实时数仓的思考与设计
  • 3
    丰富、连接、待集成—MaxCompute 生态再出发
  • 4
    securecrt克隆会话与sshd 的 MaxSessions
  • 5
    Flink 消息聚合处理方案
  • 6
    VMware安装的相关文章
  • 7
    forever让nodejs应用后台执行
  • 8
    路边的烧烤摊杂感
  • 9
    size_type、size_t、differentce_type以及ptrdiff_t
  • 10
    一些链接
  • 1
    《人工智能知识图谱构建与应用的最新突破与成果》
    32
  • 2
    《零样本学习：突破瓶颈，开启智能新征程》
    25
  • 3
    《知识表示：开启人工智能学习与推理的密钥》
    26
  • 4
    《信息传播：人工智能助力驱散虚假信息阴霾》
    24
  • 5
    《多模态融合：开启智能新时代的钥匙》
    34
  • 6
    自学记录鸿蒙 API 13：实现人脸检测 Core Vision Face Detector
    25
  • 7
    阿里云先知安全沙龙(武汉站) ——AI赋能软件漏洞检测，机遇, 挑战与展望
    440
  • 8
    在线使用：Poe Ai网页版_pc版_poe ai中文官网入口
    19
  • 9
    java项目中jar启动执行日志报错：no main manifest attribute, in /www/wwwroot/snow-server/z-server.jar-jar打包的大小明显小于正常大小如何解决
    21
  • 10
    新手指南：人工智能poe ai 怎么用？国内使用poe记住这个方法就够了！
    33

    • 相关课程

    更多
  • Go语言核心编程 - 基础语法、数组、切片、Map

    • 相关电子书

    更多
  • std::tuple与模板元编程
  • 低代码开发师（初级）实战教程
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    手把手教你白嫖阿里云服务器(免费领服务器)