我要评论在c++中，std::string是一个非常强大的类，用于处理字符串。尽管stl（标准模板库）提供了std::string的实现，了解如何模拟实现一个简单的string类可以帮助深入理解其背后的数据结构和操作。
前言
在c++标准库中，std::string 是一个极其重要且常用的类，它封装了字符串的存储与操作，为开发者提供了高效、安全的字符串处理能力。然而，仅仅停留在“会用”的层面，往往难以深入理解其底层机制与设计精髓。本文旨在通过手动实现一个简化版的 string 类，带领读者从零开始，逐步构建其核心功能，从而深刻理解。
string类的实现框架
string的底层可以看成是数据类型为字符的顺序表，而这个字符顺序表的各种操作都被封装在string类中。string类的基本框架如下
class string
{
public:
string()
{}
成员函数……
private:
char* _str;
size_t size;
size_t capacity;
};⚠ 注意：我们实现string类的时候会和标准库实现的string类产出名字冲突，那应该怎么办呢？用到之前学习的命名空间，将我们自己实现的string类写在命名空间里面就不会有名字冲突了。
📚 知识点回顾：相同名字的命名空间在不同的文件中是相通的，是同一个命名空间
// string.h
#include<iostream>
#include<cstring>
#include<cassert>
namespace pkd
{
class string
{
public:
string()
{}
成员函数……
private:
char* _str;
size_t size;
size_t capacity;
};
}
// string.cpp
#include"string.h"
namespace pkd
{
string成员函数的实现
}一. 默认成员函数
构造函数
- 默认构造函数
string的默认构造函数和普通的顺序表不同，并不是直接将 _str 置为空，而是需要为 _str 开辟空间的。原因如下：
- 字符数组和普通数组不一样，它需要字符’\0’作为结尾标识，所以需要开辟空间存储’\0’
- std::string可以空串直接打印，要能够打印空串就必须要在字符串结尾带上’\0’，不管是否存在有效的数据
- string需要兼容c语言的字符串的风格，所以其封装的字符串格式要和c语言的相同
默认构造的实现
string()
:_str(new char[1]{'\0'})
,_size(0)
,_capacity(0)
{
}
⚠ 注意：string的开辟空间全部统一使用new char[]，这样释放空间时都使用delete[]就不会产生new[]和delete[]没有配对使用的问题。关于new/delete配对使用的详细的讲解，可以点击下面的博客链接观看。
- 传参构造
string较为常用的初始化方式还是使用字符串初始化，它对应的简单的构造函数实现如下：
string(const char* str)
:_str(new char[strlen(str)])
,_size(strlen(str))
,_capacity(strlen(str))
{
strcpy(_str, str); //将str中的数据拷贝到_str中
}
这个实现方式看起来没什么问题，但是效率非常的低，使用了3次strlen函数，下面来看优化版本
string(const char* str = "")
:_size(strlen(str))
{
_str = new char[_size + 1];
_capacity = _size;
strcpy(_str, str); //将str中的数据拷贝到_str中
}
这个优化版本不仅仅提高了效率，同时还将默认构造函数和这个函数结合在一起了，代码中保留这个构造函数即可。
⚠ 注意：这个给 _str 开辟的空间大小为 _size + 1，原因是需要多一个空间存储’\0’，strlen计算出来的str的大小是没有包括’\0’的。同时，通过这点我们又发现string中 _size 和 _capacity 的大小都是没有将’\0’计算在内的。
拷贝构造
拷贝构造函数分为传统版本和现代版本。传统版本就是自己手动的进行深拷贝进行拷贝构造，现代版本就是通过构造函数进行拷贝构造。
string::string(const string& s)
:_size(s._size)
,_capacity(s._capacity)
{
_str = new char[_size + 1];
memcpy(_str, s._str, _size + 1);
}string::string(const string& s)
{
string tmp(s._str);
//swap(*this, tmp);
swap(tmp);
}
现代版本的拷贝构造就不是自己进行深拷贝了，而是使用前面写好了的构造函数进行深拷贝。不过需要注意，使用s._str构造tmp后，需要使用tmp和(*this)进行交换，而这里的交换不建议使用算法库中的swap函数（原因在下面），而是自己手写一个string类的成员函数swap来交换。
void string::swap(string& s)
{
std::swap(_str, s._str);
std::swap(_size, s.s_size);
std::swap(_capacity, s._capacity);
}
算法库中swap的缺陷
使用算法库中的swap进行交换数据效率很低，因为它的交换逻辑通过创建临时对象进行交换，进行一次交换，就要调用3次拷贝构造，效率非常的低。swap的源代码如下
template <class t> void swap ( t& a, t& b )
{
t c(a); a=b; b=c;
}
传统版本的拷贝构造
现代版本的拷贝构造
析构函数
string的析构函数较为简单，就是将空间释放即可
~string()
{
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
赋值运算符重载
赋值运算符重载也分为传统的版本和现在的版本，两个不同的版本的实现如下。
// 传统版本
string& operator=(const string& s)
{
if(this != &s)
{
// 开辟空间 + 拷贝
char* tmp = new char[s._capacity + 1];
memcpy(tmp, s._str, s._size + 1);
// 赋值
delete[] _str;
_str = tmp;
_size = s._size;
_capacity = s._capacity;
}
return *this;
}
// 现代版本
string& operator=(const string& s)
{
if(this != &s)
{
string tmp(s);
swap(tmp);
}
return *this;
}二. 迭代器
迭代器(iterator)
为了方便起见，我们使用char*类型来实现string类中的迭代器，但是要注意，迭代器只是像指针一样的东西，但是它并不一定是指针，这点下面可以在std::string中看到，这里先看我们自己如何实现迭代器(iterator)。
如下代码，string的迭代器的一种简单的实现方式就是直接给字符指针直接改个名字就可以了，而有了迭代器就可以实现拿到string起始位置和结尾位置下一个位置的迭代器的函数begin()/end()
// string.h
namespace pkd
{
class string
{
public:
//迭代器的一种实现就是使用最简单的指针
typedef char* iterator;
iterator begin()
{
return _str;
}
iterator end()
{
return _str + _size;
}
string(const char* str = "");
~string();
private:
char* _str;
size_t size;
size_t capacity;
};
}const迭代器(const_iterator)
const迭代器是专门给const string类型的对象使用的，const迭代器不是限制迭代器的值不能改变，而是限制了不能通过迭代器修改string中的值，它的底层为const char*。
// string.h
namespace pkd
{
class string
{
public:
typedef const char* const_iterator;
//有了const_iterator就可以实现对应的函数重载返回const迭代器
const_iterator begin() const;
const_iterator end() const;
};
}vs 2022编译器中std::string的迭代器类型
我们在上面说了，迭代器并不一定是指针，这里要再加一句，string类的迭代器并不一定指针，我们这里用指针实现是因为直接使用指针做为string的迭代器不仅保证了正确性，同时还使得代码简洁易懂，而vs 2022编译器下的string类的迭代器就不是一个指针，而是一个类。我们可以使用下面的代码看vs 2022编译器下string的迭代器的底层类型。
cout << typeid(std::string::iterator).name() << endl;
输出结果：class std::_string_iterator<class std::_string_val<struct std::_simple_types<char> > >
虽然以我们现在的知识水平还不能完全看懂这个结果，但是至少可以确定，迭代器不一定是指针，string的迭代器也不一定是指针。
三. 容量
size
// string.cpp
size_t string::size() const
{
return _size;
}
注意：当成员函数不需要通过this指针修改成员变量就将他置为const成员函数，这是一个好习惯
reserve
reserve理论上是即可以扩容也可以缩容的，但是缩容的代价太大了，如果后面空间又不够用了就很麻烦，所以里面的函数实现就只对扩容做处理。而因为c++中没有专门的扩容函数，所以扩容的逻辑就需要我们自己来实现
// string.cpp
void string::reserve(size_t n)
{
if(n > _capacity)
{
char* tmp = new char[n + 1]; //多开辟一个空间存放'\0'
strcpy(tmp, _str); //拷贝数据
delete[] _str;
_str = tmp;
_capacity = n;
}
}
如上，我们执行手动扩容的逻辑，新开辟一块更大的空间后将原数据拷贝，代码中保证了为’\0’预留一个空间，同时也没有忘记释放内存，那么这个函数是不是就没有问题了呢？no！来看下面的代码
这里直接给结论：使用reserve扩容之后字符串s会丢失数据，字符串会s会变成"aabbcc"，为什么？这是因为reserve内部使用的strcpy拷贝数据。前面我们学过，strcpy的拷贝逻辑是遇到’\0’之后就会结束拷贝，使用strcpy来应付c语言的字符串是足够了，因为它们都是固定以’\0’为结尾的，但是像下面的情况，string类型的字符串在’\0’后面可能还有有效的数据，此时使用strcpy就会造成数据的丢失。
string s("aabbcc");
s.push_back('\0');
s.push_back('\0');
s.push_back('!');
reserve(100); //会造成数据丢失，s变为"aabbcc"
那要如何避免这个问题呢？很简单，使用memcpy一个字节一个字节拷贝就不会出问题了
✅️正确版本
// string.cpp
void string::reserve(size_t n)
{
if(n > _capacity)
{
char* tmp = new char[n + 1]; //多开辟一个空间存放'\0'
memcpy(tmp, _str, _size) //拷贝数据
delete[] _str;
_str = tmp;
_capacity = n;
}
}
四. 元素访问
operator[]
这里我们实现两个版本，一个是给 string 类型对象使用的，可以通过[]修改内部元素的版本，另一个是给 const string 类型对象使用的不能通过[]修改内部元素的版本。
// string.cpp
char& string::operator[](size_t i)
{
return _str[i];
}
const char& string::operator[](size_t i) const
{
return _str[i];
}
五. 修改
push_back
push_back唯一需要注意的就是记得判断是否需要扩容，同时，增加字符后不要忘记在最后添加’\0’。
// string.cpp
void string::push_back(char ch)
{
// 扩容
if(_size >= _capacity)
{
size_t newcapacity = _capacity == 0 ? 4 : 2 * _capacity;
reserve(newcapacity);
}
_str[_size] = ch;
_size += 1;
_str[_size] = '\0';
}
append
append的扩容方案和push_back不同，它并不是单纯的只扩容2倍，而是根据str的大小扩容。这是因为：
- 当str非常的大时，2倍的_capacity依旧不够，此时就看一共需要多大的空间就扩容成多大的空间
- 当str很小时，为了防止多次扩容，就直接将容量扩为2倍的_capacity
// string.cpp
void string::append(const char* str)
{
size_t len = strlen(str);
if(_size + len > _capacity)
{
size_t newcapacity = _size + len < 2 * _capacity ? 2 * _capacity : _size + len;
reserve(newcapacity);
}
memcpy(_str + _size, str, len + 1);
_size += len;
}
operator+=
// string.cpp
string& string::operator+=(const char* str)
{
(*this).append(str);
return *this;
}
string& string::operator+=(char ch)
{
(*this).push_back(ch);
return *this;
}
insert
insert较为常见使用方式有两种，分别是指定位置插入一个字符和指定位置插入一个字符串，可以将这两种情况写成函数重载
- 指定位置插入字符
使用insert需要整体的挪动string中的数据，它的操作其实和顺序表的插入数据的操作大同小异，来看如下代码
❌错误示例
void string::insert(size_t pos, char ch)
{
// 扩容
if(_size >= _capacity)
{
size_t newcapacity = _capacity == 0 ? 4 : 2 * _capacity;
reserve(newcapacity);
}
// 挪动数据
size_t end = _size;
while(end >= pos)
{
_str[end + 1] = _str[end];
--end;
}
// 赋值
_str[pos] = ch;
_size += 1;
}插入操作分为3个步骤，其中的逻辑都没有什么问题，但是其实里面隐藏了错误的地方。当pos = 0时，这段代码会进入死循环，为什么？我们来看，当end = 0时进入循环挪动数据，此时–end，end本应该是-1，但是注意end的类型是size_t类型，它不会变成-1，而是会变成变成整型的最大值，此时代码就会陷入死循环。所以在挪动数据上，我们需要做一点改变。
✅正确示例
void string::insert(size_t pos, char ch)
{
// 扩容
if(_size >= _capacity)
{
size_t newcapacity = _capacity == 0 ? 4 : 2 * _capacity;
reserve(newcapacity);
}
// 挪动数据
size_t end = _size + 1;
while(end > pos)
{
_str[end] = _str[end - 1];
--end;
}
// 赋值
_str[pos] = ch;
_size += 1;
}- 指定位置插入字符串
汲取前面的教训，在指定位置插入字符串函数中，进行挪动数据的时候，尽量使用 - 的逻辑实现数据的挪动
void string::insert(size_t pos, const char* str)
{
// 扩容
size_t len = strlen(str);
if(_size + len > _capacity)
{
size_t newcapacity = _size + len < 2 * _capacity ? 2 * _capacity : _size + len;
reserve(newcapacity);
}
// 挪动数据
size_t end = _size + len;
while(end >= pos + len)
{
_str[end] = _str[end - len];
--end;
}
// 赋值
memcpy(_str + pos, str, len);
_size += len;
}erase
erase进行删除数据时会遇到两种情况（1）从pos位置开始，删除len个字符，pos + len < _size（2）将pos位置及其之后的所有元素全部都删掉，pos + len >= _size，当遇到第一种情况时，就需要将pos + len之后的数据往前面挪动较为麻烦，如果遇到第二种情况的话，只需要改’\0’的位置即可，来看如下代码
void erase(size_t pos = 0, size_t len = npos)
{
//情况（2），pos位置及之后的字符全部都要删掉
if(len == npos || pos + len >= _size)
{
//我第一次是这样写的，错误很大，这里_size-=len会减到很大的值，导致越界访问
//_size -= len;
//_str[_size] = '\0';
_str[pos] = '\0';
_size = pos - 1;
}
//情况（1），删除pos位置开始的len个字符
else
{
// i <= _size 可以把'\0'也挪动过去
for(size_t i = pos + len; i <= _size; i++)
{
_str[i - len] = _str[i];
}
_size -= len;
}
}在erase这里我们遇到了npos，所以这里就需要在类中定义好npos以便使用
// string.h
namespace pkd
{
class string
{
public:
static const size_t npos;
};
}
// string.cpp
namespace pkd
{
// 分开文件初始化时注意需要声明npos是string类的对象
const size_t string::npos = -1;
}pop_back
void string::pop_back()
{
assert(_size > 0);
_str[_size - 1] = '\0';
--_size;
}
六. 操作字符串
c_str
std::string中实现的c_str就是返回string中关于c语言的接口，所以我们这里直接返回字符串首元素的位置即可
char* string::c_str()
{
return _str;
}
注意：自行实现的string类在测试的时候如果需要直接打印，而此时又没有写<<的运算符重载要怎么办？使用c_str返回c语言类型的字符串就可以直接使用cout打印string字符串
find
find较为常用的功能是查找某个字符或者字符串出现的位置，所以需要写两个函数重载应用在不同的场景，它们的重载函数如下：
size_t find(char ch, size_t pos = 0); size_t find(const char* str, size_t pos = 0);
注意，find函数默认的起始查找位置是0，所以pos需要给0为缺省参数。下面首先实现查找一个字符的功能，要查找一个字符，只需要遍历字符串看是否配对即可，如果查找到了目标字符就返回它的下标，如果没有找到，就返回npos。
size_t string::find(char ch, size_t pos = 0)
{
// 断言防止越界访问
assert(pos < _size);
for(size_t i = 0; i < _size; i++)
{
if(_str[i] == ch)
{
return i;
}
}
return npos;
}
查找单个字符的函数逻辑较为简单，那查找相同的字符串应该怎么样实现呢？可以使用c语言库中实现的匹配字符串的函数strstr。对于字符串p，使用 strstr 在字符串s中找与p相同的子串，如果找到了则返回该子串起始位置的指针，如果没有找到就返回nullptr(空指针)。其实现逻辑如下。
size_t string::find(const char* str, size_t pos = 0)
{
assert(pos < _size);
// 注意是从pos位置开始查找，在_str中找和str相同的子串
const char* tmp = strstr(_str + pos, str);
if(tmp == nullptr)
{
return npos;
}
else
{
// tmp - _str 就是下标
return tmp - _str;
}
}
🏷️ 小优化
在上面的代码中，在s中查找字符串p是使用strstr完成的，但是我们要知道strstr的底层是通过暴力枚举查找的，其时间复杂度为 o ( n 2 ) o(n^2) o(n2)，对于需要大量查找子串的场景，这个时间复杂度太高了，为了提高一些效率我们可以尝试使用一些算法进行优化，如：kmp算法，字符串哈希……
substr
substr功能就是截取字符串，简单来说，就是截取一段字符串区间。实现substr时，我们可以创建一个临时对象存储截取的字符串，之后再通过遍历字符串区间一点一点将字符插入进临时对象中，最后返回临时对象即可。
这里有一点需要注意，因为截取的区间右端点可能会越界，所以需要特殊判断，如果右端点越界了就将右端点限制在最后一个元素的位置
string string::substr(size_t pos = 0, size_t len = npos)
{
assert(pos < _size);
//判断右端点是否越界
if(pos + len - 1 >= _size)
{
len = _size - pos;
}
//截取字符串
string ret;
for(size_t i = pos; i < pos + len; i++)
{
ret.push_back(_str[i]);
}
return ret;
}七. 非成员函数
字符串的比较
🏷️ 说明
std::string中将字符串的比较实现为全局函数是为了能支持const char* 和 string的比较，而这些比较功能的实现都是差不多的，为了方便起见，这里我们只实现string和string的比较。而string和string的比较就不需要考虑this指针抢占参数的问题，同时，为了遵循尽量少用友元的原则，这里我们就将字符串的比较都写成成员函数。
- operator<
bool string::operator<(const string& s) const
{
size_t i1 = 0, i2 = 0;
while(i1 < _size && i2 < s._size)
{
if(_str[i1] < s._str[i2])
{
return true;
}
else if(_str[i1] > s._str[i2])
{
return false;
}
else
{
++i1;
++i2;
}
}
// 如果前面都相等，那就字符串长度小的更小
return _size < s._size;
}- operator==
bool string::operator==(const string& s) const
{
if(_size != s._size)
{
return false;
}
// 此时两个字符串长度相同
for(size_t i = 0; i < _size; i++)
{
if(_str[i] != s._str[i])
{
return false;
}
}
return true;
}知识点回顾：类的关于比较的运算符重载一般实现了
==和<后，其它的运算符比较逻辑都可以通过复用这两个运算符重载来实现
- operator!=
bool string::operator!=(const string& s) const
{
return !(*this == s);
}
- operator<=
bool string::operator<=(const string& s) const
{
return *this == s || *this < s;
}
- operator>
bool string::operator>(const string& s) const
{
return !(*this <= s);
}
- operator>=
bool string::operator>=(const string& s) const
{
return !(*this < s);
}
输入/输出
operator<<
string的输入和输出本质上就是写<<和>>的运算符重载，而<<运算符重载有一个较为简单的写法，就是直接调用string的c语言的接口来使用cout输出。但是在写代码前还需要考虑一个问题，前面提到了因为this指针抢占参数位置的问题，operator<<和operator>>尽量避免写成成员函数，一般情况是将这两个运算符重载声明成为友元。思考一下，这里的情况一定需要写成友元吗？
将函数声明成为友元的目的是什么？只是为了访问string类的私有成员吧，但是其实这里并不需要直接的访问string中的私有成员，访问私有成员可以通过前面实现的一些成员函数间接访问。所以这里的operator<<和operator>>都写成全局函数即可。
ostream& operator<<(ostream& out, const string& s)
{
// 通过调用c语言的接口直接输出
out << s.c_str();
return out;
}
上面的函数看似没有什么问题，字符串都可以正常输出，那么真的是这样吗？我们来看如下情况，不难发现，字符串在’\0’之后的字符打印不出来了。而std::string是可以将’\0’之后的字符输出的，所以我们这里的实现就有问题。那么，问题出在哪里了？
string s1("aabb");
s1.push_back('\0');
s1.push_back('\0');
s1.push_back('!');
cout << s1 << endl;
/* 输出：aabb */
std::string s2("aabb");
s2.push_back('\0');
s2.push_back('\0');
s2.push_back('!');
cout << s2 << endl;
/* 输出：aabb! */
c_str()的陷阱
其实这就是c_str的问题。c风格的字符串是根据’\0’来判断字符串是否结尾的，这里将string转化为char*类型的字符串打印，编译器是以’\0’判断字符串是否结束的，但是这样就会导致string打印时遗漏数据，所以operator<<就不能直接使用c_str打印，而是需要单个字符依次打印。
✅正确写法
ostream& operator<<(ostream& out, const string& s)
{
for(size_t i = 0; i < s.size(); i++)
{
out << s[i];
}
return out;
}
operator>>
现在，我们有了上面的教训，写operator>>读取字符串的时候就一个字符一个字符的读取，边读取边进行插入，通过 ' '和\0判断字符串是否读取结束了，如果没有结束就继续读取数据。不过，还有一点需要注意，在读取字符串前需要将原字符串清空，清空字符串就使用clear成员函数即可。代码实现如下
void string::clear()
{
_str[0] = '\0';
_size = 0;
}
istream& operator>>(istream& in, string& s)
{
// 清空原始数据
s.clear();
// 读取数据
char ch;
in >> ch;
while(ch != ' ' && ch != '\n')
{
s += ch;
in >> ch;
}
return in;
}
cin自动忽略空格/换行
这里直接给出结论：这段代码有问题，读取数据会陷入死循环。那为什么会陷入死循环呢？我们平时使用cin输入一些内置类型的数据时，都是根据空格或者换行来判断一个数据是否输入完成了，而这个结束输入的标识符（空格/换行）会被编译器忽略掉。所以，当输入空格/换行给ch时，编译器将这次输入忽略掉了，继续读取下一个字符，这就导致了ch永远不可能是' ' 或者\n，所以就有了死循环。
这个问题的解决方案很简单，使用getchar()，fgetc()这种读取单个字符的函数就不会出现这种问题了，而为了保持c++的输入风格，这里我们使用istream类的成员函数——get()。
istream& operator>>(istream& in, string& s)
{
// 清空原始数据
s.clear();
// 读取数据
char ch;
ch = in.get();
while(ch != ' ' && ch != '\n')
{
s += ch;
ch = in.get();
}
return in;
}
优化
现在，保证了输入的正确性，我们来考虑效率的问题。这个效率的问题出现在哪呢？其实就是扩容的问题。代码中，对于输入的字符串是一个字符一个字符往s中插入，如果输入的字符串特别的长，这个s就需要扩容很多次，这就使得输入的效率很低。为了减少扩容次数，提高效率，我们可以使用一个临时字符数组存储字符串。每当字符串数组满了的时候，一次性将该字符串插入进s中，就可以减少扩容次数。
注意：临时字符数组的大小需要适当，如果字符数组容量过小，那么输入时还是需要执行多次插入扩容，那优化就没有意义了。而如果字符数组容量过大，就浪费了很多空间。一般情况下将字符数组的大小定义为128即可
✅正确性+优化
istream& operator>>(istream& in, string& s)
{
// 清空原始数据
s.clear();
// 读取数据
char ch;
ch = in.get();
char str[128];
size_t i = 0;
while(ch != ' ' && ch != '\n')
{
str[i++] = ch;
if(i == 127)
{
str[i] = '\0';
s += str;
i = 0;
}
ch = in.get();
}
// 将字符数组中剩余的数据插入进s中
if(i > 0)
{
str[i] = '\0';
s += str;
}
return in;
}
到此这篇关于c++ stl详解：string的模拟实现的文章就介绍到这了,更多相关c++ string模拟内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！
发表评论