一、vector的介绍

vector学习时一定要学会查看文档：cplusplus网址：vector文档介绍vector在实际中非常的重要，在实际中我们熟悉常见的接口就可以

【总结】

1.vector是表示可变大小数组的序列容器

2.就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理

3.本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小

4.vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的

5.vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。

6.与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好

使用STL的三个境界：能用，明理，能扩展 ，那么下面学习vector，我们也是按照这个方法去学习

二、vector的使用

1.构造函数

vector提供了四种构造方式–无参构造，n个val构造，迭代区间构造和拷贝构造

// 测试构造
void vector_test1()
{
vector<int> v1;  // 无参构造
vector<int> v2(5, 1);  // n个val构造
vector<int> v3(v2);   // 拷贝构造
string s("hello world");
vector<int> v4(s.begin(), s.end());   // 迭代器构造
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
for (auto e : v3)
{
cout << e << " ";
}
cout << endl;
for (auto e : v4)
{
cout << e << " ";
}
cout << endl;
}
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
28
29

【注意】

1.对于构造函数的最后一个参数alloc是空间配置器，它和内存池有关，它的作用是提高空间分配的效率，我们一般情况下不需要管这个参数，使用它的缺省值即可，这个缺省值的原因是有极少数的人需要使用自己实现的空间配置器来代替STL库里的

2.在n个val构造中，val的缺省值是T的匿名对象，该对象使用T的默认构造来初始化，而不是使用0来作为这个缺省值，这个是因为T不仅仅是内置类型，也可以是自定义类型，比如string,vector,list;当T为自定义类型的时候，0就不一定能够对val进行初始化，所以我们就用T的匿名对象去调用它的默认构造去进行初始化，当T为内置类型的时候，内置类型也会去调用它的构造函数，大家可能很惊讶，内置类型怎么可能有构造函数呢，这是编译器进行了特殊的处理，使得内置类型也具有了构造函数。

2.扩容机制

capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL

测试用例如下：

