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

vector（二）

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

vector深度剖析及模拟实现


模拟实现


0f1f01a289c948f62991fca42772cc71_d52cc360a92b45adbeaa898695ce0f9e.jpeg


参考源码，模拟实现

对比string类,推出下面变量功能


a = _start;
a+size = _finish;
a+capacity = _end_of_storage;


namespace myj
{  
    //模板
  template<class T>
  class vector
  {
  public:
     //指针实现迭代器
  typedef T* iterator;
  iterator begin()
  {
    return _start;
  }
  iterator end()
  {
    return _finish;
  }
  size_t size()
  {
    return _finish - _start;
  }
  size_t capacity()
  {
    return _end_of_storage - _start;
  }
  T& operator[](size_t pos)
  {
    assert(pos < _finish);
    return _start[pos];
  }
  vector()
    :_start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
  {
  }
  ~vector()
  {
    delete[] _start;
    _start = _finish = _end_of_storage = nullptr;
  }
  vector<T>& operator=(vector<T>v)
  {
    swap(v);
    return *this;
  }
  //标准写法
  vector(size_t n, const T& val = T())
    :_start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
  {
    reserve(n);
    for (size_t i = 0; i < n; i++)
    {
    push_back(val);
    }
  }
  //现代写法
  template<class InputIterator>
  vector(InputIterator frist, InputIterator last)
    :_start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
  {
    while (frist != last)
    {
    push_back(*frist);
    ++frist;
    }
  }
  void swap(const vector<T>& v)
  {
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_end_of_storage, v._end_of_storage);
  }
  vector(const vector<T>& v)
    :_start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
  {
    vector<T>tmp(v.begin(), v.end());
    swap(tmp);
  }   
  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;
    }
  }
  bool empty()
  {
    return _finish == _start;
  }
  void push_back(const T& val)
  {
    if (_finish == _end_of_storage)
    {
    size_t newcapacity = capacity() == 0:4 ? capacity() * 2;
    reserve(newcapacity);
    }
    *_finish = val;
    ++_finish;
  }
  void pop_back()
  {
    assert(!empty());
    --_finish;
  }
  private:
  iterator _start;
  iterator _finish;
  iterator _end_of_storage;
  };
}


迭代器失效


空间变化导致迭代器失效


iterator insert(iterator pos, const T& val)
  {
    assert(pos >= _start);
    assert(pos < _finish);
    if (_finish == _end_of_storage)
    {
    size_t newcapacity = capacity() == 0？4 ： capacity() * 2;
    reserve(newcapacity);
    }
    iterator end = _finish - 1;
    while (end > pos)
    {
    *(end + 1) = *end;
    end--;
    }
    *pos = val;
    ++_finish;
    return pos;
  }
    void test()
  {
  vector<int>v;
  v.reserve(10);
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4);
  v.push_back(5);
  v.insert(v.begin() + 3, 30);
  }


07e1f5d2c53a43c156dd98202561405a_f84cdd07cd6e42aabecf599c8f620547.png


很奇怪！！！报错的原因竟然是pos<_finish，为什么呢，明明只是插入第六个数字，预留的空间并没有使用完，但这里还是报错。


其实报错的原因是在插入第六个数字时，vector进行了扩容


重新开辟新的空间，之前的空间被释放。但是pos仍是指向之前的空间，从而造成了野指针问题

只需要在扩容前计算pos的相对位置，在新的空间中重新计算pos位置即可


d85fd1f4abe4b3a83aab1e9a55dbac05_a7100326795b4458baf4bd68405e45e2.png


改善如下


iterator insert(iterator pos, const T& val)
  {
    assert(pos >= _start);
    assert(pos < _finish);
    if (_finish == _end_of_storage)
    {
    size_t len = pos - _start;
    size_t newcapacity = capacity() == 0?4 : capacity() * 2;
    reserve(newcapacity);
    //扩容导致迭代器失效，重新调整
    pos = _start + len;
    }
    iterator end = _finish - 1;
    while (end > pos)
    {
    *(end + 1) = *end;
    end--;
    }
    *pos = val;
    ++_finish;
    return pos;
  }


2.迭代器指向的空间无意义导致失效


删除数组中的偶数并打印


void erase(size_t pos)
  {
    assert(pos >= _start);
    assert(pos < _finish);
    iterator begin = pos + 1;
    while (begin < _finish)
    {
    *(begin - 1) = *begin;
    begin++;
    }
    --_finish;
  }
void test()
  {
  std::vector<int>v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4);
  v.push_back(5);
  for (auto e : v)
  {
    cout << e << " ";
  }
  cout << endl;
  std::vector<int>::iterator it = v.begin();
  while (it != v.end())
  {
    if (*it % 2 == 0)
    {
    v.erase(it);
    }
    else
    {
    ++it;
    }
  }
  for (auto e : v)
  {
    cout << e << " ";
  }
  cout << endl;
  }


