【C++】—— vector 的模拟实现

0 前言1 vector 的成员变量1.1 stl 库中的 vector 成员变量1.2 模拟实现 vector 成员变量

2 迭代器3 size、capacity、empty4 opreator[ ]5 reserve5.1 初版 reserve5.2 _finish 的处理5.3 深拷贝5.4 终版

6 push_back 与 pop_back7 打印函数7.1 初写打印7.2 typename 关键字7.3 打印函数进阶

8 insert8.1 insert 初版8.2 迭代器失效8.2.1 情况一：类似野指针8.2.2 algorithm 库中的查找函数8.2.3 情况二：insert 后再对 pos 进行访问8.2.3.1 不扩容的情况8.2.3.1 扩容的情况

8.2.4、解决方法8.2.4.1、想法一8.2.4.2、想法二

8.3 总结

9 erase10 resize11 构造函数系列11.1 默认构造11.2 拷贝构造11.3 迭代器区间构造 与 n 个 value 构造11.3.1 迭代器区间构造11.3.2 n 个value构造11.3.3 注意事项

12 赋值运算符重载12.1 传统写法12.2 现代写法

13 源码

0 前言

前面，我们学习了

s

t

r

i

n

g

string

string，并模拟实现了它，下面我们来学习

v

e

c

t

o

r

vector

vector

v

e

c

t

o

r

vector

vector 的底层即我们前面曾经学过的<code>顺序表，它属于 STL库，为了让我们更加深入理解

v

e

c

t

o

r

vector

vector，接下来我们将模拟实现

v

e

c

t

o

r

vector

vector

1 vector 的成员变量

1.1 stl 库中的 vector 成员变量

我们学习数据结构时，曾经模拟实现过顺序表。当时我们用一个指针

a

a

a 管理从堆开辟的空间，

s

i

z

e

size

size 表示当前有效数据的个数，

c

a

p

a

c

i

t

y

capacity

capacity 表示当前空间的大小。

但是，

s

t

l

stl

stl库 中的

v

e

c

t

o

r

vector

vector 的成员变量有所差别：它的成员变量是三个迭代器

我们知道，迭代器全部都是

t

y

p

e

d

e

f

typedef

typedef 出来的，那

v

e

c

t

o

r

vector

vector 的迭代器是什么呢？

可以看到，其迭代器就是 原生指针！

那<code>start、finish、end_of_storage 变量又是什么意思呢？面对未知的东西，我们应大胆假设，小心求证。

不管他底层如何，

v

e

c

t

o

r

vector

vector 终究逃不过扩容，那我们不难猜想：start 肯定是一个指针指向一个开始，finish指向某个结束，至于end_of_storage，

s

t

o

r

a

g

e

storage

storage 是存储的意思，所以我们大胆猜测end_of_storage与空间相关，可能就是空间结束位置；那这样的话finish 可能表示数据的结束

那我们怎么取求证呢？我们可以通过一些我们熟悉功能的函数来确认

可以看到，

b

e

g

i

n

begin

begin 返回的是第一个有效数据位置，这里是<code>start；而

e

n

d

end

end 返回的是最后一个有效数据的下一个位置，这里返回的是finish；

c

a

p

a

c

i

t

y

capacity

capacity 表示空间的大小，这里返回的是end_of_storage - begin()。

因此我们的猜测是正确的，那么

v

e

c

t

o

r

vector

vector 的底层结构如下：

注：<code>finish 指向的是有效空间的下一个位置

1.2 模拟实现 vector 成员变量

我们模拟实现的

v

e

c

t

o

r

vector

vector 的成员变量，也学习库中的形式

namespace my_vector

{ -- -->

template<class T>

class vector

{

public:

//···

private:

iterator _start = nullptr;

iterator _finish = nullptr;

iterator _end_of_storage = nullptr;

};

}

这里，为了与库中的

v

e

c

t

o

r

vector

vector 区别开，我们使用命名空间

