【C++】STL容器--string的模拟实现
·
目录
- 前言
- 一、准备工作
- 二、string的模拟实现
- 三、算法库swap和string类wap
- 四、string类大小问题
前言
书接上文【C++】STL容器string的使用详情请点击查看，本文将在学习了string的使用的基础上讲解【C++】STL容器–string的模拟实现
一、准备工作
对于string类的模拟实现，我们要在了解string的接口的基础上学习：
- 在实现自己写的string类的模板时，会与库里面的std::string重名，因此我们在string.h中开辟自己的命名空间来实现string的各种函数
- 声明定义分离，String_1.h（声明string类以及相关函数），String_1.cpp（实现string相关函数），test.cpp（测试函数是否正确）
二、string的模拟实现
1、构造函数
下面我们实现两个常见的构造函数（一个是无参构造，一个是C字符串构造），使用初始化列表进行初始化，初始化列表初始化顺序和成员变量的声明顺序一一对应
1、无参构造函数
- 在初始化列表的时候_str不能初始化为nullptr，应该初始化为有一个空间，里面内容是“\0”，_size和_capacity不包含‘\0’（规定），因此都初始化为0
string::string()
:_str(new char[1] {'\0'})
,_size(0)
,_capacity(0)
{}
2、C字符串构造函数
- 在初始化列表初始化时，_str初始化为
strlen(str) + 1，strlen计算的长度不包含'\0'，_size和_capacity初始化为strlen（str），然后将str的内容拷贝到_str中
string::string(const char* str)
:_str(new char[strlen(str) + 1])
, _size(strlen(str))
,_capacity(strlen(str))
{
memcpy(_str, str, _size + 1);
}
- 上面代码有一个缺陷，strlen调用三次，strlen调用是在运行时计算的（sizeof在编译时计算），这样代价很大，怎么修改呢？
让_size先走初始化列表初始化_size，_str和_capacity放到下面初始化，这样strlen就只调用一次。
string::string(const char* str)
:_size(strlen(str))
{
_str = new char [_size + 1];
_capacity = _size;
memcpy(_str, str, _size + 1);
}
3、上面两个构造函数我们发现可以用全缺省构造函数来进行合并，这样既可以不传参构造，也可以传入常量字符串来初始化，简化代码。
- 那么缺省参数怎么给呢？给nullptr是不可以的，这个时候可以给一个空字符串（默认空字符串中有一个‘\0’）
//String_1.h
//声明
string(const char* str = "");// 空字符串中默认有一个'\0'
//String_1.cpp
//定义
string::string(const char* str) //缺省参数在声明时给出，定义时不需要再重定义
:_size(strlen(str))
{
_str = new char[_size + 1];
_capacity = _size;
memcpy(_str, str, _size + 1);
}
2、析构函数
前面构造函数_str使用new []初始化，因此析构的时候需要使用delete [] 来释放资源
string::~string()
{
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
3、拷贝构造
- 拷贝构造，使用new开和s一样的空间，记得得
s._capacity + 1，因为有默认的‘\0’，然后将s._str
中的内容拷贝给_str，再将_size和_capacity赋值
string::string(const string& s)
{
_str = new char[s._capacity + 1];
memcpy(_str, s._str, s._size + 1);
_size = s._size;
_capacity = s._capacity;
}
4、c_str
c_str这个接口用于返回C语言的字符串，不需要修改，因此使用const进行修饰
const char* string::c_str() const
{
return _str;
}
//test.cpp
namespace gy
{
void test_string1()
{
string s1;
cout << s1.c_str() << endl;
string s2("hello world");
cout << s2.c_str() << endl;
}
}
int main()
{
gy::test_string1();
return 0;
}
5、operator[]
operator[]我们实现普通的operator[]和const修饰的operator[]（普通的可读可写，const修饰的只能读，不能修改），实现字符串的下标访问
//String_1.h
const char& operator[](size_t i)const;
char& operator[](size_t i);
//String_1.cpp
const char& string::operator[](size_t i)const
{
assert(i < _size);
return _str[i];
}
char& string::operator[](size_t i)
{
assert(i < _size);
return _str[i];
}
6、begin/end以及iterator/范围for
- 迭代器可能是指针，也可能不是指针（只有指向数组的指针才能使用 原生指针做迭代器），string类可以用char*来实现迭代器，迭代器有普通的迭代器，也有const修饰的迭代器const_iterator，const迭代器不是iterator不能修改，而是iterator指向的内容不能修改（支持迭代器就支持范围for）
- 编译器会根据类型自动调用最合适的迭代器，普通对象调用普通迭代器，const对象调用const迭代器
//String_1.h
typedef char* iterator;
typedef const char* const_iterator;
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
//String_1.cpp
string::iterator string::begin()
{
return _str;
}
string::iterator string::end()
{
return _str + _size;
}
string::const_iterator string::begin() const
{
return _str;
}
string::const_iterator string::end() const
{
return _str + _size;
}
//test.cpp
void test_string2()
{
string s2("hello world");
cout << s2.c_str() << endl;
for (size_t i = 0; i < s2.size(); ++i)
{
s2[i]++;
}
cout << s2.c_str() << endl;
//
string::iterator it1 = s2.begin();
while (it1 != s2.end())
{
cout << *it1;
++it1;
}
cout << endl;
}
最终结果如下，实现了迭代器、下标遍历字符串，并修改字符串的效果
- 现在有了迭代器，让我们来实现范围for遍历字符串并修改字符串的代码
7、size/capacity/empty
- size和capacity返回对应的_size和_capacity即可
- emty：当
_size == 0时，string为空，返回1，否则返回0- 这三个函数都只是获得相应的值和判断是否为空，不需要修改信息，因此都使用const修饰，这样普通对象和const对象都能调用，不需要单独写普通和const对象的函数
size_t string::size() const
{
return _size;
}
size_t string::capacity() const
{
return _capacity;
}
bool string::empty() const
{
return _size == 0;
}
8、reserve/push_back/append
1. reserve
- 针对reserve我们只考虑扩容，不考虑缩容情况，所以在扩容前判断接收的扩容大小n和_capacity的大小，我们只考虑
n>_capacity的情况，new char[n + 1]原因是因为末尾默认一个‘\0’。- 拷贝时
特别注意不能使用strcpy，原因是strcpy在拷贝时是以‘\0’为字符串结束判断标志的，如果有字符串中间出现‘\0’，那么会判断为该字符串结束，导致后面有字符没有拷贝过来，所以不能使用strcpy来进行拷贝
//扩容，默认不缩容
void string::reserve(size_t n)
{
if (n > _capacity)
{
char* tmp = new char[n + 1];
memcpy(tmp, _str, _size + 1);
delete[] _str;
_str = tmp;
_capacity = n;
}
}
2. push_back
- push_back：尾插一个字符，在尾插时我们首先要考虑容量是否足够，判断标准为是否
_size >= _capacity或者_size == _capacity（正常情况_size不会大于_capacity，但是也可以用>=来判断），如果_size >= _capacity或者_size == _capacity，那么就需要扩容- 对于扩容的策略，我们选择2倍扩容，但是这里还有一个问题，如果_capacity == 0，0 * 2也还是等于0，这种情况无法完成扩容操作，因此我们使用三目操作符来进行扩容大小的确定：
size_t NewCapacity = _capacity == 0 ? 4 : 2 * _capacity;- 扩容完成后，就是插入字符了，我们直接在_size位置插入字符ch，再++_size，这里又有一个容易忽视的问题，插入之前_str[_size] 位置是‘\0’，在我们插入字符后，_size++，但是字符串末尾默认的’\0’也需要在末尾再插入
void string::push_back(char ch)
{
if (_size >= _capacity)
{
size_t NewCapacity = _capacity == 0 ? 4 : 2 * _capacity;
reserve(NewCapacity);
}
_str[_size] = ch;
++_size;
_str[_size] = '\0';
}
3. append
- append是尾插字符串，和push_back一样需要检查是否需要扩容，扩容条件是：
(_size + len) > _capacity- 怎么扩容计较合适呢？如果像push_back一样直接扩2倍，那么在插入长字符串时，字符串_capacity会很大造成空间浪费，如果正好扩容_size + len，那么对于频繁插入短字符串会频繁开空间（一般长字符串插入次数较少，短字符串会频繁插入），所以我们的扩容方案是：当
2 * _capacity < (_size + len)时，我们就按照_size + len扩容，否则就还是按照2 *_capacity扩容
void string::append(const char* str)
{
size_t len = strlen(str);
if ((_size + len) > _capacity)
{
size_t NewCapacity = 2 * _capacity < (_size + len) ? (_size + len) : 2 * _capacity;
reserve(NewCapacity);
}
//这种情况可以使用strcpy，因为str是常量串，中间不会有\0，但是为了防止混用，使用memcpy
//strcpy(_str + _size, str);
memcpy(_str + _size, str, len + 1);
_size += len;
}
9、operator+=
- operator+= 可以加等一个字符也可以加等一个字符串，加等字符，直接push_back；加等一个字符串直接append
string& string::operator+=(char ch)
{
push_back(ch);
return *this;
}
string& string::operator+=(const char* str)
{
append(str);
return *this;
}
运行结果如下：
10、insert/erase/pop_back
1. insert
- insert在pos位置插入一个字符，首先判断空间是否足够，不够需要扩容，再将pos位置往后的字符串包括末尾的’\0’一起往后挪一位
string& string::insert(size_t pos, char ch)
{
assert(pos <= _size);
if (_size >= _capacity)
{
size_t NewCapacity = _capacity == 0 ? 4 : 2 * _capacity;
reserve(NewCapacity);
}
for (size_t i = _size + 1; i > pos; --i) //将"\0"在内的字符后移一位
{
_str[i] = _str[i - 1];
}
_str[pos] = ch;
++_size;
return *this;
}
- 2.insert在pos位置插入字符串，首先考虑扩容问题，和append一样的扩容逻辑
string& string::insert(size_t pos, const char* str)
{
assert(pos <= _size);
size_t len = strlen(str);
if ((_size + len) > _capacity)
{
size_t NewCapacity = 2 * _capacity < (_size + len) ? (_size + len) : 2 * _capacity;
reserve(NewCapacity);
}
for (size_t i = _size + len; i >= pos + len; --i) //将"\0"在内的字符后移len位
{
_str[i] = _str[i - len];
}
for (size_t i = 0; i < len; ++i)
{
_str[pos] = str[i];
pos++;
}
_size += len;
return *this;
}
2. erase
- erase删除字符串，实现从pos位置开始，删除len个字符
- len参数给缺省参数npos，当len没有给参数时，默认给npos = -1删除pos位置往后的所有字符，同时注意：因为我们声明和定义是分离的，全局变量npos的声明在类中，定义在.cpp文件中时必须要指明类域，否则会链接错误，无法编译通过
- 当
len == npos || len >= _size - pos时，从pos位置开始到字符串结尾的字符全部删除，C/C++不支持释放一部分空间，这种情况只需要把_size指向pos，并在_size位置插入‘\0’即可；其他情况就要考虑挪动字符数据，将pos+len到_size的字符向前挪动len个位置，再_size -= len，这个时候已经不需要插入‘\0’，因为前面挪动字符的时候，已经将_size位置的字符移动到相应位置了
//String_1.h
//类中声明
public:
static const size_t npos;
//String_1.cpp
const size_t string::npos = -1;
string& string::erase(size_t pos, size_t len)
{
assert(pos < _size);
//如果pos后面的字符个数小于len
if (len == npos || len >= _size - pos)
{
_size = pos;
_str[_size] = '\0';
}
else
{
size_t i = pos + len;
while (i <= _size)
{
_str[pos] = _str[i];
pos++;
i++;
}
//也可以使用memmove移动数据
//memmove(_str + pos, _str + i, _size + 1 - i);
_size -= len;
}
return *this;
}
3. pop_back
尾删：- -_size就可以实现
void string::pop_back()
{
assert(_size > 0);
--_size;
_str[_size] = '\0';
}
11、find/substr
1. find
- find我们实现两个，找字符和找字符串，如果没有传入pos默认从string的0位置开始查找
- 对于字符串（字串）的查找，我们使用暴力遍历匹配找字串，并返回下标位置，没有找到就返回npos
- find单个字符
//String_1.h
size_t find(char ch, size_t pos = 0) const;
size_t find(const char* str, size_t pos = 0) const;
//String_1.cpp
size_t string::find(char ch, size_t pos) const
{
for (size_t i = pos; i < _size; ++i)
{
if (_str[i] == ch)
return i;
}
return npos;
}
- find字符串，我们使用strstr来找字串，返回值是str2匹配在str1中的第一个字符的指针
- 怎么将返回指针转换为下标呢？用指针-指针（首元素指针_str），返回的是两个指针的之间元素个数，这个就是对应下标
2. substr
- substr函数是从string字符串的pos位置开始取len个字符构成子字符串，并返回这个字符串
- len我们依旧给了缺省参数npos，如果
len == npos || len >= _size - pos那么就取pos开始一直到字符串结尾
void test_string6()
{
string s = "https://legacy.cplusplus.com/reference/string/string";
size_t pos1 = s.find(':');
if (pos1 != string::npos)
{
string s1(s.substr(0, pos1));
cout << s1.c_str() << endl;
}
size_t pos2 = s.find('/', pos1 + 3);
if (pos2 != string::npos)
{
string s2(s.substr(pos1 + 3, pos2 - (pos1 + 3)));
cout << s2.c_str() << endl;
}
string s3(s.substr(pos2 + 1));
cout << s3.c_str() << endl;
}
12、operator << 、operator >> 、clear、getline
- operator << 和operator >>返回值必须要是引用，因为它们不能拷贝构造，operator << 的第二个参数使用const string& s，operator >>第二个参数不能使用const string& s，因为我们的流提取是要将键盘输入的内容给s的，需要改变s的内容，同时形参的改变影响实参，所以使用
string& s
1. operator <<
- operator <<实现字符串的打印，直接和std中的string一样，
cout << s << endl打印字符串，那么operator << 必须声明成全局函数，如果在类中声明，那么this指针会抢占第一个参数，最后打印会变成这样：s >> cout，这不符合我们的习惯
ostream& operator<<(ostream& out, const string& s)
{
out << s.c_str();
return out;
}
- C语言实现字符串打印结束标志是’\0’，所以如果string字符串中间有‘\0’，那么它就只会打印’\0’，之前的字符，那么怎么解决字符串中间有’\0’的打印问题呢？可以使用范围for遍历一个一个字符给out打印，这样就能解决C语言打印以‘\0’为字符串结束的标志的情况
ostream& operator<<(ostream& out, const string& s)
{
for (auto e : s)
{
out << e;
}
return out;
}
2. operator <<
- 同样operator << 也要是全局函数
istream& operator>>(istream& in, string& s)
{
char ch;
in >> ch;
while (ch != ' ' && ch != '\n')
{
s += ch;
in >> ch;
}
return in;
}
- 我们可以看到下面的运行结果，为什么输入xxx和yyy之后一直无法输出？
- 通过调试我们发现，在cin读取字符的时候，ch根本没有读到‘ ’和‘\n’，导致程序一直在输入界面，原因是不管是cin还是scanf它们都是默认读取字符的时候遇到‘ ’和‘\n’代表该字符结束，所以在输入的时候遇到‘ ’和‘\n’它们认为是分割符，不会读入
- 那么怎么修改呢？使用
in.get()，这样不会忽略‘ ’和‘\n’
istream& operator>>(istream& in, string& s)
{
char ch = in.get();
//in >> ch;
while (ch != ' ' && ch != '\n')
{
s += ch;
ch = in.get();
}
return in;
}
- 但是又出现了下面这种情况，如果本来字符串中有字符，再输入，它会在后面追加字符，但是我们需要的是清空字符串再存入输入的字符
3. clear
下面我们来实现clear
void string::clear()
{
_str[0] = '\0';
_size = 0;
}
- 所以，输入字符之前先将s.clear()，再读取字符
istream& operator>>(istream& in, string& s)
{
s.clear();
char ch = in.get();
//in >> ch;
while (ch != ' ' && ch != '\n')
{
s += ch;
ch = in.get();
}
return in;
}
- 结果如下，测试没有问题
4. getline
cin和scanf默认读取到空格和换行符结束，那如果我们需要读取的字符串中间就有空格（比如s = hello world）怎么读取呢？可以通过实现getline来实现这一读取要求
// String.h
istream& getline(istream& in, string& s, char delim = '\n');
//String.cpp
istream& getline(istream& in, string& s, char delim)
{
s.clear();
char ch = in.get();
while (ch != delim)
{
s += ch;
ch = in.get();
}
return in;
}
5. operator>>和getline代码完善
上面operator>>和getline有一个很大的问题，如果读取键盘输入的字符串_size很大，那么s += ch
会进行很多次，导致扩容多次，怎么解决这个问题呢？
-
- 之前有了解预先给s开空间，s.reserve()，但是我们又不知道每次输入的字符串多大，所以此方法不行
-
- 我们可以创建一个有128（大小可自定）个空间的
数组buff，把读入的字符暂存在字符数组中，当数组满了之后，一次性把buff中的内容+=给s，如果没有满，在读取结束后再将buff中的内容一次性全给s，这样大大提高了效率
- 我们可以创建一个有128（大小可自定）个空间的
//cin
istream& operator>>(istream& in, string& s)
{
s.clear();
char buff[128];
int i = 0;
char ch = in.get();
//in >> ch;
while (ch != ' ' && ch != '\n')
{
/*s += ch;*/
buff[i++] = ch;
if (i == 127)
{
buff[i] = '\0';
s += buff;
i = 0;
}
ch = in.get();
}
if (i > 0)
{
buff[i] = '\0';
s += buff;
i = 0;
}
return in;
}
//getline
istream& getline(istream& in, string& s, char delim)
{
s.clear();
char buff[128];
int i = 0;
char ch = in.get();
while (ch != delim)
{
/*s += ch;*/
buff[i++] = ch;
if (i == 127)
{
buff[i] = '\0';
s += buff;
i = 0;
}
ch = in.get();
}
if (i > 0)
{
buff[i] = '\0';
s += buff;
i = 0;
}
return in;
}
13、string类比较
- 两个字符串比较大小，有三种情况，这两个字符串一样的_size，两个字符串不一样的_size
1. operator <
- 当
l1 < _size && l2 < s._size时，遍历每个字符看_str[l1] 是否小于s[l2]，小于返回true，大于返回false，等于l1++，l2++，当l1 < _size && l2 < s._size不成立时，只需要返回l2 < s._size
bool string::operator<(const string& s)const
{
size_t l1 = 0, l2 = 0;
while (l1 < _size && l2 < s._size)
{
if (_str[l1] < s[l2])
{
return true;
}
else if (_str[l1] > s[l2])
{
return false;
}
else
{
l1++;
l2++;
}
}
return l2 < s._size;
}
2. operator ==
- operator == 在
l1 < _size && l2 < s._size时，遍历每个字符看_str[l1] 是否不等于s[l2]，不等于返回false，当跳出循环时如果l1 == _size && l2 == s._size，则说明两个字符串相等
bool string::operator==(const string& s)const
{
size_t l1 = 0, l2 = 0;
while (l1 < _size && l2 < s._size)
{
if (_str[l1] != s[l2])
{
return false;
}
else
{
l1++;
l2++;
}
}
return l1 == _size && l2 == s._size;
}
有了小于和等于运算符后，后面的比较运算符就能复用上面的代码来实现了
3. operator<=
- <= 就是
operator<或者operator==
bool string::operator<=(const string& s)const
{
return *this < s || *this == s;
}
4. operator>
- 大于就是不是等于小于
bool string::operator>(const string& s)const
{
return !(*this <= s);
}
5. operator >=
- 大于等于 == 大于或者等于 / ==不是小于
bool string::operator>=(const string& s)const
{
return *this > s || *this == s;
//return !(*this < s);
}
6. operator!=
- != 就是非等于，直接复用等于即可
bool string::operator!=(const string& s)const
{
return !(*this == s);
}
14 、operator= / swap
1. 传统写法
传统写法就是自己new空间，拷贝字符
string& 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;
}
}
2. swap
- swap交换两个string类，调用库中的交换函数
void string::swap(string& s)
{
std::swap(_str, s._str);
std::swap(_size, s._size);
std::swap(_capacity, s._capacity);
}
3. 现代写法
-
- 直接调用参数是字符串的构造函数来初始化tmp，再交换this和tmp的对象，实现了operator=赋值运算符重载
string& string::operator=(const string& s)
{
if(this != &s)
{
string tmp(s._str);
swap(tmp);
}
return *this;
}
-
- 上面创建了一个临时的string类，我们也可以直接交换s和this，但是参数就不能是传引用了，而是使用
string s
- 上面创建了一个临时的string类，我们也可以直接交换s和this，但是参数就不能是传引用了，而是使用
string& string::operator=(string s)
{
swap(s);
return *this;
}
三、算法库swap和string类wap
-
算法库swap
-
string类swap
-
总结：算法库的swap可以实现两个string类的交换，但是需要三次深拷贝，效率很低，一般string类的交换不使用算法库的swap，使用string内置的swap
- 我们发现还有一个全局的swap函数，为什么还要有这个swap呢？
四、string类大小问题
- 对于string类大小的计算只需要计算成员变量的大小并考虑内存对齐问题，但是不同编译器会有优化导致结果不同，下面是VS2022编译器下的优化结果，我们发现本来按照正常来说大小应该是12，但是现在是28
源码点击获取
码道开发者社区，聚焦华为云码道 CodeArts 代码智能体，沉淀 Agent、Skill、鸿蒙开发实战内容，供开发者查阅资料、交流技术、分享工程实践
更多推荐
18
0- 0
已为社区贡献5条内容
所有评论(0)