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

C++ -- vector类模拟实现

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

C++ – vector类模拟实现

0. 成员变量

template<class T>
typedef T* iterator;
typedef const T* const_iterator;
iterator _start;
iterator _finish;
iterator _end_of_storage;
  1. 为什么这里需要模板呢？

因为我们使用数组可能是int、char等等类型，这里就依靠是顺序存储的特性，就直接用指针来充当成员变量。

1. 构造函数

vector()
  :_start(nullptr)
  , _finish(nullptr)
  , _end_of_storage(nullptr)
{}
vector(size_t n, const T& val = T()) //T()->T类型的构造 && const 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 first, InputIterator last) //迭代器区间
  :_start(nullptr)
  , _finish(nullptr)
  , _end_of_storage(nullptr)
{
  while (first != last)
  {
    push_back(*first);
    ++first;
  }
}
  1. 为什么这里的const T& val = T()？

这里的写法是为了给一个默认值，T()是针对自定义类型:string、vector等等。内置类型int()、char()等都是由编译器来初始化

2. 析构函数

~vector()
{
  delete[] _start;
  _start = _finish = _end_of_storage = nullptr;
}

3. reserve方法

void reserve(size_t capa)
{
  if (capa > capacity())
  {
    size_t len = size(); //OK:记录当前长度
    T* tmp = new T[capa];
    if (_start != nullptr)
    {
      for (size_t i = 0; i < len; ++i)
      {
        tmp[i] = _start[i];
      }
      delete[] _start;
    }
    _start = tmp;
    _finish = _start + len;
    _end_of_storage = _start + capa;
  }
}

操作：


是否扩容

拷贝数据

变化成员变量

为什么_finish = _start + len，而不是 _finish = _start + size()？


因为size() = _finish - _start , _finish = _start + size() --> _finish = _start + _finiosh - _start

5. resize方法

void resize(size_t capa, T val = T())
{
  if (capa < size())
  {
    _finish = _start + capa;
  }
  else
  {
    if (capa > capacity())
    {
      reserve(capa);
    }
    while (_finish != _start + capa)
    {
      *_finish = val;
      ++_finish;
    }
  }
}

6. insert方法

iterator insert(iterator pos, const T& val)
{
  assert(pos >= _start && pos <= _finish);
  if (_finish == _end_of_storage)
  {
    size_t len = pos - _start; //记录当前pos距离_start的距离
    reserve(capacity() == 0 ? 4 : capacity() * 2);
    pos = _start + len; //扩容:因为new的新空间会导致pos不在空间中导致后面while循环出错(pos失效解决方案)
  }
  iterator end = _finish - 1;
  while (end >= pos)
  {
    *(end + 1) = *end;
    --end;
  }
  *pos = val;
  ++_finish;
  return pos;
}
  1. 为什么需要接受pos呢？

扩容问题会导致new出新的空间给_start，连续插入会导致pos迭代器失效

  1. 对没有改动pos进行测试：

微信图片_20230524040150.png

void test1()
{
  int arr[] = { 1,2,3,4};
  vector<int> v(arr, arr + sizeof(arr) / sizeof(int));
  v.insert(v.end(), 10);
  for (auto i : v)
  {
    cout << i << " ";
  }
  cout << endl;
}

reserve后pos不在[_start, _finish)范围内，解决方案就是改动pos

7. erase方法

iterator erase(iterator pos)
{
  assert(pos >= _start && pos < _finish);
  iterator start = pos + 1;
  while (start != _finish)
  {
    *(start - 1) = *start;
    ++start;
  }
  --_finish;
  return pos; //没有返回pos就导致迭代器失效
}

visual studio2019中的erase机制是一定是会pos迭代器失效。

8. push_back方法

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

9. pop_back方法

void pop_back()
{
  assert(!empty());
  --_finish;
}

10. []运算符重载

T& operator[](const size_t& pos)
{
  assert(pos < size());
  return _start[pos];
}
const T& operator[](const size_t& pos) const
{
  assert(pos < size());
  return _start[pos];
}

11. 拷贝构造

