文章目录
- string类的模拟实现
- string基本框架的实现
- operator+=的实现
- string常用函数的实现
string类的模拟实现
前文对于string的常用函数做了讲解，由于string是一个面试官常考的点，总喜欢让模拟实现string类，下面来模拟实现一下string，赋予基本的功能，且逐步完善函数实现方式。
string基本框架的实现
string类的基本框架，比如构造函数，拷贝构造，析构函数，成员变量，起码的push_back等一些能正常使得string运行的函数的实现。
namespace String {
class string {
public:
//迭代器： string中的迭代器实际上就是指针
typedef char* iterator;
typedef const char* const_iterator;
iterator begin()
{
//begin 表示的是string的首元素地址
return _str;
}
iterator end()
{
//end 返回string最后一个元素的下一个位置，也就是'\0'
return _str + _size;
}
const_iterator begin() const
{
//begin 表示的是string的首元素地址
return _str;
}
const_iterator end() const
{
//end 返回string最后一个元素的下一个位置，也就是'\0'
return _str + _size;
}
//默认构造和带参构造合并，使用缺省参数
string(const char* str = "") //""字符串自带'\0'
:_str(new char[strlen(str) + 1])
, _size(strlen(str))
, _capacity(strlen(str))
{
//存储字符串
strcpy(_str, str);
}
//拷贝构造
//string(const string& s)
//{
// //深拷贝，就是创建一个大小一样的空间
// _str = new char[s._capacity + 1];
// strcpy(_str, s._str);
// _size = s._size;
// _capacity = s._capacity;
//}
string(const string& s)
{
_str = new char[s._capacity + 1];
memcpy(_str, s._str, s._size + 1);
_size = s._size;
_capacity = s._capacity;
}
//析构函数
~string()
{
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
void Print() {
cout << _str << "\t" << _size << "\t" << _capacity << endl;
}
//reserve 保留容量 可以扩容
void reserve(size_t n) //只是改变capacity 不改变size
{
if (n > _capacity)
{
//新建一个字符数组
cout << "reserve->" << n << endl;
char* new_str = new char[n + 1];
//更改容量
//strcpy(new_str, _str);
memcpy(new_str, _str, _size + 1);
delete[] _str;
_str = new_str;
_capacity = n;
}
}
//push_back
void push_back(char ch)
{
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
//加入字符
_str[_size] = ch;
++_size;
_str[_size] = '\0';
}
void append(const char* str)
{
if (_size + strlen(str) > _capacity)
{
reserve(_size + strlen(str));//至少保留_size + strlen(str)
}
//加入字符串
memcpy(_str + _size, str, strlen(str) + 1);//在'\0'位置（就是_str末尾）+str
_size += strlen(str);
}
//实现+= 也是使用push_back 和append函数
string& operator+=(char ch)
{
push_back(ch);
return *this;
}
string& operator+=(const char* str)
{
append(str);
return *this;
}
//返回size
size_t size() const //const表示修饰this指针，也就是说只读，如果是const对象，也可以访问，普通用户相当于权限的缩小也可也访问
{
return _size;
}
size_t capacity()
{
return _capacity;
}
private:
char* _str;
int _size;
int _capacity;
};
}
构造函数和拷贝构造
默认构造函数和带参构造函数合并，使用缺省参数
拷贝构造函数，我们要使用深拷贝，因为如果是浅拷贝，仅仅是将数值传给新的string对象，但是两者对应一个地址一个空间，当析构一个string对象后，另一个对象再次析构就会报错。
string(const char* str = "") //""字符串自带'\0'
:_str(new char[strlen(str) + 1]) //因为我们底层用的数组，所以一定要多开一位空间存放'\0'
, _size(strlen(str))
, _capacity(strlen(str))
{
//存储字符串
strcpy(_str, str); //传入字符串的时候，一般都是结尾为'\0'，中间有'\0'的都是我们为string对象增加的。所以这个地方还是使用strcpy即可
}
//拷贝构造
string(const string& s)
{
//深拷贝，就是创建一个大小一样的空间
_str = new char[s._capacity + 1];
strcpy(_str, s._str);
_size = s._size;
_capacity = s._capacity;
}
push_back和append的实现
想要实现push_back和append函数，都要在底层中考虑是否需要扩容，那么我们就顺势要写出reserve函数，让其来判断是否需要扩容。
//reserve 保留容量 可以扩容
void reserve(size_t n) //只是改变capacity 不改变size
{
if (n > _capacity)
{
//新建一个字符数组
cout << "reserve->" << n << endl;
char* new_str = new char[n + 1];
//更改容量
//strcpy(new_str, _str);
memcpy(new_str, _str, _size + 1);
delete[] _str;
_str = new_str;
_capacity = n;
}
}
void push_back(char ch)
{
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
//加入字符
_str[_size] = ch;
++_size;
_str[_size] = '\0';
}
void append(const char* str)
{
if (_size + strlen(str) > _capacity)
{
reserve(_size + strlen(str));//至少保留_size + strlen(str)
}
//加入字符串
memcpy(_str + _size, str, strlen(str) + 1);//在'\0'位置（就是_str末尾）+str
_size += strlen(str);
}
注意：为什么拷贝字符串内容的时候用memcpy而不是strcpy，这是因为，string中可能中间会有'\0'，memcpy是根据第三个参数来定要拷贝的字符长度，而strcmpy，是根据要拷贝的字符串的'\0'出现的位置，所以使用memcpy更加合适。
strcpy和memcpy的对比
- char * strcpy ( char * destination, const char * source );
- void * memcpy ( void * destination, const void * source, size_t num );
operator+=的实现
我们实现了push_back和append之后就可以直接复用这两个函数，实现operator+=
string& operator+=(char ch)
{
push_back(ch); //插入一个字符的时候
return *this;
}
string& operator+=(const char* str)
{
append(str); //插入字符串的时候
return *this;
}//因为string对象在该函数之后不会释放空间，所以传引用返回，提高效率
string常用函数的实现
下面主要是对于insert、find、erase、substr、resize、一系列重载运算符等的实现
insert的实现
我们主要实现两种insert函数 1.在pos位置上插入n个字符c 2.在pos位置上插入字符串str
string& insert(size_t pos, size_t n, char c)
{
//1.先判定pos是否正确
assert(pos <= _size);
//2.扩容
reserve(_size + n);
//3.在pos位置上开始挪动n个字符
size_t end = _size;
//因为如果pos为0的时候，无符号整型0减去1，end >= pos比较 为一个巨大值，使得该循环无法停止
//npos是static变量，定义为-1;
while (end >= pos && end != npos)
{
_str[end + n] = _str[end];
--end;
}
//4.添加n个字符
for (int i = 0; i < n; i++)
{
_str[pos + i] = c;
}
_size += n;
return *this;
}
string& insert(size_t pos, const char*str)
{
//1.pos的判定
assert(pos <= _size);
//2.扩容
int len = strlen(str);
reserve(_size + len);
//3.在pos位置上移动len个字符
size_t end = _size;
while (end >= pos && end != npos)
{
_str[end + len] = _str[end];
--end;
}
//4.将str字符串的字符依次输入
for (int i = 0; i < len; i++)
{
_str[pos + i] = str[i];
}
//5.最后_size增加
_size += len;
return *this;
}
注意：npos的使用，是为了防止size_t无符号整型在于整型pos比较时候的强制转换，整型提升，得到一个巨大值，造成无限循环。
erase的实现
主要就是判断len是否等于npos，或者pos+len>=_size，分两种情况，是否从pos删除完，实际上就是在pos位置上加上'\0'即可，反之就是间隔len个距离向前移动字符，直到pos+len<=_size，最后_size-=len
string& erase(size_t pos = 0, size_t len = npos)
{
assert(pos <= _size);
if (len == npos || pos + len >= _size)
{
//表示从pos位置删完
_str[pos] = '\0';
_size = pos;
}
else {
//从pos位置删除len个字符
//向前挪动
size_t end = pos;
while (end+len <= _size)
{
_str[end] = _str[end + len];
end++;
}
//此时end==_size
//_str[end] = '\0';
_size -= len;
}
return *this;
}
find的实现
find的实现，就是遍历找到符合条件的下标，并返回
size_t find(char ch, size_t pos = 0) const
{
assert(pos < _size);
for (size_t i = pos; i < _size; i++)
{
if (_str[i] == ch)
{
return i;
}
}
return npos; //没有找到返回-1；
}
size_t find(const char* s, size_t pos = 0) const
{
//使用strstr
assert(pos < _size);
const char* str = strstr(_str+pos, s); //使用str函数，进行比较是否有对应的字符串
if (str)
{
return str-_str;//两个指针相减，得到的是地址的偏移量
}
else {
return npos;
}
}
substr的实现
substr的实现，就是判断要解决的n的数值，然后新建一个string字符串，将从pos位置开始的n个字符依次添加到这个新字符串中，最后返回新字符串
//substr的实现
string substr(size_t pos = 0, size_t len = npos)
{
assert(pos < _size);
size_t n = len;
//如果缺省len=npos 或者是截取的范围大于_size
if (len == npos || pos + len >= _size)
{
n = _size - pos;
}
//创建一个新的字符数组
string new_str;
new_str.reserve(n);
for (size_t i = pos; i < n + pos; i++)
{
new_str += _str[i];
}
return new_str;
}
resize的实现
resize底层是有reserve的，即需要判断是否需要扩容，满足_size<=_capacity
//实现resize
void resize(size_t n, char ch = '\0')
{
//两种情况，1.n<_size 直接赋值'\0' 2.判断是否扩容
if (n < _size)
{
_size = n;
_str[_size] = '\0';
}
else
{
reserve(n);//让reserve来判断是否是需要扩容
for (size_t i = _size; i < n; i++)
{
_str[i] = ch;
}
_size = n;
_str[_size] = '\0';
}
}
opeartor重载运算符
重载运算符，只要实现一两个就能实现其他，下面我们实现的是operator< 和operator== 然后通过调用这两个函数，来实现其他operator
//字符串比较按照ascii比较
//bool operator<(const string& s)
//{
// int num=memcmp(_str, s._str, _size > s._size?s._size : _size);
// //如果在最小长度下，前面数值小于后者 num返回的是负数
//
// return num == 0 ? _size < s._size : num < 0;
// //如果如果num为0，说明等于，且前者长度小于后者，返回真值，反之返回
//}
bool operator<(const string& s)
{
size_t i1 = 0;
size_t i2 = 0;
int num = _size > s._size ? s._size : _size; //得到两者最小的长度
while (i1 < num && i2 < num)
{
if (_str[i1] < s._str[i2]) //只要不相等就返回
{
return true;
}
else if(_str[i1] > s._str[i2]) {
return false;
}
else
{
++i1; //该字符相当，那么继续++
++i2;
}
}
return _size < s._size; //现在退出循环，说明前num个字符都相等，如果此时_size<s._size 那么返回真，反之返回假
}
bool operator==(const string& s)
{
return _size == s._size && memcmp(_str, s._str, _size > s._size ? s._size : _size) == 0; //两者字符长度相等，且通过memcpy返回值是否为0来判断函数返回值
}
//我们把 _size == s._size 放在前面，那么后面只需要memcpy(_str,s._str,_size)==0即可
bool operator<=(const string& s)
{
return *this < s || *this == s;
}
bool operator>(const string& s)
{
return !(*this <= s);
}
bool operator>=(const string& s)
{
return !(*this < s);
}
//访问指定下标的字符
//operator[]的实现
//
char& operator[](size_t pos)
{
//可读写 pos表示下标
assert(pos < _size);
return _str[pos]; //返回的是单个字符所以用char 且_str变量离开该函数依旧存在，可以使用&返回
}
string& operator=(const string& s)
{
if (this != &s)
{
//调用拷贝构造函数 将s的数据给tmp
string tmp(s);
std::swap(_str, tmp._str);
std::swap(_size, tmp._size);
std::swap(_capacity, tmp._capacity);
//进行交换，交换之后tmp在函数结束之后就会释放空间，但是其通过拷贝构造函数生成的新的string对象中的数值留给了*this对象
}
return *this;
}
流插入>>和流提取<<
//流提取
ostream& operator<<(ostream& out, const String::string& s)
{
//就是将s字符串中的每一个字符都加载到out中
for (auto ch : s)
{
out << ch;
}
return out;
}
//流插入
istream& operator>>(istream& in, String::string& s)
{
//判断一个字符是否结束 按照空格或者\0来判断
s.clear();
char buff [128];
char ch = in.get();//get 字符
int i = 0;
while (ch == ' '|| ch == '\n')
{
ch = in.get(); //处理缓冲区前面的空格和换行
}
while (ch != ' ' && ch != '\n')
{
buff[i++] = ch;
//如果输入的数值在127之外
if (i == 127) //先i++ 相当于从1到127
{
//留出来一个空间给\0 所以只能这样
buff[i] = '\0';
s += buff;
i = 0;//要重置i
}
ch = in.get();
}
if (i != 0)
{
//如果i不0的话，那就是说数值长度在127之内 直接扩容
buff[i] = '\0';
s += buff;
}
return in;
}
总结：
- 有关于插入以及添加字符、字符串的函数，都需要考虑容量的问题所以底层会有reserve，比如push_back、append、resize、insert、+=等函数
- find的实现就是遍历，以及使用strstr函数，快速方便的得到下标
- erase、insert等函数都会涉及到移动数组元素，erase向前移动，insert向后移动
- 重载运算符的实现，可以方便我们使用string类
最后附上完整模拟实现string类的代码
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<assert.h>
#include<math.h>
//模拟实现string
namespace String {
class string {
public:
//迭代器： string中的迭代器实际上就是指针
typedef char* iterator;
typedef const char* const_iterator;
iterator begin()
{
//begin 表示的是string的首元素地址
return _str;
}
iterator end()
{
//end 返回string最后一个元素的下一个位置，也就是'\0'
return _str + _size;
}
const_iterator begin() const
{
//begin 表示的是string的首元素地址
return _str;
}
const_iterator end() const
{
//end 返回string最后一个元素的下一个位置，也就是'\0'
return _str + _size;
}
//默认构造函数
//string()
// :_str(new char[1])
// ,size(0)
// ,capacity(0)
//{
// _str[0] = '\0';
//}
//带参构造函数 字符串
//string(const char* str)
// :_str(new char[strlen(str)])
// ,size(strlen(str))
// ,capacity(strlen(str))
//{
// //存储字符串
// strcpy(_str, str);
//}
//默认构造和带参构造合并，使用缺省参数
string(const char* str="") //""字符串自带'\0'
:_str(new char[strlen(str)+1])
, _size(strlen(str))
, _capacity(strlen(str))
{
//存储字符串
strcpy(_str, str);
}
//拷贝构造
//string(const string& s)
//{
// //深拷贝，就是创建一个大小一样的空间
// _str = new char[s._capacity + 1];
// strcpy(_str, s._str);
// _size = s._size;
// _capacity = s._capacity;
//}
string(const string& s)
{
_str = new char[s._capacity + 1];
memcpy(_str, s._str,s._size + 1);
_size = s._size;
_capacity = s._capacity;
}
//析构函数
~string()
{
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
void Print() {
cout << _str <<"\t" << _size <<"\t"<< _capacity << endl;
}
//size_t 无符号整型
const char* c_str()
{
return _str;
}
//返回size
size_t size() const //const表示修饰this指针，也就是说只读，如果是const对象，也可以访问，普通用户相当于权限的缩小也可也访问
{
return _size;
}
//operator[]的实现
//
char& operator[](size_t pos)
{
//可读写 pos表示下标
assert(pos < _size);
return _str[pos]; //返回的是单个字符所以用char 且_str变量离开该函数依旧存在，可以使用&返回
}
//对于const对象
const char& operator[](size_t pos) const //修饰const对象，前面const修饰的话，表示不可以被修改，后面const对象就修饰this指针 const String::string* this
{
//只读
assert(pos < _size);
return _str[pos];
}
//reserve 保留容量 可以扩容
void reserve(size_t n) //只是改变capacity 不改变size
{
if (n > _capacity)
{
//新建一个字符数组
cout << "reserve->" << n << endl;
char* new_str = new char[n + 1];
//更改容量
//strcpy(new_str, _str);
memcpy(new_str, _str, _size + 1);
delete[] _str;
_str = new_str;
_capacity = n;
}
}
//push_back
void push_back(char ch)
{
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
//加入字符
_str[_size] = ch;
++_size;
_str[_size] = '\0';
}
void append(const char* str)
{
if (_size + strlen(str) > _capacity)
{
reserve(_size + strlen(str));//至少保留_size + strlen(str)
}
//加入字符串
memcpy(_str + _size, str, strlen(str)+1);//在'\0'位置（就是_str末尾）+str
_size += strlen(str);
}
//实现+= 也是使用push_back 和append函数
string& operator+=(char ch)
{
push_back(ch);
return *this;
}
string& operator+=(const char* str)
{
append(str);
return *this;
}
string& insert(size_t pos, size_t n, char c)
{
//1.先判定pos是否正确
assert(pos <= _size);
//2.扩容
reserve(_size + n);
//3.在pos位置上开始挪动n个字符
size_t end = _size;
//因为如果pos为0的时候，无符号整型0减去1，end >= pos比较 为一个巨大值，使得该循环无法停止
//npos是static变量，定义为-1;
while (end >= pos && end != npos)
{
_str[end + n] = _str[end];
--end;
}
//4.添加n个字符
for (int i = 0; i < n; i++)
{
_str[pos + i] = c;
}
_size += n;
return *this;
}
string& insert(size_t pos, const char*str)
{
//1.pos的判定
assert(pos <= _size);
//2.扩容
int len = strlen(str);
reserve(_size + len);
//3.在pos位置上移动len个字符
size_t end = _size;
while (end >= pos && end != npos)
{
_str[end + len] = _str[end];
--end;
}
//4.将str字符串的字符依次输入
for (int i = 0; i < len; i++)
{
_str[pos + i] = str[i];
}
//5.最后_size增加
_size += len;
return *this;
}
//从pos位置开始，删除len长度字符
string& erase(size_t pos = 0, size_t len = npos)
{
assert(pos <= _size);
if (len == npos || pos + len >= _size)
{
//表示从pos位置删完
_str[pos] = '\0';
_size = pos;
}
else {
//从pos位置删除len个字符
//向前挪动
size_t end = pos;
while (end+len <= _size)
{
_str[end] = _str[end + len];
end++;
}
//此时end+len==_size
//_str[end] = '\0';
_size -= len;
}
return *this;
}
//find
size_t find(char ch, size_t pos = 0) const
{
assert(pos < _size);
for (size_t i = pos; i < _size; i++)
{
if (_str[i] == ch)
{
return i;
}
}
return npos; //没有找到返回-1；
}
size_t find(const char* s, size_t pos = 0) const
{
//使用strstr
assert(pos < _size);
const char* str = strstr(_str+pos, s);
if (str)
{
return str-_str;//两个指针相减，得到的是地址的偏移量
}
else {
return npos;
}
}
//substr的实现
string substr(size_t pos = 0, size_t len = npos)
{
assert(pos < _size);
size_t n = len;
//如果缺省len=npos 或者是截取的范围大于_size
if (len == npos || pos + len >= _size)
{
n = _size - pos;
}
//创建一个新的字符数组
string new_str;
new_str.reserve(n);
for (size_t i = pos; i < n + pos; i++)
{
new_str += _str[i];
}
return new_str;
}
void clear()
{
_str[0] = '\0';
_size = 0;
}
//实现resize
void resize(size_t n, char ch = '\0')
{
//两种情况，1.n<_size 直接赋值'\0' 2.判断是否扩容
if (n < _size)
{
_size = n;
_str[_size] = '\0';
}
else
{
reserve(n);//让reserve来判断是否是需要扩容
for (size_t i = _size; i < n; i++)
{
_str[i] = ch;
}
_size = n;
_str[_size] = '\0';
}
}
//字符串比较按照ascii比较
//bool operator<(const string& s)
//{
// int num=memcmp(_str, s._str, _size > s._size?s._size : _size);
// //如果在最小长度下，前面数值小于后者 num返回的是负数
//
// return num == 0 ? _size < s._size : num < 0;
// //如果如果num为0，说明等于，且前者长度小于后者，返回真值，反之返回
//}
bool operator<(const string& s)
{
size_t i1 = 0;
size_t i2 = 0;
int num = _size > s._size ? s._size : _size;
while (i1 < num && i2 < num)
{
if (_str[i1] < s._str[i2])
{
return true;
}
else if(_str[i1] > s._str[i2]) {
return false;
}
else
{
++i1;
++i2;
}
}
return _size < s._size;
}
bool operator==(const string& s)
{
return _size == s._size && memcmp(_str, s._str, _size) == 0;
}
bool operator<=(const string& s)
{
return *this < s || *this == s;
}
bool operator>(const string& s)
{
return !(*this <= s);
}
bool operator>=(const string& s)
{
return !(*this < s);
}
//string& operator=(const string& s)
//{
// if (this != &s)
// {
// //如果不是同一个string
// //深拷贝
// char* new_str = new char[s._capacity + 1];
// memcpy(new_str, s._str, s._size);
// //删除原来地址
// delete[] _str;
// //新指向一个new_str
// _str = new_str;
// //更改容量和size
// _capacity = s._capacity;
// _size = s._size;
// }
// return *this;
//}
string& operator=(const string& s)
{
if (this != &s)
{
//调用拷贝构造函数 将s的数据给tmp
string tmp(s);
std::swap(_str, tmp._str);
std::swap(_size, tmp._size);
std::swap(_capacity, tmp._capacity);
//进行交换，交换之后tmp在函数结束之后就会释放空间，但是其通过拷贝构造函数生成的新的string对象中的数值留给了*this对象
}
return *this;
}
size_t capacity()
{
return _capacity;
}
size_t size()
{
return _size;
}
//无穷递归的问题：反复调用堆栈
// std::swap(*this,tmp)
//定义属性
private:
char* _str;
int _size;
int _capacity;
public:
const static size_t npos;
};
const size_t string::npos = -1;
}
//流提取
ostream& operator<<(ostream& out, const String::string& s)
{
//就是将s字符串中的每一个字符都加载到out中
for (auto ch : s)
{
out << ch;
}
return out;
}
//流插入
istream& operator>>(istream& in, String::string& s)
{
//判断一个字符是否结束 按照空格或者\0来判断
s.clear();
char buff [128];
char ch = in.get();//get 字符
int i = 0;
while (ch == ' '|| ch == '\n')
{
ch = in.get(); //处理缓冲区前面的空格和换行
}
while (ch != ' ' && ch != '\n')
{
buff[i++] = ch;
//如果输入的数值在127之外
if (i == 127) //先i++ 相当于从1到127
{
//留出来一个空间给\0 所以只能这样
buff[i] = '\0';
s += buff;
i = 0;//要重置i
}
ch = in.get();
}
if (i != 0)
{
//如果i不0的话，那就是说数值长度在127之内 直接扩容
buff[i] = '\0';
s += buff;
}
return in;
}
