【C++】：STL源码剖析之vector类容器的底层模拟实现

1.vector接口总览

namespace lyp

{

//模拟实现vector

template

class vector

{

public:

typedef T* iterator;

typedef const T* const_iterator;

//默认成员函数

vector(); //构造函数

vector(size_t n, const T& val); //构造函数

template

vector(InputIterator first, InputIterator last); //构造函数

vector(const vector& v); //拷贝构造函数

vector& operator=(const vector& v); //赋值运算符重载函数

~vector(); //析构函数

//iterator

iterator begin();

iterator end();

const_iterator begin()const;

const_iterator end()const;

//capacity

size_t size()const;

size_t capacity()const;

void reserve(size_t n);

void resize(size_t n, const T& val = T());

bool empty()const;

//modifiers

void push_back(const T& x);

void pop_back();

void insert(iterator pos, const T& x);

iterator erase(iterator pos);

void swap(vector& v);

//access

T& operator[](size_t i);

const T& operator[](size_t i)const;

private:

iterator _start; //指向容器的头

iterator _finish; //指向有效数据的尾

iterator _endofstorage; //指向容器的尾

};

}

2.vector模拟实现

构造函数

构造一个空vector size和capacity为0 将_start _finish _endofstorage 都置为空指针即可

vector()

:_start(nullptr)

,_finish(nullptr)

,_endofstorage(nullptr)

{}

拷贝构造函数

/*vector(const vector& v)

{

_start = new T[v.capacity()];

memcpy(_start, v._start, v.size()* sizeof(T));

_finish = _start + v.size();

_endofstorage = _start + v.capacity();

}*/

// v2(v1)

vector(const vector& v)

{

reserve(v.capacity());

for (const auto& e : v)

{

push_back(e);

}

}

void swap(vector& v)

{

std::swap(_start, v._start);

std::swap(_finish, v._finish);

std::swap(_endofstorage, v._endofstorage);

}

// v1 = v3

vector& operator=(vector v)

{

swap(v);

return *this;

}

传统写法 : 1). 新开辟一块和 v 同样容量的空间，更新 _start， _finish， _endofstorage 2). 将 v 中的数据拷贝到新开辟的空间中 注意 : 不要使用memcpy函数拷贝数据，如果数据是内置类型或浅拷贝的自定义类型，使用memcpy是没有什么问题的，但如果数据是需要深拷贝的自定义类型(string)，问题就出现了，拷贝的数据和源数据指向同一块空间 现代写法 : 使用范围for进行遍历，变量e是v中元素的拷贝，如果v中元素是需要深拷贝的自定义类型，会调用拷贝构造函数构造e，从而使e和v中元素所指向的空间不一样 (auto& e : v 也可以，因为push_back在实现的时候还会调用深拷贝类型的赋值运算符重载)

void push_back(const T& x)

{

if (_finish == _endofstorage)

{

size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;

reserve(newcapacity);

}

*_finish = x;

++_finish;

}

赋值运算符重载

传统写法 1).释放原空间，新开一块容量和v一样大的空间，更新_start，_finish， _endofstorage 2).将v中的数据拷贝到新空间中 注意 : 不能使用memcpy进行拷贝 现代写法 1).调用拷贝构造函数生成tmp对象 2).分别交换tmp和this的_start，_finish， _endofstorage

void swap(vector& v)

{

std::swap(_start, v._start);

std::swap(_finish, v._finish);

std::swap(_endofstorage, v._endofstorage);

}

// v1 = v3

vector& operator=(vector v)

{

swap(v);

return *this;

}

析构函数

1). 判断容器是否为空，若为空无需析构 2). 若不为空，将空间释放掉，_start，_finish， _endofstorage置为空指针

~vector()

{

if (_start)

{

delete[] _start;

_start = _finish = _endofstorage = nullptr;

}

}

iterator

begin/end begin()返回第一个元素的地址，end()返回最后一个元素下一位置的地址，为了能够让const对象调用，加入const版本的begin()和end() iterator begin()

iterator begin()

{

return _start;

}

iterator end()

{

return _finish;

}

const_iterator begin() const

{

return _start;

}

const_iterator end() const

{

return _finish;

}

size

返回容器中有效数据的个数，用 _finish - _start 即可

size_t size()const

{

return _finish - _start;

}

capacity

返回容器的容量，用_endofstorage - _start 即可

size_t capacity()const

{

return _endofstorage - _start;

}

reserve

1). 当n大于对象当前的capacity时，将capacity扩大到n或大于n。 2). 当n小于对象当前的capacity时，什么也不做。

实现步骤 1). 新开辟一块空间，若容器为空，将_start，_finish指向新开辟空间的首元素地址， _endofstorage指向新开辟空间的最后一个元素下一个位置 2). 若容器不为空，将数据拷贝到新空间，释放掉旧空间，更新_start，_finish， _endofstorage的位置

注意 : 将数据拷贝到新空间，仍然不能用memcpy函数，因为对于需要深拷贝的自定义类型，使用memcpy函数以后，新开辟空间里的元素和原空间里的元素所指向的内存空间是一样的，当旧空间被释放时，会调用自定义类型的析构函数，从而使得新开辟空间里的元素指向的内存空间也被释放掉了

void reserve(size_t n)

{

if (n > capacity())

{

size_t old = size();

T* tmp = new T[n];

if (_start)

{

memcpy(tmp, _start, old * sizeof(T));

delete[] _start;

}

_start = tmp;

_finish = _start + old;

_endofstorage = _start + n;

}

}

