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

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 – 构造

构造的使用：

int main(){vector<int> first;//使用vector模板实例化一个对象vector<int> second(4, 100);//4个数据，每个数据为100vector<int> third(second.begin(), second.end());//迭代器区间初始化vector<int> forth(second);//拷贝初始化return 0;}

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

使用initializer_list进行初始化：

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 9return 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 9return 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函数传入的位置只能是迭代器：

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 9for (auto e : v){cout << e << " ";}cout << endl;v.erase(v.begin() + 2);//20 1 2 3 4 5 6 7 8 9for (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的使用：

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语言的不同，下面我们用代码来实现一下杨辉三角，实现起来也是比较轻松的：

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实现时的注意事项在下边会一一点出来，所以这里直接放代码：

//因为模板函数的声明和定义分离可能会造成一些问题，所以我们只使用两个文件：.h和test.cppnamespace 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 – 类模板中的函数模板问题

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

//迭代区间构造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中深浅拷贝问题