STL_vector源码剖析

STL vector

STL2.91源码地址: https://github.com/lewischeng-ms/sgi-stl
侯捷老师用的是 2.91,不同版本的STL差异很大，靠后版本的STL用了太多typedef以及继承关系，导致可读性很差。
本文参考博客: https://blog.csdn.net/weixin_45389639/article/details/121618243

vector 源码

// vector源码
template<class T,class Alloc=alloc>
class vector
{
public:
	typedef T value_type;
	typedef value_type* iterator;
	typedef value_type& reference;
	typedef size_t size_type;
protected:
	iterator start;
	iterator finish;
	iterator end_of_storage;
public:
	iterator begin(){return start;}
	iterator end(){return finish;}
	size_type size()const{return (size_type)end_of_storage-begin();}
	bool empty()const{return begin()==end();}
	reference operator[](size_type n){
		return *(begin()+n);
	}
	reference front(){return *begin();}
	reference back(){return *(end()-1);}
    ...
};

vector源码分析

vector中定义了三个指针： start 、finish 、 end_of_storage
sizeof(vector)：三个指针的大小
在这里插入图片描述

vector扩容:空间两倍增长

vector容器的迭代器start指向第一个元素，finish指向最后一个元素的下一个元素，满足了前闭后开特性,end_of_storage是vector的容量。vector在使用上是连续的，在实现上也是连续的，所以迭代器采用non-class类型。

// vector源码
template<class T,class Alloc=alloc>
class vector
{
public:
	typedef T value_type;
	typedef value_type* iterator;
	typedef value_type& reference;
	typedef size_t size_type;
protected:
	iterator start;
	iterator finish;
	iterator end_of_storage;
public:
	iterator begin(){return start;}
	iterator end(){return finish;}
	size_type size()const{return (size_type)end_of_storage-begin();}
	bool empty()const{return begin()==end();}
	reference operator[](size_type n){
		return *(begin()+n);
	}
	reference front(){return *begin();}
	reference back(){return *(end()-1);}
    ...
};

vector.push_back()的方法，首先会判断end_of_storage是不是满了，满了的话就会扩容2倍再进行添加元素。注意：扩充的过程重并不是在原有空间后面追加容量，而是重新申请一块连续的内存空间，将原有的数据拷贝到新空间中，再释放原来空间中内存。所以扩充之后，原有的迭代器将会失效！

  void push_back(const T& x) {
    if (finish != end_of_storage) {
      construct(finish, x);
      ++finish;
    }
    else
      insert_aux(end(), x);
  }

insert_aux是vector容器用来在内部任意位置插入元素，内存不足的情况下会扩容。

template<class T, class Alloc>
void vector<T, Alloc>::insert_ux(iterator position, const T &x) {
    if (finish != end_of_storage) {     // 尚有备用空间,则将插入点后元素后移一位并插入元素
        construct(finish, *(finish - 1));   // 以vector最后一个元素值为新节点的初值
        ++finish;
        T x_copy = x;
        copy_backward(position, finish - 2, finish - 1);
        *position = x_copy;
    } else {
        // 已无备用空间,则先扩容,再插入
        const size_type old_size = size();
        const size_type len = old_size != 0 ?: 2 * old_size:1;  // 扩容后长度为原长度的两倍

        iterator new_start = data_allocator::allocate(len);
        iterator new_finish = new_start;
        try {
            new_finish = uninitialized_copy(start, position, new_start);    // 拷贝插入点前的元素
            construct(new_finish, x);                                       // 插入新元素并调整水位
            ++new_finish;
            //这个辅助还是不止被push_back调用，其他函数(insert)也会调用。 insert插入需要扩充数据，会有安插点之前和安插点之后
            //需要将安插点之后的元素也拷贝过来
            new_finish = uninitialized_copy(position, finish, new_finish);  // 拷贝插入点后的元素
        }
        catch (...) {
            // 插入失败则回滚,释放内存并抛出错误
            destroy(new_start, new_finish) :
            data_allocator::deallocate(new_start, len);
            throw;
        }
        // 释放原容器所占内存
        destroy(begin(), end());
        deallocate();
        // 调整迭代器
        start = new_start;
        finish = new_finish;
        end_of_storage = new_start + len;
    }
};

vector迭代器

列表的迭代器设置为class，因为列表的节点都是分离的
vector用指针就可以当作迭代器

class vector {
public:
  typedef T value_type;
  typedef const value_type* const_pointer;
  typedef value_type* iterator;
  };
  -------------------------------------------------
  //使用迭代器
  vector<int> vec;
  vecto<int>::iterator it = vec.begin();