同时，因为顺序表应满足不同数据类型的存储，我们实现的不是某个具体类型的类，而是类模板。既然是模板，那么函数的声明与定义就不能放在不同的文件中，因此声明和定义全在vector.h文件中，不再需要vector.cpp文件。

2 迭代器

因为

v

e

c

t

o

r

vector

vector 的迭代器是一个原生指针，与

s

t

r

i

n

g

string

string 类似，很简单，我们直接看代码

typedef T* iterator;

typedef const T* const_iterator;

iterator begin()

{

return _start;

}

iterator end()

{

return _finish;

}

const_iterator begin() const

{

return _start;

}

const_iterator end() const

{

return _finish;

}

因为 _

f

i

n

i

s

h

finish

finish 本就就是只想最后一个有效数据的下一位，因此我们end()我们直接返回 _finish 即可

3 size、capacity、empty

这三个函数都很简单，我们直接看代码

size_t size() const

{

return _finish - _start;

}

size_t capacity() const

{

return _end_of_storage - _start;

}

bool empty() const

{

return _start == _finish;

}

4 opreator[ ]

v

e

c

t

o

r

vector

vector 中的

o

p

r

e

a

t

o

r

opreator

opreator[] 与

s

t

r

i

n

g

string

string 中的

o

p

e

r

a

t

o

r

operator

operator[] 类似，都是访问第

i

i

i 个数据的元素。同样，

v

e

c

t

o

r

vector

vector 的

o

p

e

r

a

t

o

r

operator

operator[] 也要用

a

s

s

e

r

t

assert

assert 断言来判断下标是否合法

T& operator[](size_t i)

{

assert(i < size());

return _start[i];

}

const T& operator[](size_t i) const

{

assert(i < size());

return _start[i];

}

这里顺便提一下，

v

e

c

t

o

r

vector

vector 还提供了 at 函数 接口。

a

t

at

at 函数与

o

p

e

r

a

t

o

operato

operato[] 功能相同，但他们检查越界的方式不同

a

t

at

at 函数是抛异常，而

o

p

e

r

a

t

o

r

operator

operator[] 是断言

5 reserve

5.1 初版 reserve

void reserve(size_t n)

{

if (n > capacity())

{

T* tmp = new T[n];

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

delete[] _start;

_start = tmp;

_finish = _start + size();

_end_of_storage = _start + n;

}

}

在

s

t

r

i

n

g

string

string 中，我们已经模拟实现

r

e

s

e

r

v

e

reserve

reserve 了，

v

e

c

t

o

r

vector

vector 中也是需要我们手动释放和拷贝的数据的，代码细节就不再细讲了。

那上面代码有问题吗？

有的

5.2 _finish 的处理

首先是对 _

f

i

n

i

s

h

finish

finish 的处理上

这里我们更新_finish的方式是_start + size()，可是 size() 是怎么计算出来的？是通过_finish - _start计算出的，可是此时 _

s

t

a

r

t

start

start已经更新了，而_

f

i

n

i

s

h

finish

finish还未更新 ，此时他们相减会出大问题。

怎么解决呢？也很好办，那就是提前记录

s

i

z

e

size

size() 的值

<code>void reserve(size_t n)

{ -- -->

if (n > capacity())

{

//记下size()的值

size_t old_size = size();

T* tmp = new T[n];

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

delete[] _start;

_start = tmp;

_finish = _start + old_size;

_end_of_storage = _start + n;

}

}

5.3 深拷贝

还有一点，上述代码用

m

e

m

c

p

y

memcpy

memcpy 拷贝是浅拷贝，而我们需要的是深拷贝

用

m

e

m

c

p

y

memcpy

memcpy 拷贝有什么问题呢？

void test7()

{

vector<string> v1;

v1.push_back("11111");

v1.push_back("11111");

v1.push_back("11111");

v1.push_back("11111");

print_container(v1);

v1.push_back("11111");

print_container(v1);

}

运行结果：

程序崩溃了！

为什么呢？问题出现在了扩容！

我们知道

v

e

c

t

o

r

vector

vector<

s

t

r

i

