【C++】vector介绍以及模拟实现（超级详细）-阿里云开发者社区

前言

string的特性和用法以及底层的探索已经，虽然string不算container的成员之一，但是也见到了其的影子，接下来让我们看看vector

vector介绍

vector 是 C++ 标准模板库（STL）中的一个动态数组容器，它提供了动态大小调整和高效的随机访问功能。vector 的元素在内存中是连续存储的，这意味着可以通过指针或索引高效地访问元素。vector 自动管理其内部使用的内存，不需要手动分配和释放，支持常见容器操作，如插入、删除、遍历等.

vector常见操作

构造函数

(constructor)构造函数声明	接口说明
vector（size_type n, const value_type& val = value_type()）	构造并初始化n个val

vector (const vector& x); （重点）	拷贝构造
vector (InputIterator ﬁrst, InputIterator last);	使用迭代器进行初始化构造

iterator

函数声明	接口说明

begin + end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend	返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的 reverse_iterator,即begin位置

capacity

函数声明	接口说明
capacity	获取容量大小
size	size 获取数据个数
empty	判断是否为空
resize	改变vector的size
reserve	改变vector的capacity

modify

vector增删查改	接口说明
push_back（重点）	尾插
pop_back （重点）	尾删
ﬁnd	查找。（注意这个是算法模块实现，不是vector的成员接口）
insert	在position之前插入val

erase	删除position位置的数据
swap	交换两个vector的数据空间
operator[]	像数组一样访问

`vector`模拟实现

存储结构

结构上使用命名空间myvector进行封装，防止与库冲突，使用class封装成为对象vector

这样typedef的一点是和STL保持一致

写vector写成类模板，可以支持存贮多种类型数据
_start表示数据存储的开始地址
_finish表示数据存贮的的下一个地址
_end_of_storage表示数据当前开辟的最大空间的地址

namespace myvector
{
    template<class T>
    class vector
    {
        public:
         typedef T* iterator;
    typedef const T* const_iterator;
        private:

        iterator _start;
        iterator _finish;
        iterator _end_of_storage;
    };
}

默认构造函数

构造函数

初始化是使用的都是空指针

vector()
    :_start(nullptr)
        , _finish(nullptr)
        , _end_of_storage(nullptr)
    {}

使用n个val初始化对象

vector(size_t n, const T& val = T())
{
resize(n, val);
}

根据可以模板的嵌套的性质，再次进行模板的定义
这是使用两个迭代器的进行初始化

template<class InputIterator>

vector(InputIterator first, InputIterator last)
{
    while (first != last)
    {
        push_back(*first);
        ++first;
    }
}

拷贝构造函数

利用一个对象初始化另外一个对象传引用
new出和传递的对象一样大小的空间，在string类中我们利用了mencpy进行拷贝，在vector中不采用mencpy

mencpy拷贝只能进行内置类型的浅拷贝，不能进行自定义类型的深拷贝
在这里面进行依次赋值，或者push_back

最后进行_finish和_end_of_storage的初始化

vector(const vector<T>& v)
{

    _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();

}

赋值运算符重载

在operator=的参数中是值传递，是实参的拷贝，这里面利用这个特性进数据的交换
返回this指针就是赋值的内容了

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<T> operator=(vector<T> v)
{
  swap(v);
  return *this;
}

析构函数

判断_start是否为空为空，避免再次析构

~vector()
{
    if (_start)
    {

        delete[] _start;
        _start = _finish = _end_of_storage = nullptr;
    }

}

容量（capacity）

`size`和`capzcity`

vector的size和capacity不同于string类中的不一样，vector定义的是指针
充分利用只针的特性，（指针—指针）是数值，可以计算出capacity和size

size_t size()const 
{
return _finish - _start;
}
size_t capacity()const 
{
return _end_of_storage - _start;
}

reserve

