【C++】C++ STL探索:Vector使用与背后底层逻辑（一）-阿里云开发者社区

前文:vector介绍

vector是表示可变大小数组的序列容器，底层是动态开辟顺序表

vector插入新数据发生扩容，其做法是，分配一个新的数组，然后将全部元素移动到这个数组(单论时间，需要付出相对代价很高).每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小(不清楚这块空间剩余多少内存)

vector分配空间策略:vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大，不同的库采用不同的策略权衡空间的使用和重新分配。重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的

与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更

一、模拟实现Vector准备工作

在模拟实现vector过程中，为了避免跟库中vector发生冲突，需要创建个命名空间，在命名空间中实现vector。需要选择现实vector类模板去用于不同的类型(内置类型、自定义类型)

namespace vec
{
  template<class T>
  class vector
  {
  };
}

1.1 vector的成员对象

适用于不同类型的操作，可以通过模板参数列表的类型指针，去对不同类型进行访问和修改。

template<class T>
    class vector
    {
        public:
        typedef T* iterator;
        typedef const T* const_iterator;
        private:
        iterator _start = nullptr;
        iterator _finish = nullptr;
        iterator _end_of_storage = nullptr;
    };

成员说明:

typedef T* iteratror:采用原生指针去模拟迭代器(不是真正的迭代器)

_start：指向空间的第一个位置

_finish：指向最后有效数据的位置

_end_of _storage：指向空间的最后一个位置

1.2 原生指针模拟迭代器

template<class T>
  class vector
  {
  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;
    }
        
  private:
    iterator _start = nullptr;
    iterator _finish = nullptr;
    iterator _end_of_storage = nullptr;
  };

二、正式模拟实现Vector

2.1 构造函数

具体说明：allocator_type是内存配置器（内存池）和explicit这个阶段都不用去理会它。最经常使用是接口(1)和(4)，其中(1)就当作是无参的构造，不用传什么值，就使用它的缺省值()

value_type()是模板参数列表实例化转化的T类型

2.1.1 无参构造

vector()
    {}

这里就算不显式写无参构造，编译器也会自动生成。从某种意义上无参构造不用写，但是我们需要实现拷贝构造，编译器就不会默认生成无参构造函数了。总之要显式写无参构造函数。

2.1.2 vector迭代区间构造

类模板的成员函数可以是函数模板

template<class InputIterator>
    vector(InputIterator fist, InputIterator last)
{
    while (fist != last)
    {
        push_back(*fist);
        ++fist;
    }
}

使用场景：

vector<int> v2(v1.begin()+1, v1.end()-1);
print_vector(v2);
string str("abcd");
vector<int> v3(str.begin(), str.end());
print_vector(v3);

