C++第六讲：STL--vector的使用及模拟实现

1.vector简介2.vector的常见接口介绍2.1constructor -- 构造2.2destructor -- 析构2.3begin、end2.3.1vector和string的区别、vector<string>

2.4rbegin、rend2.5cbegin、cend2.6crbegin、crend2.7size、max_size、resize、capacity、empty、reserve2.8shrink_to_fit2.9operator[]、at2.10front、back2.11data2.12assign2.13push_back、pop_back2.14insert、erase2.15swap、clear2.16vector扩容规则

3.vector在OJ题中的使用3.1练习13.2练习2

4.vector的模拟实现4.1vector标准库中的源码观察4.2vector的实现4.3vector实现注意事项4.3.1注意事项14.3.2注意事项2 -- 迭代器失效问题4.3.2.1扩容引起的迭代器失效4.3.2.1.1情况14.3.2.1.2情况2

4.3.2.2删除数据，数据位置移动导致的迭代器失效

4.3.3注意事项3 -- 类模板中的函数模板问题4.3.4注意事项4 -- sting中深浅拷贝问题

1.vector简介

vertor是一个真正的容器，底层实现是一个动态开辟的数组：

所以说我们可以将vector简单地理解成：

vector的一些接口的使用和string相同，所以对于那些简单的使用，就一笔带过，本文详细要讲的还是vertor的模拟实现，以及一些其它的科普知识

2.vector的常见接口介绍

尽管不会详细讲述接口的作用，但是还是会讲接口一一列出来

2.1constructor – 构造

构造的使用：

<code>int main()

{ -- -->

vector<int> first;//使用vector模板实例化一个对象

vector<int> second(4, 100);//4个数据，每个数据为100

vector<int> third(second.begin(), second.end());//迭代器区间初始化

vector<int> forth(second);//拷贝初始化

return 0;

}

这些都是一些简单的构造，要着重处理的是：

使用initializer_list进行初始化：

<code>int main()

{ -- -->

vector<int> v = { 10, 20, 30, 40 };//使用数组进行初始化

vector<int> v1({ 20, 30, 40 });//和上面的功能是一样的

//使用数组初始化的底层其实是遍历数组，将数组中的元素一个一个地尾插到vector中

//auto il1 = { 1, 2, 3, 4, 5, 6 };

//initializer_list<int> il2 = { 1, 2, 3, 4, 5, 6 };//等价于上面的auto

//int a[] = { 1, 2, 3, 4, 5, 6 };

return 0;

}

2.2destructor – 析构

2.3begin、end

迭代器，使用起来也十分简单：

int main()

{

vector<int> v({ 1, 2, 3, 4, 5, 6, 7, 8, 9 });

//这表明迭代器的范围应该在vector<int>中，这样就可以更加清楚地理解迭代器了

vector<int>::iterator it = v.begin();

while (it != v.end())

{

cout << *it << " ";

it++;

}

cout << endl;//1 2 3 4 5 6 7 8 9

return 0;

}

既然有了迭代器，那么就可以使用范围for：

int main()

{

vector<int> v({ 1, 2, 3, 4, 5, 6, 7, 8, 9 });

for (auto e : v)

{

cout << e << " ";

}

cout << endl;//1 2 3 4 5 6 7 8 9

return 0;

}

2.3.1vector和string的区别、vector

下面还有一种使用范围for时需要注意的地方：

int main()

{

//看下面两个有什么区别：

vector<char> v;

string s1;

//1.vector中没有关于字符串的概念，只有尾插和尾删，所以并不能直接插入一个字符串，而string中能

//2.vector中并没有对于字符串特有的操作，比如连接、查找子串、替换子串等

//3.vector中不仅能存储字符数据，还能够针对于其它任何类型的数据，而string是专门处理字符的类

return 0;

}

int main()

