【C++练级之路】【Lv.6】【STL】string类的模拟实现

2024-01-16 10:28
文章标签 c++ 实现 string 模拟 stl 练级 lv.6

本文主要是介绍【C++练级之路】【Lv.6】【STL】string类的模拟实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 引言
  • 一、成员变量
  • 二、默认成员函数
    • 2.1 constructor
    • 2.2 copy constructor
    • 2.3 destructor
    • 2.4 operator=
  • 三、迭代器
    • 3.1 begin
    • 3.2 end
  • 四、元素访问
    • 4.1 operator[ ]
  • 五、容量
    • 5.1 size
    • 5.2 capacity
    • 5.3 reserve
    • 5.4 resize
  • 六、修改
    • 6.1 push_back
    • 6.2 append
    • 6.3 operator+=
    • 6.4 insert
    • 6.5 erase
    • 6.6 swap
    • 6.7 clear
  • 七、操作
    • 7.1 c_str
    • 7.2 find
  • 八、非成员函数
    • 8.1 relational operators
    • 8.2 operator<<
    • 8.3 operator>>
  • 总结

欢迎各位小伙伴关注我的专栏，和我一起系统学习C语言，共同探讨和进步哦！

学习专栏：

《进击的C++》

引言

关于STL容器的学习，我会采用模拟实现的方式，以此来更加清楚地了解其底层原理和整体架构。而string类更是有100多个接口函数，所以模拟实现的时候只会调重点和常见的函数进行实现，以此加强对重点函数的掌握。

一、成员变量

string类中包含了

  • str（指向动态开辟的字符数组）
  • _size（当前有效数据个数）
  • _capacity（最大有效容量）

同时，还包含了一个static修饰的静态成员变量npos，赋值为-1，因其类型为无符号整型，则表示最大值。

class string
{
private:char* _str;size_t _size;size_t _capacity;static size_t npos;
};size_t string::npos = -1;

标准的静态成员变量，是在类内声明，类外定义。但是，这里设计出了一种奇怪的语法，加上const修饰，就可以在类内声明加定义。

static const size_t npos = -1;

二、默认成员函数

2.1 constructor

细节：

  1. 因为计算_size和_capacity都要调用strlen函数，为了防止频繁调用，在初始化列表中调用一次将_size初始化，后续再把_size赋值给_capacity
  2. _capacity初始化时，防止后续二倍扩容时_capacity为0，则加上判断，如果_size为0，初始_capacity为3
  3. 开辟空间的大小为_capacity + 1，因为要留一个空间给\0
  4. 缺省参数为空串
string(const char* str = ""):_size(strlen(str))
{_capacity = _size == 0 ? 3 : _size;_str = new char[_capacity + 1];strcpy(_str, str);
}

2.2 copy constructor

string(const string& s):_size(s._size), _capacity(s._capacity)
{_str = new char[_capacity + 1];strcpy(_str, s._str);
}

2.3 destructor

~string()
{delete[] _str;_str = nullptr;_size = _capacity = 0;
}

2.4 operator=

细节：

  1. 先开辟一段新空间，再释放旧空间，防止空间不足（一般空间相等的很少，所以大多数情况下不相等，直接开辟新空间）
  2. 原地赋值则什么都不做，否则释放了旧空间，就没办法拷贝字符串
string& operator=(const string& s)
{if (this != &s){char* tmp = new char[s._capacity + 1];delete[] _str;_str = tmp;strcpy(_str, s._str);_size = s._size;_capacity = s._capacity;}return *this;
}

三、迭代器

3.1 begin

迭代器的实现和编译器有关，不同的编译器有不同的实现方式。这里简单的用指针来实现迭代器。

同时，重载了普通迭代器和const迭代器。

typedef char* iterator;
typedef const char* const_iterator;iterator begin()
{return _str;
}const_iterator begin() const
{return _str;
}

3.2 end

迭代器遵循左闭右开的原则，begin指向首元素，end指向末元素的下一位。

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

悄悄告诉你：范围for的底层实现，就是运用了迭代器。

四、元素访问

4.1 operator[ ]

为了方便的访问元素，我们重载了[ ]运算符。同时，也分为普通版本和const版本，对应不同string类的权限。

