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

【C++】STL——vector模拟实现（2）

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

四、容量相关的函数

1.size和capacity

size_t size() const
{
  return _finish - _start;//返回的是容器中有效数据的个数
}
size_t capacity() const
{
  return _end_of_storage - _start;//返回的是容器的实际有效容量
}

2.reserve

reserve增容：

       1.当 n > capacity 时，将capacity扩大到n；

       2.当 n < capacity 时，不进行任何操作；

void reserve(size_t n)
{
  if (n > capacity())//判断是否需要扩容
  {
    //扩容
    size_t sz = size(); //提前算好增容前的数据个数
    T* tmp = new T[n];  //开辟n个空间
    if (_start)
    {
            //数据拷贝，也不能去使用memcpy函数
      for (size_t i = 0; i < sz; i++)
      {
        tmp[i] = _start[i];
      }
      delete[]_start; //释放旧空间
    }
    _start = tmp; //指向新空间
    _finish = _start + sz;
    _end_of_storage = _start + n;
  }
}

对于reserve，我还需要注意两个问题：

1.对增容前的数据个数进行记录

1ecd1b2606ed46e9956a89f231c9802c.png

如果不提前算好增容前的数据个数，而是在增容完后更新_start，对于_finish和_end_of_storage都会出现问题，因为增容完后，就需要释放旧空间。

2.增容前后的数据拷贝不能使用memcpy

1ecd1b2606ed46e9956a89f231c9802c.png

如果使用memcpy进行数据的拷贝后，随着_start的释放，tmp作为新的_start后，当进行访问操作时，就存在非法访问

3.resize

当n<size时，是缩容，相应的数据会减少，只需要调整一下_finish的位置


当n>size时，我们还需要判断n是否大于capacity，是否增容


在resize函数中的第二个参数val，采用的是缺省（匿名对象），因为我们并不知道T是什么类型，如果是int/int*给val = 0是可以的，但是T还有可能是vector，我们给到匿名对象作为缺省值的好处在于，对于内置类型它也有自己的默认构造函数

例如:
int i = int();  // i = 0
int j = int(10);// j = 10

当我们不给val传任何参数时，它会去调用自己的默认构造函数给val

void resize(size_t n, const T& val = T())
//T()是匿名对象，它的生命周期本来只是存在于当前行，但是被const修饰以后，可以延长它的生命周期
{
  if (n < size())
  {
    _finish = _start + n;
  }
  else
  {
    if (n > capacity())
    {
      reserve(n);
    }
    while (_finish != _start + n)
    {
      *_finish = val;
      ++_finish;
    }
  }
}

五、增删查改相关的函数

1.push_back

尾插数据时，首先需要判断容器是否已满，若满则去调用reserve 

void push_back(const T& x)
{
  if (_finish == _end_of_storage)
  {
    reserve(capacity() == 0 ? 4 : capacity() * 2);
  }
  *_finish = x;
  ++_finish;
}

2.pop_back

       在进行尾删时，需要判断容器是否为空，我们这里并没有实现vector的判空操作，可以利用_finish和_start之间的关系进行判断。

void pop_back(const T& x)
{
  assert(_finish > _start);
  --_finish;
}

3.insert

insert是在某个位置插入数据，插入数据就存在是否扩容，如果不需要扩容，插入数据时不会存在然后的问题；如果需要扩容，但未调整pos，会存在pos失效；

