STL简介

什么是STL

STL(standard template libaray-标准模板库)：是C++标准库的重要组成部分，不仅是一个可复用的组件库，而且是一个包罗数据结构与算法的软件框架。

STL的版本

原始版本
Alexander Stepanov、Meng Lee 在惠普实验室完成的原始版本，本着开源精神，他们声明允许任何人任意运用、拷贝、修改、传播、商业使用这些代码，无需付费。唯一的条件就是也需要向原始版本一样做开源使用。 HP 版本–所有STL实现版本的始祖。
P. J. 版本
由P. J. Plauger开发，继承自HP版本，被Windows Visual C++采用，不能公开或修改，缺陷：可读性比较低，符号命名比较怪异。
RW版本
由Rouge Wage公司开发，继承自HP版本，被C+ + Builder 采用，不能公开或修改，可读性一般。
SGI版本
由Silicon Graphics Computer Systems，Inc公司开发，继承自HP版本。被GCC(Linux)采用，可移植性好，可公开、修改甚至贩卖，从命名风格和编程风格上看，阅读性非常高。

C标准委员会制定出语法规则，编译器厂商选择性的去支持语法，不一定所有的编译器都支持C标准委员会制定出部分语法

STL的六大组件

STL的重要性

在笔试中：
有很多题我们需要用到数据结构和算法，但是笔试时间是有限的，我们总不能现写数据结构和一个算法，比如两个栈实现队列，我们写一个栈时间就够你用的了，别说实现队列了，所以是非常重要的

在招聘工作中：

经常会有C程序员对STL不是非常了解，大多是有一个大致的映像，而对于在什么情况下应该使用哪个容器和算法都不清楚，STL是C程序员不可或缺的技能，掌握它对C++提升有很多帮助。

string

为什么学习string类？

C语言中的字符串

C语言中，字符串是以’\0’结尾的一些字符的集合，为了操作方便，C标准库中提供了一些str系列的库函数，但是这些库函数与字符串是分离开的，不太符合OOP的思想，而且底层空间需要用户自己管理，稍不留神可能还会越界访问。

#include<string>
int main()
{
    cout<<sizeof(char)<<endl;
    cout<<sizeof(wchar_t)<<endl;
    
    return 0;
}

为什么会有wchar_t呢？而且它是两个字节。

关于编码

计算机中只有二进制0、1，我们如何去表示文字呢？建立对应的编码表

1、ASCII->支持英文，1字节==8bit，有符号有0-255种表示方法，ascii编码表就是对256个值建立一个对应的表示值

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dN7EJB7T-1636190891004)(https://ts1.cn.mm.bing.net/th/id/R-C.a8c58c9e1c63e23613d69316334505a9?rik=0EKQfdqIkkoNfw&riu=http%3a%2f%2fwww.asciima.com%2fimg%2fascii-Table.jpg&ehk=UiXHk2H6LELHzgDh1FxLn1%2bMFO82gg4BpJ0%2bvpLSx7w%3d&risl=&pid=ImgRaw&r=0)]

int main()
{
   	char ch=97;
    char ch1=98;
    
    char arr[]="hello world";
    return 0;
}

计算机里存的是ascii码

2、全世界各个国家都开始用计算机了，早期的计算机中只能表示英文，不能表示其他国家的文字。需要建立出自己的编码表，那就非常乱，就出来了一个东西UniCode，Unicode的不同的实现，用了不同的存储方式。UTF-8, UTF-16, UTF-32，就是 Unicode 不同的实现。

1个字节可以有256状态，2个字节有256*256种状态，显然汉字用一个字节编码肯定是不够用的，所以汉字用两个字节去编码：

#include<string>
int main()
{
    char arr2[]="中国";
    return 0;
}

由于编码的原因，所以不仅仅有char，还有wchar_t

标准库中的string类

string类

string是表示字符串的字符串类
该类的接口与常规容器的接口基本相同，再添加了一些专门用来操作string的常规操作。
string在底层实际是：basic_string模板类的别名，typedef basic_string<char, char_traits, allocator>string;
不能操作多字节或者变长字符的序列。
string类是basic_string模板类的一个实例，它使用char来实例化basic_string模板类，并用char_traits和allocator作为basic_string的默认参数

basic_string文档

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-s1KihJMg-1636190891008)(C:\Users\15191107746\AppData\Roaming\Typora\typora-user-images\image-20211102150244902.png)]

string类对象的构造函数

函数名称	功能说明
string()	构造空的string类对象，即空字符串
string(const char* s)	用C-string来构造string类对象
string(size_t n,char c)	string类对象中包含n个字符c
string(const string&s)	拷贝构造函数

string类对象构造函数的使用：

#include<string>
template<class T>
class basic_string
{
    T* _arr;
    int _size;
    int _capacity;
};
int main()
{
    string s1();
    string s2("hello world");
    string s3("中国");
    string s4(10,'a');
    string s5(s2);
    cout<<s1<<endl;
    cout<<s2<<endl;
    cout<<s3<<endl;
    cout<<s4<<endl;
    cout<<s5<<endl;
    
    s1 = s5;
    cout<<s1<<endl;
    return 0;
}

string类的成员函数的使用

上面知道了string类对象如何初始化，那么我们想要遍历string该怎么遍历呢？

1、for循环遍历修改+读取

[]+下标方式：

int main()
{
    string s2("hello world");
    for (size_t i = 0; i < s2.size(); ++i)
    {
        //写
        s2[i] += 1;
    }
    for (size_t i = 0; i < s2.size(); ++i)
    {
        //读
        cout << s2[i] << " ";
    }
    cout << endl;
	return 0;
}

2、范围for遍历修改+读取

for(auto& e : s2)//想要修改需要加引用
{
    //写
   	e += 1;
}
for(auto e : s2)//取该对象的每个字符赋给e
{
    //读
    cout<< e <<" ";
}
cout<<endl;