resize

1). 当 n < size 时，直接将 _finish = _start + n (将有效数据长度缩小)即可 (2).当 size < n <= capacity 时，我们将有效数据的长度增加到 n，增加出来的有效数据内容是val (3).当 n > capacity时，先调用上面的 reserve 函数进行增容，再将有效数据的长度增加到 n，增加出来的有效数据内容是val

void resize(size_t n,const T& val = T())

{

// 第一种 n < size()

if (n < size())

{

_finish = _start + n;

}

// n > size()

else

{

// 增容

if (n > capacity())

reserve(n);

// 填充数据val

size_t count = n - size();

while (count--)

{

*_finish = val;

++_finish;

}

}

}

empty

判断 size() == 0 即可

bool empty()const

{

return size() == 0;

}

pop_back

尾删时，首先要判断容器是否为空，若为空，则断言报错，不为空，_finish-- 即可

void pop_back()

{

assert(size() > 0);

--_finish;

}

insert

1). 容量不够，先增容，增容之前先记录下 pos - _start 的值，否则增容之后，pos 还指向原来已经被释放的空间 2). 将 pos 位置往后的数据往后挪动一位，在pos位置插入值val

void insert(iterator pos, const T& x)

{

assert(pos >= _start && pos <= _finish);

if (_finish == _endofstorage)

{

size_t len = pos - _start;

reserve(capacity() == 0 ? 4 : capacity() * 2);

pos = _start + len;

}

memmove(pos + 1, pos, sizeof(T) * (_finish - pos));

*pos = x;

++_finish;

}

剩下两三个接口我们在下一篇博客和List类的底层模拟实现给大家补上

STL中的vector类源码简单剖析含小部分注释

vector的数据结构：一个线性连续空间 下面介绍vector的3个数据结构： start：表示目前使用空间的头 finish：表示目前使用空间的尾 end_of_storage：表示目前可用空间的尾

template

class vector {

...

protected:

iterator start; //表示目前使用空间的头

iterator finish; //表示目前使用空间的尾

iterator end_of_storage; //表示目前可用空间的尾

...

};

说明：为了降低空间配置时的速度成本，vector实际配置的大小可能比客户端需求量更大一些，以备将来可能的扩充。这便是容量的概念。也就是说，一个vector的容量永远大于或等于其大小。一旦容量等于大小，下次再新增元素时就需要新开辟一块空间。如下图所示 运用start、finish、end_of_storage三个迭代器，vector提供了首尾标示、大小、容量、空容器判断、注标[]运算符、最前端元素值、最后端元素值…等机能，如下：

template

class vector {

...

public:

iterator begin() { return start; }

iterator end() { return finish; }

size_type size() const { return size_type(end() - begin()); }

size_type capacity() 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的构造与内存管理（constructor、push_back）

template

class vector {

protected:

// simple_alloc<>见前面文章介绍

typedef simple_alloc data_allocator;

...

};

//构造函数，允许指定vector大小n和初值value

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

// 充填并予初始化

void fill_initialize(size_type n, const T& value) {

start = allocate_and_fill(n, value);

finish = start + n;

end_of_storage = finish;

}

// 配置而后充填

iterator allocate_and_fill(size_type n, const T& x) {

iterator result = data_allocator::allocate(n); //配置n个元素空间

uninitialized_fill_n(result, n, x); //全局函式，会根据第1个参数类型特性决定使用算法fill_n()或反复调用construct()来完成任务

return result;

}

push_back()函数：当我们以push_back() 将新元素安插入于vector尾端时，该函式首先检查是否还有备用空间，如果有就直接在备用空间上建构元素，并调整迭代器finish，使vector变大。如果没有备用空间了，就扩充空间（重新配置、搬移数据、释放原空间）。push_back()原型如下：

void push_back(const T& x) {

if (finish != end_of_storage) { //还有备用空间

construct(finish, x); //全局函式

++finish; //调整水位高度

}

else //已无备用空间

insert_aux(end(), x); // vector member function，见下

}

template

void vector::insert_aux(iterator position, const T& x) {

if (finish != end_of_storage) { //还有备用空间

// 在备用空间起始处建构一个元素，并以 vector 最后一个元素值为其初值。

construct(finish, *(finish - 1));

// 调整水位。

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

// 以上配置原则：如果原大小为0，则配置 1（个元素大小）

// 如果原大小不为 0，则配置原大小的两倍，

// 前半段用来放置原数据，后半段准备用来放置新数据

iterator new_start = data_allocator::allocate(len); // 实际配置

iterator new_finish = new_start;

try {

// 将原 vector 的内容拷贝到新vector

new_finish = uninitialized_copy(start, position, new_start);

// 为新元素设定初值 x

construct(new_finish, x);

// 调整水位

++new_finish;

// 将原vector的备用空间中的内容也忠实拷贝过来

new_finish = uninitialized_copy(position, finish, new_finish);

}

catch(...) {

// "commit or rollback" semantics.

destroy(new_start, new_finish);

data_allocator::deallocate(new_start, len);

throw;

}

//析构并释放原vector

destroy(begin(), end());

deallocate();

// 调整迭代器，指向新vector

vector start = new_start;

finish = new_finish;

end_of_storage = new_start + len;

}

}

源码就给大家分享这么多 源码不是我们要关注的 简单了解即可

推荐链接

 您阅读本篇文章共花了：