char& operator[](size_t pos)
{assert(pos < _size);return _str[pos];
}const char& operator[](size_t pos) const
{assert(pos < _size);return _str[pos];
}

五、容量

5.1 size

获取当前有效数据个数

细节：const修饰，保证普通和const类型string类都能访问

size_t size() const
{return _size;
}

5.2 capacity

获取当前最大有效容量

细节：同上

size_t capacity() const
{return _capacity;
}

5.3 reserve

改变当前_capacity（将其变为指定大小n）

细节：

  1. 只扩容，不缩容（因为缩容也是有代价的）
  2. 异地扩容，新开辟一个新空间，将内容拷贝过去，再释放旧空间（事实上，原地扩容只占极少数，绝大部分扩容都是异地扩容）
void reserve(size_t n)
{if (n > _capacity){char* tmp = new char[n + 1];strcpy(tmp, _str);delete[] _str;_str = tmp;_capacity = n;}
}

5.4 resize

改变当前_size（将其变为指定大小n），分为三种情况：

  1. n <= _size，在_size位置写入\0
  2. _size < n <= _capacity，填充指定字符ch直到_size为n，再重复步骤1
  3. n > _capacity，先扩容，再重复步骤2
void resize(size_t n, char ch = '\0')
{if(n > _size){reserve(n);memset(_str + _size, ch, n - _size);}_size = n;_str[_size] = '\0';
}

六、修改

6.1 push_back

尾插一个字符

细节：

  1. 如果空间不够，则二倍扩容
  2. 插入字符后，在尾部添加\0
void push_back(char ch)
{if (_size + 1 > _capacity){reserve(_capacity * 2);}_str[_size] = ch;++_size;_str[_size] = '\0';
}

6.2 append

尾插（追加）一个字符串

细节：

  1. 如果空间不够，扩容到刚好可以容纳的空间（因为二倍扩容有可能也不够）
  2. strcpy会自动把\0也拷贝过去
void append(const char* str)
{size_t len = strlen(str);if (_size + len > _capacity){reserve(_size + len);}strcpy(_str + _size, str);_size += len;
}

悄悄说一句：其实这个函数写成push_back的重载函数更好哦~

6.3 operator+=

为了更加方便地使用尾插，我们重载了+=运算符，这样无论尾插字符或者字符串都极为方便。

string& operator+=(char ch)
{push_back(ch);return *this;
}string& operator+=(const char* str)
{append(str);return *this;
}

6.4 insert

在指定位置插入一个字符

细节：

  1. 如果空间不够，二倍扩容
  2. 从pos位置开始，字符都后移一格（这里end = _size + 1 就是为了避免end == pos的判断，因为头插时pos为0，而end为无符号整数恒大于等于0，所以会导致死循环）
  3. 在pos位置插入指定字符
string& insert(size_t pos, char ch)
{assert(pos <= _size);if (_size + 1 > _capacity){reserve(_capacity * 2);}size_t end = _size + 1;while (end > pos){_str[end] = _str[end - 1];--end;}_str[pos] = ch;++_size;return *this;
}

其实，步骤2的字符后移，可以使用memmove函数（专门处理重叠空间的移动）

memmove(_str + pos + 1, _str + pos, _size + 1 - pos);

在指定位置插入一个字符串

细节：

  1. 如果空间不够，扩容到刚好可以容纳的空间
  2. 从pos位置开始，字符都后移 len 格（这里len为1的时候，其实就是上一种情况）
  3. 在pos位置用strncpy插入指定字符串（不带\0)
string& insert(size_t pos, const char* str)
{assert(pos <= _size);size_t len = strlen(str);if (_size + len > _capacity){reserve(_size + len);}size_t end = _size + 1;while (end > pos){_str[end + len - 1] = _str[end - 1];--end;}strncpy(_str + pos, str, len);_size += len;return *this;
}

同样，步骤2的字符后移 len 格，也可以使用memmove函数。

memmove(_str + pos + len, _str + pos, _size + 1 - pos);

那么，完成了指定位置的插入，我们就可以复用代码，让push_back和append复用insert函数。

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

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

6.5 erase

在指定位置删除指定长度的字符串

细节：

  1. npos要单独判断（要不然npos加上pos会溢出）
  2. len为npos，或者pos+len >= _size，代表将删除pos位置往后的所有字符串
  3. 如果pos+len < _size，则将后面未删除的字符串用strcpy拷贝到pos位置
