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

【C++ STL】vector模拟实现

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

先看一下官方文档中对构造函数是怎么描述的。


image.png

image.png

这里的allocator什么的表示内存池，能够更快的申请空间，这次的实现就不实现内存池了，直接new。


首先要先声明自己的命名空间

namespace mudan
{
  class vector
  {
  };
}

为什么这里我叫mudan呢？因为我媳妇叫牡丹，哈哈哈~


然后可以看到参数当中有很多都是没有听过的，一般都是typedef的，可以去查一下Member types


image.png


可以看到iterator其实就是模板T。

namespace mudan
{
  template<class T>
  class vector
  {
  public:
  typedef T* iterator;
  private:
  iterator _start;//起始位置
  iterator _finish;//最后一个元素的后一个位置
  iterator _end_of_capacity;//整个容器的最后一个位置的下一个位置
  };
}

成员定义好了就该实现构造函数了。


默认构造函数/析构函数

vector()
    :_start(nullptr)
    ,_finish(nullptr)
    ,_end_of_capacity(nullptr)
  {}
  //区间构造函数
  template<class InputIterator>
  vector(InputIterator first, InputIterator last)
    :_start(nullptr)
    ,_finish(nullptr)
    ,_end_of_capacity(nullptr)
  {
    while (first != last)
    {
    push_back(*first);
    first++;
    }
  }
  ~vector()
  {
    delete[] _start;
    _finish = nullptr;
    _end_of_capacity = nullptr;
  }


直接初始化为nullptr即可，因为随机的空间是不能被操作的。


image.png

image.png

可以看到初始化成功了。


然后就可以开始尝试实现push_back函数了。


而这里要实现push_back分为几种情况


1.原来的空间为nullptr就需要分配内存空间，一般先分配四个大小的空间


2.空间不够需要扩容，一般扩大到原空间的两倍较为合适


3.直接添加元素


这里需要扩容就需要实现一下reserve函数了。


image.png


而在reserve函数当中需要得知当前的容量大小，因此，可以实现一下size()和capacity()。


size()/capacity()
  size_t size()
  {
    return (_finish-_start);
  }
  size_t capacity()
  {
    return (_end_of_capacity-_start);
  }

reserve()


image.png

void reserve(size_t n)
  {
    if (n > capacity())
    {
    T* tmp = new T[n];//开辟一个n个大小的空间
    if (_start)
    {
      memcpy(tmp, _start, sizeof(T) * capacity());//将原来空间的内容拷贝过来
    }
    delete[] _start;
    }
    _start = tmp;
    _finish = _start + sz;
    _end_of_capacity = _start + n;
  }
1

push_back()

image.png

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

好了，现在可以简单的测试一下程序对不对了。


开搞！！！


image.png


咦，程序怎么崩溃了？还是报的空指针问题？


通过调试可以发现问题发生在扩容这里了。


image.png


程序走到这里都是很正常的，空间也都开辟了


image.png


但走到下一步的时候，size()传回的值确实一个超级大的数字，这是为啥？


因为_start确实有空间了，但是_finish还没有啊，而size()的实现方式是通过_finish-_start所得到的，当然会出现问题，所以这里问题就出现在size()上了。


解决方法就是提前算好size()的大小。


reserve()修改
  void reserve(size_t n)
  {
    size_t sz = size();
    if (n > capacity())
    {
    T* tmp = new T[n];//开辟一个n个大小的空间
    if (_start)
    {
      memcpy(tmp, _start, sizeof(T) * sz);//将原来空间的内容拷贝过来
    }
    delete[] _start;
    _start = tmp;
    _finish = _start + sz;
    _end_of_capacity = _start + n;
    }
  }


image.png


为了进一步验证正确性，实现一下operator[]

image.png