3、迭代器遍历：

使用迭代器遍历我们需要了解String中的Iterators成员函数，下面我们来看看迭代器遍历是怎么遍历的：

int main()
{
    string s2("hello");
    string::iterator it = s2.begin();
    //s2.begin()返回第一个有效数据位置的迭代器
    //s2.end()返回最后一个有效数据的下一个位置的迭代器
    while(it!=s2.end())
    {
        *it+=1;
        ++it;
    }
    cout<<endl;
    it = s2.begin();
    while(it!=s2.end())
    {
        cout<<*it<<" ";
        ++it;
    }
    cout<<endl;
    return 0;
}

s2.begin()返回第一个有效数据位置的迭代器
s2.end()返回最后一个有效数据的下一个位置的迭代器

迭代器是一个像指针一样的东西，有可能是指针，也有可能不是指针，迭代器遍历的好处，可以用统一类似的方式去访问容器

注意：

建议用判断循环是否继续时用!=，如果不用，遇到不是顺序表的结构就会有问题。比如链表的结构：

int main()
{
    vector<int> v = {1,2,3,4};
    vector<int>::iterator vit = v.begin();
    while (vit != v.end())
    {
        cout <<*vit << "";
        ++vit;
    }
    cout << endl;
    list<int> lt = { 1，2，3，4 };
    list<int> ::iterator lit = lt.begin();
    while ( lit !=lt.end())
    {
        cout <<*lit <<" ";
        ++lit;
    }
    cout << endl;
    return 0;
}

这里就会出问题：

因为list是链表结构，不用!=进行比较，而用<比较的话是不行的，因为链表元素的地址并不一定后面的地址大，前面的地址小

注意：

1、所有的容器都支持用迭代器，所以迭代器才是容器通用访问方式

2、vector/string这种顺序表结构支持下标+[]去访问，像list、map就不支持了

const修饰的迭代器：

void Print(const string& s)
{
    //const对象要用const迭代器，只读，不能写
    string::iterator it = s.begin();
    //string::const_iterator it = s.begin();
    //
    while(it!=s.end())
    {
        cout<<*it<<" ";
        ++it;
    }
    cout<<endl;
}
void test_string2()
{
    string s1("hello");
    Print(s1);
}
int main()
{
    test_string2();
    return 0;
}

编译不通过，为什么呢？因为s1传参到s是const对象，const对象要用const迭代器，只读，不能写

所以我们需要这样写：

string::const_iterator it = s.begin();

了解了遍历方式，下面我们来做一道OJ题：仅仅反转字母

题目描述：
给定一个字符串 S，返回 “反转后的” 字符串，其中不是字母的字符都保留在原地，而所有字母的位置发生反转。

示例 1：

输入："ab-cd"
输出："dc-ba"

示例 2：

输入："a-bC-dEf-ghIj"
输出："j-Ih-gfE-dCba"

[]+下标进行遍历：

class Solution 
{
public:
    bool isLetter(char ch)
    {
        if(ch >= 'a'&& ch <= 'z ')
            return true;
        if(ch >= 'A'&& ch <= 'Z')
            return true;
        return false;
    }
    string reverseOnlyLetters(string s) 
    {
        int begin =0;
        int end = s.size()-1;
        while(begin<end)
        {
            while(begin<end && !isLetter(s[begin]))
            {
                begin++;//找是字母
            }
            while(begin<end && !isLetter(s[end]))
            {
                end--;//找是字母
            }
            swap(s[begin],s[end]);
            begin++;
            end--;
        }
    }
	return  s;
};

使用迭代器的解法：

class Solution {
public:
    bool isLetter(char ch)
    {
        if(ch >= 'a'&& ch <= 'z ')
            return true;
        if(ch >= 'A'&& ch <= 'Z')
            return true;
        return false;
    }

    string reverseOnlyLetters(string s) 
    {
        auto it_left =s.begin();
        auto it_right = s.end()-1;
        while(it_left<it_right)
        {
            while(it_left<it_right && !isLetter(*it_left))
            {
                it_left++;//找是字母
            }
            while(it_left<it_right && !isLetter(*it_right))
            {
                it_right--;
            }
            swap(*it_left,*it_right);
            it_left++;
            it_right--;
        }
        return  s;
    }
};

下面我们来看迭代器中的rbegin和rend

rbegin指向最后一个元素，rend指向第一个元素的前一个位置：

反着遍历对象：

void test_string3()
{
    //反着遍历对象
    string s1("hello");
    string::reverse_iterator rit = s1.rbegin();
    while (rit != s1.rend())
    {
        cout << *rit << endl;
        ++rit;
    }
    cout << endl;
    //不想改可以加const
    string::const_reverse_iterator rit1 = s1.rbegin();
    while (rit1 != s1.rend())
    {
        cout << *rit1 << endl;
        ++rit1;
    }
    cout << endl;
}
int main()
{
    test_string3();
    return 0;
}

String中的Capacity成员函数

size、length、capacity、max_size：

void test_string3()
{
    string s1("hello");
    cout<<s1.size()<<endl;//推荐用size
    cout<<s1.length()<<endl;
    cout<<s1.capacity()<<endl;//随着字符串长度改变
    cout<<S1.max_size()<<endl;//实际中没什么意义
}

size和length是一样的意思，都是计算对象的长度，但推荐用size，而capacity就是容量，它是随着字符串长度的改变而改变的，max_size实际中没什么意义，因为不管初始化还是不初始化在32位操作系统下它都是231 -1字节，210241024*1024-1字节，也就是相当于2G

resize：

首先看下面代码：

int main()
{
    string s2("hello world");
    cout<<s2.size()<<endl;

    s2.resize(20);
    cout<<s2.size()<<endl;
    return 0;
}

大小不一样了，我们使用了resize，传参为20时，s2对象的size改变了，为什么呢？我们来看C++文档当中怎么说明这个函数的：

