【C++笔记】深浅拷贝以及vector的深度剖析及其实现

【C++笔记】深浅拷贝以及vector的深度剖析及其实现

?个人主页：大白的编程日记

?专栏：C++笔记

---

文章目录

【C++笔记】深浅拷贝以及vector的深度剖析及其实现前言一.编码1.1编码的定义1.2编码的理解1.3常见编码表 二.深浅拷贝三.引用计数与写时拷贝三.vector3.1vector的介绍及使用3.2 vector的增删查改3.3vector嵌套 四.vector深度剖析及模拟实现4.1vector的定义4.1 reserve4.2 迭代器4.3 构造和拷贝构造4.4 size4.5 push_back4.6 capacity4.7 pop_back4.8 empty4.9 clear4.10 resize4.11 operator= 五.迭代器失效及语法问题5.1语法问题5.2迭代器失效 后言

前言

哈喽，各位小伙伴大家好！上期我们讲了string的深度剖析和实现。今天我们来讲一下编码和string的深浅拷贝以及vector。话不多说，我们进入正题！

一.编码

1.1编码的定义

我们都知道计算机只能存储0或1。那像平时我们的文字或者英文，这些字符如何在计算机存储呢？这时有个编码表的东西就出来了。我们让一个字符和一个整形对应。也就是让字符和整形建立映射关系。这样计算机存储符号时存储对应的整形即可。所以编码本质就是——值和符号的映射编码关系。

1.2编码的理解

例如英美的文字都是由字母组成的。那他就只需要让字母与值建立映射关系即可。所以他们就发明出来了ascll码表。

ascll码表的本质——英文符号和值的映射关系。

所以我们看到字符在内存中存储的是字符对应的ascll码值。

我们输出字符的时候，编译器就会根据内存中存储的值去查编码表，打印出对应的符号。所以打印的过程是查编码表的过程。

验证
可能说前面存的是字符，大家觉得不太相信。
那现在我们存储对应的ascll码值。

发现程序并不是打印数字。而是字符。这就是因为前面我们说的打印的过程是查编码表的过程。这些数字对应ascll码表中的符号就是abc\0所以打印出来的就是abc.

乱码
所以乱码就是存的值和编码表对应不上，例如存的是ascll编码表的，查的编码表缺是其他的。值和表对应不上就会出现乱码。而我们平时看到的烫烫烫或屯屯屯就是因为我们没有初始化，里面的值是编译器给的默认随机值。随机值去编码表查到的值是什么打印的就是什么。

1.3常见编码表

那大家看到ascll编码只适用与英美。而我们的汉字博大精深，ascll码表表示不了我们的汉字。而计算机发展需要兼顾全世界的国家。因此一个适用全世界文字的编码表就出来了——Unicode.统一码也叫万国码。

Unicode里面给出了三种编码方式：
分别是：UTF-8、UTF-16、UTF-32。

UTF-8
UTF-8是一种变长编码方式。这样的好处就可以兼容ascll码表。
因为兼容性更好所以使用的更多。
- UTF-16
UTF-32

所以为了兼容不同的编码方式。库里的string写成了模版。

常见的汉字是用两个字节编码一个汉字。
还有我们国家自己搞了一个编码表——GBK，大家可以自己了解一下。

二.深浅拷贝