// 测试vector的默认扩容机制
void TestVectorExpand()
{
size_t sz;
vector<int> v;
sz = v.capacity();
cout << "making v grow:\n";
for (int i = 0; i < 100; ++i)
{
v.push_back(i);
if (sz != v.capacity())
{
sz = v.capacity();
cout << "capacity changed: " << sz << '\n';
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

vs2019

g++

3.三种遍历方式

vector和string一样，也支持三种遍历方式–下标+[]，迭代器遍历，范围for遍历

// 测试遍历
void vector_test2()
{
vector<int> v(10, 1);
// 下标+[]
for (size_t i = 0; i < v.size(); ++i)
{
cout << v[i] << " ";
}
cout << endl;
// 迭代器遍历
vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// 范围for遍历
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
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

【注意】

vector和string支持下标+[]的方式进行遍历的原因是string和vector的底层都是通过数组实现的，而数组支持随机访问，但是对于不是通过数组实现的容器，比如list,set map等等，他们就不能通过下标+[]的方式进行遍历，此外，我们还需要注意，范围for只是一个外壳，它在调用的时候也是去调用迭代器，所以迭代器是所有容器通用的遍历方式

4.容量操作

其中，最重要的两个函数为resize和reserve，resize的作用的扩容和初始化，既会改变size也会改变capacity，而reserve只用于扩容，不改变size

// 测试resize reserve
void vector_test3()
{
vector<int> v(5);
cout << v.size() << endl;
cout << v.capacity() << endl << endl;

v.reserve(10);
cout << v.size() << endl;
cout << v.capacity() << endl << endl;

v.resize(3);
cout << v.size() << endl;
cout << v.capacity() << endl << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

但是我们需要注意，resize,reserve以及clear函数都不会缩容，因为缩容需要重新开辟空间，拷贝数据和释放空间，而对于自定义类型又可能存在深拷贝的问题，时间消耗很大，在迫不得已的情况下，比如开辟了一块很大的空间，并且确定这块空间只需要一小部分，这个时候我们可以使用shrink_to_fit函数，如果capacity大于size,它会进行缩容，让size==capacity

【总结】

1.reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题

2.resize在开空间的同时还会进行初始化，影响size和capacity

5.元素访问

vector提供了以下接口来进行元素访问

其中，operator[]和at都是返回pos位置的元素的引用，且他们内部都会对pos进行合法性检查，二者不同的是，operator[]如果检查到pos位置非法的时候，那么它会直接终止程序，报断言错误，而at是抛异常

operator[]

at

【注意】在release模式下检查不出断言错误

6.增删查改

assign

assign函数用来替换vector对象中的数据，支持n个val替换和迭代区间替换

// 测试assign
void vector_test5()
{
vector<int> v1(5, 1);
v1.assign(5, 5);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
vector<int> v2(3);
v2.assign(v1.begin(), v1.end());
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

push_back && pop_back

push_back是进行尾插，pop_back是尾删，这两个函数比较简单，我们看一下示例即可：

// 测试尾插 尾删
void vector_test6()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
for (size_t i = 0; i < v.size(); ++i)
{
cout << v[i] << " ";
}
cout << endl;
v.pop_back();
v.pop_back();
for (size_t i = 0; i < v.size(); ++i)
{
cout << v[i] << " ";
}
cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

insert && erase

和string不同的是，为了提高规范性，STL的容器都统一使用iterator作为pos的类型，并且插入和删除后会返回pos

所以我们如果在中间插入或者删除数据的时候，可以和算法库里的find配合起来使用

// 测试插入 删除
void vector_test7()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);

vector<int>::iterator pos = find(v.begin(),v.end(),3);
if (pos != v.end())
{
v.insert(pos,30);
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
pos = find(v.begin(), v.end(), 2);
if (pos != v.end())
{
v.erase(pos);
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;

}
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
28
29
30
31

【注意】

在VS在，insert和erase之后会导致pos迭代器失效，如果需要再次使用，需要更新pos

不过，在Linux下不会出现这个问题：

造成这个问题的根本原因是VS使用的是PJ版本对iterator进行了封装，在每次insert和earse之后会对迭代器进行特殊处理，而g++使用的是SGI版本中的iterator原生指针，为了代码的可移植性，我们统一认为insert和earse使用之后迭代器会失效，所以需要再次使用迭代器，我们必须对其进行更新，我们以移除vector中的所有偶数为例：

// 迭代器失效
void vecrtor8()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);

vector<int>::iterator pos = v.begin();
while (pos != v.end())
{
if (*pos % 2 == 0)
{
pos = v.erase(pos);
}
else
{
++pos;
}
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
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
28
29

swap

和string一样，由于算法库里的swap函数存在深拷贝的问题，vector自己提供了一个不需要深拷贝的swap函数，用于交换两个vector对象：

同时，为了避免我们不使用成员函数的swap，vector还将算法库中的vector进行了重载，然后该重载函数的内部又去调用成员函数swap:

// 测试交换
void vector_test9()
{
vector<int> v1(5, 1);
vector<int> v2(5, 2);
vector<int> v3(5, 3);
v1.swap(v2);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
std::swap(v1, v3);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

三、vector深度剖析及模拟实现

1.核心框架

我们学习STL可以去阅读别人优秀的代码，然后理解其中的逻辑和细节后我们自己去独立实现几次，因此我们可以对阅读STL的源码，但是当前阶段我们只需要学习STL库的核心框架，并不需要逐行进行的阅读，其中有些语法我们也无法理解，我们也可以阅读优秀的书籍，我这里推荐侯捷老师的《STL源码剖析》,这本书使用的是SGI版本，这个版本适合阅读，《STL源码剖析》电子版和《stl30》源码我放在了下面，需要的自取：

STL源码剖析：https://www.aliyundrive.com/s/Nc4mpLC43kj
stl30：https://www.aliyundrive.com/s/pnwMuB9uwEN
1
2

我们就可以得到vector源码的核心框架：

namespace hdp
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;

// 成员函数
        // ......
private:
T* _start;
T* _finish;
T* _endofstorage;
};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

我们可以看到，vector和string一样，都是一个指针指向一个动态开辟的数组，但是二者不同的是，string是用_size和_capacity两个size_t 的成员变量来维护这块空间，而vector是用_finish和_endofstorage两个指针来维护这块空间，其中二者在本质上是一样的，其中_size=_finish-_start;_capacity=_endofstorage -_start;

2.reserve使用memcpy拷贝问题

我们模拟实现的reserve函数如下：

// 预留空间
void reserve(size_t n)
{
if (n > capacity())
{
size_t oldSize = size();
T* tmp = new T[n];

// 如果_start不为空则进行拷贝
if (_start)
{
memcpy(tmp, _start, sizeof(T) * oldSize);  // 深层次的深拷贝的时候会出错
delete[] _start;
}
_start = tmp;
_finish = tmp + oldSize;
_endofstorage = _start + n;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

我们初步认识的时候可能认为这段代码没有问题，但是它对于内置类型来说确实是没有问题的，也进行了深拷贝，但是它对于需要进行深拷贝的自定义类型来说就有问题了，如下：

void vector_test_copy()
{
hdp::vector<vector<int>> vv;
vector<int> v(5, 1);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
}
1
2
3
4
5
6
7
8
9
10

程序报错的原因如下：

当我们插入4个v对象的时候，如上图，pu_back内部就会调用reserve函数进行扩容，扩容时虽然我们进行了深拷贝，但是空间的内容我们是使用memcpy按字节拷贝的，这里导致原来的vv里面的v元素和现在的vv里的元素指向同一块空间，当我们拷贝完毕之后，使用delete[]释放空间原来的空间的时候使得同一块空间被释放了两次，因为v(自定义类型)会调用自身的析构函数，所以现在的vv里面的元素都执行已经被释放了的空间，如下图：

所以我们在reserve函数的内部不能时候memcpy函数直接按照字节为单位拷贝原来空间中的各个元素，因为这些元素也可能指向一块动态开辟的空间，而是应该调用每个元素的拷贝构造进行拷贝，如下图：

对于reserve函数的具体实现如下：

// 预留空间
void reserve(size_t n)
{
if (n > capacity())
{
size_t oldSize = size();
T* tmp = new T[n];

// 如果_start不为空则进行拷贝
if (_start)
{
for (size_t i = 0; i < oldSize; ++i)
{
tmp[i] = _start[i];
}

delete[] _start;
}
_start = tmp;
_finish = tmp + oldSize;
_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

对于代码中tmp[i] = _start[i],我们可能认为是赋值运算符重载，其实不是这样的，因为这里只是为 了完成初始化工作，所以编译或会自动调用拷贝构造函数。

【总结】

1.memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中

2.如果拷贝的是自定义类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝

【结论】如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃

3.构造函数错误调用问题

我们模拟实现构造函数中 的迭代区间构造和n格val构造后，会发现一个问题，我们使用n个val来构造其他类型的对象的时候没有问题，但是构造int类型的对象时会编译出错：

// n个val初始化
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}

// 迭代器初始化
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
13
14
15
16
17
18
19
20
21
22
23
24
25
26

这是由于编译器在进行模板实例化和函数参数匹配时会调用最匹配的一个函数，当我们将T实例化为int的时候，由于两个参数都是int，所以对于迭代器构造函数来说，它会直接将InputIterator实例化为int;对于n个val的构造来说，它需要将T实例化为int，还需要将第一参数隐式转换为size_t，所以这个时候，编译器会调用迭代器构造，同时迭代器构造内部会对first进行解引用，所以这个报错"非法的间接寻址"

对于这个问题，我们有很多的解决方式：比如调用时将第一个参数强转为size_t,又或将n个val构造的第一个参数设置为int,我们这里和STL源码保持一致–提供第一个参数为int的n个val构造的重载函数：

// n个val初始化
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}

vector(int n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n);
for (int i = 0; i < n; ++i)
{
push_back(val);
}
}
// 迭代器初始化
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
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

4.insert和 erase迭代器失效问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。

对于vector可能会导致其迭代器失效的操作有：会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等

我们模拟实现的insert和earse函数如下：

// 在pos位置插入数据
// 迭代器失效 : 扩容引起，野指针问题
iterator insert(iterator pos, const T& val)
{
// 断言pos的位置
assert(pos >= _start);
assert(pos < _finish);

// 空间不够进行扩容
if (_finish == _endofstorage)
{
size_t len = pos - _start;
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);

// 扩容会导致pos迭代器失效，需要更新处理一下
pos = _start + len;
}

// 挪动数据
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}

*pos = val;
++_finish;

return pos;
}

// 删除pos位置数据
iterator erase(iterator pos)
{
// 断言pos的位置
assert(pos >= _start);
assert(pos < _finish);

// 挪动数据
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
++begin;
}

--_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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

我们在VS在insert和erase调用之后迭代器会失效，再次访问的时候会报错，这是因为PJ版本下的iterator不是原生指针，如下：

可以看到，VS中的迭代器是一个类，当我们进行insert和erase调用之后，iterator中的某个函数可能会将pos置为空或者其他操作，所以我们再次访问pos位置的数据就会报错，除非我们每次调用之后都更新pos:

在linux在，g++却不会出现这样的问题，这个是因为g++使用的是SGI版本，该版本的iterator是一个原生指针，同时它的insert和erase的内部实现和我们模拟实现的类似。

这里也存在一个问题，lnsert 和erase 之后pos的意义变了–我们插入元素之后pos不再指向原来的元素，而是指向我们新插入元素的位置；erase之后也不再指向原来的元素，而是指向该元素的后一个元素，特别是当erase尾部数据之后，pos就等于_finish

【总结】

erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了

SGI STL中，迭代器失效后，代码并不一定会崩溃，但是运行结果肯定不对，如果it不在begin和end范围内，肯定会崩溃的

我们统一认为insert和erase之后，迭代器失效了，更新之后才能继续使用，这样保证了代码的跨平台性

迭代器失效解决办法：在使用前，对迭代器重新赋值即可

5.模拟实现完整代码

6.1 vector.h

#pragma once

namespace hdp
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;

// 迭代器
iterator begin()
{
return _start;
}

iterator end()
{
return _finish;
}

// const 迭代器
const_iterator begin()  const
{
return _start;
}

const_iterator end()  const
{
return _finish;
}

// 重载[]
T& operator[](size_t pos)
{
assert(pos < size());
return *(_start + pos);
}

// const 重载[]
const T& operator[](size_t pos) const
{
assert(pos < size());
return *(_start + pos);
}

// 无参构造
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}

// n个val初始化
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}

vector(int n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n);
for (int i = 0; i < n; ++i)
{
push_back(val);
}
}

// 迭代器初始化
template <class InputIterator>

vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}

// 拷贝构造
// v1(v2)  写法1
/*vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(v.capacity());
for (const auto& e : v)
{
push_back(e);
}
}*/

// 拷贝构造  写法2
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}

