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

【C++】学习笔记——vector_3

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

七、vector

3. vector的模拟实现

上篇文章我们讲解了非常 玄幻 的拷贝构造函数，同样的方法，我们也能用这种方法来实现 赋值重载函数 。

void swap(vector<T>& v)
{
  std::swap(_start, v._start);
  std::swap(_finish, v._finish);
  std::swap(_endofstorage, v._endofstorage);
}
vector<T>& operator=(vector<T> v)
{
  // 通过传参时的拷贝构造，直接与其交换
  swap(v);
  return *this;
}

传值传参会调用拷贝构造，所以我们只需要将其与我们要赋值的给交换即可。

我们来测试一下：

// 测试区
void test06()
{
  vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4);
  v.push_back(5);
  vector<int> v1 = v;
  for (auto e : v1)
  {
    std::cout << e << " ";
  }
  std::cout << std::endl;
}
// test.cpp
#include<iostream>
#include"vector.h"
using namespace std;
int main()
{
  my::test06();
  return 0;
}

接下来实现一个比较奇怪的东西：迭代器区间构造 。一般容器都会支持这个函数。

// 类模板的成员函数可以是函数模板
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
  //
}

是的，类模板里面又加了一个函数模板，这样的作用是什么呢？这样的作用就是，这个函数模板可以不局限于类内的迭代器，只要符合模板参数，其他类的迭代器同样可以调用该函数 。这样可以使容器与容器之间发生交互。原理就是这样，实现起来也很简单：

// 类模板的成员函数可以是函数模板
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
  while (first != last)
  {
    push_back(*first);
    ++first;
  }
}

我们来测试一下：

// 测试区
void test07()
{
  vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4);
  v.push_back(5);
  // 这里也可以使用其他容器的迭代器
  vector<int> v1(v.begin() + 1, v.end() - 1);
  for (auto e : v1)
  {
    std::cout << e << " ";
  }
  std::cout << std::endl;
}
// test.cpp
#include<iostream>
#include"vector.h"
using namespace std;
int main()
{
  my::test07();
  return 0;
}

所以说这个迭代器区间构造也是非常好用的。

还有这个构造函数：构造 n 个给定值

// 和resize差不多
vector(size_t n, const T& val = T())
{
  reserve(n);
  for (size_t = 0; i < n; ++i)
  {
    push_back(val);
  }
}

我们来测试一下：

void test08()
{
  // 初始化 10 个 1
  vector<int> v(10, 1);
  for (auto e : v)
  {
    std::cout << e << " ";
  }
  std::cout << std::endl;
}

啊？哪出问题了？看看错误列表：

通过错误行数，我们找到了：

啊？咋调用到这来了，误把我的参数看成迭代器了？该怎么办呢？其实是这样的：我们实现的 构造n个给定值 的构造函数里，第一个参数是 size_t ，而在迭代器区间构造函数里，两个参数是相同的 ，这样会导致，我构造 10 个 1 所给的参数更加符合 迭代器区间构造函数 ，因为对另一个来说，有一个 size_t 参数不匹配，所以优先调用迭代器区间构造函数了。所以怎么办？简简单单：size_t 换成 int 就行 ，虽然对于个数来说， size_t 更加符合，毕竟没有负数，但是 int 也不影响。

vector(int n, const T& val = T())
{
  reserve(n);
  for (size_t i = 0; i < n; ++i)
  {
    push_back(val);
  }
}

OK，完美解决。

我来给出一个情景：

void test09()
{
  vector<std::string> v;
  v.push_back("11111");
  v.push_back("22222");
  v.push_back("33333");
  for (auto e : v)
  {
    std::cout << e << " ";
  }
  std::cout << std::endl;
}

这段程序的结果是什么？

没错，是不是非常简单？再来看看：

void test09()
{
  vector<std::string> v;
  v.push_back("11111");
  v.push_back("22222");
  v.push_back("33333");
  v.push_back("44444");
  v.push_back("55555");
  for (auto e : v)
  {
    std::cout << e << " ";
  }
  std::cout << std::endl;
}

这样呢？

蛤，报错了。打印倒是打印出来了，那么问题肯定不是出在打印上面，那就是析构。析构出了问题，我们首先想到的就是深浅拷贝，我们所有的函数都避免了浅拷贝，为什么最后还是会出现析构问题？

其实问题出在 reserve 函数里的 memcpy 。memcpy其实是浅拷贝，按照字节一个一个拷贝。就出现了如下图的情况。

这样导致我们在析构 _start 时，将内容也给析构了，所以后面生命周期结束时的析构就出现了多重析构的问题。既然知道了问题所在，那该如何解决问题呢？

