【C++】STL:string
慕雪年华

这是接触STL的第一篇博客,让我们以string为始,走入SLT的世界吧!

[TOC]

1.何为STL

STL是C++标准库的重要组成部分,其作用是为绝大多数数据结构提供轮子,是一个包罗了数据结构和算法的软件框架。

在之前C语言的数据结构专栏中,顺序表、链表等等都是需要我们自己造轮子来实现。但在C++中,有STL就好比站在了巨人的肩膀上,可以走的更远。当我们需要使用这些内容时,无需自己重新造轮子,从而大大提高了开发效率。

1.1 STL版本

这里我直接贴一个C语言中文网的链接👉【点我】

里面详细介绍了STL发展历程中出现的几个版本,其中SGI因为被Linux的GCC所使用,可移植性高。之后的博客主要是学习SGI STL版本。

image

1.2 STL组成

同样是C语言中文网的资料👉【链接】,我将它整理为了下面这个思维导图

image

在面试中,STL的内容也是HR经常考察的。所以我们一定要认真学习这一部分的知识点!

1.3 STL的一些吐槽

如果你去Cplusplus网站上看过STL库的接口,你就会发现STL库的设计有些复杂。有很多地方都考虑的过于细致,导致函数接口非常多,想要全记住这些接口是有些困难的

image

当然,这也是我自己太菜了的缘故。或许以后用的多了,这些就理所应当的记住了吧。

同时,因为STL使用了模板,所以当你多次使用STL时(比如vector容器)就容易出现代码冗余

好啦,不bb这些没用的了,还是直接进入正题string类吧!


2.String

参考cplusplus的标准文档:string

string类是表示字符串的字符串类,该类的接口和常规的容器基本相同,并添加了一些专门用于操作字符串的常规操作。使用string需要包含<string>using namespace std;

  • 这里为什么是string而没有.h呢?
  • 其实编译器处理头文件并不会关注头文件的后缀,且C语言中已经有一个string.h了,为了避免冲突,所以使用了<string>作为头文件

下面介绍一些常用的string类函数接口,标题中的英文和cplusplus网站中的分类对应

2.1 编码格式

Class instantiations栏目下,可以看到string有很多不同的类,这些类的主要区别在于编码方式的不同。我们主要学习的是第一个的string

image

什么是编码格式呢?在编程学习中,比较常用的便是ASCii码,除此之外,还有utf-8utf-16等等。

image

ASII码表中,英文单词、数字、各类标点符号都有它们对应的值,这样才能在只支持01二进制的电脑上显示出对应的内容。当计算机需要显示英文单词的时候,就会去查找这一个表。所以ASCII码表是漂亮国设计的。

我们知道,英文中的基础只有26个单词,算上大小写也就52个。但是我们中华文化博大精深,计算机需要显示中文的时候,一个char类型的空间已经不够。所以我们需要整出一个我们自己的编码格式,以此让计算机支持显示中文——GBK就是这样一个编码格式

image

GBK使用两个字节来存储一个汉字,一些不常用的生僻字可能需要3-4个字节来存储。

用下面这个简单的函数来测试,我们可以发现,中文中谐音字的编码是相近的

image

在网络上,我们打某些词汇会被替换成****,就是程序在后台实别了你的编码。同时如果想进行模糊匹配,把谐音字也屏蔽掉的话,就可以把这个词周围的编码全部屏蔽了。

同理,utf-16utf-32为了支持别的国家的语言,就会用更长的字节来存储文字。这里不进行详解。


string类有非常多的接口,我们并不需要完全掌握所有的函数接口。只需要学会常用的接口,在遇到一些不常用的,在需要使用的时候可以去查找cplusplus的文档。

2.2 构造函数(constructor)

image

下面是一些常用的string类的构造函数

构造函数功能
string()空的string对象(空的字符串)
string(size_t n,char c)string类对象中包含n个字符c
string(const char*s)利用常量字符串来构造对象
string(const string&s)拷贝构造