vector(const vector<T>& v)
  :_start(nullptr)
  , _finish(nullptr)
  , _end_of_storage(nullptr)
{
  reserve(v.capacity());
  _start = new T[v.capacity()];
  for (size_t i = 0; i < v.size(); ++i)
  {
    _start[i] = v._start[i];
  }
  _finish = _start + v.size();
  _end_of_storage = _start + v.capacity();
}
  1. 为什么用for循环依次拷贝数据，而不是memcpy()呢？

假如是string类型，拷贝的时候就需要深拷贝，但是memcpy是浅拷贝

12. 迭代器

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;
}

13. 完整代码

#pragma once
#include <assert.h>
namespace myvector
{
  template<class T>
  class vector
  {
  public:
    typedef T* iterator;
    typedef const T* const_iterator;
    vector()
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {}
    vector(size_t n, const T& val = T()) //T()->T类型的构造 && const T&引用修饰->起别名延长了生命周期
      :_start(nullptr)
      ,_finish(nullptr)
      ,_end_of_storage(nullptr)
    {
      reserve(n);
      for (size_t i = 0; i < n; ++i)
      {
        push_back(val);
      }
    }
    vector(int n, const T& val = T()) //T()->T类型的构造 && const T&引用修饰->起别名延长了生命周期
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {
      reserve(n);
      for (int i = 0; i < n; ++i)
      {
        push_back(val);
      }
    }
    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)
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {
      reserve(v.capacity());
      for (auto i : v)
      {
        push_back(i);
      }
    }*/
    //vector<自定义类型>-->两次析构会程序崩溃
    //vector(const vector<T>& v)
    //  :_start(nullptr)
    //  , _finish(nullptr)
    //  , _end_of_storage(nullptr)
    //{
    //  reserve(v.capacity());
    //  _start = new T[v.capacity()];
    //  memcpy(_start, v._start, sizeof(T) * v.size()); //memcpy也是浅拷贝
    //  _finish = _start + v.size();
    //  _end_of_storage = _start + v.capacity();
    //}
    vector(const vector<T>& v)
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {
      reserve(v.capacity());
      _start = new T[v.capacity()];
      for (size_t i = 0; i < v.size(); ++i)
      {
        _start[i] = v._start[i];
      }
      _finish = _start + v.size();
      _end_of_storage = _start + v.capacity();
    }
    iterator begin()
    {
      return _start; //传值返回:临时对象具有常性
    }
    iterator end()
    {
      return _finish;
    }
    const_iterator begin() const
    {
      return _start;
    }
    const_iterator end() const
    {
      return _finish;
    }
    T& operator[](const size_t& pos)
    {
      assert(pos < size());
      return _start[pos];
    }
    const T& operator[](const size_t& pos) const
    {
      assert(pos < size());
      return _start[pos];
    }
    size_t capacity() const
    {
      return _end_of_storage - _start;
    }
    size_t size() const
    {
      return _finish - _start;
    }
    void resize(size_t capa, T val = T())
    {
      if (capa < size())
      {
        _finish = _start + capa;
      }
      else
      {
        if (capa > capacity())
        {
          reserve(capa);
        }
        while (_finish != _start + capa)
        {
          *_finish = val;
          ++_finish;
        }
      }
    }
    //void reserve(size_t capa)
    //{
    //  if (capa > capacity())
    //  {
    //    size_t len = size(); //OK:记录当前长度
    //    T* tmp = new T[capa];
    //    if (_start != nullptr)
    //    {
    //      memcpy(tmp, _start, sizeof(T) * size()); //memcpy是浅拷贝
    //      delete[] _start;
    //    }
    //    _start = tmp;
    //    _finish = _start + len;
    //    //_finish = _start + size(); //err:size() = _finish - _start --> _finish = _finish
    //    _end_of_storage = _start + capa;
    //  }
    //}
    void reserve(size_t capa)
    {
      if (capa > capacity())
      {
        size_t len = size(); //OK:记录当前长度
        T* tmp = new T[capa];
        if (_start != nullptr)
        {
          for (size_t i = 0; i < len; ++i)
          {
            tmp[i] = _start[i];
          }
          delete[] _start;
        }
        _start = tmp;
        _finish = _start + len;
        //_finish = _start + size(); //err:size() = _finish - _start --> _finish = _finish
        _end_of_storage = _start + capa;
      }
    }
    void push_back(const T& val)
    {
      if (_finish == _end_of_storage)
      {
        reserve(capacity() == 0 ? 4 : capacity() * 2);
      }
      *(_finish) = val;
      ++_finish;
    }
    bool empty()
    {
      return _start == _finish;
    }
    void pop_back()
    {
      assert(!empty());
      --_finish;
    }
    iterator insert(iterator pos, const T& val)
    {
      assert(pos >= _start && pos <= _finish);
      if (_finish == _end_of_storage)
      {
        size_t len = pos - _start; //记录当前pos距离_start的距离
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        pos = _start + len; //扩容:因为new的新空间会导致pos不在空间中导致后面while循环出错(pos失效解决方案)
      }
      iterator end = _finish - 1;
      while (end >= pos)
      {
        *(end + 1) = *end;
        --end;
      }
      *pos = val;
      ++_finish;
      return pos;
    }
    iterator erase(iterator pos)
    {
      assert(pos >= _start && pos < _finish);
      iterator start = pos + 1;
      while (start != _finish)
      {
        *(start - 1) = *start;
        ++start;
      }
      --_finish;
      return pos; //没有返回pos就导致迭代器失效
    }
    ~vector()
    {
      delete[] _start;
      _start = _finish = _end_of_storage = nullptr;
    }
    void out(const vector<T>& v)
    {
      for (size_t i = 0; i < v.size(); ++i)
      {
        cout << v[i] << " ";
      }
      cout << endl;
      vector<T>::const_iterator it = v.begin();
      while (it != v.end())
      {
        cout << *it << " ";
        ++it;
      }
      cout << endl;
    }
  private:
    iterator _start;
    iterator _finish;
    iterator _end_of_storage;
  };
}