// v1 = v2
// v1 = v1;  // 极少数情况，能保证正确性，所以这里就这样写没什么问题
// 赋值重载
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}

// 析构
~vector()
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}

// 预留空间
void reserve(size_t n)
{
if (n > capacity())
{
size_t oldSize = size();
T* tmp = new T[n];

// 如果_start不为空则进行拷贝
if (_start)
{
// memcpy(tmp, _start, sizeof(T) * oldSize);  // 深层次的深拷贝的时候会出错
for (size_t i = 0; i < oldSize; ++i)
{
tmp[i] = _start[i];
}

delete[] _start;
}
_start = tmp;
_finish = tmp + oldSize;
_endofstorage = _start + n;
}
}

//调整空间大小
void resize(size_t n, T val = T())
{
if (n > capacity())
{
reserve(n);
}
if (n > size())
{
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else
{
_finish = _start + n;
}
}

// 在尾部插入数据
void push_back(const T& val)
{
if (_finish == _endofstorage)
{
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
}

*_finish = val;
++_finish;
}

// 删除尾部数据
void pop_back()
{
// 为空时不进行删除
assert(!empty());
--_finish;
}

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

// 在pos位置插入数据
// 迭代器失效 : 扩容引起，野指针问题
iterator insert(iterator pos, const T& val)
{
// 断言pos的位置
assert(pos >= _start);
assert(pos < _finish);

// 空间不够进行扩容
if (_finish == _endofstorage)
{
size_t len = pos - _start;
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);

// 扩容会导致pos迭代器失效，需要更新处理一下
pos = _start + len;
}

// 挪动数据
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}

