文章目录

vector的底层结构迭代器容量操作size()capacity()reserve()resize()

默认成员函数构造无参构造函数带参构造函数

析构拷贝构造赋值重载

operator[ ]插入删除操作insert()任意位置插入erase()任意位置删除push_back()尾插pop_back()尾删

vector的底层结构

我们的目的不是去模拟实现vector，而是更深入地理解vector的底层原理，更好地提升自己。本篇将简单地模拟实现vector，更好地理解它的构造和原理。参考：vector使用说明

在C++的STL中，vector是最常用的容器之一，底层是一段连续的线性内存空间（泛型的动态类型顺序表），可以支持随机访问。vector可以存储各种类型，int、char、string等，所以它是一种类模板，可以套用各种类型。

STL标准库中vector的核心是这样定义的，这里的alloc涉及到内存池的知识，我们可以先不用管。

vector的底层会用三个指针，利用三个指针相减来实现动态存储。

我们自己定义一个vector类

<code>template<class T>

class vector

{

public:

typedef T* iterator;//迭代器

typedef const T* const_iterator;//常量迭代器

private:

iterator _start;

iterator _finish;

iterator _end_of_storage;

}

---

迭代器

vector的迭代器是一个原生指针,他的迭代器和string相同都是操作指针来遍历数据。

迭代器返回的是存储数据的起始位置和末尾的下一个位置，区间是左开右闭的[_start, _finish)

实现了迭代器，我们在代码测试时就可以使用范围for了。

iterator begin()

{

return _start;

}

iterator end()

{

return _finish;

}

const_iterator begin() const

{

return _start;

}

const_iterator end() const

{

return _finish;

}

---

容量操作

size()

size_t size() const

{

return _finish - _start;

}

---

capacity()

size_t capacity() const

{

return _end_of_storage - _start;

}

---

reserve()

这个函数十分重要，因为vector许多地方都会用reserve()去扩容，并且还有几个非常容易搞错的地方。

reserve只能扩容，不能增容，因此要进行判断是否需要扩容，缩容就不进行操作。

扩容的步骤是：申请一块更大的新空间，再将旧空间数据移动到新空间中，最后释放旧空间。

下面这种写法有什么问题？

void reserve(size_t n)

{

if (n > capacity())

{

//申请新空间

T* tmp = new T[n];

if (_start)

{

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

//释放旧空间

delete[] _start;

}

_start = tmp;

_finish = tmp + size();

_end_of_storage = _start + n;

}

}

错误一：倒数第二行的_finish没有发生变化

看这段代码的最后三行，_start先指向新空间的起始位置，_finish再调用size()的话，此刻的size()已经不是当初的size()了。size()的返回值是_finish - _start，而原本的_start已经改变成了tmp，此时_finish的值 = _start + _finish - _start = _finish；所以_finish没有发生变化。

解决方法有两种：

1._start和_finish赋值的顺序调换一下，先改变_finish，再改变_start。

2.挪动数据前先保留原本的size()；

我们这里采用第二种写法。

void reserve(size_t n)

{

if (n > capacity())

{

T* tmp = new T[n];

size_t old_size = size();//保留之前的size

if (_start)

{

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

delete[] _start;

}

_start = tmp;

_finish = tmp + old_size;

_end_of_storage = _start + n;

}

}

2.不能用memcpy去拷贝内容，而用赋值去拷贝内容。

对于int、char等内置类型，可以使用memcpy不会出问题。对于自定义类型一般也没有问题，但是对于动态申请资源的自定义类型，memcpy就会发生浅拷贝，导致一块空间析构两次。

比如vector<string>类型，此时的T是string类型。上一篇我们了解过string的底层原理，string底层用的是char*指针_str来存储字符串的地址，因此需要动态申请空间。

所以我们是在申请的空间（_start）上面又申请了一块空间（_str），如果我们使用memcpy去拷贝_start中的内容到tmp中；就会把申请的_str指向的地址拷贝给tmp，这样_start和tmp中的_str就会指向同一块空间，再执行delete[] _start;的时候就会执行string的析构函数把这块空间释放。

所以不能用memcpy浅拷贝，解决方法：

一个个遍历用=赋值，对于string这种深拷贝的类，调用的是string的赋值重载完成深拷贝。

注意：这里的string使用的是STL库中的string类。

<code>void reserve(size_t n)

{

if (n > capacity())

{

T* tmp = new T[n];

size_t old_size = size();//保留之前的size

if (_start)

{

for (size_t i = 0; i < old_size; i++)

{

tmp[i] = _start[i];

}

delete[] _start;

}

_start = tmp;

_finish = tmp + old_size;

_end_of_storage = _start + n;

}

}

---

resize()