void reserve(size_t n)
{
  // 比当前容量大才允许扩容
  if (n > capacity())
  {
    size_t old_size = size();
    // 开空间
    T* tmp = new T[n];
    // for循环赋值
    for (size_t i = 0; i < old_size; ++i)
    {
      tmp[i] = _start[i];
    }
    // 释放旧空间
    delete[] _start;
    // 更改地址
    _start = tmp;
    _finish = _start + old_size;
    _endofstorage = _start + n;
  }
}

换成 for循环赋值就可以了 。

最后再给大家阐述一下 迭代器失效的问题。我们在 insert 中第一次遇到了迭代器失效的问题，但是我们通过更新地址的问题解决了迭代器失效的问题。

void insert(iterator pos, const T& val)
{
  assert(pos >= _start);
  assert(pos <= _finish);
  // 记录相对位置
  size_t len = pos - _start;
  if (_finish == _endofstorage)
  {
    reserve(capacity() == 0 ? 4 : 2 * capacity());
  }
  // 如果发生异地扩容，需要更新 迭代器 ，否则将会发生迭代器失效
  pos = _start + len;
  iterator it = _finish - 1;
  while (it >= pos)
  {
    *(it + 1) = *it;
    --it;
  }
  *pos = val;
  ++_finish;
}

但是，大家有没有想过，这里的迭代器传入的是临时变量，临时变量更新了后，实参并不会修改，所以在外面这个迭代器的值已经 不可信 了。有人说可以将这个迭代器使用 引用传参 ，这样也不可以！

v.insert(v.begin(), 1);
• 1

这里传参都是传的临时变量，然而 临时变量具有常性，加了引用就用不了了，除非再加 const ，加了 const 就更不行了，不能修改的迭代器算什么迭代器？所以这里没有一种好的解决办法，想告诉大家的是：迭代器在修改容器的内容后就已经不再可信了 ，若需要再次使用迭代器，重新创建一个即可。

我们知道了 insert 可能产生 迭代器失效，那么 erase 会产生吗？有小伙伴可能会说，erase 根本就不会扩容，没有空间移动，那就不会出现迭代器失效。我再给大家看看一个场景：我们来删除容器里的偶数

void test10()
{
  vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4);
  v.push_back(5);
  auto it = v.begin();
  while (it != v.end())
  {
    if (*it % 2 == 0)
    {
      v.erase(it);
    }
    ++it;
  }
  for (auto e : v)
  {
    std::cout << e << " ";
  }
  std::cout << std::endl;
}

没出现问题，那这样呢：

void test10()
{
  vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  // 这里有两个 4
  v.push_back(4);
  v.push_back(4);
  v.push_back(5);
  auto it = v.begin();
  while (it != v.end())
  {
    if (*it % 2 == 0)
    {
      v.erase(it);
    }
    ++it;
  }
  for (auto e : v)
  {
    std::cout << e << " ";
  }
  std::cout << std::endl;
}

？这怎么出问题了？

void test10()
{
  vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4);
  v.push_back(5);
  // 这样呢？
  v.push_back(4);
  auto it = v.begin();
  while (it != v.end())
  {
    if (*it % 2 == 0)
    {
      v.erase(it);
    }
    ++it;
  }
  for (auto e : v)
  {
    std::cout << e << " ";
  }
  std::cout << std::endl;
}

啊？这样程序还能挂掉？

聪明的小伙伴们可以想到，erase 函数删除后会将后面的数据前往移动，删除后迭代器的位置是一个新的数据，然后 ++it 就会错过元素，就会出现答案不对的情况，如果错过了 end 迭代器表示的位置，将会导致循环终止不了，所以引发了一系列问题。那么，该如何解决呢？

auto it = v.begin();
while (it != v.end())
{
  if (*it % 2 == 0)
  {
    v.erase(it);
  }
  else
  {
    ++it;
  }
}

这样可以吗？说可以也可以，说不可也不可以。在一般情况下，erase 都不会产生 缩容 的情况，但是没有规定不可以缩容，假如真的有个容器 erase 后会发生缩容问题，那就会导致迭代器失效，就不能使用了。那么库里的 vector 是怎么解决这个问题的呢？我们来看看函数原型：

是的，库里 vector 的 erase 会返回一个迭代器，指向刚刚被删除的位置。所以库里的 erase 应该这样使用：

auto it = v.begin();
while (it != v.end())
{
  if (*it % 2 == 0)
  {
    // 更新迭代器
    it = v.erase(it);
  }
  else
  {
    ++it;
  }
}

那我们的 erase 就要做出相应的修改：