我们来翻译一下它的意思：
改变这个字符串对象的长度为n，如果n小于当前字符串的长度，则将当前值缩短到第n个字符，删除第n个字符以外的字符。如果n大于当前字符串长度,延长字符串长度，并在最后插入指定内容直到达到的延长后的长度n。如果指定c, 用c来初始化,否则,他们初始化值字符(null字符)。

对于上面的代码我们进行调试：

当指定了填充的字符：

上面是resize大于size的情况，那么小于的情况呢，请看下面的调试：

int main()
{
    string s2("hello world");
    cout<<s2.size()<<endl;

    s2.resize(5);
    cout<<s2.size()<<endl;
    return 0;
}

可以看到当前值缩短到第5个字符，删除第5个字符以外的字符

reserve：

首先看下面代码：

int main()
{
    string s4("hello world");
    cout<<s4.capacity()<<endl;

    s4.reserve(20);
    cout<<s4.size()<<endl;
    cout<<s4.capacity()<<endl;
    return 0;
}

reserve是一个改变容量的函数，这里我们明明改了20，为什么容量变成了31呢？我们同样的查看一下C++文档：

如果n大于当前字符串的容量，该函数将使容器的容量增加至少n个字符。其他情况容量不会改变

n大于当前字符串容量的测试：

n小于当前字符串的测试：

windows和Linux的增容规则的测试

windows下的增容规则：

void test()
{
    string s;
    size_t sz = s.capacity();
    cout<<"making s grow:\n"<<sz<<endl;
    for(int i = 0;i<500;i++)
    {
        s.push_back('c');
        if(sz!=s.capacity())//如果真，则说明增容了
        {
            sz = s.capacity();
            cout<<"capacity changed: "<<sz<<'\n';
        }
    }
}

可以看到windows下的增容规则大约是1.5倍的增容

Linux下的增容规则：

可以看到Linux下的增容规则是二倍增容

那么resize和reserve的意义是什么呢？

reserve的作用：如果我们知道数据的多少，就可以一次性就把空间开好，避免增容，提高效率，resize的作用：既要开好空间，还要对这些空间初始化，就可以用resize

clear

clear就是将字符串变成空字符串

void test_string()
{
    string s1("hello");
    cout<<s1<<endl;
    s1.clear();
    cout<<s1<<endl;
}

可以看到s1已经变成了空字符串

empty

判断一个字符串是不是空字符串

String中Modifiers的成员函数

push_back、append
push_back尾插一个字符，append为尾插字符串

int main()
{
	string s1("hello");
	s1.push_back(' ');
	s1.append("world");
	cout << s1 << endl;
	return 0;	
}

还可以使用+=插入：

int main()
{
    string s1("hello");
    //更推荐用+=
    s1 +=' ';
    s1 +="world";
    cout<<s1<<endl;
    return 0;
}

insert

int main()
{
    s1.insert(0,"hello");
	cout<<s1<<endl;
    return 0;
}

erase

npos是一个string类下的静态变量，它的值为-1：

erase有两个参数，一个pos，一个len，pos和len都给了缺省值，pos的缺省值是0，而npos是-1，但len是size_t类型，转换为无符号数是一个很大的数，所以len的缺省值是一个很大的数

int main()
{
    string s3("hello world");
    s2.erase(5);//给一个参数，删完
    s2.erase(5，2);//给两个参数，删2个
    return 0;
}

给一个参数：

给两个参数：

insert和erase能不用就不用，因为insert和erase在头部或者中间等位置插入删除需要挪动数据，效率低下，尽量少用，了解即可

注意：不给参数相当于clear，变成了空字符串。

find和rfind

find

这里我们需要注意find的返回值：第一次匹配的第一个字符的位置。如果没有找到匹配，函数返回string::npos。

rfind

这里我们需要注意find的返回值：最后匹配的第一个字符的位置。如果没有找到匹配，函数返回string::npos。

substr

这个函数是取出子串，有两个参数：pos，len，pos指的是你想要从哪里开始，len是取得长度，并且它两都有缺省值

我们想要取出文件名的后缀就需要用到rfind和substr这两个函数：

因为最后面的.才是后缀，所以我们需要找最后一个.字符，所以需要用到rfind这个函数

void test_string6()
{
    //取出文件的后缀
    string file1("test.txt");
    string file2("test.cpp");
    size_t pos1 = file1.rfind('.');
    if (pos1 != string::npos)
    {
        string sub1 = file1.substr(pos1, file1.size() - pos1);
        //string sub1 = file1.substr(pos1);
        cout << sub1 << endl;
    }
    size_t pos2 = file2.rfind('.');
    if (pos2 != string::npos)
    {
        string sub2 = file2.substr(pos2, file2.size() - pos2);
        //string sub2 = file2.substr(pos2);
        cout << sub2 << endl;
    }
}
int main()
{
    test_string6();
    return 0;
}

取出url协议、域名、uri：

int main()
{
    string url("http://www.cplusplus.com/reference/string/string/find/");
    cout << url << endl;
    //取出url协议、域名、uri
    size_t i1 = url.find('://');
    if (i1 != string::npos)
    {
        //找到
        string protocol = url.substr(0, i1 - 0);
        cout << "protocol："<<protocol << endl;
    }
    size_t i2 = url.find('/', i1 + 3);
    if (i2 != string::npos)
    {
        //找到
        string domain = url.substr(i1 + 3, i2 - (i1 + 3));
        cout <<"domain："<< domain << endl;
    }
    string uri = url.substr(i2);
    cout <<"uri："<< uri << endl;
    return 0;
}

讲解了上面的函数，下面我们来看几个OJ题：

字符串中的第一个唯一字符

题目描述：
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

示例：

s = "leetcode"
返回 0

s = "loveleetcode"
返回 2