n

g

string

string> 中，每个

s

t

r

i

n

g

string

string 都指向一块堆空间。

虽然

v

e

c

t

o

r

vector

vector 是深拷贝，但是

v

e

c

t

o

r

vector

vector 中的每个

s

t

r

i

n

g

string

string 都是浅拷贝，而<code>每个string都指向一块资源。这意味着新开辟的

t

m

p

tmp

tmp 中，每个 string 都是与对应旧空间的 string 指向同一块空间，

d

e

l

e

t

e

delete

delete 后，会调用析构函数，将旧空间指向的资源全部释放掉，此时新空间的每个

s

t

r

i

n

g

string

string 都是指向一块已经被释放的空间，自然会出现问题。

那如何解决呢？那就是<code>对vector中的每个成员都进行深拷贝。我们不能再使用

m

e

m

c

p

y

memcpy

memcpy，而是要自己赋值

void reserve(size_t n)

{ -- -->

if (n > capacity())

{

size_t old_size = size();

T* tmp = new T[n];

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

{

_tmp[i] = _start[i];

}

delete[] _start;

_start = tmp;

_finish = _start + old_size;

_end_of_storage = _start + n;

}

}

_tmp[i] = _start[i];是赋值，本质是调用自定义类型的赋值重载函数，实现了每个成员的深拷贝，而[ ]，则是前面实现的operator[]重载函数

5.4 终版

<code>void reserve(size_t n)

{ -- -->

if (n > capacity())

{

size_t old_size = size();

T* tmp = new T[n];

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

{

_tmp[i] = _start[i];

}

delete[] _start;

_start = tmp;

_finish = _start + old_size;

_end_of_storage = _start + n;

}

}

6 push_back 与 pop_back

p

u

s

h

push

push_

b

a

c

k

back

back 直接往尾部放数据即可，但要注意空间不够要扩容

void push_back(const T& x)

{

if (_finish == _end_of_storage)

{

size_t n = size() == 0 ? 4 : 2 * size();

reserve(n);

}

*_finish = x;

++_finish;

}

p

o

p

pop

pop_

b

a

c

k

back

back 也很简单，但要注意判断是否为空。

void pop_back()

{

assert(!empty());

--_finish;

}

7 打印函数

STL库 中，

v

e

c

t

o

r

vector

vector 是没有重载

o

p

e

r

a

t

o

r

operator

operator<< 的。

为什么呢？因为库事先并不知道你要以什么形式打印：是连续打印，还是每打印一个数据就空格还是每打印一个就换行？而且自己实现一个打印函数并不困难。因此库就交给程序员自己实现。

7.1 初写打印

那么我们就自己实现一个打印函数吧。

打印函数是一个全局函数

template<class T>

void print_vector(const vector<T>& v)

{

vector<T>::const_iterator it = v.begin();

while (it != v.end())

{

cout << *it << " ";

++it;

}

cout << endl;

}

但上述函数写的是有问题的

7.2 typename 关键字

为什么呢？

问题出现在<code>vector<T>::const_iterator it;中

可以直接突破类域，用类名::方式去类中取东西，能取到两种：一种是 静态成员变量，另一种是在 类中

t

y

p

e

d

e

f

typedef

typedef 的类型。

C++规定：类模板没有被实例化之前，编译器是不会往里面去取东西的。

编译器走到

p

r

i

n

t

print

print_

v

e

c

t

o

r

vector

vector 时，

v

e

c

t

o

r

vector

vector 模板还没被实例化出来。而因为不敢去模板中取，编译器不知道

c

o

n

s

t

const

const_

i

t

e

r

a

t

o

r

iterator

iterator 是 类型 还是 静态成员变量，如果取到静态成员变量，后面还跟着变量 it 就会出大问题。因此编译器报错。

要解决上述问题，需在前面加上

t

y

p

e

n

a

m

e

typename

typename 关键字。加上

t

y

p

e

n

a

m

e

typename

typename，即明确告诉编译器

c

o

n

s

t

const

const_

i

