感谢大佬的光临各位，希望和大家一起进步，望得到你的三连，互三支持，一起进步

数据结构习题_LaNzikinh篮子的博客-CSDN博客

初阶数据结构_LaNzikinh篮子的博客-CSDN博客

收入专栏：C++_LaNzikinh篮子的博客-CSDN博客

其他专栏：c语言基础_LaNzikinh篮子的博客-CSDN博客

个人主页：LaNzikinh-CSDN博客

文章目录

前言一.vector的介绍及使用二.vector的底层和实现总结

---

前言

我们前面讲解了标准库里的string类，讲解了他的实现，用法，现在我们来讲解另一个在标准库中的类，vector类

---

一.vector的介绍及使用

介绍及补充

vector就像数组一样，向量对其元素使用连续的存储位置，这意味着也可以使用指向其元素的常规指针上的偏移量来访问它们的元素，并且与在数组中一样高效。但与数组不同的是，它们的大小可以动态变化，其存储由容器自动处理。可以把vector理解成C语言中，学过的数据结构中的顺序表

vector这个类，我们把它看成顺序表，那么存放顺序表的东西不像是我们以前C语言中只能存放整形的数据，他还可以存放各种各样的数据，我甚至都可以存放一个类在里面，比如说存放，字符型浮点型等各种数据，所以说为了保证可以存放的多样性，那么他肯定是用一个那模板去完成的这个结构，所以说我们如果要创建一个这样的对象，我们用内模板的实例化，注意内模板只有显示实例化，所以我们要提前在括号内标注好它的类型

<code>int main()

{

vector<int> v1;

vector<char> a;

vector<vector<int>> a2;

return 0;

}

很多人就会有一个疑问这个vector<vector<int>> a2，到底表示什么。

先说结果：这个是初始化了一个二维数组

初始化

最为常用的5种初始化的方式。

1.vector<int> v; //默认初始化，最常用

2.vector<int> v = {1,2,3.0,4,5,6,7};

3.vector<int> v(7,3);

4.vector<int> v(v.begin()+2,v.end()-1);

vector<vector<int>> a2

也可以用下标去证明，可以访问到

也可以来看一下底层代码

注意：因为是引用返回，所以返回的是对象的本身，所以是可以修改的

使用

其实经过前面string的学习，我们也大致了解了一些接口，在C++中这些标准库中的类模板的接口都是大体相同的，所以很多东西的接口的用法，其实都跟string是一样的，但是也有细微的区别。

两个扩容函数reserve，resize

resize是改变vector的size，resize是改变vector的capacity,reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题.resize在开空间的同时还会进行初始化，影响size。

<code>vector<int> v(10, 1);

v.reserve(20);

cout << v.size() << endl;

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

v.resize(15, 2);

cout << v.size() << endl;

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

v.resize(25, 3);

cout << v.size() << endl;

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

v.resize(5);

cout << v.size() << endl;

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

对于reserve来说不存在缩容，但是在string中，他是会缩容的，对于resize来说，capacity是不改变的，size会变，若n>size（resize(n,1);），扩容插入数据，如果n<size,size会缩，但是capacity是不改变。

补充：可以用vector<char> v；来代替string s吗？

不可以，因为在string中，存在\0.

接口函数的使用就不再做过多的展示了和前面的string的用法差不多，实在不会的可以自己去看一下文档一些参数的使用变化，这里主要还是讲底层和一些细节

下面这些是一些重要的接口函数，会使用就可以了

二.vector的底层和实现

我们讲底层之前可能跟我们之前讲的很多东西有变化，但其实本质是一样的，通过观察这个底层的图片来看，vector的底层跟我们之前实现的数据结构的底层不一样，他好像不在由size，capacity来控制的，而是有三个指针去控制的，但实际上本质是一模一样的，只不过是变成了三个指针控制

<code>iterator _start = nullptr;

iterator _finish = nullptr;