resize函数用于改变vector的大小，调整vector中元素的数量。

n > size()：多余空间添加元素（第二个参数）

n <= size()：删除n后面的元素。

void resize(size_t n, const T& val = T())//匿名对象

{

if (n <= size())

{

_finish = _start + n;

}

else

{

reserve(n);

while (_finish != _start + n)

{

*_finish++ = val;

}

}

}

---

默认成员函数

构造

无参构造函数

vector()

:_start(nullptr)

,_finish(nullptr)

,_end_of_storage(nullptr)

{ }

使用

vector<int> v1;

vector<string> s2;

带参构造函数

vector(size_t n, const T& val = T())

{

resize(n, val);

}

使用

vector<int> v1(10);//开辟5个int大小空间，默认初始化为0

vector<int> v2(10, 1);//开辟10个int大小空间，并初始化为1

vector<string> s2(10,"abc");//开辟10个string大小空间，并初始化为"abc"

---

析构

~vector()

{

if (_start)

{

delete[] _start;

_start = _finish = _end_of_storage = nullptr;

}

}

---

拷贝构造

写法一：尾插法

vector(const vector<T>& v)

: _start(nullptr)

, _finish(nullptr)

, _end_of_storage(nullptr)

{

reserve(v.size());

for (auto& e : v)//引用防止调用拷贝构造

{

push_back(e);

}

}

写法二：常规法

vector(const vector<T>& v)

: _start(nullptr)

, _finish(nullptr)

, _end_of_storage(nullptr)

{

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

for (size_t i = 0; i < v.size(); i++)

{

_start[i] = v._start[i];

}

_finish = _start + v.size();

_end_of_storage = _start + v.capacity();

}

---

赋值重载

和string一样，我们直接复用标准库的swap函数。

注意：用swap的话，拷贝构造的参数要用传值传递（不能改变实参），且不能用const修饰（发生交换）

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;

}

---

operator[ ]

两个重载版本，一个普通对象调用，一个const对象调用。

T& operator[](size_t pos)

{

assert(pos < size());

return _start[pos];

}

const T& operator[](size_t pos) const

{

assert(pos < size());

return _start[pos];

}

---

插入删除操作

insert()任意位置插入

插入之后，如果原始空间发生扩容，则pos指针仍指向原来空间的位置，迭代器就会发生失效。所以我们需要在扩容之前保存pos的相对位置，然后重新指向正确位置。

//insert后 迭代器可能会失效，扩容就会引起失效

iterator insert(iterator pos, const T& val)

{

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

if (_finish == _end_of_storage)

{

size_t len = pos - _start;//保存pos相对位置，防止失效

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

reserve(newcapacity);

//解决迭代器失效问题

pos = _start + len;

}

iterator end = _finish - 1;

while (end >= pos)

{

*(end + 1) = *end;

end--;

}

*pos = val;

_finish++;

return pos;

}

但是，这样只保证了能正确插入数据。如果在使用时，我们insert()一个元素后，迭代器还会可能失效，因为我们使用的传值传递，形参不会影响实参。因此insert()函数返回pos这个位置的迭代器，我们在外部使用的时候更新迭代器即可。

vector<int> v(5, 1);

vector<int>::iterator p = v.begin() + 1;

p = v.insert(p, 10);//更新迭代器

---

erase()任意位置删除

iterator erase(iterator pos)

{

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

iterator end = pos;

while (end < _finish - 1)

{

*end = *(end + 1);

end++;

}

_finish--;

return pos;

}

删除虽然不会扩容（不用保存pos指针的相对位置），但是删除一个元素后，后面的元素都会向前移动，此时迭代器指向空间虽然不变，但内容变成了下一个元素，我们在使用的时候要注意这个问题。

int main()

{

vector<int> v1;

v1.push_back(1);

v1.push_back(2);

v1.push_back(2);

v1.push_back(6);

auto it = v1.begin();

//法一：边使用边更新

while (it != v1.end())

{

if (*it % 2 == 0)

{

it = v1.erase(it);

}

else

{

it++;

}

}

//法二：使用完将迭代器减一，防止++出现走两步的情况

while (it != v1.end())

{

if (*it % 2 == 0)

{

v1.erase(it);

it--;

}

it++;

}

}

---

push_back()尾插

实现insert()函数后，我们就可以直接复用。

void push_back(const T& val)

{

/*if (_finish == _end_of_storage)

{

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

reserve(newcapacity);

}

*_finish++ = val;*/

insert(end(), val);

}

---

pop_back()尾删

同样直接复用erase()，让erase()自己判断合法性。

void pop_back()

{

/*assert(size() > 0);

_finish--;*/

erase(_finish - 1);

}

---

vector模拟实现代码