t

e

r

a

t

o

r

iterator

iterator 是类型。（可以看做编译器的甩锅。编译器：你说了是类型的啦，我给你过了，如果他是成员变量的话那也是你的问题，不怪我）

但如果是取静态成员变量，前面什么都不用加，因为如果真是静态成员变量，你不会像vector<T>::const_iterator it这样用的，直接就vector<T>::const_iterator;这样

template<class T>

void print_vector(const vector<T>& v)

{ -- -->

//没有实例化的类模板里面取东西，编译器不能区分const_iterator是类型还是静态成员变量

typename vector<T>::const_iterator it = v.begin();

while (it != v.end())

{

cout << *it << " ";

++it;

}

cout << endl;

}

这样就可以啦

当然，这还有一种更简单的方式，用

a

u

t

o

auto

auto 就没有那么麻烦，因为

a

u

t

o

auto

auto 直接是由v.begin()推导而来

template<class T>

void print_vector(const vector<T>& v)

{

auto it = v.begin();

while (it != v.end())

{

cout << *it << " ";

++it;

}

cout << endl;

}

7.3 打印函数进阶

但上述打印函数，稍稍改进一下，就可以变成所有类型容器的打印函数，而不仅仅是

v

e

c

t

o

r

vector

vector 类型的

template<class Container>

void print_container(const Container& v)

{

auto it = v.begin();

while (it != v.end())

{

cout << *it << " ";

++it;

}

cout << endl;

}

需要注意的是判断条件while (it != v.end())只能是 !=，有些小伙伴可能会写while (it < v.end())。对于

s

t

r

i

n

g

string

string 与

v

e

c

t

o

vecto

vector 来说是没问题，因为他们本来就是原生指针；但对其他容器就不行了，比例

l

i

s

t

list

list 链表，它的

i

t

e

r

a

t

o

r

iterator

iterator 是一个类，不存在比较大小的概念。

8 insert

8.1 insert 初版

void insert(iterator pos, const T& x)

{

assert(pos >= begin() && pos <= end());

if (_finish == _end_of_storage)

{

size_t n = size() == 0 ? 4 : 2 * size();

reserve(n);

}

iterator i = end();

while (pos != i)

{

*i = *(i - 1);

--i;

}

*pos = x;

++_finish;

}

上述代码其实是有问题的

我们一起来看看

8.2 迭代器失效

8.2.1 情况一：类似野指针

上述代码其实是有问题的

我们先来测试一个不需要扩容的

void test1()

{

vector<int> v1;

v1.reserve(10);

v1.push_back(1);

v1.push_back(2);

v1.push_back(3);

v1.push_back(4);

v1.insert(v1.begin() + 1, 10);

print_vector(v1);

}

运行结果：

没有问题

那再来一个需要扩容的

<code>void test1()

{ -- -->

vector<int> v1;

v1.reserve(4);

v1.push_back(1);

v1.push_back(2);

v1.push_back(3);

v1.push_back(4);

v1.insert(v1.begin() + 1, 10);

print_vector(v1);

}

运行结果：

可以看到，报错了

为什么呢？这是因为

p

o

s

pos

pos 迭代器失效了

我们结合图来看就很容易看懂了。扩容后，<code>pos 依然指向旧空间，此时旧空间已经被释放了，

p

o

s

pos

pos 迭代器就是一个野指针，同时while (pos != i)判断语句永远也不会成立，造成死循环。

怎么办呢？我们应记录 pos 迭代器与 _start 的相对位置，再将 pos 映射到新空间中

void insert(iterator pos, const T& x)

{ -- -->

assert(pos >= begin() && pos <= end());

if (_finish == _end_of_storage)

{

size_t len = pos - _start;

size_t n = size() == 0 ? 4 : 2 * size();

reserve(n);

pos = _start + len;

}

iterator i = end();

while (pos != i)

{

*i = *(i - 1);

--i;

}

*pos = x;

++_finish;

}

8.2.2 algorithm 库中的查找函数

这里，介绍

a

l