operator[]
reference就是T&
  T& operator[](size_t pos)
  {
    assert(pos < size());
    assert(pos >= 0);
    return _start[pos];
  }
  const T& operator[](size_t pos)const 
  {
    assert(pos < size());
    assert(pos >= 0);
    return _start[pos];

为什么库里要实现两个operator[]？


因为有时候传过来的是const类型，因为返回是引用类型，所以会有权限的放大的问题，因此const对应const的operator就可以了。


image.png


可以看到程序是正常运行的。

image.png

pop_back()
  void pop_back()
  {
    _finish--;
  }

为了支持范围for，实现一个begin()和end()，因为范围for是很简单的替换，只认begin()和end()。


begin()/end()
  const_iterator begin()const
  {
    return _start;
  }
  const_iterator end()const
  {
    return _finish;
  }
  iterator begin()
  {
    return _start;
  }
  iterator end()
  {
    return _finish;
  }

image.png


然后就是利用迭代器进行遍历


image.png


如果这里的iterator不是在public当中typedef的就会报错，因为会受到访问限定符的约束。


insert()

image.png


在position位置之前插入一个val。


根据以前实现的顺序表可以知道，如果要在1 2 3 4 5 6当中的3之前插入一个520，需要将3 4 5 6全都往后挪动一个位置，空出一个位置给520–>1 2 520 3 4 5 6。


void insert(iterator pos, const T& val)
  {
    assert(pos >= _start);
    assert(pos <= _finish);
    if (_finish == _end_of_capacity)
    {
    reserve(capacity() == 0 ? 4 : 2 * capacity());
    }
    iterator end = _finish - 1;
    while (end >= pos)
    {
    *(end + 1) = *end;
    end--;
    }
    *pos = val;
    ++_finish;
  }

为了测试代码的正确性，可以测试一下这个程序------>在所有的偶数之前插入一个当前偶数的二倍。


image.png


但走着走着怎么程序就挂掉了呢？并且出现了随机数。


其实跟着之前的代码走一遍就知道哪里出错了。


image.png


首先，第一个问题就是it没有++会导致一直都是在第二个位置进行插入，再一个问题就是当容量不够的时候是需要扩容的，这里的扩容不是原地扩容，所以会导致野指针的问题，即pos的指向已经不是原来的内容了。


我们回到库当中的insert的定义：


image.png


可以看到还给了一个迭代器版本的insert，这里就可以利用这个迭代器版本的insert的返回值来更新it，让it动起来并且会更新it的地址，当遇到不是偶数的时候直接++即可，返回值就是更新后的pos位置，为了防止迭代器失效可以在每次扩容之后更新一下pos的位置，不过要先计算好pos位置离_start的距离是多少。


iterator insert(iterator pos, const T& val)
  {
    assert(pos >= _start);
    assert(pos <= _finish);
    if (_finish == _end_of_capacity)
    {
    size_t len = pos - _start;
    reserve(capacity() == 0 ? 4 : 2 * capacity());
    pos = _start + len;//更新迭代器位置，防止迭代器失效
    }
    iterator end = _finish - 1;
    while (end >= pos)
    {
    *(end + 1) = *end;
    end--;
    }
    *pos = val;
    ++_finish;
    return pos+1;
  }
======================================================================================
  while (it != arr.end())
  {
    if ((*it) % 2 == 0)
    {
    it=arr.insert(it, (*it) * 2);
    }
    it++;
  }
  for (auto e : arr)
  {
    cout << e << " ";
  }

image.png


目前来看都是正常的。


然后就是实现一下erase了。


erase()

erase()也是和之前写过的顺序表一样，直接向前覆盖就行了。

image.png

image.png

假如要实现一个删除所有奇数的程序，利用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;
  }

image.png

operator=
  vector<T>& operator=(const vector<T> v)
  {
    swap(v);
    return *this;
  }
swap
  void swap(vector<T>& v)
  {
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_end_of_capacity, v._end_of_capacity);
  }


resize()
  void resize(size_t n,const T&val=T())
  {
    if (n > capacity())
    {
    reserve(n);//大于直接扩容
    }
    if (n > size())
    {
    //初始化并且填上值
    while (_finish < _start + n)
    {
      *_finish = val;
      ++_finish;
    }
    }
    else
    {
    _finish = _start + n;
    }
  }

现在，vector的常用接口基本都实现好了，做一道杨辉三角的题目试试。


class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ret(numRows);
        for (int i = 0; i < numRows; ++i) {
            ret[i].resize(i + 1);
            ret[i][0] = ret[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
            }
        }
        return ret;
    }
};

这是使用官方的库实现的。


但使用我们自己的突然程序就崩溃了。


image.png


可以看到，是在析构函数崩溃的，可以先猜想，是不是因为同一块内存空间析构了两次导致的呢？


image.png


这里的第二个_start是浅拷贝。


image.png


image.png


等_start析构完了，tmp也变成也指针了，但最后tmp还要析构一次，所以会导致一块内存析构两次的结果。


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

最后发现还是跑不了，靠，原来是忘记写拷贝构造了，默认的浅拷贝还是会导致同一块内存析构两次。


拷贝构造

vector(const vector<T>& v)
    :_start(nullptr)
    , _finish(nullptr)
    , _end_of_capacity(nullptr)
  {
    vector<T> tmp(v.begin(), v.end());
    swap(tmp);
  }
  template<class InputIterator>
  vector(InputIterator first, InputIterator last)
    : _start(nullptr)
    , _finish(nullptr)
    , _end_of_capacity(nullptr)
  {
    while (first != last)
    {
    push_back(*first);
    first++;
    }
  }
  vector(size_t n, const T& val = T())
    :_start(nullptr)
    ,_finish(nullptr)
    ,_end_of_capacity(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)
    , _end_of_capacity(nullptr)
  {
    reserve(n);
    for (int i = 0; i < n; ++i)
    {
    push_back(val);
    }
  }

image.png


现在程序就没啥问题咯。


总代码

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