开始判断需要扩容的大小是否大于capacity，以避免重复扩容效率低下
在开始时候记录原始空间的大小，是为了避免迭代器失效

进行空间的扩容，会将原来的空间析构，原始的计算空间大小已经已释放，指向的_start _finish _end_of_storage已经失效

这里还是采用在这里面进行依次赋值，或者push_back
更新_start _finish _end_of_storage

void reserve(size_t n)
{
    if (n > capacity())
    {
        T* tmp = new T[n];
        size_t sz = size();
        if (_start)
        {
            //memcpy(tmp, _start, sizeof(T)*capacity());
            //string 类深拷贝
            for (int i = 0; i < sz; i++)
            {
                tmp [i] = _start[i];
            }
            delete[] _start;
        }

        _start = tmp;
        _finish = sz + _start;
        _end_of_storage = _start + n;
    }
}

resize

两种情况

N<capacity
直接进行移动_finish
N>capacity
进行容量的检查和扩容，依次赋值val

const T& val = T()这句话是针对内置类型和自定义类型，C++这里将内置类型进行了升级

int = 1; <=> int(1);//这里int有点像构造函数

void resize(size_t n, const T& val = T())
{
    if (n < capacity())
    {
        _finish = n + _start;
    }
    else
    {
        reserve(n);
        while (_finish != _start + n)
        {
            *_finish = val;
            ++_finish;
        }
    }
}

修改（modify）

push_back

首先进行容量的检查
直接将_finsih位置解引用赋值，++_finsih

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

    *_finish = x;
    ++_finish;
}

pop_back

复用erase

void pop_back()
{
erase(end()-1);
}

insert

进行断言，防止pos越界访问
判断空间的大小_finish == _end_of_storage
size_t step = pos - _start用step记录，距离 _start距离，扩容的时候将原空间释放，pos将无法访问,扩容完成后进行pos的恢复

将pos位置的数据依次进行移动、
插入pos位置的值，修改_finish
为了避免迭代器失效，返回现在的位置pos

iterator insert(iterator pos, const T& x)
{
    assert(pos <= _finish && pos >= _start);

    if (_finish == _end_of_storage)
    {
        //防止迭代器失效
        size_t step = pos - _start;

        size_t newcapacity = capacity() == 0 ? 0 : capacity() * 2;
        reserve(newcapacity);
        //防止迭代器失效
        pos = _start + step;
    }

    iterator end = _finish - 1;
    while (end >= pos)
    {
        *(end + 1) = *end;
        ++end;
    }
    *pos = x;
    ++_finish;
    
    return pos
}

erase

进行断言，防止pos越界访问
将pos后面的元素向前面移动，进行覆盖
为了避免迭代器失效，返回现在的位置pos

iterator erase(iterator pos)
{
    assert(pos <= _finish && pos >= _start);

    while (pos != _finish)
    {
        *pos = *(pos + 1);
        pos++;
    }

    --_finish;
    
    return pos
}

元素访问（Element access）

operator [ ]

实现const和非const两种，只读和可读可改
充分利用字符串特性可以进行下标的访问

T& operator[](size_t pos)
{
    assert(pos >= 0 && pos < size());

    return _start[pos];
}

const T& operator[](size_t pos)const
{
    assert(pos >= 0 && pos < size());

    return _start[pos];
}

迭代器（iterator）

本质还是指针，直接进行指针的返回就好

//iterator
const_iterator cbegin()
{
    return _finish;
}

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

源码

#include <string.h>
#include <assert.h>
#include <iostream>

namespace MyVector
{
  template <class T>
  class vector
  {
  public:

    //iterator
    const_iterator cbegin()
    {
      return _finish;
    }