除此之外,在文档中我们还可以看到更多构造函数

image

除此之外,我们还可以调用赋值操作符进行构造。下面是赋值重载的3个版本,想必都能看懂,是通过对象、常量字符串和字符进行赋值操作。

image

string类中也重载了流提取和流插入操作符,方便我们直接对对象进行输入输出操作。

image

image

我们还可以选取一个范围进行构造,比如下面这个

image

需要注意的是,该构造函数的第三个传参有缺省值npos

1
string (const string& str, size_t pos, size_t len = npos);

查文档可以看到,nops其实是-1,而它的类型是无符号整型,-1就代表无符号整形的最大值。即从pos位置开始,往后取最大值的长度(实际上压根没有那么长的字符串)

image

2.3 析构函数(destructor)

析构函数有个好处,就是编译器自己会进行调用,我们只需要简单了解即可。

image

2.4 遍历string对象

我们可以通过下面的3种方式来遍历一个string对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void test3()
{
//尝试遍历一个string
string s1("hello world!");
//1.重载[]
//通过调用成员函数size得知长度
cout << "operator[] " << endl;
for (int i = 0; i < s1.size(); i++)
{
cout << s1[i] << " ";
}
cout << endl;

//2.范围for
//本质上调用的是迭代器
cout << "auto " << endl;
for (auto c : s1)
{
cout << c << " ";
}
cout << endl;

//3.迭代器
//在很多容器中是通用的
string::iterator it = s1.begin();//指向开头
//end指向最后一个数据的下一个位置(即'\0')
cout << "string::iterator " << endl;
while (it != s1.end())
{
cout << *it << " ";
it++;//使用方法类似指针
}
cout << endl;
}

可以看到这三个方式都成功打印出了s1对象的完整内容

image

其中范围for编译器在操作的时候是用迭代器来实现的,这一点通过查看汇编可以看出来

image

2.5 operator[]和at(Element access)

上面我们用到了operator[]重载,需要了解的是,这个重载返回的是值的引用。也就是说,我们除了可以用这个方式来访问值的内容以外,还可以通过这种方式来改变string中某一个位置的值。

image

1
2
const string s1("hello");
s1[0]='x'//此时调用的是const版本的重载,不可修改

at函数的使用方式和[]重载类似

image

区别就是,当operator[]遇到越界情况的时候,如果相等和小于长度,都不会报错。但是当下标大于长度时,会引发未定义行为

image

at()的处理方式是,只要长度不小于string的长度,就抛出异常

image

2.6 正向和反向迭代器Iterators

除了在2.2.3中使用过的正向迭代器以外,string还有一个反向迭代器rbegin

1
2
3
4
5
6
7
8
9
//反向迭代器
string::reverse_iterator rit = s1.rbegin();//指向结尾字符('\0'之前)
//end指向开头数据的前一个位置
while (rit != s1.rend())
{
cout << *rit << " ";
rit++;//使用方法类似指针
}
cout << endl;

这里需要注意的是,虽然这个迭代器是反向的,但是我们使用的时候,依旧会rit++而不是减

image

注意,基本的迭代器是可读可写的。在string里面还实现了const的迭代器

1
2
const_iterator begin() const;
const_reverse_iterator rbegin() const;

如果你觉得这样写太麻烦,而且容易记不住。可以让auto来自动进行推导

1
2
const string s1("hello");
auto rit = s1.rbegin();

C++11中,为了和基本的方式进行区分,新增了以c为前缀的4个迭代器。其使用和const_iterator是没有区别的。

image


2.7长度和容量操作Capacity

image

2.7.1 size和length

这其中size和length的功能完全相同。只是早期string设计的时候以length作为字符串的长度。在新版本中为了和其他接口比如List进行同步,又新增了一个size来表示字符串长度。

image


2.7.2 resize和reserve

注意区分reserve和reverse

我们可以通过reserve对内存进行扩容操作,容量变大是因为需要内存对齐

image