g

o

r

i

t

h

m

algorithm

algorithm 库中的查找函数，

f

i

n

d

find

find 函数模板适用于所有的容器，只需要传一个迭代器区间给它，就能帮你查找

库中的

f

i

n

d

find

find函数 是一个<code>模板：

需要注意的是，传值要传<code>左闭右开区间

8.2.3 情况二：insert 后再对 pos 进行访问

8.2.3.1 不扩容的情况

我们知道，

i

n

s

e

r

t

insert

insert 函数的

p

o

s

pos

pos 形参是一个迭代器，如果我们想在指定数据之前插入数据，就可以用 find 模板找到相应数据的迭代器

现在，我用

f

i

n

d

find

find函数 找到

p

p

p 为 5 的位置，在之前插入数据 100，并将 5

∗

*

∗ 10

<code>void test2()

{ -- -->

vector<int> v1;

v1.push_back(1);

v1.push_back(2);

v1.push_back(3);

v1.push_back(4);

v1.push_back(5);

v1.push_back(6);

int x = 5;

auto p = std::find(v1.begin(), v1.end(), x);

if (p != v1.end())

{

v1.insert(p, 40);

*(p) *= 10;

}

print_container(v1);

}

运行结果：

为什么是<code>100 * 10 呢？

这是因为迭代器失效了，在

i

n

s

e

r

t

insert

insert 以后，我们可以认为迭代器 p 就已经失效了。我们结合图来理解

用

i

n

s

e

r

t

insert

insert 插入数据后，

p

p

p 指向的位置已经变了。你以为它指向的还是 5，但实际上他已经变了

8.2.3.1 扩容的情况

上述情况还不是最恐怖的，最恐怖的是扩容的情况

<code>void test3()

{ -- -->

vector<int> v1;

v1.push_back(1);

v1.push_back(2);

v1.push_back(3);

v1.push_back(4);

int x = 2;

auto p = std::find(v1.begin(), v1.end(), x);

if (p != v1.end())

{

v1.insert(p, 100);

*(p) *= 10;

}

print_container(v1);

}

运行结果：

现在连100 都不乘10了，为什么呢？还是迭代器失效的问题，我们来看图

p

o

s

pos

pos 的位置还是指向旧空间，这时再对

p

o

s

pos

pos 访问，就是类似于<code>野指针的访问。

8.2.4、解决方法

8.2.4.1、想法一

那应该怎么解决上述问题呢？

在解决完第一种情况的代码中，我们在函数内是对

p

o

s

pos

pos 进行了更新的

但是形参的改变并不影响实参，那我们可不可以用引用呢？

<code>void insert(iterator& pos, const T& x)

这样，

p

o

s

pos

pos 是引用，就能改变函数外的

p

p

p 了。

但这样是不行的，因为会影响传参

vector<int> v;

v1.insert(v1.begin(), 10);

像这样，我们传递第一个迭代器，但这样传参，v1.begin()的返回值中间会产生一个临时变量，实际传递的就是这个临时变量。临时变量是常性，必须用

c

o

n

s

t

const

const 引用，普通的引用是传不进去的。

那如果我加

c

o

n

s

t

const

const 呢？

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

加了

c

o

n

s

t

const

const，里面的

p

o

s

pos

pos 就无法改变了，所以还是不行

8.2.4.2、想法二

我们来看一下库中的

i

n

s

e

r

t

insert

insert 是怎么处理的

库中给了一个返回值，返回的是更新之后的

p

o

s

pos

pos。

<code>iterator insert(iterator pos, const T& x)

{ -- -->

assert(pos >= begin() && pos <= end());

if (_finish == _end_of_storage)

{

size_t len = pos - _start;

size_t n = size() == 0 ? 4 : 2 * size();

reserve(n);

pos = _start + len;

}

iterator i = end();

while (pos != i)

{

*i = *(i - 1);

--i;

}

*pos = x;

++_finish;

return pos;

}

所以如果真要

i

n

s

e

r

t

insert

insert 后继续访问

p

