当前位置：首页 > news >正文

[CPP6] string模拟实现

news 2025/7/1 12:22:27

1. string 介绍

2. string重要接口介绍

2.1. 构造

2.1.1. sizeof(string)

2.1.2. string::npos

2.1.3. c_str()

2.2. 遍历

2.2.1. 下标 + 方括号遍历

2.2.2. 迭代器遍历(重点: 迭代器)

2.2.3. 范围 for 遍历

2.3. capacity

2.3.1. size() == length()

2.3.2. max_size()

2.3.3. string 扩容机制

2.3.4. clear()

2.3.5. shrink_to_fit()

2.3.6. reserve -> 扩容

2.3.7. resize()

2.4. element access([] 元素访问)

2.5. modify

2.5.1. push_back/append/+=

2.5.2. erase

2.5.3. replace 替换练习

2.5.4. string 可用的三个 swap -> 设计的精妙

2.6. String operations

2.6.1. c_str C语言字符串

2.6.2. find 的使用练习: 去文件后缀 + 分割网址

2.6.3. substr 取子串

2.6.4. find_first_of,find_last_of,find_first_not_of,find_last_not_of(strtok)

2.7. Non-member function overloads(非成员函数重载)

2.7.1. operator+ 为啥重载两份?

2.7.2. operator<< 流插入 operator>>流提取

2.7.3. getline()

3. string的模拟实现

3.1. string结构的设计

3.2. string构造函数

3.2.1. 构造函数

3.2.2. 拷贝构造函数

3.2.3. 赋值运算符重载

3.3. 析构函数

3.4. 遍历

3.4.1. operator[]重载

3.4.2. 迭代器与范围 for

3.5. 字符/字符串插入

3.5.1. 尾插一个字符

3.5.2. 尾插一个字符串

3.5.3. +=字符串

3.5.4. 任意位置插入字符

3.6. erase函数

3.7. resize函数接口

3.8. swap交换

3.9. 取子串函数接口substr

3.10. operator==赋值重载及其它判断符重载

3.11. 流插入和流提取接口

3.11.1. 流插入接口

3.11.2. 流提取接口

3.11.3. getline接口

3.12. find接口

3.12.1. 在一个字符串中找一个字符

3.12.2. 在一个字符串中找一个子串

3.13. 所有代码一览

1. string 介绍

STL归类问题：string 因出现较早, 没有归类到 STL 中. string 概念: 字符串是表示字符序列的对象.

string 是经过特化的类:

std::string

typedef basic_string<char> string;

std::wstring (windows 可能会用到)

typedef basic_string<wchar_t> wstring;

std::u16string (明确规定了是 u_16 编码)

typedef basic_string<char16_t> u16string;

std::u32string (明确规定了是 u_32 编码)

typedef basic_string<char32_t> u32string;

string 的意义: C 语言是直接开固定空间的字符数组, 开多了浪费, 开少了不够用, 关键是数组这个玩意还不支持运行时扩容! 内部更加灵活. 内部自动开空间释放空间, 是更加方便安全高效的.

2. string重要接口介绍

2.1. 构造

2.1.1. sizeof(string)

string 的构造问题: 其大小是 28 字节(32 平台下), 其具体构造因不同平台而异.

VS2022 与 gcc 的 string 构造

VS下string的结构
string总共占28个字节, 内部结构稍微复杂一点

联合体: 定义 string 的存储空间. 当字符串长度小于16时, 使用内部固定的字符数组来存放, 当字符串长度大于16时, 从堆上开辟空间.

union _Bxty
{value_type _Buf[_BUF_SIZE];pointer_Ptr;char _Alias[BUF_SIZE];
}_Bx;

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

size 表示字符串长度, capacity 表示总空间大小.
最后, 还有一个指针做一些其他事情.

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

总空间大小
字符串有效长度
引用计数

struct _Rep_base
{size_type _M_length;//总空间大小size_type _M_capacity;//字符串有效长度_Atomic_word _M_refcount;//引用计数
};

指向堆空间的指针, 用来存储字符串

2.1.2. string::npos

2.1.3. c_str()

c_string: 后面带一个 `\0`, 以 `\0` 为结束标志的字符串.

2.2. 遍历

2.2.1. 下标 + 方括号遍历

为啥要重载一个 const 版本和非 const 版本?

因为有可能会给一个 const 对象~

2.2.2. 迭代器遍历(重点: 迭代器)

iterator 的简单介绍

迭代器是一种各种容器统一, 其中封装了遍历容器的逻辑和状态从而使得用户以一种统一的方式对不同容器进行遍历操作而忽略容器具体实现细节的设计模式(编程概念).

迭代器相比 operator[] 的优势在于, 通过屏蔽底层实现细节的方式, 迭代器对于所有容器都是统一的, 通用的.