iterator erase(iterator pos)
{
  assert(pos >= _start);
  // 不要等于 _finish
  assert(pos < _finish);
  iterator it = pos + 1;
  while (it < _finish)
  {
    *(it - 1) = *it;
    ++it;
  }
  --_finish;
  return pos;
}

再来测试一下：

ok，实现完毕。到这里我们的 vector 已经非常优秀了。

4. vector实现代码整合

vector.h 头文件：

#pragma once
#include<assert.h>
namespace my
{
  template<class T>
  class vector
  {
  public:
    typedef T* iterator;
    typedef T* const_iterator;
    iterator begin()
    {
      return _start;
    }
    iterator end()
    {
      return _finish;
    }
    const_iterator begin() const
    {
      return _start;
    }
    const_iterator end() const
    {
      return _finish;
    }
    // 类模板的成员函数可以是函数模板
    template<class InputIterator>
    vector(InputIterator first, InputIterator last)
    {
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }
    vector()
    {}
    vector(const vector<T>& v)
    {
      reserve(v.capacity());
      for (auto& e : v)
      {
        push_back(e);
      }
    }
    vector(int n, const T& val = T())
    {
      reserve(n);
      for (size_t 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(_endofstorage, v._endofstorage);
    }
    vector<T>& operator=(vector<T> v)
    {
      // 通过传参时的拷贝构造，直接与其交换
      swap(v);
      return *this;
    }
    ~vector()
    {
      delete[] _start;
      _start = _finish = _endofstorage = nullptr;
    }
    size_t size() const
    {
      // 数据个数
      return _finish - _start;
    }
    size_t capacity() const
    {
      // 容量大小
      return _endofstorage - _start;
    }
    // 下标 + [] 访问
    T& operator[](size_t pos)
    {
      assert(pos < size());
      return _start[pos];
    }
    void reserve(size_t n)
    {
      // 比当前容量大才允许扩容
      if (n > capacity())
      {
        size_t old_size = size();
        // 开空间
        T* tmp = new T[n];
        // for循环赋值
        for (size_t i = 0; i < old_size; ++i)
        {
          tmp[i] = _start[i];
        }
        // 释放旧空间
        delete[] _start;
        // 更改地址
        _start = tmp;
        _finish = _start + old_size;
        _endofstorage = _start + n;
      }
    }
    void resize(size_t n, const T& val = T())
    {
      // 插入数据
      if (n > size())
      {
        reserve(n);
        while (_finish < _start + n)
        {
          *_finish = val;
          ++_finish;
        }
      }
      // 删除数据
      else
      {
        _finish = _start + n;
      }
    }
    void push_back(const T& val)
    {
       判断扩容
      //if (_finish == _endofstorage)
      //{
      //  reserve(capacity() == 0 ? 4 : 2 * capacity());
      //}
       插入数据
      //*_finish = val;
      //++_finish;
      insert(end(), val);
    }
    // 尾删
    void pop_back()
    {
      //assert(!empty());
      //
      //--_finish;
      erase(end() - 1);
      --_finish;
    }
    // 判断容器是否为空
    bool empty()
    {
      return _start == _finish;
    }
    void insert(iterator pos, const T& val)
    {
      assert(pos >= _start);
      assert(pos <= _finish);
      // 记录相对位置
      size_t len = pos - _start;
      if (_finish == _endofstorage)
      {
        reserve(capacity() == 0 ? 4 : 2 * capacity());
      }
      // 如果发生异地扩容，需要更新 迭代器 ，否则将会发生迭代器失效
      pos = _start + len;
      iterator it = _finish - 1;
      while (it >= pos)
      {
        *(it + 1) = *it;
        --it;
      }
      *pos = val;
      ++_finish;
    }
    iterator erase(iterator pos)
    {
      assert(pos >= _start);
      // 不要等于 _finish
      assert(pos < _finish);
      iterator it = pos + 1;
      while (it < _finish)
      {
        *(it - 1) = *it;
        ++it;
      }
      --_finish;
      return pos;
    }
  private:
    // 数据起始地址
    iterator _start = nullptr;
    // 数据末尾的下一个地址
    iterator _finish = nullptr;
    // 容量末尾的下一个地址
    iterator _endofstorage = nullptr;
  };
  