文章标签：
C++
存储
编译器
关键词：
C++类
C++ vector
C++ vector类
c++云原生数据仓库 AnalyticDB PostgreSQL版类
txfwuupyzmygs
目录
相关文章
西柚与蓝莓
|
5天前
|
C++ 容器
C++中向量的操作vector
C++中向量的操作vector
西柚与蓝莓
17 6
დ旧言~
|
3天前
|
设计模式 安全 编译器
【C++11】特殊类设计
【C++11】特殊类设计
დ旧言~
22 10
芯动大师
|
8天前
|
C++
C++友元函数和友元类的使用
C++中的友元（friend）是一种机制，允许类或函数访问其他类的私有成员，以实现数据共享或特殊功能。友元分为两类：类友元和函数友元。类友元允许一个类访问另一个类的私有数据，而函数友元是非成员函数，可以直接访问类的私有成员。虽然提供了便利，但友元破坏了封装性，应谨慎使用。
芯动大师
39 9
小余大牛成长记
|
4天前
|
存储 编译器 C语言
【C++基础 】类和对象（上）
【C++基础 】类和对象（上）
小余大牛成长记
8 1
ForcibleBugMaker
|
12天前
|
存储 C语言 C++
【C++】vector的使用上
**C++ STL的vector简介与用法：** Vector是动态顺序数组，提供高效下标访问，支持动态增长。与数组类似但可自动调整大小。常用构造函数包括默认、填充、迭代器范围和拷贝构造。析构函数自动释放内存。赋值运算符执行深拷贝。迭代器接口包括`begin()`和`end()`（反向对应`rbegin()`和`rend()`)，C++11增加了const版本以支持只读访问。示例代码展示了不同构造函数和迭代器的使用。
ForcibleBugMaker
22 9
ForcibleBugMaker
|
12天前
|
编译器 C++
【C++】string类的使用④（字符串操作String operations ）
这篇博客探讨了C++ STL中`std::string`的几个关键操作，如`c_str()`和`data()`，它们分别返回指向字符串的const char*指针，前者保证以&#39;\0&#39;结尾，后者不保证。`get_allocator()`返回内存分配器，通常不直接使用。`copy()`函数用于将字符串部分复制到字符数组，不添加&#39;\0&#39;。`find()`和`rfind()`用于向前和向后搜索子串或字符。`npos`是string类中的一个常量，表示找不到匹配项时的返回值。博客通过实例展示了这些函数的用法。
ForcibleBugMaker
19 1
ForcibleBugMaker
|
12天前
|
存储 C++
【C++】string类的使用③（非成员函数重载Non-member function overloads）
这篇文章探讨了C++中`std::string`的`replace`和`swap`函数以及非成员函数重载。`replace`提供了多种方式替换字符串中的部分内容，包括使用字符串、子串、字符、字符数组和填充字符。`swap`函数用于交换两个`string`对象的内容，成员函数版本效率更高。非成员函数重载包括`operator+`实现字符串连接，关系运算符（如`==`, `&lt;`等）用于比较字符串，以及`swap`非成员函数。此外，还介绍了`getline`函数，用于按指定分隔符从输入流中读取字符串。文章强调了非成员函数在特定情况下的作用，并给出了多个示例代码。
ForcibleBugMaker
11 1
დ旧言~
|
4天前
|
存储 Java C++
【c++】vector模拟
【c++】vector模拟
დ旧言~
6 0
ForcibleBugMaker
|
12天前
|
编译器 C++
【C++】vector的使用下
**C++ 中的 `std::vector` 概要：** - **元素获取：** 支持 `operator[]`（越界时不检
ForcibleBugMaker
11 0
ForcibleBugMaker
|
12天前
|
C++
【C++】string类的使用④（常量成员Member constants）
C++ `std::string` 的 `find_first_of`, `find_last_of`, `find_first_not_of`, `find_last_not_of` 函数分别用于从不同方向查找目标字符或子串。它们都返回匹配位置，未找到则返回 `npos`。`substr` 用于提取子字符串，`compare` 则提供更灵活的字符串比较。`npos` 是一个表示最大值的常量，用于标记未找到匹配的情况。示例代码展示了这些函数的实际应用，如替换元音、分割路径、查找非字母字符等。
ForcibleBugMaker
13 0

