一、vector类的成员变量

跟以前的成员变量不同，vector的成员变量为：

iterator _start;// 数据开始
iterator _finish;// 数据结束
iterator _endofstorage;// 空间结尾
1
2
3

iterator是typedef出来的：

typedef T* iterator;
1

三个成员变量的含义：
_start指向数据的开始，_finish指向结束位置的下一个位置，_endofstorage指向整个空间的最后。

二、vector类的接口实现

2.1 构造函数

// 构造函数
vector()
: _start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}
1
2
3
4
5
6

2.2 析构函数

~vector()
{
if (_start)
{
delete[]_start;
_finish = _endofstorage = _start = nullptr;
}
}
1
2
3
4
5
6
7
8

2.3 size和capacity

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

size_t capacity() const
{
return _endofstorage - _start;
}
1
2
3
4
5
6
7
8
9

指针相减就代表中间的数据个数

2.4 扩容

2.4.1 reserve扩容

void reserve(size_t n)
{
if (n < size())
{
_finish = _start + n;
}
else
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, sizeof(T) * sz); 不能这么写
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
delete[]_start;
}
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

需要注意的细节：
1️⃣ 初始空间的大小要提前保存（新空间size会改变）
2️⃣ 要注意改变三个成员函数
3️⃣不能使用memcpy（浅拷贝）

假设现在定义一个vector<string>的类：

当我们扩容需要拷贝时，如果使用memcpy就会发生这种情况：

调用析构函数就会引发崩溃

2.4.2 resize扩容

resize跟reserve比起来就多了一个初始化。

void resize(size_t n, const T& val = T())// 匿名对象
{
if (n < size())
{
_finish = _start + n;
}
else
{
if (n > capacity())
{
reserve(n);
}
while (_finish != _endofstorage)
{
*_finish = val;
_finish++;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

要注意的是单独使用T()时，当前行结束就会自动调用销毁。而使用const T& val = T()就可以延长生命周期。

2.5 尾插

void push_back(const T& x)
{
if (_finish == _endofstorage)
{
// 扩容
reserve(capacity() == 0 ? 4 : 2 * capacity());
}
*_finish = x;
_finish++;
}
1
2
3
4
5
6
7
8
9
10

2.6 尾删

void pop_back()
{
assert(size() > 0);
_finish--;
}
1
2
3
4
5

2.7 []重载

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

const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
1
2
3
4
5
6
7
8
9
10
11

2.8 迭代器和const迭代器

iterator begin()
{
return _start;
}

const_iterator begin() const
{
return _start;
}

iterator end()
{
return _finish;
}

const_iterator end() const
{
return _finish;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.9 拷贝构造

// 拷贝构造
vector(const vector<T>& x)
{
_start = new T[x.capacity()];
_finish = _start;
_endofstorage = _start + x.capacity();
// 拷贝
for (size_t i = 0; i < x.size(); i++)
{
*_finish = x[i];
_finish++;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.9.1 现代写法

要写现代写法我们首先需要构造一个临时的vector类然后交换，而我们现在的构造函数没有参数，所以我们要再写一个构造函数。

2.9.1.1 迭代器版构造函数❗️❗️

template <class InputIterator>
vector(InputIterator first, InputIterator last)
: _start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
while (first != last)
{
push_back(*first);
first++;
}
}
1
2
3
4
5
6
7
8
9
10
11
12

我们可以看到这种迭代器以前没有见过：

2.9.1.2 迭代器的分类❗️❗️

迭代器有很多类型：

只读迭代器：input_iterator
只写迭代器：output_iterator
单向迭代器：forward_iterator只能++操作
双向迭代器： bidirectional_iterator支持++和--操作
随机迭代器：randomAccess_iterator支持++、--、+=、-=、等操作， 访问任意位置

继承关系：

接下来就可以写现代写法的拷贝构造了：

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

// 现代写法
// v1(v2)
vector(const vector<T>& x)
: _start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
vector<T> tmp(x.begin(), x.end());
swap(tmp);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.10 赋值拷贝

vector<T>& operator=(const vector<T>& x)
{
for (size_t i = 0; i < x.size(); i++)
{
push_back(x[i]);
}
return *this;
}
1
2
3
4
5
6
7
8

赋值拷贝跟拷贝构造的区别是：

赋值拷贝是把一个类赋值给另一个已经构造好的类，而拷贝构造是创建出一个新的类并赋值。

2.10.1 现代写法

//现代写法
vector<T>& operator=(vector<T> x)
{
swap(x);
return *this;
}
1
2
3
4
5
6

2.11 插入

iterator insert(iterator pos, const T& val)
{
assert(pos <= _finish);
assert(pos >= _start);
if (size() == capacity())
{
// 扩容
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len;
}
// 移动数据
iterator cur = end() - 1;
while (cur >= pos)
{
*(cur + 1) = *cur;
cur--;
}
*pos = val;
_finish++;
return pos;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

为什么要用迭代器当返回值？

插入可能改变空间，导致迭代器失效。

2.12 删除

iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos <= _finish);
assert(size() > 0);
iterator del = pos;
while (del != end())
{
*del = *(del + 1);
del++;
}
_finish--;
return pos;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

为什么要用迭代器当返回值？

有的删除可能会缩容，导致迭代器失效。