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

【C++ STL】vector模拟实现

2023-08-23 65 发布于辽宁
版权
举报
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【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
+关注
60文章
目录
打赏
0
0
0
0
3
分享
相关文章
平凡程序猿~
|
18天前
|
存储 缓存 C++
C++ 容器全面剖析：掌握 STL 的奥秘，从入门到高效编程
C++ 标准模板库（STL）提供了一组功能强大的容器类，用于存储和操作数据集合。不同的容器具有独特的特性和应用场景，因此选择合适的容器对于程序的性能和代码的可读性至关重要。对于刚接触 C++ 的开发者来说，了解这些容器的基础知识以及它们的特点是迈向高效编程的重要一步。本文将详细介绍 C++ 常用的容器，包括序列容器（`std::vector`、`std::array`、`std::list`、`std::deque`）、关联容器（`std::set`、`std::map`）和无序容器（`std::unordered_set`、`std::unordered_map`），全面解析它们的特点、用法
平凡程序猿~
20 1
C++ 容器全面剖析：掌握 STL 的奥秘，从入门到高效编程
羑悻的小杀马特
|
21天前
|
算法 编译器 C++
模拟实现c++中的vector模版
模拟实现c++中的vector模版
羑悻的小杀马特
52 28
ephemerals__
|
9天前
|
存储 算法 C++
【c++丨STL】priority_queue（优先级队列）的使用与模拟实现
本文介绍了STL中的容器适配器`priority_queue`（优先级队列）。`priority_queue`根据严格的弱排序标准设计，确保其第一个元素始终是最大元素。它底层使用堆结构实现，支持大堆和小堆，默认为大堆。常用操作包括构造函数、`empty`、`size`、`top`、`push`、`pop`和`swap`等。我们还模拟实现了`priority_queue`，通过仿函数控制堆的类型，并调用封装容器的接口实现功能。最后，感谢大家的支持与关注。
ephemerals__
46 1
ephemerals__
|
2月前
|
C++ 容器
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器：栈（stack）和队列（queue）。容器适配器是在已有容器基础上添加新特性或功能的结构，如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数（empty、size、top/front/back、push/pop、swap），并提供了使用示例和模拟实现代码。通过这些内容，读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后，作者鼓励读者点赞支持。 总结：本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现，帮助读者掌握这两种容器适配器的特性和应用场景。
ephemerals__
65 21
平凡程序猿~
|
18天前
|
存储 算法 C++
深入浅出 C++ STL：解锁高效编程的秘密武器
C++ 标准模板库（STL）是现代 C++ 的核心部分之一，为开发者提供了丰富的预定义数据结构和算法，极大地提升了编程效率和代码的可读性。理解和掌握 STL 对于 C++ 开发者来说至关重要。以下是对 STL 的详细介绍，涵盖其基础知识、发展历史、核心组件、重要性和学习方法。
平凡程序猿~
21 0
ephemerals__
|
3月前
|
编译器 C语言 C++
【c++丨STL】list模拟实现（附源码）
本文介绍了如何模拟实现C++中的`list`容器。`list`底层采用双向带头循环链表结构，相较于`vector`和`string`更为复杂。文章首先回顾了`list`的基本结构和常用接口，然后详细讲解了节点、迭代器及容器的实现过程。 最终，通过这些步骤，我们成功模拟实现了`list`容器的功能。文章最后提供了完整的代码实现，并简要总结了实现过程中的关键点。 如果你对双向链表或`list`的底层实现感兴趣，建议先掌握相关基础知识后再阅读本文，以便更好地理解内容。
ephemerals__
58 1
ephemerals__
|
3月前
|
算法 C语言 C++
【c++丨STL】list的使用
本文介绍了STL容器`list`的使用方法及其主要功能。`list`是一种双向链表结构，适用于频繁的插入和删除操作。文章详细讲解了`list`的构造函数、析构函数、赋值重载、迭代器、容量接口、元素访问接口、增删查改操作以及一些特有的操作接口如`splice`、`remove_if`、`unique`、`merge`、`sort`和`reverse`。通过示例代码，读者可以更好地理解如何使用这些接口。最后，作者总结了`list`的特点和适用场景，并预告了后续关于`list`模拟实现的文章。
ephemerals__
78 7
ephemerals__
|
4月前
|
存储 编译器 C语言
【c++丨STL】vector的使用
本文介绍了C++ STL中的`vector`容器，包括其基本概念、主要接口及其使用方法。`vector`是一种动态数组，能够根据需要自动调整大小，提供了丰富的操作接口，如增删查改等。文章详细解释了`vector`的构造函数、赋值运算符、容量接口、迭代器接口、元素访问接口以及一些常用的增删操作函数。最后，还展示了如何使用`vector`创建字符串数组，体现了`vector`在实际编程中的灵活性和实用性。
ephemerals__
179 4
ephemerals__
|
4月前
|
C语言 C++ 容器
【c++丨STL】string模拟实现（附源码）
本文详细介绍了如何模拟实现C++ STL中的`string`类，包括其构造函数、拷贝构造、赋值重载、析构函数等基本功能，以及字符串的插入、删除、查找、比较等操作。文章还展示了如何实现输入输出流操作符，使自定义的`string`类能够方便地与`cin`和`cout`配合使用。通过这些实现，读者不仅能加深对`string`类的理解，还能提升对C++编程技巧的掌握。
ephemerals__
179 5
ephemerals__
|
4月前
|
存储 编译器 C语言
【c++丨STL】string类的使用
本文介绍了C++中`string`类的基本概念及其主要接口。`string`类在C++标准库中扮演着重要角色，它提供了比C语言中字符串处理函数更丰富、安全和便捷的功能。文章详细讲解了`string`类的构造函数、赋值运算符、容量管理接口、元素访问及遍历方法、字符串修改操作、字符串运算接口、常量成员和非成员函数等内容。通过实例演示了如何使用这些接口进行字符串的创建、修改、查找和比较等操作，帮助读者更好地理解和掌握`string`类的应用。
ephemerals__
118 2
AI助理

你好，我是AI助理

可以解答问题、推荐解决方案等