迭代器类型分为多种，比较常见的有：

普通迭代器iterator: -> 可读可写
反向迭代器reverse_iterator:
const 迭代器const_iterator: -> 只读迭代器
const 反向迭代器const_reverse_iterator:

begin和end是一种左闭右开的范围

需要注意的是，反向迭代器在实际实践中用的比较少.

2.2.3. 范围 for 遍历

范围for 是迭代器的进一步封装调用.

范围 for 的底层是 begin()和 end(), 也就是迭代器, 是一样的, 只不过套了壳而已.

2.3. capacity

2.3.1. size() == length()

历史原因导致的, length()出现更早, size()更加通用.

2.3.2. max_size()

最大长度是多少, 没意义, 一般来说是平台不同, max_size()值也不同...

2.3.3. string 扩容机制

探究一下 string 的扩容机制: 在不同平台下, 扩容机制均不相同(VS 下是 1.5 倍, Linux 是 2 倍速).

//探索capacity的扩容机制
string s;
size_t sz = s.capacity();
cout << s.capacity() << endl;for (int i = 0; i < 1000; i++)
{s.push_back('x');if (sz != s.capacity()){cout << s.capacity() << endl;sz = s.capacity();}
}

2.3.4. clear()

clear() 清数据, 一般不会缩空间.

2.3.5. shrink_to_fit()

可以缩容, 但是不会缩小到 0(取决于平台, VS 下至少是 15).

2.3.6. reserve -> 扩容

void reserve (size_t n = 0);

区分两个单词：reserve 保留； reverse 翻转

这个地方写算法题的时候尽量用 resize, 只给空间直接访问就会坑.
不同平台下的扩容策略不一定, VS 下是多给, 而 Linux 是你要多少给你多少.
reserve 在 VS 下不会缩容, 但是也不一定... 通常不会缩容.

2.3.7. resize()

void resize (size_t n);
void resize (size_t n, char c);

n < s.size() 执行删除操作
n = s.size() 不做任何操作
n > s.size() && n < s.capacity() 会填充一些字符
n > s.capacity 扩容并且填充一些字符

2.4. element access([] 元素访问)

char& at (size_t pos);
const char& at (size_t pos) const;

operator[] 与 at() 的异同: 越界检查有所不同, at 会抛出异常, [] 会断言报错(停止程序).

2.5. modify

2.5.1. push_back/append/+=

push_back: 插入单个字符.

append: 插入一个字符串.

+=: 经常用的是+=, 单个字符/字符串都可以.

2.5.2. erase

删除~ 唯一需要注意的是这个接口的效率在删除一部分的时候效率一般(O(N)).

2.5.3. replace 替换练习

效率比较低, 建议少用.

// 第一种效率一般
string s("do you know my apple?\n");
size_t pos = s.find(' ');
while (pos != s.npos)
{s.replace(pos, 1, "%20");pos = s.find(' ');
}
cout << s << endl;// 第二种思路更好, 效率更佳
string s("do you know my apple?\n");
string ret;
for (auto& ch : s)
{if (ch == ' '){ret += "%20";}else{ret += ch;}
}
cout << ret << endl;

2.5.4. string 可用的三个 swap -> 设计的精妙

string 中特有的 swap 函数

问题：算法库中也提供了swap，这里string为什么要专门写一个swap进行交换呢？？？

string::swap是专门针对于string交换的，很高效。
算法库中的swap是一种模板，优点是对所有STL都适用，缺点是效率对string来说一般。

莫名其妙调用的string中的swap ->

一般有三个swap，即:

算法库中实现的全局swap函数模板、string中类外的全局swap、string类内的swap. string 通过设计一个全局的 swap 和类内的 swap, 达到即使程序员包含了算法头文件的情况下, 也会优先使用 string::swap, 因为 string::swap 是具体的函数, 而 algorithm::swap 是模板.

注意：insert/erase/replace效率都很一般

2.6. String operations

2.6.1. c_str C语言字符串

string要兼容c-string，原因在于CPP是由C发展而来的.

返回一个C语言字符串.

2.6.2. find 的使用练习: 去文件后缀 + 分割网址

find有点类似于我们C语言中用的strstr函数.

查找函数，支持多种查找方式.

//取文件后缀
string s("test.bilibili.cpp.zip.txt");
size_t pos = s.rfind('.');
cout << s.substr(pos, string::npos);

// 网址分为协议、域名、网址
// Protocol domain name URL
string s("https://legacy.cplusplus.com/reference/string/string/substr/");
string protocol/*协议*/, domain/*域名*/, url/*ui*/;
size_t p = s.find(':');
size_t d = s.find('/', p + 3);
if (p != string::npos) // 如果找得到p. protocol = s.substr(0, p);
if (d != string::npos) // 如果找得到d点. domain = s.substr(p + 3, d - p - 3);url = s.substr(d, string::npos);
cout << protocol << endl;
cout << domain << endl;
cout << url << endl;