但在实际应用中,当字符串的容量快要写满的时候,程序会自动进行扩容,大概是1.5倍

image


resize的操作是修改string类的长度size,并同时进行扩容

1
2
3
4
string s1("hello");
cout << s1.capacity() << endl;
s1.resize(100);
cout << s1.capacity() << endl;

通过调试可以发现,这里会把size修改为100,并将多余内容全部初始化为0

image

我们还可以给resize进行传参,指定初始化的内容

image


同时,这两个函数一般都不会对容量进行缩容

image

但是resize会修改size的大小,即抛弃掉10以后的内容,但保持容量不变

image

需要注意的是,在VS2019中(不同编译器可能不一样),reserve如果传参小于15,则会对容量进行缩容到15(string对象默认会开辟15个字节的capacity)

image


2.8修改内容(Modifiers)

string可以通过很多方式来增加、删除内容

2.8.1 尾插

image

它们的基本使用如下,其中最方便的肯定是+=操作了,又清晰又简单!

image

2.8.2 中间插入

string并没有提供一个头插的选项,而是提供了一个Insert,可以在任何位置进行插入

image

insert函数的时间复杂度相对较高,因为在中间或者开头插入内容需要挪动数据。空间不够的时候还需要执行扩容操作,效率较低。

image

2.8.3 删除

可以通过erase函数删除数据

image

  • 1:默认从0开始完全删除,可以选择从pos位置开始删除len长度的数据
  • 2:利用迭代器删除p位置的内容
  • 3:删除一个范围的数据,从first开始last结束

这个很容易理解,在这里就不做演示了

2.8.4 替换

这个函数使用并不频繁,其修改操作不如使用拷贝复制😂

image

比如其中第二个函数的作用是将str对象中,从subpos位置开始的sublen长度内容复制到本对象中。

2.8.5 交换

在string类中有一个交换函数,同时,std标准库里面也有一个交换函数

1
2
s1.swap(s2);//string类
swap(s1,s2);//std标准

image

  • string类里面的函数是交换类对象的指针
  • 而标准库里面的swap函数需要进行深拷贝交换

所以string类里面的swap函数在处理对象的时候,比标准库里面的swap效率会高一些

2.9字符串操作(String operations)

2.9.1 c_str

这个接口的作用是返回一个字符串的指针,其主要是为了和C语言的一些函数对应,比如利用strcmp拷贝一个string对象到内置字符串char arr[]中。

image


2.9.2 find

这里可以看到非常多种类的查找函数(偷懒不写示例了)

image

  • find函数可以查找string中的某一个字符或者字符串,并返回起始位置的下标
  • 该函数默认从头开始查找,你也可以单独指定从pos位置开始查找

image

  • 和迭代器一样,rfind则是从末尾开始找指定内容

有些时候我们需要查找的内容并不是从头开始的,所以就需要从尾部开始找。

  • substr是从指定pos位置开始获取长度为len的子串

image


2.10 很多操作符重载

string里面有非常多的操作符重载,支持和字符串、字符、对象进行大小对比。虽然看的有点麻了,但实际上它们只是方便我们使用。底层实现了解一下就可以了(我这是不是废话…)

image

其实一部分内容都是可以通过编译器的隐式类型转化或者临时构造一个string类来实现的,但是设计string的大佬们显然觉得多即是好,哈哈。

3.模拟实现

要想切切实实弄明白STL的源码结构,其中一个最好的办法就是尝试模拟实现一个和std库里面string使用方法/功能相同的轮子

我的string模拟实现源码已经托管到gitee了【链接

其实string和vector就是一个简单的顺序表,其二者的底层差距主要在string只能保存字符(串),当然,内部的接口有一些细微的差距,这会在vector的博客里面进行讲解。

大部分函数可以直接在gitee上面查看,我写了还算靠谱的注释,有任何问题可以在gitee或者本博客下留言。


3.1 利用指针模拟实现迭代器

