【C++笔记】string类深度解剖及其模拟实现

大白的编程日记. 2024-10-21 16:05:01 阅读 95

【C++笔记】string类深度解剖及其模拟实现

🔥个人主页大白的编程日记

🔥专栏C++笔记


文章目录

【C++笔记】string类深度解剖及其模拟实现前言一.string类说明1.1为什么实现string类1.2string类了解

二.string类的常用接口说明2.1string类对象的常见构造2.2string类对象的容量操作2.3string类对象的访问及遍历操作2.4string类对象的修改操作2.5string类非成员函数2.6字符串补充接口

二.vs和g++下string结构的说明二. string的实现2.1string的定义2.2 构造和拷贝构造2.3 operator[]2.4 迭代器2.5 string比较2.6 reserve2.7 push_back2.8 append2.9 operator+=2.10 insert2.11 find2.12 clear2.13erase2.13 IO流2.15 operator=

后言

前言

哈喽,各位小伙伴大家好!上期我们讲了模版,就用我们来讲一下string类及其实现。话不多说,我们进入正题!向大厂冲锋!

一.string类说明

1.1为什么实现string类

C语言中,字符串是以’\0’结尾的一些字符的集合,为了操作方便,C标准库中提供了一些str系列的库函数,但是这些库函数与字符串是分离开的,不太符合面向对象的思想,而且底层空间需要用户自己管理,稍不留神可能还会越界访问。并且日常生活中字符串使用场景还是很多的,比如:身份证,电话号码等。所以单独搞一个数据结构出来给字符窜还是很有必要的

1.2string类了解

string其实是typedef basic_string char来的。那意思除了char还有其他的字符类型吗?是的。由于编码原因还有其他的字符类型。所以string是一个类模版。

想学习了解string类可以看这个文档:string的文档介绍

在使用string类时,必须包含#include头文件以及using namespace std

二.string类的常用接口说明

2.1string类对象的常见构造

string的构造有这些。

但重点是这几个。

默认构造

构造空串。

用一个常量字符串构造

用一个string构造

用n个字符构造

用另一个stirng的pos位置开始后面的len个字符构造

如果给的长度过大会怎么样呢?会越界吗?

字符串的前n个字符构造

2.2string类对象的容量操作

函数名称 功能说明
size(重点) 返回字符串有效字符长度
length 返回字符串长度
empty(重点) 检测字符串释放为空串,是返回true,否则返回false
capacity 返回空间总大小
clear(重点) 清空有效字符
reserve(重点) 为字符串预留空间
resize(重点) 将有效字符的个数该成n个,多出的空间用字符c填充

string容量相关代码演示

length

length获取字符串的长度。但是这个接口不具有通用性。比如二叉树就没有length.

size

获取字符串的长度。size具有通用性。

empty

判断字符串是否为空。

- clear清理有效字符内容。

- capacity 返回空间总大小。string容量只包含有效字符,也就是说这里是16个字符的空间。

C++string的capacity如何扩容是没有规定的。具体看平台实现。

vs下是先用一个16字符大小buff字符数组存储,当字符数组不够用时再开辟一块空间。第一次2倍扩,后面1.5倍扩容。

g++是2倍扩容。

reserve

reserve保留空间。可以避免频繁扩容。

resize

将有效字符的个数该成n个,多出的空间用给定字符填充字符填充,如果没有就填充0。

总结

size()与length()方法底层实现原理完全相同,引入size()的原因是为了与其他容器的接口保持一致,一般情况下基本都是用size()。clear()只是将string中有效字符清空,不改变底层空间大小。resize(size_t n) 与 resize(size_t n, char c)都是将字符串中有效字符个数改变到n个,不同的是当字符个数增多时:resize(n)用0来填充多出的元素空间,resize(size_t n, char c)用字符c来填充多出的元素空间。注意:resize在改变元素个数时,如果是将元素个数增多,可能会改变底层容量的大小,如果是将元素个数减少,底层空间总大小不变。reserve(size_t res_arg=0):为string预留空间,不改变有效元素个数,当reserve的参数小于string的底层空间总大小时,reserver不会改变容量大小。

2.3string类对象的访问及遍历操作

函数名称 功能说明
operator[](重点) 返回pos位置的字符,const string类对象调用
begin +end begin获取一个字符的迭代器 + end获取最后一个字符下一个位置的迭代器
rbegin+rend begin获取一个字符的迭代器 + end获取最后一个字符下一个位置的迭代器
范围for C++11支持更简洁的范围for的新遍历方式

string中元素访问及遍历演示

