STL源码剖析学习笔记——vector-创新互联

vector 一、前言

《STL源码剖析》学习到了容器，实现的成员函数顿时多了起来，生硬的列出来不太适合把握细节，也不方便自己以后复习，于是决定从测试代码出发，自顶向下，从元素的操作一路下探到内存分配。

创新互联建站一直秉承“诚信做人，踏实做事”的原则，不欺瞒客户，是我们最起码的底线！ 以服务为基础，以质量求生存，以技术求发展，成交一个客户多一个朋友！为您提供成都网站制作、成都做网站、成都网页设计、小程序开发、成都网站开发、成都网站制作、成都软件开发、APP应用开发是成都本地专业的网站建设和网站设计公司，等你一起来见证！二、测试代码纵览 2.1 自定义数据结构

using std::string;
using std::cout;
using std::endl;
using tinystl::vector;

class Person{public:
    Person() = default;
    Person(string& name, int age):m_Age(age), m_Name(name) {}
    Person(const char* name, int age):m_Age(age), m_Name(name) {}
    ~Person()= default;
    friend std::ostream& operator<<(std::ostream& os, const Person& p);
    string m_Name;
    int m_Age{};
};

std::ostream& operator<<(std::ostream& os, const Person& p) {os<< p.m_Name<< ' '<< p.m_Age;
    return os;
}

这部分没什么特别的，只是想确认咱这个粗制滥造的vector不只能存内置类型的数据，整了个Person类，只有m_Name和m_Age两个成员变量，然后全局重载了流运算符方便打印。

2.2 测试内容

1、构造：constructor

2、插入：push_back、insert

3、读取：operator[]、front、back

4、删除：erase、clear

5、改变大小：resize

下面进入正题！！！

三、故事从5个Person对象开始 3.1 构造、内存分配

vectorpv(5, Person("yzh", 22));
cout<< "size = "<< pv.size()<< ", "<< "capacity = "<< pv.capacity()<< endl;

这段代码首先创建了一个匿名Person对象，传入vector的构造函数中，要求它新建一个容器，并且存五个叫yzh的22岁哥们，接下来看构造函数干了啥。

vector(size_type n, const T &value) {fill_initialize(n, value); }

这里的size_type只是一个typedef，实际上是size_t，后者又是个typedef，不过这就不重要了，总之一般就是个unsigned long类型。在vector中声明了数个typedef，后面还能遇到的。

可以看到由于vector有好几个构造函数，构造的方法大差不差，所以给封装进了一个fill_initialize函数。

//用于构造函数，初始化元素头尾和空间尾指针
void fill_initialize(size_type n, const T& value) {_start = allocate_and_fill(n, value);
    _finish = _start + n;
    _end_of_storage = _finish;
}

初始化的这三个东西是什么？往前面翻翻，哦原来是唯三的保护成员变量，类型是iterator迭代器，再往前找，iterator原来就是T*也就是原生指针类型。对于vector来说很合理，因为它是连续的、可以随机访问的空间，和指针没有任何区别，当然也支持指针所拥有的所有操作。

using iterator = T *;

iterator _start;
iterator _finish;
iterator _end_of_storage;

此时就搞清楚这个fill_initialize在干什么了，通过allocate_and_fill分配5个Person对象的空间并且填入元素，这个函数指定是返回了分配空间的首地址，正好接过来初始化首指针。尾指针finish不难理解，关键是这个end_of_storage是干啥的？现在我只能根据变量名猜测它指示了分配的空间的最后位置，具体为什么是这样还得继续往后执行看。

知道了vector是如何初始化的，我希望继续深入认识到底容器中的内存分配和对象的构造是怎么设计的，于是兴趣转向这个allocate_and_fill函数。

iterator allocate_and_fill(size_type n, const T& val) {//申请一片内存空间，并返回起始地址
    iterator start = data_allocator::allocate(n);
    tinystl::uninitialized_fill_n(start, n, val);
    return start;
}

这里的data_allocator::allocate(n)忠实的执行了一件事：分配内存。具体实现并不复杂，只是调用了全局的operator new申请了一片空间并返回首地址。uninitialized_fill_n(start, n, val)则将对象构造与内存分配区分开来，在已分配的空间上构造了n个元素，具体实现按下不表，如果有时间的话可以单独做一下笔记。

总而言之，经过这么一番折腾，一个vector容器终于构造完成，三个指针也指向了第一个元素、最后一个元素的后一个（前闭后开）、分配内存最后一个位置的后一个（目前和元素末尾指针指向一样）。下面回到最开始的测试代码。