  // 测试区
  void test01()
  {
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    for (int i = 0; i < v.size(); ++i)
    {
      std::cout << v[i] << " ";
    }
    std::cout << std::endl;
  }
  void test02()
  {
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    vector<int>::iterator it = v.begin();
    while (it != v.end())
    {
      std::cout << *it << " ";
      ++it;
    }
    std::cout << std::endl;
    for (auto e : v)
    {
      std::cout << e << " ";
    }
    std::cout << std::endl;
  }
  void test03()
  {
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    // 头部插入一个0
    v.insert(v.begin(), 0);
    // 尾删
    v.pop_back();
    for (auto e : v)
    {
      std::cout << e << " ";
    }
    std::cout << std::endl;
  }
  void test04()
  {
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.resize(10);
    for (auto e : v)
    {
      std::cout << e << " ";
    }
    std::cout << std::endl;
    v.resize(30, 7);
    for (auto e : v)
    {
      std::cout << e << " ";
    }
    std::cout << std::endl;
    v.resize(3);
    for (auto e : v)
    {
      std::cout << e << " ";
    }
    std::cout << std::endl;
  }
  void test05()
  {
    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)
    {
      std::cout << e << " ";
    }
    std::cout << std::endl;
    vector<int> v1(v);
    for (auto e : v1)
    {
      std::cout << e << " ";
    }
    std::cout << std::endl;
  }
  void test06()
  {
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    vector<int> v1 = v;
    for (auto e : v1)
    {
      std::cout << e << " ";
    }
    std::cout << std::endl;
  }
  void test07()
  {
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    // 这里也可以使用其他容器的迭代器
    vector<int> v1(v.begin() + 1, v.end() - 1);
    for (auto e : v1)
    {
      std::cout << e << " ";
    }
    std::cout << std::endl;
  }
  void test08()
  {
    // 初始化 10 个 1
    vector<int> v(10, 1);
    for (auto e : v)
    {
      std::cout << e << " ";
    }
    std::cout << std::endl;
  }
  void test09()
  {
    vector<std::string> v;
    v.push_back("11111");
    v.push_back("22222");
    v.push_back("33333");
    v.push_back("44444");
    v.push_back("55555");
    for (auto e : v)
    {
      std::cout << e << " ";
    }
    std::cout << std::endl;
  }
  void test10()
  {
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(4);
    auto it = v.begin();
    while (it != v.end())
    {
      if (*it % 2 == 0)
      {
        it = v.erase(it);
      }
      else
      {
        ++it;
      }
    }
    for (auto e : v)
    {
      std::cout << e << " ";
    }
    std::cout << std::endl;
  }
}

tset.cpp 源文件

#include<iostream>
#include"vector.h"
using namespace std;
int main()
{
  my::test10();
  return 0;
}

未完待续

文章标签：
C++
容器
关键词：
C++学习笔记
lge101058
目录
相关文章
HermanYe996
|
4月前
|
C++
c++学习笔记07 结构体
C++结构体的详细学习笔记07，涵盖了结构体的定义、使用、数组、指针、嵌套、与函数的交互以及在结构体中使用const的示例和解释。
HermanYe996
43 0
1387503158665997
|
3月前
|
安全 C语言 C++
C++学习笔记
C++学习笔记
1387503158665997
42 2
HermanYe996
|
4月前
|
C++
c++学习笔记02 运算符
C++学习笔记，介绍了C++中的运算符，包括基本的加减乘除、求模、前后置递增递减、赋值运算符、比较运算符和逻辑运算符的使用及其注意事项。
HermanYe996
47 6
HermanYe996
|
4月前
|
C++
c++学习笔记01 基本知识与数据类型
C++学习笔记，涵盖了C++中的常量定义、数据类型、变量内存大小计算、基本数据类型（整型、实型、字符型、字符串型、布尔型）以及转义字符的使用。
HermanYe996
48 4
HermanYe996
|
4月前
|
算法 C++
c++学习笔记04 数组
这篇文章是C++学习笔记4，主题是数组。
HermanYe996
50 4
qq2108462953
|
4月前
|
C++
【学习笔记】【C/C++】 c++字面值常量
【学习笔记】【C/C++】 c++字面值常量
qq2108462953
46 1
HermanYe996
|
4月前
|
存储 C++
c++学习笔记05 函数
C++函数使用的详细学习笔记05，包括函数的基本格式、值传递、函数声明、以及如何在不同文件中组织函数代码的示例和技巧。
HermanYe996
40 0
c++学习笔记05 函数
qq2108462953
|
4月前
|
编译器 C++
【C/C++学习笔记】C++声明与定义以及头文件与源文件的用途
【C/C++学习笔记】C++声明与定义以及头文件与源文件的用途
qq2108462953
63 0
qq2108462953
|
4月前
|
存储 C++
【C/C++学习笔记】string 类型的输入操作符和 getline 函数分别如何处理空白字符
【C/C++学习笔记】string 类型的输入操作符和 getline 函数分别如何处理空白字符
qq2108462953
55 0
HermanYe996
|
4月前
|
C++
c++学习笔记09 引用
C++引用的详细学习笔记，解释了引用的概念、语法、使用注意事项以及引用与变量的关系。
HermanYe996
45 0