string的遍历方式有三种:

下标+[]

<code>char& string::operator[](size_t pos)

{

assert(pos < _size);

return _s[pos];

}

这里因为string的底层是字符数组所以我们可以用下标+[]直接访问到pos位置的字符

从而遍历字符串。同时我们返回的是pos位置字符的引用这样还可以修改pos位置的字符。

迭代器

迭代器支持所有容器的访问。

<code>string s("hello,world!");

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

while (it!=s.end())

{

cout << *it << " ";

it++;

}

范围for遍历

auto关键字:

在这里补充2个C++11的小语法,方便我们后面的学习。

在早期C/C++中auto的含义是:使用auto修饰的变量,是具有自动存储器的局部变量,后来这个不重要了。C++11中,标准委员会变废为宝赋予了auto全新的含义即:auto不再是一个存储类型指示符,而是作为一个新的类型指示符来指示编译器,auto声明的变量必须由编译器在编译时期推导而得。

用auto声明指针类型时,用auto和auto*没有任何区别,但用auto声明引用类型时则必须加&当在同一行声明多个变量时,这些变量必须是相同的类型,否则编译器将会报错,因为编译器实际只对第一个类型进行推导,然后用推导出来的类型定义其他变量。

auto不能作为函数的参数,可以做返回值,但是建议谨慎使用

auto不能直接用来声明数组

auto的价值就是自动推导类型,如果类型过长就很方便。

但是一定程度牺牲了可读性。

范围for遍历的用法如下:

<code>//自动迭代 自动判断结束

string s("hello,world!");

for (auto x : s)

{

cout << x << " ";

}

所有的容器都支持范围for,因为i所有的容器都支持迭代器。

范围for写起来更方便。

加上引用即可。

总结

反向迭代器

反向迭代器就是倒着遍历容器。

<code>string s("hello,world!");

string::reverse_iterator rit = s.rbegin();

while (rit!=s.rend())

{

cout << *rit << " ";

rit++;

}

在这里插入图片描述

const迭代器

如果是const容器就需要用const迭代器访问呢。因为普通迭代器可读可写。但是容器的数据不允许修改。

2.4string类对象的修改操作

函数名称 功能说明
push_back 字符串后尾插字符c
append 在字符串后追加一个字符串
operator+=(重点) 在字符串后追加字符串str
c_str(重点) 返回C格式字符串
find+npos(重点) 从字符串pos位置开始往后找字符c,返回该字符在字符串中的位置
rfind 从字符串pos位置开始往前找字符c,返回该字符在字符串中的位置
substr 在str中从pos位置开始,截取n个字符,然后将其返回

string中插入和查找等代码演示

push_back

可以尾插一个字符。

append

字符串后追加一个字符串。

operator+=

字符串后追加字符串str.

insert

在某个位置插入字符或字符串。

但注意要谨慎使用insert因为在头部或中间位置插入必然要挪动数据。大量使用会降低程序效率。

find

字符串的某个位置开始查找第一个位置的字符或字符串。找到就返回目标起始位置。

需要注意的是如果不存在查找目标,那就返回npos

erase

在某个位置删除一个或多个字符

需要注意的是,如果用数字作为位置的话,len大于剩余字符串的长度或是npos。

只会删除到最后一个位置的字符。

注意erase也需要谨慎使用,因为删除也要挪动数据。

replace

字符串的一部分替换为一个字符或字符串。

repalce也会挪动数据所以也不要大量使用。

c_str

返回C格式字符串.兼容c语言返回c语言字符串的首地址。

如果len大于pos后的字符长度或len==npos。

就从pos构造到最后一个位置。

find_first_of

在一个string中查找出现在另一个字符串的字符第一次出现的位置

另外再字符串中表示转义字符如\n,只需要多加一个\即可。因为对\转义字符转义后就表示不是转义字符了。

find_last_of

在一个string从后往前查找出现在另一个字符串的字符第一次出现的位置。

这时我们就可以利用这个接口完成windows或linux下的路径分割。

substr

用另一个string从pos位置后的len个字符构造string。

2.5string类非成员函数

上面的几个接口大家了解一下,下面的OJ题目中会有一些体现他们的使用。string类中还有一些其他的操作,这里不一一列举,大家在需要用到时不明白了查文档即可。

operator+

在这里插入图片描述

这里perator+重载成全局的是为了支持这样的写法。

如果重载成成员函数,那this指针就会锁定左边第一个位置。

也就不支持,字符串+string的写法了。relational operators

支持string与string或字符串比较。

在这里插入图片描述

getlibe