从string开始,我们第一次接触了stl中的迭代器这一新鲜玩意。

1
2
3
4
5
6
7
8
9
//反向迭代器
string::reverse_iterator rit = s1.rbegin();//指向结尾字符('\0'之前)
//end指向开头数据的前一个位置
while (rit != s1.rend())
{
cout << *rit << " ";
rit++;//使用方法类似指针
}
cout << endl;

看起来很牛,实际上它的操作和我们自己写的指针大差不差。我们大可以直接使用指针来模拟实现出一个相同功能的迭代器!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//迭代器相关
const_iterator begin() const
{
return _a;
}
const_iterator end() const
{
return _a + _size;
}
iterator begin()
{
return _a;
}
iterator end()
{
return _a + _size;
}

//以下是string模拟实现中私有成员变量
private:
char* _a;//实际存放数据
size_t _size;//有效长度
size_t _capa;//容量大小
const static size_t npos;//声明

看吧,是不是很简单!🌃这个迭代器的使用方法和顺序表中的指针一模一样,这里就不演式啦!感兴趣的伙伴可以把源码考下来自己试试。


3.2 深拷贝

在之前类和对象的博客中,我已经简单实现过一次深拷贝(链接

对于string来说,深拷贝的操作和博客里面演示的是一样的,都是通过给予新的空间,然后用strcpy或者memset拷贝内容过去。

1
2
3
4
5
6
7
8
//拷贝构造
string(const string& s)
:_size(s._size),
_capa(s._capa)
{
_a = new char[_capa+1];
strcpy(_a, s._a);
}

除了拷贝构造以外,赋值重载同样需要深拷贝操作,但是它的操作和构造函数又有些不同

  • 拷贝构造时,该对象还不存在,通过构造函数构造出内容
  • 赋值重载时,该对象可能已经有自己的数据,需要先释放已有的才能获取新的

这就需要我们在赋值重载的时候,先delete掉原本的内容,再去进行赋值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//深拷贝赋值重载
string& operator=(const string& s) {
//和拷贝构造不同的是,赋值重载之前,this可能已经有自己的内容了
//所以在执行操作之前,我们需要把this自己的内容先释放掉
if (this != &s)//不要自己拷贝自己
{
delete[] _a;//删除已有空间
_size = s._size;
_capa = s._capa;
//_a = new char[_capa + 1];//有一定风险
char* tmp = new char[_capa + 1];
strcpy(tmp, s._a);
_a = tmp;
}
}

这样我们的赋值重载便也实现完毕了

3.3 关于insert函数操作字符和字符串的区间问题

当我们使用insert来处理字符的时候,需要将插入位置之后的数据往后挪动。

而insert字符串的时候,则需要挪动该字符串长度的数据。

这时候就非常容易出现挪动不完整/越界等等问题!

关于insert代码可以看gitee代码的190-237行,如果你不太能理解这里的移动问题,最好的办法,就是画图!画图会让你清楚的认识到需要移动多长,指针应该指向哪里进行移动。理清思路后,写代码就会容易很多。

3.4 关于push_back的边界控制问题

之前我实现的代码中,尾插的时候没有加上\0进行边界控制

这一点需要注意,因为模拟实现的底层用的就是C语言的字符串。在每一次尾插之后,都需要用\0来标记字符串的结尾。否在我们拷贝构造和reserve的时候使用strcpy就会出现越界错误。

越界错误一般都是在析构delete的时候检查出来的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void push_back(char ch)
{
if (_size + 1 >= _capa)
{
reserve(_capa == 0 ? 4 : _capa * 2);
//这里的判断是为了辨别是否在空对象尾插
}

_a[_size] = ch;
_size++;
//因为reserve和基础的拷贝构造用的都是strcpy
//所以必须要有\0来标识结尾!
_a[_size] = '\0';
}

结语

关于string类的介绍到这里就结束啦!

如果有什么新增内容的话,我会对本篇博客进行修改

如果有什么问题,欢迎评论区提出哦!