iterator _end_of_storage = nullptr;

_finish就是我们的size， _end_of_storage就是我们的capacity

完成模拟实现时，记得先typedef我们的迭代器

typedef T* iterator;

typedef const T* const_iterator;

2.1构造，析构，拷贝构造，赋值，初始化函数

每次模拟实现的时候都先来一些比较经典的函数，先内敛函数再其他成员函数

构造函数

这里的构造函数，我们直接调用编译器器的即可，无需自己实现，这里要注意一个东西，不要写错了，我自己就犯了这样的错误。=default是用编译器生成的，=delete才是删除，要注意单词。

vector() = default;

拷贝构造

扩容函数还没有实现，但是是这个原理

vector(const vector<T>& v)

{

reserve(v.size());

for (auto& e : v)

{

push_back(e);

}

}

初始化

他其实还存在很多种的初始化方式，我们前面也列举了，他还可以初始化一个类，所以这些我们都要实现

无论你是什么样的数据，即便你给或者没给我都可以这样用，const T& val = T()；给了一个缺省值，你给任意数据给我，如果你什么都不传的话，我就用这个来初始化，如果你传了的话，那我就接收

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

{

reserve(n);

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

{

push_back(val);

}

}

类初始化，类模板的成员函数，还可以继续是函数模版，随便那个类型的迭代器都可以

这个地方用了一个迭代器类型，你要把他的迭代器传过来就可以了，无论你是哪个地方的迭代器都可以

template <class InputIterator>

vector(InputIterator first, InputIterator last)

{

while (first != last)

{

push_back(*first);

++first;

}

}

赋值

operator=，和之前的string差不多的思想，如果不相等的话就清除，相等的话就循环，但是这样子写，感觉有一点繁琐和麻烦，所以现在有一种全新的写法插进来就可以了。

// v1 = v3

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

{

if (this != &v)

{

clear();

reserve(v.size());

for (auto& e : v)

{

push_back(e);

}

}

return *this;

}

新

我直接写一个交换函数，把他们直接把它复制来，只要一个函数即可，也很省事，注意这个地方也涉及到了一个深浅拷贝的问题，我们后面会用到的。

void swap(vector<T>& v)

{

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

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

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

}

// v1 = v3

//vector& operator=(vector v)

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

{

swap(v);

return *this;

}

析构

~vector()

{

if (_start)

{

delete[] _start;

_start = _finish = _end_of_storage = nullptr;

}

}

2.2扩容函数reserve，resize

reserve

先用一个变量来记录一下我的size大小，然后开辟一个你给我大小的空间，之后再依次赋值，然后删去最开始的空间，注意是三个指针，然后再依次给予就可以了，思想并不难。

void reserve(size_t n)

{

if (n > capacity())

{

size_t old_size = size();

T* tmp = new T[n];

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

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

{

tmp[i] = _start[i];

}

delete[] _start;

_start = tmp;

_finish = tmp + old_size;

_end_of_storage = tmp + n;

}

}

为什么memcpy不可以？

因为memcpy是浅拷贝，我们之前的赋值调用了交换函数，他是深拷贝，所以这个题目我们用循环赋值的方法来解决，前拷贝对于内置类型可以，但是对于自定义类型是不行的，自定类型只能用深拷贝，拷贝

resize

如果你给了我，我就帮你初始化，没给我那么就是你那个类型的自动去初始化，我调用你的构造函数，T val = T()，让你这个类型去帮我初始化，注意因为在vector中，resize会存在缩容，所以这个地方我们实现的时候也要体现

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

{

if (n < size())

{

_finish = _start + n;

}

else

{

reserve(n);

while (_finish < _start + n)

{

*_finish = val;

++_finish;

}

}

}

2.3insert和erase（难，存在迭代器失效问题）

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

例子1：野指针

这个insert的实现，就是一个明显的迭代器失效