string& erase(size_t pos, size_t len = npos)
{assert(pos < _size);if(len == npos || pos + len >= _size){_size = pos;_str[_size] = '\0';}else{strcpy(_str + pos, _str + pos + len);_size -= len;}return *this;
}

6.6 swap

交换两个string类的值

细节：使用std库中的swap函数，交换各个成员变量的值

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

6.7 clear

清空字符串

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

七、操作

7.1 c_str

获取字符串

细节：const修饰，保证普通和const类型string类都能访问

const char* c_str() const
{return _str;
}

7.2 find

查找指定字符或者字符串，返回其下标

细节：

  1. 使用缺省参数pos = 0，可以从指定位置开始向后查找，如果未指定，则从头查找
  2. 查找字符串用strstr函数，找到返回指针，用指针-指针的方式得到下标
size_t find(char ch, size_t pos = 0)
{assert(pos < _size);for (size_t i = pos; i < _size; ++i){if (_str[i] == ch){return i;}}return npos;
}size_t find(const char* str, size_t pos = 0)
{assert(pos < _size);char* p = strstr(_str, str);if (p == nullptr){return npos;}return p - _str;
}

八、非成员函数

8.1 relational operators

重载比较关系的运算符

细节：

  1. 一般实现了两个，剩下的都可以复用
  2. this指针用const修饰，保证普通和const的string类都可以相互比较（正着比，反着比都可以）
bool operator==(const string& s) const
{return strcmp(_str, s._str) == 0;
}bool operator!=(const string& s) const
{return !(*this == s);
}bool operator>(const string& s) const
{return strcmp(_str, s._str) > 0;
}bool operator>=(const string& s) const
{return *this > s || *this == s;
}bool operator<(const string& s) const
{return !(*this >= s);
}bool operator<=(const string& s) const
{return !(*this > s);
}

8.2 operator<<

重载流插入运算符

细节：遍历字符串，可以采用下标+[ ]的循环形式，也可以使用范围for

ostream& operator<<(ostream& out, const string& s)
{for (auto& ch : s){out << ch;}return out;
}

8.3 operator>>

重载流提取运算符

细节：

  1. 每次流插入之前，先清理字符串，防止写入的内容连接在之前的内容后面
  2. 提取字符时使用get函数。因为>>运算符在缓冲区中提取字符时，会自动忽略空格和换行，而get函数可以全部提取出来。
istream& operator>>(istream& in, string& s)
{s.clear();char ch = in.get();while (ch != ' ' && ch != '\n'){s += ch;ch = in.get();}return in;
}

以上代码是能够完成功能的实现，但是从效率的角度考虑，还是不够高效。所以，我们可以优化一下：

  1. 创建一个小型字符数组buf
  2. 提取的字符先填充到buf
  3. 等buf填充满后，再将buf尾插到s
  4. 如果循环结束，buf中还有剩余字符，则再尾插到s
istream& operator>>(istream& in, string& s)
{s.clear();char ch = in.get();size_t i = 0;char buf[128] = { 0 };while (ch != ' ' && ch != '\n'){buf[i++] = ch;if(i == 127){s += buf;i = 0;}ch = in.get();}if (i != 0){s += buf;}return in;
}

总结

我们来模拟实现string类，不是为了造一个更好的轮子，而是熟练掌握重点函数的功能与应用，顺便巩固之前学习的C++语法。常言道，没学过STL，那你根本没学过C++！C++的梦幻之旅，才刚刚开始……

看到这里了还不给博主扣个： ⛳️ 点赞☀️收藏 ⭐️ 关注！ 💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖
拜托拜托这个真的很重要！ 你们的点赞就是博主更新最大的动力！ 有问题可以评论或者私信呢秒回哦。

这篇关于【C++练级之路】【Lv.6】【STL】string类的模拟实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/612251。

相关文章

python使用watchdog实现文件资源监控

python使用watchdog实现文件资源监控

《python使用watchdog实现文件资源监控》watchdog支持跨平台文件资源监控,可以检测指定文件夹下文件及文件夹变动,下面我们来看看Python如何使用watchdog实现文件资源监控吧... python文件监控库watchdogs简介随着Python在各种应用领域中的广泛使用，其生态环境也
阅读更多...
el-select下拉选择缓存的实现