vectorpv(5, Person("yzh", 22));
cout<< "size = "<< pv.size()<< ", "<< "capacity = "<< pv.capacity()<< endl;

初始化完成，让我们看看现在容器的大小吧。

pv.size()返回的是已经填入元素的个数，pv.capacity()返回的是总的分配空间的大小，也就是容器的“容量”。不难想象实现其实就是首尾指针相减，只是一个是用finish减start，一个是用end_of_storage。

非常好，和预想的一样，可以进入下一步了，也是重头戏，揭开了vector动态增长的奥秘。

3.2 插入、空间再分配

本节的主角是这样一行代码：

pv.push_back(Person("wqy", 100));

我想要将一个百岁老头的信息插入到元素的最后一个位置。之前说过end_of_storage指示已分配空间的最后一个位置，那如果还有多余的空位那就好办了，直接在上面构造出来这个新来的哥们就行了。

templatevoid vector::push_back(const T &val) {if (_finish != _end_of_storage) {tinystl::construct(_finish, val);
        ++_finish;
    } else {//如果当前已经申请到的空间不足以放下新的元素了，执行这个函数
        insert_aux(end(), val);
    }
}

空间不够了怎么办？不急，执行一个辅助函数实现传说中的搬家。

templatevoid vector::insert_aux(vector::iterator position, const T &x) {if(_finish != _end_of_storage) {//这函数不只给push_back用，这里还得判断
        //在最后一个元素的后一个位置构造一个最后元素
        tinystl::construct(_finish, *(_finish - 1));
        ++_finish;
        //细节，必须要确保存储下来的是元素的一个副本,不然以后修改容器里面的值影响容器外面岂不是乱套
        T x_copy = x;
        //position后面整体右移
        std::copy_backward(position, _finish - 2, _finish - 1);
        *position = x_copy;
    }
    else {const size_type old_size = size();
        //如果原空间为0，新空间为1，否则为两倍的原空间
        //注意这里的新空间指的是分配的内存，跟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 {//别忘了uninitialized系列主打的是构造与内存分配的分离～
            //首先把插入位置之前的对象拷贝到新位置去
            new_finish = tinystl::uninitialized_copy(_start, position, new_start);
            //构造插入对象
            tinystl::construct(new_finish, x);
            ++new_finish;
            //继续把插入位置后面的拷贝到新位置去，接在插入对象后面
            new_finish = tinystl::uninitialized_copy(position, _finish, new_finish);
        }
        catch (...) {//要么做完，要么一个别做！
            tinystl::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;
    }
}
}

关键点都写在了注释中，总而言之思路就是之前分配的空间用完了，那么我只能去别处在申请一片更大的空间（原来的地方肯定不能直接在屁股后面申请了，谁都没法保证后面还有没有空间）。那么申请多少？现在用了多少，以后很有可能也会用多少，所以整个两倍大的空间（个人理解）。最后举家搬迁，完成这次增长。不难看出这个操作一套下来需要消耗大量的资源和时间，如果频繁搬家会导致效率极低。

有三个细节我容易忽视：

1、x_copy：容器存的是副本，可别把传入的引用存进去了

2、commit-rollback语义：如果发生异常，不能直接终止吧，很多时候罪不至死；更不能卡一半直接返回吧，用户直接摸不清头脑你到底走到哪一步，所以要么做完，要么回退到执行前的状态，你好我好大家好～

3、copy_backward：往后拷贝的时候，可能会因为复制位置的起始点处于原来的区间内而导致出现覆盖的问题导致实际效果和期待的不一样，还是看看cppreference的官方解释吧：

Copies all elements in the range[first, last)starting from first and proceeding to last - 1. The behavior is undefined ifd_firstis within the range[first, last). In this case, std::copy_backward may be used instead.

最后看看size和capacity的变化（上面的是之前的，下面的是这插入结束后的），和预想一样，容量翻倍，size加一。下一位！

3.3 元素访问

中场休息放松一下。

pv[0].m_Name = "ywt";
cout<< "front = "<< pv.front()<< ' '<< "back = "<< pv.back()<< endl;

元素的访问可以说毫无技术含量。尤其是对于随机访问迭代器来说，有了首尾指针和偏移量可以轻松返回我想要的任意位置的元素，不多说直接上代码吧。

//提取特定位置的元素
reference front() {return *_start; }
reference back() {return *(_finish - 1); }
reference operator[](size_type n) {return *(begin() + n); }