class Solution {
public:
    int firstUniqChar(string s) 
    {
        int count[26]={0};
        for(auto e:s)
        {
            //统计每个字母出现的次数
            count[e-'a']++;
        }
        for(size_t i = 0;i<s.size();i++)
        {
            if(count[s[i]-'a']==1)
            {
                return i;
            }
        }
        return -1;
    }
};

字符串最后一个单词的长度

题目描述：
计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。

（注：字符串末尾不以空格为结尾）

输入描述：

输入一行，代表要计算的字符串，非空，长度小于5000。

输出描述：

输出一个整数，表示输入字符串最后一个单词的长度。

示例1

输入：

hello nowcoder

输出：

#include<iostream>
using namespace std;
int main()
{
    string s;
    getline(cin,s);
    size_t pos = s.rfind(' ');
    if(pos!=string::npos)
    {
        //找到
        //hello world
        cout<<s.size()-(pos+1)<<endl;
    }
    else
    {
        cout<<s.size()<<endl; 
    }
    return 0;
}

验证回文串

class Solution {
public:
    bool isLetterOrNum(char ch)
    {
        if(ch>='a'&&ch<='z'
        ||ch>='A'&&ch<='Z'
        ||ch>='0'&&ch<='9')
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    bool isPalindrome(string s) 
    {
        int begin = 0;
        int end = s.size()-1;
        while(begin<end)
        {
            while(begin<end && !isLetterOrNum(s[begin]))
            {
                begin++;//找是数字或字母
            }
            while(begin<end && !isLetterOrNum(s[end]))
            {
                end--;//找是数字或字母
            }
            if(s[begin]!=s[end])
            {
                //不相等
                if(s[begin]<'A'|| s[end]<'A')
                {
                    //有一个不是字母就返回false
                    return false;
                }
                else if(s[begin]<s[end] && s[begin]+32==s[end])
                {
                    begin++;
                    end--;
                }
                else if(s[begin]>s[end] && s[end]+32==s[begin])
                {
                    begin++;
                    end--;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                begin++;
                end--;
            }
        }
        return true;
    }
};

方法二：

class Solution {
public:
    bool isLetterOrNum(char ch)
    {
        if(ch>='a'&&ch<='z'
        ||ch>='A'&&ch<='Z'
        ||ch>='0'&&ch<='9')
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    bool isPalindrome(string s) 
    {
        for(auto& ch:s)
        {
            if(ch>='A'&&ch<='Z')
            {
                ch+=32;
            }
        }
        int begin = 0;
        int end = s.size()-1;
        while(begin<end)
        {
            while(begin<end && !isLetterOrNum(s[begin]))
            {
                begin++;//找是数字或字母
            }
            while(begin<end && !isLetterOrNum(s[end]))
            {
                end--;//找是数字或字母
            }
            if(s[begin]!=s[end])
            {
                //不相等
                return false;
            }
            else
            {
                begin++;
                end--;
            }
        }
        return true;
    }
};

科学计算中，或者在特殊场景中，还需更大位数的整数进行表示和运算，那么如何处理呢？

在C++当中有个BigInteger库：
字符串表示整数，无论多大的整数都可以表示，能够实现整数±/*

下面我们来看一道OJ题：

两个字符串相加

题目描述：
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如BigInteger），也不能直接将输入的字符串转换为整数形式。

示例 1：

输入：num1 = "11", num2 = "123"
输出："134"

示例 2：

输入：num1 = "456", num2 = "77"
输出："533"

示例 3：

输入：num1 = "0", num2 = "0"
输出："0"

思路：

end1、end2分别指向两个字符串的尾，给一个变量表示进位，从尾开始拿到整形值val1，val2，然后val1，val2，进位变量相加

class Solution {
public:
    string addStrings(string num1, string num2) 
    {
        string retStr;
        int end1= num1.size()-1;
        int end2= num2.size()-1;
        int carry = 0;
        while(end1>=0||end2>=0)//两个都结束才结束
        {
            int val1=0,val2=0;
            if(end1>=0)
            {
                val1 = num1[end1]-'0';
                end1--;
            }
            if(end2>=0)
            {
                val2 = num2[end2]-'0';
                end2--;
            }
            int ret = val1+val2+carry;
            //ret大于9时需要进位
            if(ret>9)
            {
                carry = 1;
                ret -= 10;
            }
            else
            {
                carry = 0;
            }
            //retStr.insert(0,1,ret+'0');
            //可以先尾插再逆置
            retStr += ret+'0';
        }
        //结束如果carry为1，需要插入字符1
        if(carry == 1)
        {
            //retStr.insert(0,1,'1');
            retStr += '1';
        }
        reverse(retStr.begin(),retStr.end());
        return retStr;
    }
};

时间复杂度n方,原因就在于insert的复杂度为n方，我们先尾插再逆置就好了，这样时间复杂度O(N)

在string当中还有数字转字符(to_string)，字符转数字的函数(stoi)：

#include<string>
void test_string()
{
    int i = 12344;
    string str = to_string(i);
    cout<<str<<endl;
    
    int j = stoi(str);
    cout<<j<<endl;
    
}
int main()
{
    test_string();
    return 0;
}

string类的模拟实现

经典的string类问题

namespace zsb
{
    class string
    {
    public:
        string(const char* str) :_str(str)//str和_str指向一块空间('h'的地址)
        {}
    private:
       const char* _str;
    };
    void test_string1()
    {
        string s1("hello");//常量字符串
    }
}

这段代码看着是没啥问题，可以正常运行，可是我们string是需要实现增删查改这些操作的，这样写就会有问题，我们看下面代码

namespace zsb
{
	class string
	{
	public:
		string(char* str)
			:_str(str)//str和_str指向一块空间('h'的地址)
		{}
		char& operator[](size_t pos)
		{
			return _str[pos];//*(_str+pos)
		}
	private:
		char* _str;
	};
	void test_string1()
	{
		string s1("hello");//常量字符串
		s1[0] = 'x';//常量字符串不允许修改
	}
}
int main()
{
	zsb::test_string1();
	return 0;
}

这段代码是错误的，常量字符串是不允许修改的，str和_str指向一块空间('h’的地址)，*(_str+pos)是常量字符串下标为pos位置的字符，hello是常量字符串是不能修改的，所以上面代码是会报错的

那么我们怎么做呢，让它们指向不同的空间就好了，在初始化时，new一块相同大小空间给_str，然后再进行拷贝，这样就可以解决了：

namespace zsb
{
    class string
    {
    public:
        string(const char* str):_str(new char[strlen(str)+1])//构造函数这样写
        {
            strcpy(_str,str);
        }
        ~string()
        {
            delete[] _str;
            _str = nullptr;
        }
        char& operator[](size_t pos)
        {
            return _str[pos];//*(_str+pos)
        }
    private:
        char* _str;
    };

    void test_string1()
    {
        string s1("hello");//常量字符串
        s1[0]='x';//常量字符串不允许修改
    }
}

那么还有一个问题我们想这样初始化对象呢？

string s2(s1);//不写拷贝构造，是浅拷贝，如何解决？

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

浅拷贝

浅拷贝是按位拷贝对象，它会创建一个新对象，这个对象有着原始对象属性值的一份精确拷贝。如果属性是基本类型，拷贝的就是基本类型的值；如果属性是内存地址（引用类型），拷贝的就是内存地址，因此如果其中一个对象改变了这个地址，就会影响到另一个对象。拷贝出来的目标对象的指针和源对象的指针指向的内存空间是同一块空间，浅拷贝只是一种简单的拷贝，让几个对象公用一个内存，然而当内存销毁的时候，指向这个内存空间的所有指针需要重新定义，不然会造成野指针错误。

浅拷贝(如果成员有指针)造成的问题：

析构两次空间
其中一个去修改值，会影响另外一个

深拷贝

如果一个类中涉及到资源的管理，其拷贝构造函数、赋值运算符重载以及析构函数必须要显式给出。一般情况都是按照深拷贝方式提供。拷贝对象时，新开一块跟你一样大的空间，再把原对象空间上的值拷贝过来。

namespace bit
{
    class string
    {
    public:
        string(const char* str):_str(new char[strlen(str)+1])//构造函数这样写
        {
            strcpy(_str,str);
        }
        //s2(s1) 深拷贝
        //深拷贝传统写法
        string(const string& s)
            :_str(new char[strlen(s._str)+1])
        {
            strcpy(_str,s._str);
        }
        ~string()
        {
            delete[] _str;
            _str = nullptr;
        }
        char& operator[](size_t pos)
        {
            assert(pos>=0 && pos< size());
            return _str[pos];//*(_str+pos)
        }
        //对于普通数组而言，越界读一般检查不出来，越界写是抽查，可能会检查出来
    private:
        char* _str;
    };
   
    void test_string1()
    {
        string s1("hello");
        s1[0]='x';
        string s2(s1);//不写拷贝构造，是浅拷贝，如何解决？自己写拷贝构造
    }
}

注意：
当我们显式的写了深拷贝时，建议写一些成员函数使用引用接收参数，这样的目的是减少拷贝构造，因为深拷贝比浅拷贝的代价更大

下面我们再来写赋值运算符重载：

那么我们怎么写赋值运算符重载呢？

s1 = s3

所以上图描述的赋值并不合理，我们这样写赋值重载：释放原空间的数据，然后再开辟一块和被拷贝的对象的_str一样大小的空间，然后再将值拷贝进去：

//s1 = s3
string& operator=(const string& s)
{
    if(this!=&s)
    {
        delete[] _str;
        _str = new char[strlen(s._str)+1];
        strcpy(_str,s._str);
    }
    return *this;
}

但是这个代码有一个小小的问题：

**万一我们new失败了呢？**上面的代码如果new失败了，我们还把原来的东西给人家破坏掉了，这样不太好

所以我们先new空间再delete：

string& operator=(const string& s)
{
    if(this!=&s)
    {
        _str = new char[strlen(s._str)+1];
        delete[] _str;
        strcpy(_str,s._str);
    }
    return *this;
}

先开空间，再释放，如果new失败了，抛异常后面的不会再执行，这样不会破坏原来的空间

上面说的深拷贝和赋值都是传统的写法，下面我们来看现代写法：

深拷贝和赋值的现代写法

深拷贝现代写法：

//s2(s1)
string(const string& s)
{
    string tmp(s.str);//拿s的成员进行构造
    swap(_str,tmp._str);
}

但是此时这个代码还有问题：当tmp释放的时候会错误，因为它的_str指向的是随机地址，释放会导致错误，所以我们需要将s2的_str先初始化为nullptr：

//s2(s1)
string(const string& s)
    :_str(nullptr)
{
    string tmp(s.str);//拿s的成员进行构造
    swap(_str,tmp._str);
}

赋值现代写法：

//s1=s2
string& operator=(const string& s)
{
    if(this!=&s)
    {
        string tmp(s.str);
        swap(_str,tmp._str)
    }
    return *this;
}

赋值重载现代写法更简洁的写法：

//s1=s2
string& operator=(string s)
{
	swap(_str,s._str);
    //this->swap(s);
    return *this;
}

我们需要注意的是函数的形参特意写成了值传参，而不是引用传参，我们知道值传参就是一次拷贝构造这里相当于用s2去拷贝构造了s，这里的s其实干的工作相当于就是非简洁写法中tmp对象的工作，然后将s1的_str和s的_str交换，就成功赋值成功了，最后s在函数栈帧结束的时候它就会销毁。

string类的模拟实现

模拟实现string类的构造函数

//默认构造函数
//string(char* str="\0")
string (char* str="")//注意这里缺省不能写空指针，因为初始化里有strlen，不能对空指针解引用
    :_size(strlen(str)),_capacity(_size)
{
    _str = new char[_capacity+1];
    strcpy(_str,str);
}

我们前面用了string类里面的增删查改的一些东西，我们现在来模拟实现：

在插入元素时，我们先要考虑是否增容，所以我们先写reserve函数：

模拟实现string类的reserve

void reserve(size_t n)
{
    if(n>_capacity)
    {
        char* tmp = new char[n+1];
        strcpy(tmp,_str);
        delete[] _str;
        _str = tmp;
        _capacity = n;
    }
}

reserve函数的功能是重置容量，它的规则是当参数n大于原容量时，将它的容量增加至n，注意这里会有\0所以需要多申请一个空间。

模拟实现push_back

尾插字符：

void push_back(char ch)
{
    if(_size>=_capacity)
    {
        //增容
        reserve(_capacity*2);
    }
    _str[_size]=ch;
    _size++;
    _str[_size]='\0';
}

上面的写法对吗？其实还存在一点小问题：这样写时_capacity为0时会出问题，当_capacity为0时，就会增容失败，后面插入字符时就会发生越界的情况，故这样写是有问题的

应该这样写：

void push_back(char ch)
{
    if(_size>=_capacity)
    {
        //增容
        //reserve(_capacity*2);//这样写时_capacity为0时会出问题
        size_t newcapacity = _capacity == 0? 4 : _capacity*2;
        reserve(newcapacity);
    }
    _str[_size]=ch;
    _size++;
    _str[_size]='\0';
}

模拟实现尾插字符串函数：

void append(const char* str)
{
    size_t len = strlen(str);
    if(_size+len > _capacity)
    {
        //增容
        reserve(_size+len);
    }
    strcpy(_str+_size,str);//将str拷贝到尾部
    _size += len;
}

模拟实现swap函数

void swap(string& s)
{
    //全局的swap
    ::swap(_str,s._str);
    ::swap(_size,s._size);
    ::swap(_capacity,s._capacity);
}

+=字符运算符重载：

string& operator+=(char ch)
{
    //复用push_back
    push_back(ch);
    return *this;
}

push_back我们实现了尾插字符，+=字符其实也就是尾插字符，所以可以进行复用

+=字符串运算符重载

string& operator+=(const char* str)
{
    //复用append
    append(str);
    return *this;
}

append我们实现了尾插字符串，+=字符串其实也就是尾插字符串，所以可以进行复用

我们前面也了解过resize的写法，我们这里来模拟实现它：

模拟实现resize

首先我们来分析一下库里面的string的成员函数resize的功能：
resize是重置字符串的大小，具体细节是什么呢？

当参数n小于等于_size时，我们需要删除第n个之后的字符，并将_size置为n，这是最简单的情况

当参数n大于_size时，我们需要将_size改为n，并且将大于部分初始化为’\0’(如果不写第二个参数默认为\0)或者指定字符，但是此时我们还需要考虑容量够不够，所以还要考虑n>_capacity的情况，此时我们需要增容到n，然后通过for循环将_size后的字符初始化，并且更新_size，注意需要将最后面改为\0。

void resize(size_t n, char ch = '\0')
{
    if (n <= _size)
    {
        _size = n;
        _str[_size] = '\0';
    }
    else
    {
        if (n > _capacity)
        {
            reserve(n);
        }
        for (int i = _size; i < n; i++)
        {
            _str[i] = ch;
        }
        _size = n;
        _str[_size] = '\0';
    }
}

上面就是resize的模拟实现

下面是两个简单获取_size和_capacity的接口：

获取_size和_capacity

size_t size()const
{
    return _size;
}

size_t capacity()const
{
    return _capacity;
}

用const修饰防止_size和_capacity被修改

重载[]以及迭代器的模拟实现

我们前面说的遍历字符串有三种方法：1、[]下标遍历 2、迭代器遍历 3、范围for

下面我们再来看一下这三种方法的遍历：

void test_string3()
{
    string s1("hello");
    for(size_t i =0;i<s1.size();i++)
    {
        cout<<s1[i]<<" ";
    }
    cout<<endl;
    
    string::iterator it= s1.begin();
    while(it!=s1.end())
    {
        cout<<*it<<" ";
        ++it;
    }
    cout<<endl;
    
    for(auto e:s1)
    {
        cout<<e<<" ";
    }
    cout<<endl;//范围for原理就是被替换成迭代器
}

使用[]下标遍历，我们需要重载[]运算符：

char& operator[](size_t pos)
{
	assert(pos>=0 && pos<size());
    return _str[pos];
}

使用迭代器遍历，我们需要模拟string里面的迭代器，这里类似指针：

typedef char* iterator;
iterator begin()
{
    return _str;
}
iterator end()
{
    return _str+_size;
}

可以看到string里面的迭代器只是用char*typedef出来的，begin和end函数也只是返回字符串的首尾指针，非常简单

对于范围for，它的底层原理其实就是迭代器实现

普通对象可读可写，const对象可读不可写，比如我们想要写一个print函数，因为不修改数据，所以参数用const来修饰：

void print(const string& s)
{
    for(size_t i =0;i<s.size();i++)
    {
        cout<<s[i]<<" ";
    }
    cout<<endl;
    
    string::const_iterator it= s.begin();
    while(it!=s.end())
    {
        cout<<*it<<" ";
        ++it;
    }
    cout<<endl;
    
    for(auto e:s)
    {
        cout<<e<<" ";
    }
    cout<<endl;//范围for原理就是被替换成迭代器
}

const对象要调用const修饰的函数，所以我们需要写const修饰的[]下标重载和迭代器的实现：

//只读
const char& operator[](size_t pos)const
{
    assert(pos>=0 && pos< size());
    return _str[pos];//*(_str+pos)
}
typedef const char* const_iterator;
const_iterator begin()const
{
    return _str;
}
const_iterator end()const
{
    return _str+_size;
}

insert函数的模拟实现

insert我们实现两个接口：

1、插入字符：

string& insert(size_t pos, char ch)
{
	assert(pos <= _size);
	if (_size == _capacity)
	{
		//增容
		size_t newcapacity = _capacity == 0 ? 4 : 2 * _capacity;
		reserve(newcapacity);
	}
	//挪动数据
	//helloworld\0
	int end = _size + 1;
	while (end > pos)
	{
		_str[end] = _str[end - 1];
		end--;
	}
	_str[pos] = ch;
	_size++;
	return *this;
}

这里挪动数据时end不能变为负数，变为负数这里比较会发生提升，有符号的数会转换成无符号的数，这里就进入了死循环，所以这里解决方式有两种一种是让end开始等于_size+1，一种是将while循环体里的pos强转为int

2、插入字符串

string& insert(size_t pos, const char* str)
{
	assert(pos <= _size);
	size_t len = strlen(str);
	if (len == 0)
	{
		return *this;
	}
	if (len + _size > _capacity)
	{
		reserve(len + _size);
	}
	//挪动数据
	//helloworld\0 
	size_t end = _size + len;
	while (end >= pos + len)
	{
		_str[end] = _str[end - len];
		end--;
	}
	for (size_t i = 0; i<len; i++)
	{
		_str[pos + i] = str[i];
	}
	_size += len;
	return *this;
}

插入字符串的主要思想是和插入字符一样的，但是需要注意这里增容会有些不一样，这里增容就不能增2倍了，因为不确定插入字符串长度，万一字符串长度大于2倍的_capacity就出大问题了，所以这里需要先求出字符串的长度，然后如果len+_size大于容量时就进行增容，增容到len+_size。

尾插就也可以复用insert了：

void push_back(char ch)
{
	this->insert(_size, ch);
}

void append(const char* str)
{
	this->insert(_size, str);
}

erase删除字符模拟实现

void erase(size_t pos,size_t len = npos)
{
    //hello
    assert(pos < _size);
    if(pos+len>=_size||len = npos)
    {
        //全部删完
        _str[pos]='\0';
        _size = pos;
    }
    else
    {
        //删除一部分
        strcpy(_str+pos,_str+pos+len);
        _size -= len;
    }
}

删除字符有两种情况全部删完的情况和部分删除的情况：当使用者第二个参数不传参时，默认为npos，npos是个超大的数，所以相当于pos位置后全部删除，还有就是当pos+len>=_size时也需要全部删除

返回字符串的c_str函数

const char* c_str()
{
	return _str;
}

写了c_str函数我们就可以这样打印字符串：

int main()
{
    Z::string s1("hello world");
	cout<<s1.c_str()<<endl;
    return 0;
}

+字符和字符串重载

//存在深拷贝对象，尽量少用
string operator+(string& s,char ch)
{
	string ret = s;
	ret += ch;
	return ret;
}

string operator+(string& s,const char* str)
{
	string ret = s;
	ret += str;
	return ret;
}

这里存在几次深拷贝，所以我们需要少用这个接口

流插入运算符<<重载

ostream& operator<<(ostream& out,const string& s)
{
    // 不管字符数组中的内容是啥，size是多少，就要输出多少个有效字符
    for(size_t i = 0;i<s.size();++i)
    {
        out<<s[i];
    }
    return out;
}

下面我们来看一下下面这两种输出字符串的方式有什么区别呢？

void teststring1()
{
	Z::string s1("hello world");
	cout<<s1.c_str()<<endl;
	cout << s1 << endl;
}

注意：一般情况下，这两种输出方式没什么区别，但是注意这种情况：

void teststring1()
{
	Z::string s1("hello world");
    s1.resize(20);
	cout<<s1.c_str()<<endl;
	cout << s1 << endl;
}

resize会将长的空间全部初始化为\0(如果没给定字符)，而使用c_str进行打印时，c_str返回的是字符指针。它打印的是字符串遇到\0就会终止，而重载<<打印s1会打印\0，不管字符数组中的内容是啥，size是多少，就要输出多少个有效字符

清空函数

void clear()
{
    _str[0]='\0';
    _size=0;
}

流提取运算符>>重载

istream& operator>>(istream& in,string& s)
{
    char ch;
    in >> ch;
    while(ch!=' ' && ch!='\n')//cin是输入空格和换行时结束
    {
        s += ch;
        in >> ch;
    }
    return in;
}

那么这样对不对呢？我们来试一下:

void teststring3()
{
	Z::string s1;
	cin >> s1;
	cout << s1<<endl;
}
int main()
{
	teststring3();
	return 0;
}

不对，发现并没有输出，因为in就是cin，cin是获取不到空格和换行符的，和C语言的scanf是一样的

所以我们要用这个函数来获取字符：

istream& operator>>(istream& in,string& s)
{
    char ch;
    ch = in.get();
    while(ch!=' ' && ch!='\n')//cin是输入空格和换行时结束
    {
        s += ch;
        ch = in.get();
    }
    return in;
}

这样还是有点问题，看下面的情况：

void teststring3()
{
	Z::string s1("hello");
	cin >> s1;
	cout << s1<<endl;
}
int main()
{
	teststring3();
	return 0;
}

cin输入是需要将前面的覆盖的，但是这里没有覆盖，std域里面的string中的>>运算符重载就是输入将之前的覆盖掉了，所以我们在操作之前需要清空字符串，使用clear函数

istream& iperator>>(istream& in,string& s)
{
    s.clear();
    char ch;
    ch = in.get();
    while(ch!=' '&& ch!='\n')
    {
        s+=ch;
        ch = in.get();
    }
    return in;
}

这样才正确了。

getline的模拟实现

下面我们实现getline的模拟实现，getline唯一的差别是它读取的字符包含空格，读取到空格不结束：

istream& getline(istream& in,string& s)
{
    s.clear();
    char ch;
    ch = in.get();
    while(ch!='\n')
    {
        s+=ch;
        ch = in.get();
    }
    return in;
}

>、==、!=、<、<=、>=运算符重载：

我们首先写**>运算符重载：**

我们给定i1和i2作为字符串的迭代下标进行比较，i1和i2都小于它的长度大小时才进行循环，当下标i1处的字符大于下标i2处的字符时返回true，当下标i1处的字符小于下标i2处的字符时返回false，循环出来有三种情况：

1、s1 = “abc” s2 = “abc” 相等

2、s1 = “abcd” s2 = “abc” 大于

3、s1 = “abc” s2 = “abcd” 小于

bool operator>(const string& s1,const string s2)
{
    size_t i1 = 0,i2 = 0;
    while(i1<s1.size() && i2<s2.size())
    {
        if(s1[i1]>s2[i2])
        {
            return true;
        }
        else if(s1[i1]<s2[i2])
        {
            return false;
        }
        else
        {
            i1++;
            i2++;
        }
    }
    if(i1==s1.size())
    {
        //s1结束
        return false;
    }
    else
    {
        return true;
    }
}

==运算符重载：

bool operator==(const string& s1,const string& s2)
{
    size_t i1 = 0,i2 = 0;
    while(i1<s1.size()&&i2<s2.size())
    {
        if(s1[i1]!=s2[i2])
        {
            reture false;
        }
        else
        {
            ++i1;
            ++i2;
        }
    }
    if(i1==s1.size()&&i2==s2.size())
    {
        return true;
    }
    else
    {
        return false;
    }
}

==运算符重载和>运算符重载几乎差不多，就是循环出来判断有所区别而已，==运算符重载判断i1和i2同时结束就返回true。

剩余的运算符都可以进行复用：

inline bool operator!=(const string& s1,const string& s2)
{
    return !(s1==s2);
}
inline bool operator>=(const string& s1,const string& s2)
{
    return s1>s2||s1==s2;
}
inline bool operator<(const string& s1,const string& s2)
{
    return !(s1>=s2);
}
inline bool operator<=(const string& s1,const string& s2)
{
    return !(s1>s2);
}

find的模拟实现

查找一个字符：

size_t find(char ch,size_t pos = 0)
{
    for(size_t i = pos;i<_size;i++)
    {
        if(_str[i]==ch)
        {
            return i;
        }
    }
    return npos;
}

在前面我们查阅C++文档进行find的学习时，知道了find函数找到了返回第一个找到的下标，否则返回npos

查找一个字符串：

size_t find(const char* sub,size_t pos = 0)
{
    const char* pi = strstr(_str+pos,sub);
    if(pi == nullptr)
    {
        return npos;
    }
    else
    {
        return pi-_str;//返回下标
    }
}

查找一个字符串我们可以使用C语言库函数strstr进行模拟实现

strstr库函数的第一个参数是被浏览的字符串，第二个参数是被查找的子串，他返回的是第一次找到的子串的起始位置，没有找到则返回空。find找到了返回子串的起始下标，pi减去str起始就是子串的起始下标

写时拷贝

在数据第一次写入到某个存储位置时，首先将原有内容拷贝出来，写到另一个位置处，然后再将数据写入到存储设备中，该技术只拷贝在拷贝初始化开始之后修改过的数据

浅拷贝存在的问题：

这块空间会在两个对象析构函数中被delete两次

**引用计数：**表示有多少个对象指向这块空间，每次析构–引用计数，如果它大于0，说明它被多个对象指向

引用计数可以解决这个问题

一个对象被修改会影响另外一个对象

**写时拷贝：**哪个对象需要去写数据，哪个对象再进行深拷贝
写时拷贝的本质是在写的时候一种延迟深拷贝，但是如果你拷贝对象以后没有人进行修改，没有深拷贝，提高效率

编译器是深拷贝还是写时拷贝的验证：

int main()
{
    std::string s1( "hello worldxxxXXXXXXXXXX");
    std::string s2(s1);
	printf("%p\n", s1.c_str());
    printf("%p\n", s2.c_str());
	return 0;
}

VS2013编译器：

vs2013编译器不是写时拷贝。

Linux(gcc编译器)：

可以看到地址是不一样的，所以Linux现在也是不支持写时拷贝的，因为博主的vim版本较新，现在Linux已经不使用写时拷贝了，之前是支持的。

关于string的一个小细节：

请看下面的代码：

int main()
{
    std::string s1("1111");
    std::string s2("1111111111111111111111111111");
    cout<<sizeof(s1)<<endl;
    cout<<sizeof(s2)<<endl;    
    return 0;
}

可能大家认为是12，但并不是12：

为什么是28呢？
这其是vs编译器下的一个技术优化，成员变量还有char_buf[16]，字符串长度小于16，都存在buf中，大于16都存在_str指向的堆空间，这里减少空间碎片

调试验证：

s1对象：

s2对象：

欢迎大家学习交流！觉得文章不错点个赞吧！

C++STL之string类的使用和实现

STL简介

什么是STL

STL的版本

STL的六大组件

STL的重要性

string

为什么学习string类？

C语言中的字符串

标准库中的string类

string类

string类对象的构造函数

string类的成员函数的使用

string类的模拟实现

经典的string类问题

浅拷贝

深拷贝

深拷贝和赋值的现代写法

string类的模拟实现

模拟实现string类的构造函数

模拟实现string类的reserve

模拟实现push_back

模拟实现swap函数

+=字符运算符重载：

+=字符串运算符重载

模拟实现resize

获取_size和_capacity

重载[]以及迭代器的模拟实现

insert函数的模拟实现

erase删除字符模拟实现

返回字符串的c_str函数

+字符和字符串重载

流插入运算符<<重载

清空函数

流提取运算符>>重载

getline的模拟实现

>、==、!=、<、<=、>=运算符重载：

find的模拟实现

写时拷贝

相关文章

热门标签

最新文章

目录