2.6.3. substr 取子串

string substr (size_t pos = 0, size_t len = npos) const;

2.6.4. find_first_of,find_last_of,find_first_not_of,find_last_not_of(strtok)

这四个函数有点类似于strtok函数，属于一种匹配的函数。在字符串中查找与指定字符集合中任意一个字符匹配的第一个位置.

// string::find_first_of
#include <iostream>       // std::cout
#include <string>         // std::string
#include <cstddef>        // std::size_tint main ()
{std::string str ("Please, replace the vowels in this sentence by asterisks.");std::size_t found = str.find_first_of("aeiou");while (found!=std::string::npos){str[found]='*';found=str.find_first_of("aeiou",found+1);}std::cout << str << '\n';return 0;
}

2.7. Non-member function overloads(非成员函数重载)

2.7.1. operator+ 为啥重载两份?

原因：全局 operator+(), 支持string + "123" 也支持 "123" + string.

2.7.2. `operator<<` 流插入 `operator>>`流提取

下面程序会死循环：

std::istream& operator>>(std::istream& in, string& str)
{char ch;std::cin >> ch; // 从流里面读一个字符，这个字符不包含空格while (ch != ' ' && ch != '\n'){str += ch;std::cin >> ch;}return in;
}

cin会自动忽略空格、换行符

std::istream& operator>>(std::istream& in, string& str)
{str.clear(); // 清理原来的内容char ch;ch = in.get(); // 从流里面读一个字符，这个字符包含空格while (ch != ' ' && ch != '\n'){str += ch;ch = in.get();}return in;
}

2.7.3. getline()

std::getline (string) C++98C++11

(1) istream& getline (istream& is, string& str, char delim);

(2) istream& getline (istream& is, string& str);

解决cin读入只能读到空格的问题。cin一读到空格就不读了的问题.

注意: C 语言在 unit 系统下也有一个 getline 函数.

3. string的模拟实现

3.1. string结构的设计

string底层我们使用字符数组来实现，即顺序表，惟一与顺序表做区分的是我们的string后面默认有个\0，这个需要注意的.

class string
{
private:char* _str;size_t _size;size_t _capacity;
};

3.2. string构造函数

3.2.1. 构造函数

//分开写的情况下：
//无参构造器
string():_str(new char) // 不写nullptr而执意多开一个空间原因在于为'\0'预留位置, 更好的与c_str相结合. , _size(0), _capacity(0)
{_str[0] = '\0'; // 虽然有size维护string的有效字符个数, 多写一个'\0'可以与C_str更好的进行结合. 
}//有参构造器
string(const char* str):_size(strlen(str))
{_capacity = _size;  _str = new char[_size + 1];  strcpy(_str, str); 
}

string(const char* str = "") // ""自带'\0', 可以方便的用作拷贝使用. :_size(strlen(str))
{_capacity = _size; // 该成员一般不包含'\0'在内_str = new char[_capacity + 1];strcpy(_str, str);
}

3.2.2. 拷贝构造函数