{

//但是我们可以这样写：

vector<string> v;

//这样就可以使用针对字符串的操作了：

string s1 = "张三";

v.push_back(s1);

v.push_back("李四");

for (auto e : v)

{

cout << e << " ";

}

cout << endl;

v[0] += 'x';//这里使用的是string中的+=，因为v[0]就是一个string类的对象

v[0] += "apple";

for (auto e : v)

{

cout << e << " ";

}

cout << endl;

//v[0][0]++;//张 -》 峙

//C++中，对于汉字的编码，是通过汉字的后一个字节来将相同读音的汉字排在一起的

v[0][1]++;//张 -》 掌

v[0][1]++;//掌 -》 涨

for (auto e : v)

{

cout << e << " ";

}

cout << endl;

return 0;

}

但是这里会出现问题：

2.4rbegin、rend

反向迭代器

2.5cbegin、cend

const_iterator

2.6crbegin、crend

const_reverse_iterator

2.7size、max_size、resize、capacity、empty、reserve

2.8shrink_to_fit

这个接口是将capacity改变成适合它的size的函数，但是不建议使用，首先，它只是一个请求，并不是强制的，其次，如果实现决定减少容量，可能会造成内存的重新分配，导致所有的迭代器会失效，迭代器的失效在后边会详细阐述

2.9operator[]、at

访问，[]访问越界时会断言报错，at是抛异常

2.10front、back

放回的是头、尾元素的引用

2.11data

vector的实现底层是一个数组，而data函数的作用就是将底层的数组返回

2.12assign

将新内容赋给vector，覆盖原来的旧内容

2.13push_back、pop_back

尾插、尾删元素

2.14insert、erase

不同的是，vector中的insert和erase函数传入的位置只能是迭代器：

<code>int main()

{ -- -->

vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

v.insert(v.begin(), 20);

v.insert(v.begin()+2, 10);//20 1 10 2 3 4 5 6 7 8 9

for (auto e : v)

{

cout << e << " ";

}

cout << endl;

v.erase(v.begin() + 2);//20 1 2 3 4 5 6 7 8 9

for (auto e : v)

{

cout << e << " ";

}

cout << endl;

return 0;

}

2.15swap、clear

clear函数不改变capacity

2.16vector扩容规则

结论：vector中的扩容是按照1.5倍来进行扩容的

//测试代码：

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

}

}

}

3.vector在OJ题中的使用

3.1练习1

链接: 只出现一次的数字

这道题实现十分简单，只需要异或即可，重点是观察vector的使用：

<code>class Solution { -- -->

public:

int singleNumber(vector<int>& nums) {

int sum = 0;

for(auto e : nums)

{

sum ^= e;

}

return sum;

}

};

3.2练习2

链接: 杨辉三角OJ

这一题就相当不一样了，我们通过画图来解释一下：

所以这里我们就看出了C++和C语言的不同，下面我们用代码来实现一下杨辉三角，实现起来也是比较轻松的：

<code>class Solution { -- -->

public:

vector<vector<int>> generate(int numRows) {

vector<vector<int>> vv(numRows);

for(int i = 0; i<numRows; i++)

{

vv[i].resize(i+1, 1);//使用resize能够在开辟空间的同时进行初始化，所以说更好用

}

for(int i = 2; i<numRows; i++)

{

for(int j = 1; j<vv[i].size()-1; j++)

{

vv[i][j] = vv[i-1][j] + vv[i-1][j-1];

}

}

return vv;

}

};

4.vector的模拟实现

4.1vector标准库中的源码观察

以后我们对于文档的查看会相当频繁，也会十分重要，所以我们现在看一下原码：

源码可能有几百行，也有可能会有几千行，所以当我们看源码时，不能够逐字逐句地去看，这样效率很低，我们首先要做的就是观察这些源码的大致框架,这里我们只看一个stl函数：push_back，所以我们只拿这一个函数举例：

通过上述分析，我们可以了解该函数的使用了，但是也体会到了源文件的恐怖！了解了上述的源文件之后，我们也可以看着尝试写出自己的vector：

4.2vector的实现