p

p，一定要更新

p

p

p 再访问

void test4()

{

vector<int> v1;

v1.push_back(1);

v1.push_back(2);

v1.push_back(3);

v1.push_back(4);

int x = 2;

auto p = std::find(v1.begin(), v1.end(), x);

if (p != v1.end())

{

p = v1.insert(p, 100);

*(p + 1) *= 10;

}

print_container(v1);

}

运行结果：

8.3 总结

用

i

n

s

e

r

t

insert

insert 后，<code>迭代器 p 就失效了，最好的办法就是不再用

p

p

p 去访问。如果非要访问，一定要更新一下迭代器

p

p

p 再去访问

9 erase

iterator erase(iterator pos)

{ -- -->

assert(pos < end() && pos >= begin());

iterator i = pos;

while (i != end() - 1)

{

*(i) = *(i + 1);

++i;

}

--_finish;

return pos;

}

同样，

e

r

a

s

e

erase

erase 也存在迭代器失效的问题。我们使用的时候一定要注意！

e

r

a

s

e

erase

erase之后就不要再访问迭代器，一定要访问也要先更新再访问，更新后的迭代器指向要删除数据的下一个位置

10 resize

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

{

if (n < size())

{

_finish = _start + n;

}

else

{

reserve(n);

while (_finish < _start + n)

{

*_finish = val;

++_finish;

}

}

}

r

e

s

i

z

e

resize

resize 的功能与实现这里就不再过多解释，这里大家直接看代码即可。

这里我们重点讲一下 const T& val = T()的写法

这是自定义类型给缺省值的方法。因为

v

e

c

t

o

r

vector

vector 是模板，给缺省值时不能再像 const T& val = 0 这样给，因为是模板，你不知道 T 是什么类型，像前面给 0 就表示 T 一定是 0 了，肯定是不合适的。T 可能是

i

n

t

int

int，可能是

d

o

u

b

l

e

double

double、也可能是自定义类型。

如果是自定义类型的对象，我们就调用它的默认构造。上述给缺省值的方法就是给 T 的一个匿名对象并调用它的默认构造。

那如果 T 是内置类型：

i

n

t

int

int、

d

o

u

b

l

e

double

double怎么办？他们没有默认构造这一概念啊

在此之前，我们确实是认为默认函数是没有构造函数这一概念的，但是为了兼容像模板这样的场景，内置类型也有了构造函数的概念(还有析构函数的概念)。

void test5()

{

int i = int();

int j(1);

cout << i << endl;

cout << j << endl;

cout << int(2) << endl;

}

运行结果：

11 构造函数系列

11.1 默认构造

<code>vector()

:_start(nullptr)

,_finish(nullptr)

,_end_of_storage(nullptr)

{ -- -->}

但实际上，并不需要这么麻烦，因为我们在成员变量声明时，结了缺省值，我们这样就可以了

vector() { }

学习类与对象时，我们知道：所有成员都会走初始化列表。如果我们没有显式写在初始化列表，对于内置类型：没有缺省值不做任何处理，但现在我们在成员变量声明时，结了缺省值，则用缺省值初始化。

在C++11中，给了一个方式可以 强制生成默认构造：

vector() = default;

因为编译器只有在程序员没有自己实现任何构造函数（拷贝构造也是构造）时才会生成默认构造，如果我们自己实现了带参的构造，又想编译器生成默认构造，就可以用上述语法

11.2 拷贝构造

vector(const vector<T>& v)

{

reserve(v.capacity());

for (auto& e : v)

{

push_back(e);

}

}

拷贝构造，就是遍历 对象

v

v

v，将

v

v

v 的值全部

p

u

s

h

push

push_

b

a

c

k

back

back 进

t

h

i

s

this

this 中。这里范围for用了引用，是为了减少拷贝，而为了避免频繁的扩容，使用

r

e

s

e

r

v

e

reserve

reserve 提前开辟空间。

11.3 迭代器区间构造 与 n 个 value 构造

11.3.1 迭代器区间构造