当数组中存在五个数时，删除偶数可以正常打印输出


2dc49f600740a0ffe0f9d53a7872fc06_29557460c9484b3b87bb897f390a49b4.png


当数组中存在四个数时，程序是否也可以运行呢？


结果如下


3c646665d1b345e17e1af052fa27f625_6b8802513a0e45379430d14a3d06e4cc.png


为什么五个数字程序正常运行，四个数字程序便崩溃了呢？下面为大家来解答一下


当 it与 _finish相等时程序刚好结束，不会崩溃


ad8b24ffc8e9c3a362a83571a7221d3f_c91fbd4071c14532bb275623d97c3b7f.png


当删除数字4之后， it永远不会与 _finish相等，程序也就崩溃


bcf9c5c2e706e8779095ad4b267172b5_a020176dcefe4a9f87ef7ba1ddf83270.png


为了避免迭代器失效，需要进行改进。

在删除数据之后，由迭代器返回删除位置的信息，便可避免迭代器失效的问题

改进如下


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


使用memcpy拷贝问题


void reserve(size_t n)
  {
    if (n > capacity())
    {
    size_t oldsize = size();
    T* tmp = new T[n];
    if (_start)
    {
      memcpy(tmp,_start,sizeof()*oldsize);
      delete[] _start;
    }
    _start = tmp;
    _finish = tmp + oldsize;
    _end_of_storage = tmp + n;
    }
  }
void test()
  {
  vector<vector<int>>vv;
  vector<int>v(5, 0);
  vv.push_back(v);
  vv.push_back(v);
  vv.push_back(v);
  vv.push_back(v);
  vv.push_back(v);
  for (size_t i = 0; i < vv.size(); i++)
  {
    for (size_t j = 0; j < vv.size(); j++)
    {
    cout << vv[i][j] << " ";
    }
    cout << endl;
  }
  cout << endl;
  }


创建二维数组，当插入第五个数据时，打印的结果与期待的不同，为什么呢？？？


其实也是由于扩容所导致的

当插入第五个数据时，也就是第五个一维数组时，编译器进行扩容：先将之前的数据整体拷贝给先开辟的空间，然后释放之前的空间；从而就导致了现有的空间所指向的内容已经被编译器给释放，打印的结果便与所期待的不同


修改也很简单：不能只是简单的拷贝，需要重新开辟空间进行赋值即可


f3216d755577b2b04cb22c92a049fa28_6c73ccd04f164c0fa39937c1a3063a0e.png


b1c7dbec2d177d48a005c646532fdf5f_e1923ababaac4909af0e7ae050966053.png


修改


void reserve(size_t n)
  {
    if (n > capacity())
    {
    size_t oldsize = size();
    T* tmp = new T[n];
    if (_start)
    {
      for (size_t i = 0; i < oldsize; ++i)
      {
      tmp[i] = _start[i];
      }
      delete[] _start;
    }
    _start = tmp;
    _finish = tmp + oldsize;
    _endofstorage = _start + n;
    }
  }

打印结果

5b7bf33f85567956febca6b5693fee47_07adc3d69df44e179ecc98e6d9da62f3.png

文章标签：
编译器
-初生-
目录
相关文章
小陈在拼命
|
6月前
|
存储 算法 测试技术
C++：Vector的使用
C++：Vector的使用
小陈在拼命
48 1
只是雪豹
|
6月前
|
存储 编译器 C语言
vector讲解
vector讲解
只是雪豹
73 0
嘎嘎旺
|
6月前
|
编译器 C++
【c++】vector
【c++】vector
嘎嘎旺
44 0
禁默
|
23天前
|
算法 C++ 容器
C++之打造my vector篇（下）
C++之打造my vector篇（下）
禁默
25 0
Z_sorrain
|
3月前
|
安全 Java
Vector的使用
Vector的使用
Z_sorrain
18 2
大柏怎么被偷了
|
3月前
|
存储 算法 C语言
【C++】vector的认识与使用
【C++】vector的认识与使用
大柏怎么被偷了
53 1
ForcibleBugMaker
|
4月前
|
编译器 C++
【C++】vector的使用下
**C++ 中的 `std::vector` 概要：** - **元素获取：** 支持 `operator[]`（越界时不检
ForcibleBugMaker
28 0
算精通
|
5月前
|
存储 索引 容器
vector
【6月更文挑战第17天】
算精通
52 0
Lei宝啊
|
6月前
|
算法 编译器 C++
(C++)vector介绍及其使用
(C++)vector介绍及其使用
Lei宝啊
59 0
DyeDD
|
11月前
|
编译器 C++
c++ vector的使用
vector 的初始化
DyeDD
59 0