*pos = val;
++_finish;

return pos;
}

// 删除pos位置数据
iterator erase(iterator pos)
{
// 断言pos的位置
assert(pos >= _start);
assert(pos < _finish);

// 挪动数据
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
++begin;
}

--_finish;

return pos;

}

// 清空
void clear()
{
_start = _finish;
}

// 判空
bool empty()
{
return _start == _finish;
}

// 获取数据个数
size_t size()
{
return _finish - _start;
}

// 获取容量
size_t capacity()
{
return _endofstorage - _start;
}
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};
}
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292

6.2 test.cpp

#include <iostream>
#include <vector>
#include <assert.h>
#include <algorithm>
using namespace std;
#include  "vector.h"

// 测试三种遍历
void test_vector1()
{
hdp::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);

// 下标+[]遍历
for (size_t i = 0; i < v.size(); ++i)
{
cout << v[i] << " ";
}
cout << endl;

// 迭代器遍历
hdp::vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;

// 范围for遍历
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}

// 测试尾插和容量改变
void test_vector2()
{
hdp::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
cout << v.capacity() << endl;

v.reserve(10);
cout << v.capacity() << endl;

// 比当前容量小时，不缩容
v.reserve(4);
cout << v.capacity() << endl;

v.resize(8);
v.resize(15, 1);
v.resize(3);
}

// 测试插入
void test_vector3()
{
hdp::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);

v.insert(v.begin(), 4);
v.insert(v.begin() + 2, 4);

// 没有find成员
//vector<int>::iterator it = v.find(3);

hdp::vector<int>::iterator it = find(v.begin(), v.end(), 3);
if (it != v.end())
{
v.insert(it, 30);
}

for (auto e : v)
{
cout << e << " ";
}
cout << endl;

hdp::vector<int> v1;
v1.push_back(10);
v1.push_back(20);
v1.push_back(30);

v1.swap(v);
swap(v1, v);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
void test_vector4()
{
hdp::vector<vector<int>> vv;
vector<int> v(5, 1);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);

for (size_t i = 0; i < vv.size(); ++i)
{
for (size_t j = 0; j < vv[i].size(); ++j)
{
cout << vv[i][j] << " ";
}
cout << endl;
}
cout << endl;
}

// 测试删除
void test_vector5()
{
// 要求删除所有偶数
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);


vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it);
}
else
{
++it;
}
}

for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
int main()
{
try
{
//test_vector1();
//test_vector2();
//TestVectorExpand();
//test_vector3();
//test_vector4();
test_vector5();
}
catch (const exception& e)
{
cout << e.what() << endl;
}
return 0;
}


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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174