自定义IO输入终止符。

以这道题为例。

题目:最后一个单词的长度

2.6字符串补充接口

刷题时可能需要用到一些快速判断的接口。

在这里插入图片描述

二.vs和g++下string结构的说明

注意:下述结构是在32位平台下进行验证,32位平台下指针占4个字节。

vs下string的结构

string总共占28个字节,内部结构稍微复杂一点,先是有一个联合体,联合体用来定义string中字符串的存储空间:

当字符串长度小于16时,使用内部固定的字符数组来存放

当字符串长度大于等于16时,从堆上开辟空间

<code>union _Bxty

{ // storage for small buffer or pointer to larger one

value_type _Buf[_BUF_SIZE];

pointer _Ptr;

char _Alias[_BUF_SIZE]; // to permit aliasing

} _Bx;

这种设计也是有一定道理的,大多数情况下字符串的长度都小于16,那string对象创建好之后,内部已经有了16个字符数组的固定空间,不需要通过堆创建,效率高。

其次:还有一个size_t字段保存字符串长度,一个size_t字段保存从堆上开辟空间总的容量.

最后:还有一个指针做一些其他事情。

故总共占16+4+4+4=28个字节。

g++下string的结构

G++下,string是通过写时拷贝实现的,string对象总共占4个字节,内部只包含了一个指针,该指针将来指向一块堆空间,内部包含了如下字段:

二. string的实现

2.1string的定义

这里我们用一个char*指针指向字符串空间。

一个size表示有效字符个数。一个capacity表示空间大小。

在定义一个npos。

<code>class string

{

private:

char* _s;

size_t _size;

size_t _capacity;

static const size_t npos;

};

前面我们说静态成员不能再声明的位置给缺省值,因为他不走初始化列表。但是注意这里的static const相当于就是一个定义,可以给缺省值。可以认为是编译器特殊处理了。并且只有static const 整形可以。

private:

char* _s;

size_t _size;

size_t _capacity;

static const size_t npos=-1;

static const int N = 10;

int buff[N];

};

某种程度可以理解为这样的设计,方便定义一个整形常量。去定义一个数组。

2.2 构造和拷贝构造

这里我们给一个缺省值就可以构造函数和拷贝构造都一起实现。注意缺省值要给空字符串而不能给空指针,表示有一个字符串但字符串为空。同时申请空间时要多开一个给\0。

string::string(const char* str="")code>

{

_capacity = _size = strlen(str);

_s = new char[_size + 1];

strcpy(_s, str);

}

2.3 operator[]

直接返回字符的引用即可。

operator[]还可以实现const版本只读不写。

char& string::operator[](size_t pos)

{

assert(pos < _size);

return _s[pos];

}

const char& string::operator[](size_t pos) const

{

assert(pos < _size);

return _s[pos];

}

2.4 迭代器

迭代器就是模拟指针的行为。

我们直接返回第一个字符和最后一个字符端点指针即可。

typedef char* iterator;

typedef const char* const_iterator;

string::const_iterator string::begin() const

{

return _s;

}

string::const_iterator string::end() const

{

return _s + _size;

}

string::iterator string::begin()

{

return _s;

}

string::iterator string::end()

{

return _s+_size;

}

还有注意范围for必须按照库里的命名风格走,他只是傻瓜式的替换。

例如我们把begin换成大写的。范围for我们自己写的迭代器能跑,范围for不行。

2.5 string比较

这里我们实现operator<和operator==再复用即可。

<code>bool operator<(const string& s1, const string& s2)

{

return strcmp(s1.c_str(), s2.c_str())<0;

}

bool operator>(const string& s1, const string& s2)

{

return !(s1 <= s2);

}

bool operator==(const string& s1, const string& s2)

{

return strcmp(s1.c_str(), s2.c_str())==0;

}

bool operator<=(const string& s1, const string& s2)

{

return s1 == s2 || s1 < s2;

}

bool operator>=(const string& s1, const string& s2)

{

return !(s1 < s2);

}

bool operator!=(const string& s1, const string& s2)

{

return !(s1 == s2);

}

2.6 reserve

这里我们直接new手动开空间,注意要多开一个给\0.

然后拷贝原数据。释放旧空间。

void string::reserve(size_t n)

{

if (n > _capacity)

{

char*tmp = new char[n+1];

strcpy(tmp, _s);

delete[] _s;

_s = tmp;

_capacity = n;

}

}

2.7 push_back

这里插入我们先检查一下是否需要扩容。然后再进行插入,同时size++,末尾补上\0

void string::push_back(char ch)