class String{public:/*String():_str(new char[1]){*_str = '\0';}*///String(const char* str = "\0") 错误示范//String(const char* str = nullptr) 错误示范String(const char* str = ""){// 构造String类对象时，如果传递nullptr指针，可以认为程序非if (nullptr == str){assert(false);return;}_str = new char[strlen(str) + 1];strcpy(_str, str);}~String(){if (_str){delete[] _str;_str = nullptr;}}private:char* _str;};// 测试void TestString(){String s1("hello bit!!!");String s2(s1);}

这段代码运行崩溃。为什么呢？
因为s1和s2指向同一块空间，就会对同一块空间析构两次。
导致s1和s2指向同一块空间的原因就是因为浅拷贝。

上述String类没有显式定义其拷贝构造函数与赋值运算符重载，此时编译器会合成默认的，当用s1构造s2时，编译器会调用默认的拷贝构造。最终导致的问题是，s1、s2共用同一块内存空间，在释放时同一块空间被释放多次而引起程序崩溃，这种拷贝方式，称为浅拷贝。

浅拷贝

浅拷贝：也称位拷贝，编译器只是将对象中的值拷贝过来。如果对象中管理资源，最后就会导致多个对象共享同一份资源，当一个对象销毁时就会将该资源释放掉，而此时另一些对象不知道该资源已经被释放，以为还有效，所以当继续对资源进项操作时，就会发生发生了访问违规。

如果类没有指向资源。那浅拷贝是可以的。
但是如果类指向资源，浅拷贝就不止西沟两次的问题。
还有两个对象共享一个资源空间的风险。

深拷贝
所以解决浅拷贝的问题就是重新开一块新的空间即可。
如果一个类中涉及到资源的管理，其拷贝构造函数、赋值运算符重载以及析构函数必须要显式给出。一般情况都是按照深拷贝方式提供。

三.引用计数与写时拷贝

写时拷贝就是一种拖延症，是在浅拷贝的基础之上增加了引用计数的方式来实现的。

引用计数：用来记录资源使用者的个数。在构造时，将资源的计数给成1，每增加一个对象使用该资源，就给计数增加1，当某个对象被销毁时，先给该计数减1，然后再检查是否需要释放资源，如果计数为1，说明该对象时资源的最后一个使用者，将该资源释放；否则就不能释放，因为还有其他对象在使用该资源。

三.vector

3.1vector的介绍及使用

vector学习时一定要学会查看文档,vector的文档使用vector在实际中非常的重要，在实际中我们熟悉常见的接口就可以，下面列出了哪些接口是要重点掌握的。

由于前面我们已经讲过string了vector这里很多都是类似的。所以这里就不过多赘述了。

vector的定义

构造函数声明	接口说明
vector()（重点）	无参构造
vector（size_type n, const value_type& val =value_type()）	构造并初始化n个val
vector (const vector& x); （重点）	拷贝构造
vector (InputIterator first, InputIterator last);	使用迭代器进行初始化构造

vector iterator 的使用

iterator的使用	接口说明
begin+end	获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iterator
rbegin+rend	获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator

vector空间增长问题

容量空间	接口说明
size	获取数据个数
capacity	获取容量大小
empty	判断是否为空
resize	改变vector的size
reserve	改变vector的capacity

reserve

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

我们验证一下vector的扩容方式。

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

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

那reserve的扩容规则还是和string的一样吗？

和string不同的是不会缩容。string可能会缩容。

resize
resize有三种情况。

3.2 vector的增删查改

这里erase和insert不支持下标。

vector不支持流插入和流提取。
因为vector的流插入和流提取是不确定的。
如果我们实现vector的流插入和流提取这样写就可以了。

3.3vector嵌套

vector除了可以存内置类型。还可以存储自定义类型。
例如vector存储string。

这时我们将的隐式类型转化就可以用上了。
同时范围for这里的引用就很有必要，减少深拷贝。
不改变加上const。

那vector嵌套vector是什么呢？

vector嵌套就是多维数组。
vector再嵌套一层vector就是二维数组。


这里vv[i][j]的调用本质是两个operator=.

template<class T>class vector{T& operator[](size_t n){return a[i];}private:T* _a;size_t size;size_t capacity};

vector是个模版。这里编译器实例化了两个类。

所以本质vv[i][j]是两个operator[]调用的另一种写法。

四.vector深度剖析及模拟实现

我们先看库里的实现。
库里用是三个迭代器实现vector。
一个指向起始位置，一个指向最后一个数据的位置的下一个位置，一个指向空间的下一个位置。

大体结构如下：

那现在我们自己来模拟实现一个vector.

4.1vector的定义

template<class T>class vector {public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};

4.1 reserve

我们检查一下是否需要扩容。如果扩容就申请空间拷贝数据。更新三个迭代器即可。

void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];if (tmp != nullptr){size_t old_size =size();/*memcpy(tmp, _start, sizeof(T) * size());*///浅拷贝for (int i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = _start + old_size;_end_of_storage = _start+n;}}}

4.2 迭代器

迭代器只需要返回起始位置和有效数据的最后一个数据即可。

iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}

4.3 构造和拷贝构造

构造直接用缺省值走初始化列表即可。
拷贝构造先reserve开空间，然后复用push_back拷贝数据即可。
n个T的val值构造。直接reserve，然后尾插val即可。
迭代器区间构造。直接尾插迭代器区间数据即可。