热门文章

最新文章

  • 1
    Facebook 的 C++ 11 组件库 Folly Futures
  • 2
    C++模板初阶
  • 3
    c++读取和写入TXT文件的整理
  • 4
    C++的const用法
  • 5
    C++ Builder初学问与答(十四)
  • 6
    C++类模板的三种特化
  • 7
    [C++再学习系列] 变量与声明时初始化
  • 8
    【一通百通】C/C++的std标准总结
  • 9
    读书笔记 effective c++ Item 11 在operator=中处理自我赋值
  • 10
    IBM RSA (IBM rational software architect ) V8 学习之三 C++类图
  • 1
    【AIGC】LangChain Agent（代理）技术分析与实践
    471
  • 2
    基于阿里云向量检索 Milvus 版和 LangChain 快速构建 LLM 问答系统
    1113
  • 3
    利用LangChain构建的智能数据库操作系统
    155
  • 4
    LangChain：1. Prompt基本使用
    74
  • 5
    ICDE2024 ｜VDTuner：向量数据库自动调优技术
    51
  • 6
    Langchain 与 Elasticsearch：创新数据检索的融合实战
    73
  • 7
    adb: error: cannot create file/directory ‘d:/1.png‘: No such file or directory
    32
  • 8
    Android Activity重写dump方法实现通过adb调试代码
    31
  • 9
    RAG：AI大模型联合向量数据库和 Llama-index，助力检索增强生成技术
    344
  • 10
    Android 对adb命令的拦截
    35

    • 相关课程

    更多
  • AnalyticDB PostgreSQL 企业智能数据中台：一站式管理数据服务资产
  • 大数据知识图谱—钱大妈数据中台建设最佳实践
  • 大数据知识图谱—数据中台的智能进化—阿里巴巴十二年数据平台发展历程
  • C++ 入门教程开发文档

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce

    • 相关实验场景

    更多
  • 使用PAI-EAS一键部署ChatGLM及LangChain应用
  • 基于Elasticsearch向量检索的以文搜图
    • 下一篇
    2024年阿里云免费云服务器及学生三百通用额度申请教程参考