在stl库中，还提供了一个构造方法：迭代器区间构造

这里讲一个新的知识点：类模板里面的成员函数可以是函数模板

为什么要用模板呢？这样不行吗？

<code>vector(iterator first, iterator last)

如果是这样的话，那么迭代器构造只能用

v

e

c

t

o

r

vector

vector 迭代器构造，如果是函数模板的话可以用任意的迭代器进行构造

代码如下：

template<class InputIterator>

vector(InputIterator first, InputIterator last)

{ -- -->

while (first != last)

{

push_back(*first);

++first;

}

}

测试：

void test6()

{

list<int> l1;

l1.push_back(1);

l1.push_back(2);

l1.push_back(3);

l1.push_back(4);

l1.push_back(5);

l1.push_back(6);

vector<int> v1(++l1.begin(), --l1.end());

print_vector(v1);

}

运行结果：

可见，迭代器区间可以用任意容器迭代器进行初始化，但它要求类型是匹配的

11.3.2 n 个value构造

n

n

n 个

v

a

l

u

e

value

value 的构造很简单，不断

p

u

s

h

push

push_

b

a

c

k

back

back 就行

<code>vector(size_t n, const T& val = T())

{ -- -->

reserve(n);

while (n--)

{

push_back(val);

}

}

11.3.3 注意事项

调用

n

n

n 个

v

a

l

u

e

value

value 的构造函数时，会出现一个很奇怪的报错

void test7()

{

vector<int> v(10, 1);

print_vector(v);

}

为什么我调用的时

n

n

n 个

v

a

l

u

e

value

value 的构造，结果报错报到<code>迭代器区间的构造了呢？

这是因为编译器把vector<int> v(10, 1);中的 10 和 1 识别成两个迭代器了。

为什么会这样呢？编译器有一个原则，那就是匹配最匹配的

我们先来看

n

n

n 个

v

a

l

u

e

value

value 的构造

vector(size_t n, const T& val = T())对 10 和 1 来说，T 是

i

n

t

int

int 是确定的

但是

n

n

n 是

s

i

z

e

size

size_

t

t

t，

i

n

t

int

int 要进行类型转换

再看迭代器区间构造

vector(InputIterator first, InputIterator last)，它实例化出来是两个

i

n

t

int

int，不用类型转换，所以编译器选择迭代器区间构造

那怎么解决呢？

stl库中选择重载多个

n

n

n 个

v

a

l

u

e

value

value 的构造函数，让你永远有更好的选择

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

{ -- -->

reserve(n);

while (n--)

{

push_back(value);

}

}

vector(int n, const T& value = T())

{

reserve(n);

while (n--)

{

push_back(value);

}

}

vector(long long n, const T& value = T())

{

reserve(n);

while (n--)

{

push_back(value);

}

}

12 赋值运算符重载

赋值运算符重载分为现代写法与传统写法，这在

s

t

r

i

n

g

string

string 的模拟实现中讲过类似的，这里就不再细讲了，我们直接看代码

12.1 传统写法

void clear()

{

_finish = _start;

}

vector<T>& operator=(const vector<T>& v)

{

clear();

if (this != &v)

{

reserve(v.capacity());

const_iterator it = v.begin();

while (it != v.end())

{

push_back(*it);

++it;

}

}

return *this;

}

12.2 现代写法

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> tmp)

{

swap(tmp);

return *this;

}

注：类里面可以用类名替代类型，类外面不行

比如这样：用 类名vector 替代 类型vector<int>

void swap(vector& v)

{

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

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

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

}

vector<T>& operator=(vector tmp)

{

swap(tmp);

return *this;

}

不过并不推荐这种写法，因为对新手来说不友好。

13 源码

//vector.h

#pragma once

#include<iostream>

#include<assert.h>

#include<vector>

namespace my_vector