其中需要注意的大概只有前闭后开的问题了，finish那个位置是一片“虚空”，真正的最后一个元素在前一位，别越界哦！（无论是程序或生活中）

3.4 如果我想任意插入呢？

push_back实现了在末尾插入一个元素，确实已经可以覆盖实际使用中大部分插入场景了，但在中间插入任意个元素的操作还是难以避免的，怎么实现呢？老规矩先上测试代码。

auto itr = pv.begin() + 2;
auto itr2 = pv.insert(itr, 1, Person("nxl", 3));
cout<< *itr2<< endl;

首先很重要的一点，STL规定插入的元素必须插在指定位置的前一个，咱们模仿也得讲规矩是吧～

看传参，一个迭代器，一个数，一个临时对象。得，猜也猜得到是在迭代器指定的位置插入n个对象呗，让我们来看具体实现吧。

templatetypename vector::iterator vector::insert(vector::iterator pos, vector::size_type n, const T &val) {if(n == 0) return pos;
    //用来定位插入元素的第一位
    const difference_type offset = pos - begin();
    if(static_cast(_end_of_storage - _finish) >= n) {//情况1：备用的空间大于待插入元素个数
        T val_copy = val;
        //插入位置后面有多少元素
        const size_type elems_after = _finish - pos;
        iterator old_finish = _finish;
        //如果后面的元素比要插入的多，意味着需要构造的只有原来的元素
        if(elems_after >n) {//空出n个位置，那么后n个需要构造
            tinystl::uninitialized_copy(_finish - n, _finish, _finish);
            _finish += n;
            //把剩下的后移n位，注意第三个参数的含义！！
            //first, last  -  the range of the elements to copy from
            //d_last   -  the end of the destination range
            std::copy_backward(pos, old_finish - n, old_finish);
            //空出来的填元素就可以了
            std::fill(pos, pos + n, val_copy);
        }
        //如果插入位置后面的元素比插入的少，意味着后面的元素要全部前往未构造区域，同时会有插入元素需要构造
        else {//想象一下后面元素搬迁后的场景，中间会有一些没构造的区域，先给他干上去一部分插入元素
            tinystl::uninitialized_fill_n(_finish, n - elems_after, val_copy);
            _finish += n - elems_after;
            //随后开始大迁徙
            tinystl::uninitialized_copy(pos, old_finish, _finish);
            _finish += elems_after;
            //最后鸠占鹊巢
            std::fill(pos, old_finish, val_copy);
        }
    }
    else {//情况2：备用的空间不够插了
        const size_type old_size = size();
        //如果需要的新空间比老空间还多，那就需要更大的空间正好装下，否则还是两倍的原空间
        //注意这里的新空间指的是分配的内存，跟size()没关系
        const size_type len = old_size + std::max(old_size, n);
        iterator new_start = data_allocator::allocate(len);
        iterator new_finish = new_start;
        try {//别忘了uninitialized系列主打的是构造与内存分配的分离～
            //首先把插入位置之前的对象拷贝到新位置去
            new_finish = tinystl::uninitialized_copy(_start, pos, new_start);
            //构造插入对象
            new_finish = uninitialized_fill_n(new_finish, n, val);
            //继续把插入位置后面的拷贝到新位置去，接在插入对象后面
            new_finish = tinystl::uninitialized_copy(pos, _finish, new_finish);
        }
        catch (...) {//要么做完，要么一个别做！
            tinystl::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;
    }
    return begin() + offset;
}

注：其中，全局函数destroy实现了对象的析构，deallocate调用allocator::deallocate()实现了内存空间的回收，继续坚持分离构造与空间分配，把操作的粒度细化以满足各种各样的需求。

代码很长，但是空间不足的部分和之前的insert_aux是几乎重复的，无非是从插入一个变成插入许多，所以其实应该包装起来的，偷懒了。

空间足够的时候需要充分发挥一波空间想象力（或者直接画画图），到底备用空间和插入元素个数的大小比较会带来什么样的影响，换句话说，什么情况下在插入时待插入的元素有一部分会踏入“虚空（备用的未构造空间）”？想通了代码就很好理解了。

最后打印一下返回的迭代器指向哪，验证一下返回的确实是插入元素的第一个位置。这又牵扯到一个迭代器失效的问题了，也就是当insert发生后，插入位置后面的所有早先定义的迭代器都不能再用了，强行使用很有可能不是我想要的效果，好在有了这个确定无疑的返回值，又可以愉快的玩耍了哈哈。（后面erase也有同样的问题，不再赘述）

3.5 删除

快结束喽！有插入就有删除，上代码！

pv.pop_back();
cout<< "after pop: back = "<< *(pv.end() - 1)<< endl;

首先是pop_back()弹出末尾元素。其实就是删掉最后一个嘛，简单，尾指针向前一位，析构掉这个位置的对象，完事！实现如下：

void pop_back() {--_finish;
    tinystl::destroy(_finish);
}

erase则略微复杂一点点，有两个重载，一个删除指定位置的一个元素，一个删除指定区间内的所有元素

pv.erase(pv.end() - 2, pv.end() - 1);
pv.erase(pv.end() - 3);

在删除前让我们再见一见所有的元素们，马上就要分别之时了，别忘了wqy已经被弹出去了。

templatetypename vector::iterator vector::erase(vector::iterator first, vector::iterator last) {//把删除元素区间后面的所有元素前移一位，覆盖掉删除元素（至少覆盖一部分）
    // 返回复制元素末尾的后一个位置
    iterator it = std::copy(last, _finish, first);
    //细节，虽然不知道it在前还是last在前，但我能确定的是从it开始到finish的一定都不要
    tinystl::destroy(it, _finish);
    //删掉多少finish前移多少
    _finish = _finish - (last - first);
    //返回删掉元素的后一个位置
    return first;
}

templatetypename vector::iterator vector::erase(vector::iterator pos) {if (pos + 1 != end()) {//把pos后面的都复制到pos的位置来
        std::copy(pos + 1, _finish, pos);
    }
    --_finish;
    data_allocator::destroy(_finish);
    //原来的迭代器会失效，不要erase(iter++)，大概率不是咱想要的效果
    return pos;
}

经历了insert的洗礼，理解erase的实现过程基本不成问题了，还就是那个移动元素+析构，似乎没有特别的坑，注释应该足够详细了，过！

3.6 修改元素个数

最后一站，学习resize()，上代码

cout<< "size = "<< pv.size()<< ", "<< "capacity = "<< pv.capacity()<< endl;
if(!pv.empty()) cout<< "not empty"<< endl;
else cout<< "empty"<< endl;

经过前面一顿折腾，掐指一算容器里面还剩4个元素。

empty函数不多说，检查一下首尾指针是否相等即可。

bool empty() {return begin() == end(); }

接下来开始resize，并打印一下信息

pv.resize(20, Person("null", 1000));
cout<< "size = "<< pv.size()<< ", "<< "capacity = "<< pv.capacity()<< endl;
for(const auto& n : pv) {cout<< n.m_Name<< ' ';
}
cout<< endl;

resize也有两个重载，主要应对扩大的时候我还想给变大的空间初始化的场景，代码如下：

void resize(size_type new_size, const T& val) {if(new_size< size())
        erase(begin() + new_size, end());
    else
        insert(end(), new_size - size(), val);
}
void resize(size_type new_size){resize(new_size, T());
}

如果新大小更大的话，应该发生的是插入操作，否则是删除操作。插入的情况下，插入的元素如果没有指定的话就直接默认构造。全都是封装好的函数了，写的人舒服看的人也舒服～打印一下信息，再试试缩小

pv.resize(3);
cout<< "size = "<< pv.size()<< ", "<< "capacity = "<< pv.capacity()<< endl;

最后试试清空，有了区间erase，还怕不会清空？

pv.clear();
cout<< "size = "<< pv.size()<< ", "<< "capacity = "<< pv.capacity()<< endl;
if(!pv.empty()) cout<< "not empty"<< endl;
else cout<< "empty"<< endl;

void clear() {erase(begin(), end());}//清空容器

上效果！！

四、后记

芜湖，vector的学习笔记终于结束啦，现如今C++慢慢发育起来STL也是日新月异了，这个基于GNU2.9的tinystl实现肯定是显得久远了。不过没关系，以后有机会再拜读新的源码，尤其是C++11、17带来的那些新东西，很多都还用不明白，离吃透还早呢。。。不管怎么说，我已经彻底爱上这个语言了，list再见！！

哦对了，如果小弟有幸能被大佬看到这篇笔记，希望可以指点出我的错误，毕竟自学，有时候感觉挺怕走了弯路还不自知的，，太感谢了！！

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章名称：STL源码剖析学习笔记——vector-创新互联
网页地址：http://cqcxhl.cn/article/iceod.html