因为对于vector实现时的注意事项在下边会一一点出来，所以这里直接放代码：

<code>//因为模板函数的声明和定义分离可能会造成一些问题，所以我们只使用两个文件：.h和test.cpp

namespace Mine

{ -- -->

template<class T>

class vector

{

public:

typedefT* iterator;

typedefconst T* const_iterator;

//无参构造函数

vector()

:_start(nullptr)

, _finish(nullptr)

, _endofstorage(nullptr)

{ }

//析构函数

~vector()

{

if (_start)

{

delete[] _start;

}

_start = _finish = _endofstorage = nullptr;

}

//size、capacity的返回

size_t size() const

{

return _finish - _start;

}

size_t capacity() const

{

return _endofstorage - _start;

}

尾插

//void push_back(const T& x)

//{

////既然要插入，那么就要检查空间的大小是否充足

//if (_finish == _endofstorage)

//{

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

//}

//*_finish = x;

//_finish++;

//}

//reserve -- 空间开辟

void reserve(size_t n)

{

//reserve不一定只在push_back函数中使用，还可能会直接使用

//所以这里要比较n和空间的大小

if (n > capacity())

{

//为了改变tmp的指向，我们需要知道原来start和tmp差的距离为多少

size_t oldSize = size();

//开辟空间的逻辑为：先创建一块空间，再将原来空间的内容复制过来

T* tmp = new T[n];

if (_start)

{

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

for (int i = 0; i < oldSize; i++)

{

tmp[i] = _start[i];

}

delete[] _start;

}

_start = tmp;

_finish = _start + oldSize;

_endofstorage = _start + n;

}

}

//访问操作符

T& operator[](size_t pos)

{

assert(pos < size());

return _start[pos];

}

//迭代器实现

iterator begin()

{

return _start;

}

iterator end()

{

return _finish;

}

const_iterator begin() const

{

return _start;

}

const_iterator end() const

{

return _finish;

}

//判空

bool empty()

{

return _endofstorage == _finish;

}

//删除最后一个元素

void pop_back()

{

assert(!empty);

_finish--;

}

//尾插

void push_back(const T& x)

{

既然要插入，那么就要检查空间的大小是否充足

//if (_finish == _endofstorage)

//{

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

//}

//*_finish = x;

//_finish++;

insert(_finish, x);

}

//插入函数

iterator insert(iterator pos, const T& x)

{

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

//对于插入数据，仍然需要判断空间的大小

if (_finish == _endofstorage)

{

//和上面的处理相似，需要先知道pos位置到开始位置的距离，然后再修正pos的位置即可

int len = pos - _start;

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

pos = _start + len;

}

//将pos之后的数据向后移动一位

iterator i = _finish -1;

while (i >= pos)

{

*(i + 1) = *i;

i--;

}

*pos = x;

_finish++;

return pos;

}

//erase -- 删除函数的实现

iterator erase(iterator pos)

{

assert(pos >= _start);

assert(pos < _finish);

//要删除pos位置的数据，我们将pos位置之后的数据向前移动就行了

iterator it = pos + 1;

while (it < _finish)

{

*(it - 1) = *it;

it++;

}

_finish--;

return pos;

}

//resize -- 重新分配空间

void resize(T& n, T& val = T())//因为传入的不一定是什么类型，所以T()就表示调用T类型对象的构造函数

//默认构造其实是没有默认构造的，而有了模板之后，C++对默认构造进行了升级，那么就可以使用默认构造了

{

if (n <= size())

{

//当要缩容时，直接改变_finish的指向即可

_finish = _start + n;

}

else

{

//需要扩容时，扩容，而且将扩容的空间进行初始化

reserve(n);

while (_finish < _start + n)

{

*_finish = val;

_finish++;

}

}

}

//拷贝构造函数

vector(const vector<T>& v)

{

reserve(v.capacity());

//这里我们可以按照传统的写法：开空间，拷贝，也可以这样：

for (auto& e : v)

{

push_back(e);

}

}

//交换函数

void swap(vector<T>& v)

{

swap(_start, v._start);

swap(_finish, v._finish);

swap(_endofstorage, v._endofstorage);

}

//赋值运算符重载

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

{

swap(*this, v);

return *this;

}

//迭代区间构造

template <class InputIterator>

//写成函数模板的优点为：扩大了传入参数的范围，可以是int形，甚至可以是string形

vector(InputIterator first, InputIterator last)

{

while (first != last)

{

push_back(*first);

first++;

}

}

//n个val进行的构造

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

{

//先写reserve是为了避免一直开辟空间的问题

reserve(n);

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

{

push_back(val);

}

}

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

{

reserve(n);

for (int i = 0; i < n; i++)

{

push_back(val);

}

}

//使用数组进行初始化

vector(initializer_list<T> il)

{

reserve(il.size());

for (auto& e : il)

{

push_back(e);

}

}

private:

iterator _start;

iterator _finish;

iterator _endofstorage;

};

}