vector(){}vector(const vector<T>& v){reserve(v.capacity());for (auto& x : v){push_back(x);}}vector(size_t n,const T& val=T())//调用T的默认构造{reserve(n);while (n--){push_back(val);}}//类模板的成员函数还可以是函数模板template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}

类模板的成员函数还可以是函数模板。

4.4 size

直接返回_finish - _start就是数据个数

size_t size() const{return _finish - _start;}

4.5 push_back

我们检查一下是否扩容。需要就reserve即可。
然后插入数据，++_finish即可。

void push_back(const T x){if (_finish == _end_of_storage){reserve(capacity()==0?4:2*capacity());}*_finish = x;++_finish;}

4.6 capacity

size_t capacity() const{return _end_of_storage - _start;}

4.7 pop_back

尾删直接_finish–即可。

void pop_back(){assert(size());_finish--;}

4.8 empty

empty直接判断是否_start==_finish即可。

bool emtpy(){return _start==_finish;}

4.9 clear

直接让_start = _finish即可。

void clear(){_start = _finish;}

4.10 resize

n>size就扩容然后插入数据即可。否则更新_finish删除数据即可。

void resize(size_t n, T val = T())//调用构造 内置类型也有构造和析构{if (n > size())//大于size插入数据{reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}else{_finish = _start+n;}}

为了兼容这种场景，内置类型也认为有构造和析构函数。

4.11 operator=

赋值重载我们继续用string的交换方式即可。

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& operator=(vector& v)//类里面可以类名替代类型 类外面不行{swap(v);return *this;}

五.迭代器失效及语法问题

5.1语法问题

default
C++11 标准引入了一个新特性：default函数。程序员只需在函数声明后加=default;，就可将该函数声明为 default 函数，编译器将为显式声明的 default 函数自动生成函数体。例如：

vector() = default;//强制生成

Default 函数特性仅适用于类的特殊成员函数，且该特殊成员函数没有默认参数.

template<class T>void print_Container(const  vector<T>& v){//规定不能去没有实例化的类里面取东西//因为编译器无法区分这里的const_iterator是类型还是成员变量//typename就是说是类型，让程序员自己确认。用auto也可以自动识别vector<T>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";it++;}}

typename
类名替代类型
类里面类名可以替代类型。

vector<T>& operator=(vector<T>& v)//类里面可以类名替代类型 类外面不行{swap(v);return *this;}

所以这个代码还可以这样写

vector& operator=(vector& v)//类里面可以类名替代类型 类外面不行{swap(v);return *this;}

5.2迭代器失效

插入后失效

void 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;}for (iterator i = _finish; i >=pos ; i--){ *i =*(i - 1);}*(pos) = x;_finish++;}

以insert的pos为例，扩容后pos还指向旧空间。但是旧空间销毁了。
这时pos就是野指针。我们要认为此时pos已经失效了。

所以我们扩容后要计算相对位置更新pos。但是形参的改变不影响实参。函数内部修复，不能改变外面的实参。

void 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;}for (iterator i = _finish; i >=pos ; i--){ *i =*(i - 1);}*(pos) = x;_finish++;}

vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);print_Container(v);cout << endl;vector<int>::iterator it = find(v.begin(), v.end(), 2);v.insert(it, 10);*it *= 10;print_Container(v);cout << endl;

所以这里扩容后再insert访问到的位置就是旧空间的位置。所以会出现随机值。
并且也没有再2的位置插入。

那是不是不扩容就没事了。

vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);print_Container(v);cout << endl;vector<int>::iterator it = find(v.begin(), v.end(), 2);v.insert(it, 100);*it*= 10;

我们原本是想让2*=10.却在100的位置*=10.
这时因为insert后数据挪动，2的位置后移
迭代器指向的位置是插入的100.这也是一种变相的迭代器失效。
因为我们无法得知什么时候扩容。

所以vs下进行强制检查。不能继续访问，访问就报错。

一句话insert后就认为迭代器已经失效，不要再访问了。

删除后失效

我们这里写一个删除所有偶数的程序。

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

如果我们继续访问erase后的迭代器就会出现各种问题。

后言

这就是编码和深浅拷贝以及vector的深度剖析及其实现。大家自己好好消化理解。
今天就分享到这里，感谢的大家耐心垂阅！咱们下期见！拜拜~