{

if (_size == _capacity)

{

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

}

_s[_size++] = ch;

_s[_size] = '\0';

}

2.8 append

这里我们先计算插入字符串的长度。然后检查一下二倍扩容是否够。不够就申请size+len的空间。再拷贝数据,更新size即可。

void string::append(const char* str)

{

size_t len = strlen(str);

if (_size+len > _capacity)

{

reserve(_size + len>2*_capacity? _size + len:2*_capacity);

}

strcpy(_s + _size, str);

_size += len;

}

2.9 operator+=

这里我们直接复用append和push_back即可。

string& string::operator+=(const char* str)

{

append(str);

return *this;

}

string& string::operator+=(char ch)

{

push_back(ch);

return *this;

}

2.10 insert

这里我需要检查扩容。然后再挪动数据。插入数据,再更新size即可。

void string::insert(size_t pos, char ch)

{

assert(pos <= _size);

if (_size == _capacity)

{

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

}

for (int i = _size+1; i >pos; i--)

{

_s[i] = _s[i-1];

}

_s[pos] = ch;

_size++;

}

void string::insert(size_t pos, const char* str)

{

int len = strlen(str);

assert(pos <= _size);

if (_size+len > _capacity)

{

reserve(_size + len >2*_capacity ? _size + len : 2 * _capacity);

}

for (int i = _size+len; i >=pos+len; i--)

{

_s[i] = _s[i-len];

}

int j = 0;

for (int i = pos; i <pos+len; i++)

{

_s[i] = str[j++];

}

_size+=len;

}

2.11 find

find查找

size_t string::find(char ch, size_t pos)

{

assert(pos < _size);

for (int i = pos; i < _size; i++)

{

if (_s[i] == ch)

{

return i;

}

}

return npos;

}

size_t string::find(const char* str, size_t pos)

{

assert(pos < _size);

const char* ch = strstr(_s+pos, str);

if (ch == nullptr)

{

return npos;

}

return ch - _s;

}

2.12 clear

直接把size改为0,同时在补上\0即可。

void string::clear()

{

_s[0] = '\0';

_size = 0;

}

2.13erase

如果pos开始的len个字符长度超过剩余的最大长度。那就直接把pos位置不上/0,更改size即可。

如果长度不超过剩余的最大长度,那就直接挪动数据。

再更改size即可。

void string::erase(size_t pos, size_t len)

{

assert(pos >= 0 && pos < _size);

if (pos + len >= _size )

{

_s[pos] = '\0';

_size = pos;

}

else

{

for (int i = pos+len; i <= size(); i++)

{

_s[i-len] = _s[i];

}

_size -= len;

}

}

2.13 IO流

operator<< 输出直接遍历字符输出即可。

operator>>输入为了避免频繁插入扩容和空间浪费

我们先用一个大小适中的字符数据存储读取数据。

当字符数据满了就把字符数据尾插入到str。

依次这样读取数据即可。

当读取结束再将字符数据的数据尾插str即可。

ostream& operator<<(ostream& out, const string& str)

{

for (auto& x : str)

{

out << x;

}

return out;

}

istream& operator>>(istream& in, string& str)

{

str.clear();//清空数据

char ch;

const int N = 256;

char buff[N];//定义字符数组

int i = 0;

ch = in.get();//字符

while (ch != ' ' && ch != '\n')//遇到空格和换行结束

{

buff[i++] = ch;

if (i == N - 1)//空间满

{

buff[i] = '\0';

str += buff;//将数据插入str

i = 0;

}

ch = in.get();//继续读取。

}

if (i > 0)//读取结束且还有数据未插入

{

buff[i] = '\0';

str += buff;//将数据插入str

}

return in;

}

2.15 operator=

这里我们可以手动new空间在拷贝内容。更新size和capacity。

也可用算法库里的swap交换。相当于让编译器帮我们干活。

void string::swap(string& str)

{

std::swap(_s, str._s);

std::swap(_size, str._size);

std::swap(_capacity, str._capacity);

}

string& string::operator=(const string& tmp)//传统写法

{

if (this != &tmp)

{

delete[] _s;

_s = new char[tmp._capacity + 1];

strcpy(_s, tmp._s);

_size = tmp._size;

_capacity = tmp._capacity;

}

return *this;

}

string& string::operator=(string tmp)

{

swap(tmp);

return *this;

}

后言

这就是string类深度解剖及其模拟实现。大家不熟悉string的可以去官方查文档。今天就分享到这,感谢大家的耐心垂阅!咱们下期见!拜拜~



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。