4.3vector实现注意事项

4.3.1注意事项1

4.3.2注意事项2 – 迭代器失效问题

4.3.2.1扩容引起的迭代器失效

这次引起的迭代器失效本质是野指针问题，但是迭代器并不就是指针，VS所实现的迭代器就不仅仅是一个指针，而是一个复杂的类，其中除了对于指针的封装，而且还增加了对于迭代器的一些检查，我们可以通过指令来看到：

4.3.2.1.1情况1

4.3.2.1.2情况2

在vector类和string类的标准库实现中，并没有find接口的实现，但是，在标准库中，有find函数，所以我们可以直接使用标准库中的find函数

4.3.2.2删除数据，数据位置移动导致的迭代器失效

4.3.3注意事项3 – 类模板中的函数模板问题

模板类的成员函数，也可以时函数模板：

<code>//迭代区间构造

template <class InputIterator>

//写成函数模板的优点为：扩大了传入参数的范围，可以是int形，甚至可以是string形

vector(InputIterator first, InputIterator last)

{ -- -->

while (first != last)

{

push_back(*first);

first++;

}

}

//我们可以这样进行使用：

int main()

{

Mine::vector<int> v1;

v1.push_back(1);

v1.push_back(2);

v1.push_back(3);

v1.push_back(4);

v1.push_back(5);

for (auto e : v1)

{

cout << e << " ";

}

cout << endl;

//1.可以使用vector的迭代区间进行构造

vector<int> v2(v1.begin(), v1.end());

for (auto e : v2)

{

cout << e << " ";

}

cout << endl;

//2.可以使用string的迭代区间按进行构造

string s1("hello");

vector<int> v3(s1.begin(), s1.end());

for (auto e : v3)

{

cout << e << " ";

}

cout << endl;

return 0;

}

vector中还有一个构造：n个val进行的构造：

//n个val进行的构造

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

{

//先写reserve是为了避免一直开辟空间的问题

reserve(n);

fot(size_t i = 0; i < n; i++)

{

push_back(val);

}

}

但是当我们这样写时，会发生错误：

int main()

{

Mine::vector<int> v1;

v1.push_back(1);

v1.push_back(2);

v1.push_back(3);

v1.push_back(4);

v1.push_back(5);

for (auto e : v1)

{

cout << e << " ";

}

cout << endl;

Mine::vector<int> v2(10, 1);//err

//vector<double> v2(10, 1.1);

for (auto e : v2)

{

cout << e << " ";

}

cout << endl;

return 0;

}

因为Mine::vector v2(10, 1);调用的是vector(InputIterator first, InputIterator last)函数，该函数的参数更加匹配，所以我们要再创建一个int类型的构造来解决这个问题：

//n个val进行的构造

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

{

//先写reserve是为了避免一直开辟空间的问题

reserve(n);

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

{

push_back(val);

}

}

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

{

reserve(n);

for (int i = 0; i < n; i++)

{

push_back(val);

}

}

4.3.4注意事项4 – sting中深浅拷贝问题