void insert(iterator pos, const T& x)

{

assert(pos >= _start);

assert(pos <= _finish);

// 扩容

if (_finish == _end_of_storage)

{

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

}

iterator end = _finish - 1;

while (end >= pos)

{

*(end + 1) = *end;

--end;

}

*pos = x;

++_finish;

}

他的思想是没有任何问题的和string中的insert实现是一样的，但是问题就在扩容那个地方和返回值，我们先说扩容来看一个图片就知道了

这个扩容他是创造了一个新的空间，但是我的pos这个迭代器还只向着原空间，你释放了之前那个空间迭代器也释放了，这就是一个野指针，也是造成迭代器失效的一个原因，还一个原因就是返回值，因为我们知道形参的改变不能影响实参，如果你不去设置返回值的话，我出了这个函数还是野指针，所以说我需要一个返回值来接收，这样子才是真正的改变

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

{

assert(pos >= _start);

assert(pos <= _finish);

// 扩容

if (_finish == _end_of_storage)

{

size_t len = pos - _start;

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

pos = _start + len;

}

iterator end = _finish - 1;

while (end >= pos)

{

*(end + 1) = *end;

--end;

}

*pos = x;

++_finish;

return pos;

}

这样就对了

例子2：位置改变

vector<int> v = { 1,2,3,4 };

v.insert(p, 20);

(*p) *= 10;

由于挪动的数据，已经不是指向原来的位置了，所以我们可以认定insert以后的迭代器全部失效了，不用再访问了

解决办法，要用返回值来更就可以了

<code>p = v.insert(p, 20);

erase

他的实现思路和string中的erase是一样的，但是他也存在迭代器失效问题

void erase(iterator pos)

{

assert(pos >= _start);

assert(pos < _finish);

iterator it = pos + 1;

while (it != end())

{

*(it - 1) = *it;

++it;

}

--_finish;

}

如果我要删除一个数据，我的pos也会被删除，所以我们erase的迭代器失效，要用返回值来更就可以了

<code>it = s.erase(it);

2.4头插，尾插函数

void push_back(const T& x)

{

// 扩容

if (_finish == _end_of_storage)

{

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

}

*_finish = x;

++_finish;

}

void pop_back()

{

assert(!empty());

--_finish;

}

2.5迭代器函数

iterator begin()

{

return _start;

}

iterator end()

{

return _finish;

}

const_iterator begin() const

{

return _start;

}

const_iterator end() const

{

return _finish;

}

2.6简单的内联函数

void clear()

{

_finish = _start;

}

size_t size() const

{

return _finish - _start;

}

size_t capacity() const

{

return _end_of_storage - _start;

}

bool empty() const

{

return _start == _finish;

}

2.7下标访问函数

T& operator[](size_t i)

{

assert(i < size());

return _start[i];

}

2.8输出函数

注意：在vector中，没有流插入和流提取，所以说要自己写一个非成员函数来完成输出的工作

template<class T>

void print_vector(const vector<T>& v)

{

// 规定，没有实例化的类模板里面取东西，编译器不能区分这里const_iterator

// 是类型还是静态成员变量

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

auto it = v.begin();

while (it != v.end())

{

cout << *it << " ";

++it;

}

cout << endl;

for (auto e : v)

{

cout << e << " ";

}

cout << endl;

}

如果是vector<T>::const_iterator，这里不能确定const_iterator是类中重定义的类型还是静态变量，编译期间无法确定，所以需要显式用typename指定这个const_iterator是一个类型。或者直接用auto

因为vector也可以存放模板，所以

template<class Container>

void print_container(const Container& v)

{

for (auto e : v)

{

cout << e << " ";

}

cout << endl;

}

---

总结

关于vector的讲解，到这里就没有了，下次将继续推进标准库中的容器，文章的难点主要还是在于这个迭代器失效问题，把容器讲得差不多了之后会专门做一个迭代器的章节