    const_iterator cend() const
    {
      return _start;
    }
    iterator begin()
    {
      return _start;
    }
    iterator end()
    {
      return _finish;
    }
    const_iterator begin()const
    {
      return _start;
    }
    const_iterator end()const
    {
      return _finish;
    }
    //默认构造
    vector()
      :_start(nullptr)
      , _finish(nullptr)
      , _end_of_storage(nullptr)
    {}
    vector(size_t n, const T& val = T())
    {
      resize(n, val);
    }
    ~vector()
    {
      if (_start)
      {
        
        delete[] _start;
        _start = _finish = _end_of_storage = nullptr;
      }

    }
    vector(const vector<T>& v)
    {

      _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();

    }


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

    template<class InputIterator>

    vector(InputIterator first, InputIterator last)
    {
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }
    vector<T> operator=(vector<T> v)
    {
      swap(v);
      return *this;
    }



    //capacity
    void reserve(size_t n)
    {
      if (n > capacity())
      {

        std::cout << "reserve(size_t n)" << std::endl;
        T* tmp = new T[n];
        size_t sz = size();
        if (_start)
        {
          //memcpy(tmp, _start, sizeof(T)*capacity());
          //string 类深拷贝
          for (int i = 0; i < sz; i++)
          {
            tmp [i] = _start[i];
          }
          delete[] _start;
        }

        _start = tmp;
        _finish = sz + _start;
        _end_of_storage = _start + n;
      }
    }


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


    size_t size()const 
    {
      return _finish - _start;
    }
    size_t capacity()const 
    {
      return _end_of_storage - _start;
    }

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

      *_finish = x;
      ++_finish;
    }

    void pop_back()
    {
      erase(end()-1);
    }
    void insert(iterator pos, const T& x)
    {
      assert(pos <= _finish && pos >= _start);

      if (_finish == _end_of_storage)
      {
        //防止迭代器失效
        size_t step = pos - _start;

        size_t newcapacity = capacity() == 0 ? 0 : capacity() * 2;
        reserve(newcapacity);
        //防止迭代器失效
        pos = _start + step;
      }

      iterator end = _finish - 1;
      while (end >= pos)
      {
        *(end + 1) = *end;
        ++end;
      }
      *pos = x;
      ++_finish;
            
            return pos;
    }

    void erase(iterator pos)
    {
      assert(pos <= _finish && pos >= _start);
      
      while (pos != _finish)
      {
        *pos = *(pos + 1);
        pos++;
      }

      --_finish;
            
            return pos;
    }

    void resize(size_t n, const T& val = T())
    {
      if (n < capacity())
      {
        _finish = n + _start;
      }
      else
      {
        reserve(n);
        while (_finish != _start + n)
        {
          *_finish = val;
          ++_finish;
        }
      }
    }
    
    T& operator[](size_t pos)
    {
      assert(pos >= 0 && pos < size());

      return _start[pos];
    }

    const T& operator[](size_t pos)const
    {
      assert(pos >= 0 && pos < size());

      return _start[pos];
    }

  private:

    iterator _start;
    iterator _finish;
    iterator _end_of_storage;
  };

}

【C++】vector介绍以及模拟实现（超级详细）

前言

vector介绍

vector常见操作

构造函数

iterator

capacity

modify

`vector`模拟实现

存储结构

默认构造函数

构造函数

拷贝构造函数

赋值运算符重载

析构函数

容量（capacity）

`size`和`capzcity`

reserve

resize

修改（modify）

push_back

pop_back

insert

erase

元素访问（Element access）

operator [ ]

迭代器（iterator）

源码

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

【C++】vector介绍以及模拟实现（超级详细）

前言

vector介绍

vector常见操作

构造函数

iterator

capacity

modify

vector模拟实现

存储结构

默认构造函数

构造函数

拷贝构造函数

赋值运算符重载

析构函数

容量（capacity）

size和capzcity

reserve

resize

修改（modify）

push_back

pop_back

insert

erase

元素访问（Element access）

operator [ ]

迭代器（iterator）

源码

热门文章

最新文章

相关课程

相关电子书

`vector`模拟实现

`size`和`capzcity`