// 传统写法 
string(string& s){_capacity = s._capacity;_size = s._size;_str = new char[_capacity + 1]; // string拷贝构造是深拷贝类型, 必须开空间. strcpy(_str, s._str);}

//现代写法
string(string& s)
{string temp(s._str); // 这个地方会去调用构造函数，构造出一个新的堆过来swap(temp);
}

现代写法: 现代写法本质是一种代码复用, 在运行效率上并没有提升.

3.2.3. 赋值运算符重载

string& operator=(const string& s) // 细节: 参数s带const, 防止被反赋值了. 
{// 更新参数_capacity = s._capacity;_size = s._size;delete[] _str;char* temp = new char[_capacity + 1]; // 注意给'\0'预留位置_str = temp;strcpy(_str, s._str);return *this;
}

编译器根据逻辑来调用赋值/构造, 而不是根据写法. 切忌不能单看是不是写的等于号哈，如果string s已存在，string sc正在创建，那调用的就是拷贝构造，如果s和sc都已经存在了，那就是调用的是赋值运算符重载。

/*
//现代写法
string& operator=(const string& s)
{string temp(s.c_str());swap(temp);return *this;
}
*/
//极简版
string& operator=(string temp)
{swap(temp);return *this;
}

3.3. 析构函数

~string()
{delete[] _str; // 注意析构的时候[] 与 new[]一定要匹配. _str = nullptr;_capacity = _size = 0;
}

3.4. 遍历

string的遍历方式主要有三种，其一曰方括号，其二曰迭代器，其三曰范围for；

3.4.1. operator[]重载

char& operator[](size_t pos) // 思考: 这里使用char&类型在于能够支持可读可写. 
{assert(pos < _size); // asser检查相比于C语言的数组访问抽查更加严格, 因而更加安全. return _str[pos];
}

const char& operator[](size_t pos) const // 提供const版本是为了const string的[]实现. /* const 使用的三必要: 1. 防止string字符被修改2. 与非const operator[]构成函数重载3. 编译器自动与const string进行匹配*/
{return _str[pos];
}

3.4.2. 迭代器与范围 for

CPP 中的范围 for 是 begin 和 end 的逻辑替换.

3.5. 字符/字符串插入

3.5.1. 尾插一个字符

void push_back(const char& ch)
{if (_capacity == _size){reserve(_capacity == 0 ? 4 :2*_capacity);}_str[_size++] = ch;_str[_size] = '\0'; // 细节: 带上'\0'
}string& operator+=(const char& ch)
{push_back(ch);
}

3.5.2. 尾插一个字符串

string& append(const char* str)
{size_t len = strlen(str);//扩大s的长度倍数if (len + _size > _capacity){reserve(_capacity + len);}//拷贝数据strcpy(_str + _size, str); // 注：strcpy也会把\0拷贝过去//更新_size_size += len;return *this;
}

3.5.3. +=字符串

string& operator+=(const char* s)
{this->append(s);return *this;
}

3.5.4. 任意位置插入字符

string& insert(size_t pos,char ch)
{assert(pos <= _size);if (_size == _capacity){reserve(_capacity == 0 ? 4 : 2 * _capacity);}//坑1：size_t end必须是-1才会结束循环, 然而end是无符号数, 因此不会停下循环. //size_t end = _size;//while (end >= pos)//{//	_str[end + 1] = _str[end];//	end--;//}//坑2：下面写法会发生隐式类型转换, 比较的时候仍然按照size_t的逻辑进行比较. //int end = _size;//while (end >= pos)//{//	_str[end + 1] = _str[end];//	end--;//}//修改1：修改的方法一就是强制类型转换, 把pos也变成int. int end = _size;while (end >= (int)pos){_str[end + 1] = _str[end];end--;}//修改2：修改的第二种方法是避开负数, 现在我通过修改比较符号和数字, 实现避开负数. /*int end = _size + 1;while (end > pos){_str[end] = _str[end - 1];end--;}*/_str[pos] = ch;_size++;return *this;
}

3.6. erase函数

这个函数是“清理”的意思，第一个pos是从哪开始清理，len是清理删除字符的长度。

void erase(size_t pos, size_t len = npos)
{assert(pos <= _size);if (len == npos || /*pos + len >= _size*/ pos >= _size - len) {                                  // 细节: 尽量避免溢出问题, 因为甲方更容易溢出. _str[pos] = '\0';}else{strcpy(_str + pos, _str + pos + len);}
}

3.7. resize函数接口

这个函数是干啥的呢？重新设置_size大小的。
resize:LINK

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

3.8. swap交换

string 中封装了一个类内 swap 和类外全局 swap, 这样做的好处可以让程序员无意识的使用效率最高的 swap, 而不是首选库中算法 swap 模板.

void swap(string& s)
{std::swap(_str, s._str);std::swap(_capacity, s._capacity);std::swap(_size, s._size);
}

void swap(string& s1, string& s2)
{s1.swap(s2);
}

3.9. 取子串函数接口substr

string substr(size_t pos, size_t len = npos)
{assert(pos < _size);string s;if (len == npos || pos + len >= _size){s += _str + pos;}else{for (size_t i = 0; i < len; i++){s.insert(i, _str[i + pos]);}}return s;
}

注意：npos是不可修改静态全局变量，其值为-1，其声明包含于类内，在类外进行定义, 使用 npos 必须指明 string。

static const int npos;

3.10. operator==赋值重载及其它判断符重载

bool operator==(const string& s1, const string& s2) // 两个参数都带const是因为这样可以提高代码安全性
{int cmp = strcmp(s1.c_str() , s2.c_str());return cmp == 0;
}

operator==() 实现为类内函数存在不能调用问题.

string s1("hello world");
string s2("hello world");//但是这种实现方式有缺陷：
cout << (s1 == s2) << endl;cout << (s1 == "hello world") << endl;//right,隐式类型转换cout << ("hello world" == s2) << endl;// == error,because it is not string//"hello world" == s2 ,即是hello world.operator==(s2);//为了弥补这个缺陷，c++将其实现成了全局函数
//实现为全局函数主要是为了支持char*的隐式类型转换

代码复用逻辑, operator 大小比较通常可以进行代码复用.

bool operator<(const string& s1, const string& s2)
{int cmp = strcmp(s1.c_str(), s2.c_str());return cmp < 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);
}bool operator!=(const string& s1, const string& s2)
{return !(s1 == s2);
}