el-select下拉选择缓存的实现

《el-select下拉选择缓存的实现》本文主要介绍了在使用el-select实现下拉选择缓存时遇到的问题及解决方案,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录项目场景：问题描述解决方案：项目场景：从左侧列表中选取字段填入右侧下拉多选框，用户可以对右侧
阅读更多...
深入理解C++ 空类大小

深入理解C++ 空类大小

《深入理解C++空类大小》本文主要介绍了C++空类大小,规定空类大小为1字节,主要是为了保证对象的唯一性和可区分性,满足数组元素地址连续的要求,下面就来了解一下... 目录1. 保证对象的唯一性和可区分性2. 满足数组元素地址连续的要求3. 与C++的对象模型和内存管理机制相适配查看类对象内存在C++中，规
阅读更多...
Python pyinstaller实现图形化打包工具

Python pyinstaller实现图形化打包工具

《Pythonpyinstaller实现图形化打包工具》：本文主要介绍一个使用PythonPYQT5制作的关于pyinstaller打包工具,代替传统的cmd黑窗口模式打包页面,实现更快捷方便的... 目录1.简介2.运行效果3.相关源码1.简介一个使用python PYQT5制作的关于pyinstall
阅读更多...
使用Python实现大文件切片上传及断点续传的方法

使用Python实现大文件切片上传及断点续传的方法

《使用Python实现大文件切片上传及断点续传的方法》本文介绍了使用Python实现大文件切片上传及断点续传的方法,包括功能模块划分（获取上传文件接口状态、临时文件夹状态信息、切片上传、切片合并）、整... 目录概要整体架构流程技术细节获取上传文件状态接口获取临时文件夹状态信息接口切片上传功能文件合并功能小
阅读更多...
python实现自动登录12306自动抢票功能

python实现自动登录12306自动抢票功能

《python实现自动登录12306自动抢票功能》随着互联网技术的发展,越来越多的人选择通过网络平台购票,特别是在中国,12306作为官方火车票预订平台,承担了巨大的访问量,对于热门线路或者节假日出行... 目录一、遇到的问题？二、改进三、进阶–展望总结一、遇到的问题？1.url-正确的表头：就是首先ur
阅读更多...
C#实现文件读写到SQLite数据库

C#实现文件读写到SQLite数据库

《C#实现文件读写到SQLite数据库》这篇文章主要为大家详细介绍了使用C#将文件读写到SQLite数据库的几种方法,文中的示例代码讲解详细,感兴趣的小伙伴可以参考一下... 目录1. 使用 BLOB 存储文件2. 存储文件路径3. 分块存储文件《文件读写到SQLite数据库China编程的方法》博客中，介绍了文
阅读更多...
Redis主从复制实现原理分析

Redis主从复制实现原理分析

《Redis主从复制实现原理分析》Redis主从复制通过Sync和CommandPropagate阶段实现数据同步,2.8版本后引入Psync指令,根据复制偏移量进行全量或部分同步,优化了数据传输效率... 目录Redis主DodMIK从复制实现原理实现原理Psync: 2.8版本后总结Redis主从复制实
阅读更多...
JAVA利用顺序表实现“杨辉三角”的思路及代码示例

JAVA利用顺序表实现“杨辉三角”的思路及代码示例

《JAVA利用顺序表实现“杨辉三角”的思路及代码示例》杨辉三角形是中国古代数学的杰出研究成果之一,是我国北宋数学家贾宪于1050年首先发现并使用的,：本文主要介绍JAVA利用顺序表实现杨辉三角的思... 目录一：“杨辉三角”题目链接二：题解代码：三：题解思路：总结一：“杨辉三角”题目链接题目链接：点击这里
阅读更多...
基于Python实现PDF动画翻页效果的阅读器

基于Python实现PDF动画翻页效果的阅读器

《基于Python实现PDF动画翻页效果的阅读器》在这篇博客中,我们将深入分析一个基于wxPython实现的PDF阅读器程序,该程序支持加载PDF文件并显示页面内容,同时支持页面切换动画效果,文中有详... 目录全部代码代码结构初始化 UI 界面加载 PDF 文件显示 PDF 页面页面切换动画运行效果总结主
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2