iterator insert(iterator pos, const T& x)
{
  assert(pos >= _start);
  assert(pos <= _finish);
  if (_finish == _end_of_storage)
  {
    //扩容会导致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;
  return pos;
}
void test_vector4()
{
  vector<int> v1;
  v1.push_back(1);
  v1.push_back(2);
  v1.push_back(3);
  v1.push_back(4);
  vector<int>::iterator it = find(v1.begin(), v1.end(), 2);
  if (it != v1.end())
  {
    //如果insert中发生了扩容，那么会导致it指向的空间被释放
    //it本质就是一个野指针，这种问题，我们叫做迭代器失效
    v1.insert(it, 30);
  }
  for (auto e : v1)
  {
    cout << e << " ";
  }
  cout << endl;
}

1ecd1b2606ed46e9956a89f231c9802c.png

当插入数据需要扩容时，扩容会将旧空间的数据拷贝到新空间，再释放旧空间，此时pos就指向了一块释放的空间，再对pos位置进行访问时，就属于野指针问题，一般我们还需要加上对pos位置的提前调整，防止迭代器失效。


       insert的返回值是iterator：虽然在插入数据的过程中调整了pos，解决了内部的迭代器失效问题，但是外部的迭代器（it）还是失效的，我们需要将更新后的迭代器利用返回值的形式返回，防止需要再次使用这个迭代器时发生失效。

4.erase

erase也会存在迭代器失效的问题 

iterator erase(iterator pos)
{
  assert(pos >= _start);
  assert(pos < _finish);
  iterator begin = pos + 1;
  while (begin < _finish)
  {
    *(begin - 1) = *begin;
    ++begin;
  }
  --_finish;
  return pos;
}
void test_vector5()
{
  vector<int> v1;
  v1.push_back(1);
  v1.push_back(2);
  v1.push_back(3);
  v1.push_back(4);
  v1.push_back(5);
  //要求删除v1中所有的偶数
  //         g++下     vs下
  // 1 2 3 4 5 --> 正常    断言报错 vector的迭代器的失效主要是在insert和erase中
  // 1 2 3 4   --> 崩溃    断言报错
  // 1 2 4 5   --> 结果不对  断言报错
    //测试库中的erase --- 存在失效
  vector<int> v2;
  v2.push_back(1);
  v2.push_back(2);
  v2.push_back(3);
  v2.push_back(4);
  v2.push_back(5);
  std::vector<int>::iterator it = v2.begin();
  while (it != v2.end())
  {
    if (*it % 2 == 0)
    { 
      v2.erase(it);
    }
    ++it;
  }
   /*************************************************/
  vector<int>::iterator it = v1.begin();
  while (it != v1.end())
  {
    if (*it % 2 == 0)
    {
      it = v1.erase(it);//每次跟新一下迭代器，不会存在失效了
    }
    else
    {
      ++it;
    }
  }
  for (auto e : v1)
  {
    cout << e << " ";
  }
  cout << endl;
}

5.swap

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

六、完成代码 

#pragma once
namespace vec
{
  template<class T>
  class vector
  {
    //typedef T* iterator;//typedef也受访问限定符的限制，放在这里默认是私有的
  public:
    typedef T* iterator;
    typedef const T* const_iterator;
    iterator begin()
    {
      return _start;
    }
    iterator end()
    {
      return _finish;
    }
    const_iterator begin() const
    {
      return _start;
    }
    const_iterator end() const
    {
      return _finish;
    }
    void swap(vector<T>& v)
    {
      std::swap(_start, v._start);
      std::swap(_finish, v._finish);
      std::swap(_end_of_storage, v._end_of_storage);
    }
    vector()
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {}
    //v2(v1)
    //传统写法
    /*
        vector(const vector<T>& v)
    {
      _start = new T[v.capacity()];
      _finish = _start + v.size();
      _end_of_storage = _start + v.capacity();
      memcpy(_start, v._start, v.size() * sizeof(T));//存在浅拷贝
    }
    vector(const vector<T>& v)
    {
      _start = new T[v.capacity()]; //让v2开辟一块和v一样大小的空间
      for (size_t i = 0; i < v.size(); i++)
      {
        _start[i] = v[i];//通过循环进行赋值
      }
      //最后调整_finish和_end_of_storage的大小
      _finish = _start + v.size();
      _end_of_storage = _start + v.capacity();
    }
        */
    //v2(v1)
    //现代写法
    //一个类模板的成员函数，又可以是一个函数模板
    template <class InputIterator>
    vector(InputIterator first, InputIterator last)
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }
    vector(const vector<T>& v)//也支持vector(const vector& v)
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {
      vector<T> tmp(v.begin(), v.end());
      swap(tmp);
      //this->swap(tmp);
    }
    //v1 = v2
    //vector<T>& operator=(const vector<T>& v) //传统写法
    //vector& operator=(vector v)语法上也支持这样写
    vector<T>& operator=(vector<T> v)//推荐写
    {
      swap(v);
      return *this;
    }
    ~vector()
    {
      if (_start)
      {
        delete[] _start;
        _start = _finish = _end_of_storage = nullptr;
      }
    }
    const T& operator[](size_t i) const
    {
      assert(i < size());
      return _start[i];
    }
    T& operator[](size_t i)
    {
      assert(i < size());
      return _start[i];
    }
    size_t size() const
    {
      return _finish - _start;
    }
    size_t capacity() const
    {
      return _end_of_storage - _start;
    }
    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());存在浅拷贝
          for (size_t i = 0; i < sz; i++)
          {
            //T是int，一个一个拷贝没问题
            //T是自定义类型，一个个拷贝调用的是深拷贝赋值，也没问题
            tmp[i] = _start[i];
          }
          delete[]_start;
        }
        _start = tmp;
        _finish = _start + sz;
        _end_of_storage = _start + n;
      }
    }
    void resize(size_t n, const T& val = T())
        //T()是匿名对象，它的生命周期本来只是存在于当前行，但是被const修饰以后，可以延长它的生命周期
    {
      if (n < size())
      {
        _finish = _start + n;
      }
      else
      {
        if (n > capacity())
        {
          reserve(n);
        }
        while (_finish != _start + n)
        {
          *_finish = val;
          ++_finish;
        }
      }
    }
    iterator insert(iterator pos, const T& x)
    {
      assert(pos >= _start);
      assert(pos <= _finish);
      if (_finish == _end_of_storage)
      {
        //扩容会导致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;
      return 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;
    }
    void push_back(const T& x)
    {
      if (_finish == _end_of_storage)
      {
        //扩容
        reserve(capacity() == 0 ? 4 : capacity() * 2);
      }
      *_finish = x;
      ++_finish;
    }
    void pop_back(const T& x)
    {
      assert(_finish > _start);
      --_finish;
    }
  private:
    iterator _start;
    iterator _finish;
    iterator _end_of_storage;
  };
}
文章标签：
C++
容器
关键词：
C++ stl
C++ vector
C++ stl vector
霄沫凡M
目录
相关文章
ephemerals__
|
7天前
|
编译器 C语言 C++
【c++丨STL】list模拟实现（附源码）
本文介绍了如何模拟实现C++中的`list`容器。`list`底层采用双向带头循环链表结构，相较于`vector`和`string`更为复杂。文章首先回顾了`list`的基本结构和常用接口，然后详细讲解了节点、迭代器及容器的实现过程。 最终，通过这些步骤，我们成功模拟实现了`list`容器的功能。文章最后提供了完整的代码实现，并简要总结了实现过程中的关键点。 如果你对双向链表或`list`的底层实现感兴趣，建议先掌握相关基础知识后再阅读本文，以便更好地理解内容。
ephemerals__
15 1
ephemerals__
|
20天前
|
算法 C语言 C++
【c++丨STL】list的使用
本文介绍了STL容器`list`的使用方法及其主要功能。`list`是一种双向链表结构，适用于频繁的插入和删除操作。文章详细讲解了`list`的构造函数、析构函数、赋值重载、迭代器、容量接口、元素访问接口、增删查改操作以及一些特有的操作接口如`splice`、`remove_if`、`unique`、`merge`、`sort`和`reverse`。通过示例代码，读者可以更好地理解如何使用这些接口。最后，作者总结了`list`的特点和适用场景，并预告了后续关于`list`模拟实现的文章。
ephemerals__
34 7
ephemerals__
|
2月前
|
存储 编译器 C语言
【c++丨STL】vector的使用
本文介绍了C++ STL中的`vector`容器，包括其基本概念、主要接口及其使用方法。`vector`是一种动态数组，能够根据需要自动调整大小，提供了丰富的操作接口，如增删查改等。文章详细解释了`vector`的构造函数、赋值运算符、容量接口、迭代器接口、元素访问接口以及一些常用的增删操作函数。最后，还展示了如何使用`vector`创建字符串数组，体现了`vector`在实际编程中的灵活性和实用性。
ephemerals__
66 4
ephemerals__
|
2月前
|
C语言 C++ 容器
【c++丨STL】string模拟实现（附源码）
本文详细介绍了如何模拟实现C++ STL中的`string`类，包括其构造函数、拷贝构造、赋值重载、析构函数等基本功能，以及字符串的插入、删除、查找、比较等操作。文章还展示了如何实现输入输出流操作符，使自定义的`string`类能够方便地与`cin`和`cout`配合使用。通过这些实现，读者不仅能加深对`string`类的理解，还能提升对C++编程技巧的掌握。
ephemerals__
81 5
ephemerals__
|
2月前
|
存储 编译器 C语言
【c++丨STL】string类的使用
本文介绍了C++中`string`类的基本概念及其主要接口。`string`类在C++标准库中扮演着重要角色，它提供了比C语言中字符串处理函数更丰富、安全和便捷的功能。文章详细讲解了`string`类的构造函数、赋值运算符、容量管理接口、元素访问及遍历方法、字符串修改操作、字符串运算接口、常量成员和非成员函数等内容。通过实例演示了如何使用这些接口进行字符串的创建、修改、查找和比较等操作，帮助读者更好地理解和掌握`string`类的应用。
ephemerals__
63 2
oioihoii
|
19天前
|
存储 对象存储 C++
C++ 中 std::array＜int, array_size＞ 与 std::vector＜int＞ 的深入对比
本文深入对比了 C++ 标准库中的 `std::array` 和 `std::vector`，从内存管理、性能、功能特性、使用场景等方面详细分析了两者的差异。`std::array` 适合固定大小的数据和高性能需求，而 `std::vector` 则提供了动态调整大小的灵活性，适用于数据量不确定或需要频繁操作的场景。选择合适的容器可以提高代码的效率和可靠性。
oioihoii
42 0
ephemerals__
|
2月前
|
存储 算法 Linux
【c++】STL简介
本文介绍了C++标准模板库（STL）的基本概念、组成部分及学习方法，强调了STL在提高编程效率和代码复用性方面的重要性。文章详细解析了STL的六大组件：容器、算法、迭代器、仿函数、配接器和空间配置器，并提出了学习STL的三个层次，旨在帮助读者深入理解和掌握STL。
ephemerals__
61 0
ephemerals__
|
23天前
|
存储 编译器 C语言
【c++丨STL】vector模拟实现
本文深入探讨了 `vector` 的底层实现原理，并尝试模拟实现其结构及常用接口。首先介绍了 `vector` 的底层是动态顺序表，使用三个迭代器（指针）来维护数组，分别为 `start`、`finish` 和 `end_of_storage`。接着详细讲解了如何实现 `vector` 的各种构造函数、析构函数、容量接口、迭代器接口、插入和删除操作等。最后提供了完整的模拟实现代码，帮助读者更好地理解和掌握 `vector` 的实现细节。
ephemerals__
31 0
Svan.
|
3月前
|
存储 程序员 C++
C++常用基础知识—STL库(2)
C++常用基础知识—STL库(2)
Svan.
89 5
白子寰
|
3月前
|
存储 C++ 索引
【C++打怪之路Lv9】-- vector
【C++打怪之路Lv9】-- vector
白子寰
27 1