具体说明：在使用该接口时，需要注意不可以(--v1.begin(), --v1.end()使用。这里begin()和end()函数是传值返回，返回临时对象具有常性，不能通过++或–修改临时对象

2.1.3 初始化构造

vector(size_t n, const T* val = T())
{
    reserve(n);
    for (size_t i = 0; i < n; i++)
    {
        push_back(val);
    }
}

这段初始化构造逻辑是没有问题的，但是在调用过程可能会出现问题

首先给出三组数据，去使用初始化构造函数
    vector<int> v1(10, 1);
    print_vector(v1);
    vector<int> v2(10u, 1);
    print_vector(v2);
    vector<int> v3(10, 'a');
    print_vector(v3);

具体说明：在调用过程中会报出非法的间接寻址错误，原因在于第一个实例化(就这个比较特别)，调用的是函数模板，这里*first就会报错，想走捷径，发现掉坑里面。

vector v1(10, 1)参数部分都是整型类型，如果使用下面的初始化构造，需要int转化为size_t（发生隐式类型转化）。对于模板初始化函数而言，自动推导类型，对此上面更加匹配(那就报错哦)
vector v2(10u, 1)参数部分都是无符号整数，有现成吃现成，就是调用第二个
vector v3(10, 'a')参数部分是不同类型，自然调不动第一个函数，调用第二个函数，进行类型转化

解决措施：实现函数重载，特殊情况特殊处理

vector(size_t n, const T* val = T())
{
    reserve(n);
    for (size_t i = 0; i < n; i++)
    {
        push_back(val);
    }
}
vector(int n, const T& val = T())
{
    reserve(n);
    for (int i = 0; i < n; i++)
    {
        push_back(val);
    }
}

2.2 拷贝构造

vector(const vector<T>& v)
{
    //需要开一样大的空间
    reserve(v.capacity());
    for (auto& e : v)
    {
        push_back(e);
    }
}

具体说明:这里可以采用string类拷贝构造方式，但是这个更加简洁。auto自动识别类型建议加&，如果T是自定义类型，就需要调用多次拷贝构造(深拷贝)

2.3 初始化列表

auto x = { 1,2,3,4,5,6 };
cout << typeid(x).name() << endl;
cout << sizeof(x) << endl;
输出结果:
class std::initializer_list<int>

当我们想实现像数组nums[5] = {12,3,4,5}这样初始化，库提供初始化列表initializer_list的方式满足了我们的需求。

其中vector类也包含了这种方式

initializer_list y = {1,2,3,4,5};

vector x = {1,2,3,4,5};

通过类模板在vector类中实现该功能

vector(initializer_list<T> il)
{
    reserve(il.size());
    for (auto& e : il)
    {
        push_back(e);
    }
}

2.4 析构函数

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

2.5 operator[] 下标访问

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

具体说明：

下标加方括号仅限于物理逻辑连续的容器，比如:string、vector、list之类。

针对对象是否被const修饰，需要重载两个函数(可读可写，可读不可写)。使用引用返回，可以修改到实参和提高效率

2.6 swap 交换函数

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

2.7 operator= 赋值运算符重载

//v2 = v1;
    vector<T>& operator=(vector<T> v)
    {
        swap(v);
        return *this;
    }

说明：跟string是同一套流程，这里就直接选用优化现代写法版本

2.8 得到当前元素空间信息

2.8.1 size(有效元素个数)

size_t size() const
{
    //指针 - 指针
    return _finish - _start;
}

2.8.2 capacity(当前空间容量)

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

说明:

size是有效元素的个数，capacity是当前空间的容量

都是通过指针-指针得到的大小

2.9 reserve

2.9.1 第一版本:野指针问题

void reserve(size_t n)
{
    if (n > capacity())
    {
        T* tmp = new T[n];
        memcpy(tmp, _start, size(T) * n);
        delete[] _start;
        _start = tmp;
        _finish =  tmp + size();
        _end_of_storage =  tmp + n;
    }
}

不足之处:迭代器失效的问题，出现野指针_finish指向错误。在delete[] _start的时候，finish还在指向旧空间，导致调用size()得到数据错误。

解决办法:在销毁旧空间之前，提前保留size()的大小

void reserve(size_t n)
{
    if (n > capacity)
    {
        T& tmp = new T[n];
        size_t size = size();
        memcpy(tmp, _statr, sizeof(T) * n);
        delete[] _start;
        _start = tmp;
        _finish = tmp + size;
        _end_of_storage = tmp + n;
    }
}

2.9.2 第二版本：浅拷贝问题

问题说明:这里memcpy是逐字节拷贝，属于浅拷贝。当T为自定义类型，使用memcpy进行浅拷贝操作，会指向同一块空间。

_str指向的空间没有拷贝，导致指向同一块空间，调用析构函数会造成野指针问题。

解决办法:

void reserve(size_t n)
{
    if (n > capacity())
    {
        size_t old_size = size();
        T* tmp = new T[n];
        //memcpy(tmp, _start, size(T) * n);
        for (size_t i = 0; i < old_size; i++)
        {
            //自定义类型会赋值运算符重载
            tmp[i] = _start[i];
        }
        delete[] _start;
        _start = tmp;
        _finish = tmp + old_size;
        _end_of_storage = tmp +n ;
    }
}

这属于一种更加暴力的解法，直接将_start里面的数据拷贝过来

【C++】C++ STL探索:Vector使用与背后底层逻辑（二）https://developer.aliyun.com/article/1617342

【C++】C++ STL探索:Vector使用与背后底层逻辑（一）