{

template<class T>

class vector

{

public:

// Vector的迭代器是一个原生指针

typedef T* iterator;

typedef const T* const_iterator;

iterator begin()

{

return _start;

}

iterator end()

{

return _finish;

}

const_iterator begin() const

{

return _start;

}

const_iterator end() const

{

return _finish;

}

size_t size() const

{

return _finish - _start;

}

size_t capacity() const

{

return _end_of_storage - _start;

}

bool empty()

{

return _start == _finish;

}

void clear()

{

_finish = _start;

}

vector()

:_start(nullptr)

, _finish(nullptr)

, _end_of_storage(nullptr)

{ }

// C++11 前置生成默认构造

vector() = default;

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

{

reserve(n);

while (n--)

{

push_back(value);

}

}

vector(int n, const T& value = T())

{

reserve(n);

while (n--)

{

push_back(value);

}

}

vector(long long n, const T& value = T())

{

reserve(n);

while (n--)

{

push_back(value);

}

}

vector(const vector<T>& v)

{

reserve(v.capacity());

const_iterator it = v.begin();

while (it != v.end())

{

push_back(*it);

it++;

}

}

template<class InputIterator>

vector(InputIterator first, InputIterator last)

{

InputIterator tmp = first;

//不能是< , list那些就不行

while (tmp != last)

{

push_back(*tmp);

tmp++;

}

}

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> tmp)

{

swap(tmp);

return *this;

}

~vector()

{

if(_start)

{

delete[] _start;

_start = _finish = _end_of_storage;

}

}

T& operator[](size_t n)

{

assert(n < size());

return *(_start + n);

}

const T& operator[](size_t n) const

{

assert(n < size());

return *(_start + n);

}

void reserve(size_t n);

void push_back(const T& x);

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

void pop_back();

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

iterator erase(iterator pos);

private:

iterator _start = nullptr; // 指向数据块的开始

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

iterator _end_of_storage = nullptr; // 指向存储容量的尾

};

template<class T>

void vector<T>::push_back(const T& x)

{

if (size() == capacity())

{

size_t new_capacity = capacity() ? 2 * capacity() : 4;

reserve(new_capacity);

}

*_finish = x;

_finish++;

}

template<class T>

void vector<T>::reserve(size_t n)

{

if (n > capacity())

{

iterator tmp = new T[n];

size_t preserve_size = size();

int m = 0;

iterator it = begin();

while (it != end())

{

*(tmp + m) = *it;

++m;

++it;

}

//memcpy(tmp, _start, sizeof(T) * size());

delete[] _start;

_start = tmp;

_finish = _start + preserve_size;

_end_of_storage = _start + n;

}

}

template<class T>

void vector<T>::resize(size_t n, const T& value)

{

if (n <= size())

{

_finish = _start + n;

}

else

{

reserve(n);

int m = n - size();

while (m--)

{

*_finish = value;

++_finish;

}

}

}

template<class T>

void vector<T>::pop_back()

{

assert(!empty());

_finish;

}

/

template<class T>

typename vector<T>::iterator vector<T>::insert(typename vector<T>::iterator pos, const T& x)

{

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

/*if (size() == capacity())

{

size_t new_capacity = capacity() ? 2 * capacity() : 4;

reserve(new_capacity);

}*/

//相对位置

if (size() == capacity())

{

size_t len = pos - _start;

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

pos = _start + len;

}

iterator it = end();

while (it > pos)

{

*it = *(it - 1);

it--;

}

*pos = x;

++_finish;

return pos;

}

template<class T>

typename vector<T>::iterator vector<T>::erase(typename vector<T>::iterator pos)

{

assert(pos < end() && pos >= begin());

iterator it = pos + 1;

while (it != end())

{

*(it - 1) = *it;

++it;

}

--_finish;

return pos;

}

template<class T>

void print_vector(const vector<T>& v)

{

typename vector<T>::const_iterator it = v.begin();

while (it != v.end())

{

std::cout << *it << " ";

++it;

}

std::cout << std::endl;

}

template<class Container>

void print_container(const Container& v)

{

auto it = v.begin();

while (it != v.end())

{

std::cout << *it << " ";

++it;

}

std::cout << std::endl;

}

}