目录
?
一、String类实现
为了和库里面的string 区分开，使用命名空间delia将?string类和库里string隔离开
string类有3个成员变量：_str字符串内容、_size字符串大小、_capacity字符串容量
namespace delia
{
class string
{
private:
char* _str;
size_t _size;
size_t _capacity;
}
}string的模拟实现包括：
1.string类的构造?
分配空间时，要多分配1个字节的空间，这1个字节是留给'\0'的，_size最大为申请字节数-1，_capacity最大也为申请字节数-1?
//构造函数
string(const char* str = "")
{
_str = new char[strlen(str) + 1];
strcpy(_str, str);
_size = strlen(str);
_capacity = _size;
}?
2.swap()?
使用库里的swap函数交换*this和s的内容：包括_str字符串内容、_size字符串大小和_capacity字符串容量?
//实现交换函数
void swap(string& s)
{
//用::指定调用全局的swap函数即库里的swap函数
::swap(_str, s._str);
::swap(_size, s._size);
::swap(_capacity, s._capacity);
}3.拷贝构造
（1）先使用s._str作为参数构造一个临时对象
（2）将临时对象tmp的内容和*this进行交换
注意：必须要在初始化列表进行初始化 ，否则交换完毕后tmp出了拷贝构造函数作用域会调用析构函数释放tmp在堆上申请的空间，因为如果_str没有被初始化为空指针，那么_str就是随机值，交换后，tmp对象的成员_str也是随机值，随机值的空间时不可以被释放的，会导致不可预知的错误；空指针时可以被释放的，因此_str必须被初始化为空指针。
//现代拷贝构造
string(const string& s)
:_str(nullptr)
, _size(0)
, _capacity(0)
{
string tmp(s._str);
swap(tmp);
}4.赋值运算符重载
使用swap()函数将*this的内容和s进行交换?
//赋值运算符重载
string& operator=(string s)
{
swap(s);
return *this;
}?
5.析构
释放_str在对上申请的空间、将_size和_capacity置0?
//析构函数
~string()
{
delete[] _str;
_str = nullptr;
_size = 0;
_capacity = 0;
}?
6.迭代器
分两种：普通迭代器（可读可写）和const迭代器（只读）?
（1）普通迭代器
//迭代器
iterator begin()
{
return _str;
}
//迭代器
iterator end()
{
return _str + _size;
}（2）const迭代器
//const迭代器
iterator begin() const
{
return _str;
}
//const迭代器
iterator end() const
{
return _str + _size;
}?
7.operator[ ]
?也分为普通operator[ ]（可读可写）和const?operator[ ]（只读）
char要加&，如果不加，那么return就是传值返回，返回的是_str[i]的拷贝，即临时对象，而临时对象具有常性，不能被修改，只能读；如果要对_str进行修改的话，char要加&，用传引用返回
//const string对象遍历，只读
char& operator[](size_t i) const
{
assert(i < _size);
return _str[i];
}
//非const string对象遍历，可读可写
char& operator[](size_t i)
{
assert(i < _size);
return _str[i];
}?
8.size()
//求string对象大小
size_t size() const
{
return strlen(_str);
}?
9.c_str()
获取c形式字符串，将 const string* 类型 转化为 const char* 类型?
const char* c_str()
{
return _str;
}?
10.reserve()?
开空间，扩展_capacity，_size不变?
（1）申请新空间
（2）拷贝字符串
（3）释放旧空间
（4）指向新空间
（5）更新容量?
void reserve(size_t n)
{
if (n > _capacity)
{
char* tmp = new char[n + 1];//1.申请新空间，多开的那一个空间，存放\0
strncpy(tmp, _str, _size + 1);//2.将字符串包含\0在内都拷贝到新空间
delete[] _str;//3.释放旧空间
_str = tmp;//4.指向新空间
_capacity = n;//5.更新容量
}
}11.resize()
开空间+初始化，扩展_capacity，_size也要修改?
（1）当n<_size，无需增容?
（2）当n>_size，分两种情况
?? ??? ??? ?①_size < n <_capacity，无需增容，直接将_size到n位置置为val
?? ??? ??? ?②n >_capacity，需增容，并将_size到n位置置为val
?? ??? ???n>_size的这两种情况只有是否增容的区别，其他没有区别，可以合二为一
void resize(size_t n, char val = '\0')//如果没有显式给出val，val为\0
{
//1.当n<_size，无需增容
if (n < _size)
{
_size = n;//直接更新_size
_str[_size] = '\0';//将_size位置置为\0
}
//2.当n>_size，分两种情况
//（1）_size < n <_capacity，无需增容，直接将_size到n位置置为val
//（2）n >_capacity，需增容，并将_size到n位置置为val
//这两种情况只有是否增容的区别，其他没有区别
else
{
if (n > _capacity)
{
reserve(n);
}
for (size_t i = _size; i < n; i++)
{
_str[i] = val;
}
_str[n] = '\0';//将n的位置置\0
_size = n;//更新_size
}
}?
12.push_back()
要考虑是否需要开空间
//尾插一个字符
void push_back(char ch)
{
//字符个数已经达到容量时，重新开空间
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);//如果是第一次开空间，就开4个字节，如果不是第一次开空间，就开成原来的2倍容量
}
_str[_size] = ch;//将字符ch缀到字符串末尾
_str[_size + 1] = '\0';//字符ch后面加\0，表明字符串结束
_size++;//字符串大小+1
}13.append()
将str内容copy至this._str+_size（*this._str的末尾）位置?
?
?
//追加字符串
void append(const char* str)
{
size_t len = _size + strlen(str);//函数执行完毕后字符串的大小
if (len > _capacity)
{
reserve(len);//空间不够，增容
}
strcpy(_str + _size, str);//将str内容拷贝至_str末尾
_size = len;//更新_size
}?
14.operator+=()
分为两种情况：
（1）+= 1个字符?，使用push_back插入
（2）+= 字符串，使用append追加到字符串末尾
//+= 1个字符
string& operator+= (char c)
{
push_back(c);//尾插字符
return *this;
}
//+= 字符串
string& operator+= (const char* str)
{
append(str);//拼接字符串
return *this;
}?
15.insert()
在指定位置插入字符：
（1）判断是否需要增容
（2）将pos位至字符串末尾的字符都向后挪一个位置
（3）将要插入的字符插入到pos位
（4）更新_size
?
//insert插入一个字符
string& insert(size_t pos, const char ch)
{
assert(pos <= _size);//pos必须小于等于字符串长度
if (_size == _capacity)
{
reserve(2 * _capacity);//如果满了就增容
}
size_t end = _size + 1;
while (end > pos)//将pos至_size之间的字符依次向后挪动一个位置，来腾出pos位置
{
_str[end] = _str[end - 1];
end--;//end为0时，因此end类型应为int，那么end--就为-1，pos为无符号数，不满足循环条件，退出循环
//但如果end类型为size_t，那么end为0时，end--就为-1，在内存中存储为无符号数(-1补码全1)，满足循环条件，永远无法退出循环
}
_str[pos] = ch;//pos位置插入ch
_size++;//更新_size
return *this;
}16.erase()
删除字符，len为要删除的字符个数，分两种情况：
（1）从pos到字符串末尾的字符个数<要删除的字符个数，说明this._str长度不够删，那pos之后全都被删完了，直接将pos位置'\0'，_size更新为pos即可。
?
（2）从pos到字符串末尾的字符个数≥要删除的字符个数，说明this._str长度够删，但是剩余的字符需要向前挪动len位
?
//erase 删除字符
string& erase(size_t pos, size_t len = npos)
{
assert(pos < _size);
size_t leftLen = _size - pos;//从pos位置到字符串结束的字符长度
if (leftLen < len)//1.pos之后的字符全部删掉
{
_str[pos] = '\0';
_size = pos;
}
else//2.pos之后的字符删掉一部分，没删完的部分要挪到pos位置
{
strcpy(_str + pos, _str + pos + len);
_size -= len;
}
return *this;
}
?
17.find()
分为查找字符和查找字符串
//查找字符
size_t 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;//没找到就返回-1
} //查找字符串(子串)
size_t find(const char* str, size_t pos = 0)
{
assert(pos < _size);
const char* ret = strstr(_str + pos, str);
if (ret)
{
return ret - _str;//计算str与_str的偏移量，即str在_str中的下标
}
else
{
return npos;//没找到就返回-1
}
}?
18.operator>
字符串比较，只需要实现>和==，剩余的可以用这两个实现重载?
bool operator>(const string& s)
{
return strcmp(_str, s._str) < 0;
}?
19.operator==
bool operator==(const string& s)
{
return strcmp(_str, s._str) == 0;
}?
20.operator>=
bool operator>=(const string& s)
{
return (*this > s) || (*this == s);
}?
21.operator<
bool operator<(const string& s)
{
return !(*this >= s);
}?
22.operator<=
bool operator<=(const string& s)
{
return !(*this > s);
}?
23.operator!=
bool operator!=(const string& s)
{
return !(*this == s);
}?
24.clear()
将字符串清空?
void clear()
{
_size = 0;
_str[0] = '\0';
}?
25.operator<<
输出重载<<让string直接输出打印，像内置类型一样，用范围for就可以实现
ostream& operator<<(ostream& out, const string& s)
{
for (auto ch: s)
{
out << s;
}
return out;
}?
26.operator>>?
输入重载>>让string直接输入，像内置类型一样；从标准输入流读取字符，遇到' '或'\0'就停止?
istream& operator>>(istream& in, string& s)
{
s.clear();
char ch;
ch = in.get();
while (ch != ' ' && ch != '\0')
{
s += ch;
ch = in.get();
}
return in;
}?完整代码段：
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<assert.h>
#include<stdlib.h>
using namespace std;
//定义一个新的命名空间，和全局命名空间隔离开
namespace delia
{
class string
{
public:
typedef char* iterator;
//迭代器
iterator begin()
{
return _str;
}
//迭代器
iterator end()
{
return _str + _size;
}
//const迭代器
iterator begin() const
{
return _str;
}
//const迭代器
iterator end() const
{
return _str + _size;
}
//构造函数
string(const char* str = "")
{
_str = new char[strlen(str) + 1];//1是留给'/0'的，_size最大为申请字节数-1，_capacity也为申请字节数-1
strcpy(_str, str);
_size = strlen(str);
_capacity = _size;
}
//现代拷贝构造
string(const string& s)
:_str(nullptr)
, _size(0)
, _capacity(0)
{
string tmp(s._str);
swap(tmp);
}
//赋值运算符重载
string& operator=(string s)
{
swap(s);
return *this;
}
//析构函数
~string()
{
delete[] _str;
_str = nullptr;
_size = 0;
_capacity = 0;
}
//实现交换函数
void swap(string& s)
{
::swap(_str, s._str);//用::指定调用全局的swap函数即库里的swap函数
::swap(_size, s._size);
::swap(_capacity, s._capacity);
}
//const string对象遍历，只读
char& operator[](size_t i) const//char要加&，如果不加，那么return就是传值返回，返回的是_str[i]的拷贝，临时对象，而临时对象具有常性，不能被修改，只能读
//如果要对_str进行修改的话，char要加&，用传引用返回
{
assert(i < _size);
return _str[i];
}
//非const string对象遍历，可读可写
char& operator[](size_t i)
{
assert(i < _size);
return _str[i];
}
//求string对象大小
size_t size() const
{
return strlen(_str);
}
//获取c形式字符串，将 const string* 类型 转化为 const char* 类型
const char* c_str()
{
return _str;
}
//开空间，扩展_capacity，_size不变
void reserve(size_t n)
{
//1.申请新空间
//2.拷贝字符串
//3.释放旧空间
//4.指向新空间
//5.更新容量
if (n > _capacity)
{
char* tmp = new char[n + 1];//1.申请新空间，多开的那一个空间，存放\0
strncpy(tmp, _str, _size + 1);//2.将字符串包含\0在内都拷贝到新空间
delete[] _str;//3.释放旧空间
_str = tmp;//4.指向新空间
_capacity = n;//5.更新容量
}
}
//开空间+初始化，扩展_capacity，_size也要修改
void resize(size_t n, char val = '\0')//如果没有显式给出val，val为\0
{
//1.当n<_size，无需增容
if (n < _size)
{
_size = n;//直接更新_size
_str[_size] = '\0';//将_size位置置为\0
}
//2.当n>_size，分两种情况
//（1）_size < n <_capacity，无需增容，直接将_size到n位置置为val
//（2）n >_capacity，需增容，并将_size到n位置置为val
//这两种情况只有是否增容的区别，其他没有区别
else
{
if (n > _capacity)
{
reserve(n);
}
for (size_t i = _size; i < n; i++)
{
_str[i] = val;
}
_str[n] = '\0';//将n的位置置\0
_size = n;//更新_size
}
}
//尾插一个字符
void push_back(char ch)
{
//字符个数已经达到容量时，重新开空间
if (_size == _capacity)
{
reserve(_capacity == 0 ? 4 : _capacity * 2);//如果是第一次开空间，就开4个字节，如果不是第一次开空间，就开成原来的2倍容量
}
_str[_size] = ch;//将字符ch缀到字符串末尾
_str[_size + 1] = '\0';//字符ch后面加\0，表明字符串结束
_size++;//字符串大小+1
}
//追加字符串
void append(const char* str)
{
size_t len = _size + strlen(str);//函数执行完毕后字符串的大小
if (len > _capacity)
{
reserve(len);//空间不够，增容
}
strcpy(_str + _size, str);//将str内容拷贝至_str末尾
_size = len;//更新_size
}
//+= 1个字符
string& operator+= (char c)
{
push_back(c);//尾插字符
return *this;
}
//+= 字符串
string& operator+= (const char* str)
{
append(str);//拼接字符串
return *this;
}
//insert插入一个字符
string& insert(size_t pos, const char ch)
{
assert(pos <= _size);//pos必须小于等于字符串长度
if (_size == _capacity)
{
reserve(2 * _capacity);//如果满了就增容
}
size_t end = _size + 1;
while (end > pos)//将pos至_size之间的字符依次向后挪动一个位置，来腾出pos位置
{
_str[end] = _str[end - 1];
end--;//end为0时，因此end类型应为int，那么end--就为-1，pos为无符号数，不满足循环条件，退出循环
//但如果end类型为size_t，那么end为0时，end--就为-1，在内存中存储为无符号数(-1补码全1)，满足循环条件，永远无法退出循环
}
_str[pos] = ch;//pos位置插入ch
_size++;//更新_size
return *this;
}
//erase 删除字符
string& erase(size_t pos, size_t len = npos)
{
assert(pos < _size);
size_t leftLen = _size - pos;//从pos位置到字符串结束的字符长度
if (leftLen < len)//1.pos之后的字符全部删掉
{
_str[pos] = '\0';
_size = pos;
}
else//2.pos之后的字符删掉一部分，没删完的部分要挪到pos位置
{
strcpy(_str + pos, _str + pos + len);
_size -= len;
}
return *this;
}
//查找字符
size_t 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;//没找到就返回-1
}
//查找字符串(子串)
size_t find(const char* str, size_t pos = 0)
{
assert(pos < _size);
const char* ret = strstr(_str + pos, str);
if (ret)
{
return ret - _str;//计算str与_str的偏移量，即str在_str中的下标
}
else
{
return npos;//没找到就返回-1
}
}
//字符串比较，只需要实现>和==
bool operator>(const string& s)
{
return strcmp(_str, s._str) < 0;
}
bool operator==(const string& s)
{
return strcmp(_str, s._str) == 0;
}
// 其它4个运算符都可以对>和==这两个运算符进行重载
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);
}
bool operator!=(const string& s)
{
return !(*this == s);
}
void clear()
{
_size = 0;
_str[0] = '\0';
}
private:
char* _str;
size_t _size;
size_t _capacity;
static const size_t npos;
};
const size_t string::npos = -1;//npos初始化
//输出重载<<让string直接输出打印，像内置类型一样，用范围for就可以实现
ostream& operator<<(ostream& out, const string& s)
{
for (auto ch: s)
{
out << s;
}
return out;
}
//输入重载>>让string直接输入，像内置类型一样；从标准输入流读取字符，遇到' '或'\0'就停止
istream& operator>>(istream& in, string& s)
{
s.clear();
char ch;
ch = in.get();
while (ch != ' ' && ch != '\0')
{
s += ch;
ch = in.get();
}
return in;
}
void f(const string& s)
{
for (size_t i = 0; i < s.size(); i++)
{
cout << s[i] << " ";
}
cout << endl;
}
void test_string1()
{
string s1("hello world");
string s2(s1);
string s3("cplusplus.com");
std::swap(s1, s3);//调用库里的swap函数，3次深拷贝，再把原来的空间释放掉，再开一样大的空间，代价大
s1.swap(s3);//调用delia::string类里面的成员函数swap，仅仅只是成员变量的交换，s3指向了s1的空间，s1指向了s3的空间
string s4 = s1.c_str();
s1[2] = 'w';
f(s1);//h e w l o w o r l d
for (size_t i = 0; i < s1.size(); i++)
{
cout << s1[i] << " ";
}
cout << endl;//h e w l o w o r l d
}
void test_string2()
{
string s1("hello world");
//使用迭代器遍历
string::iterator it = s1.begin();
while (it != s1.end())
{
cout << *it << " ";
it++;
}
cout << endl;//h e l l o w o r l d
//使用范围for遍历,范围for会被编译器替换成迭代器形式,如果把17-26行屏蔽，会发现编译不过
for (auto ch : s1)
{
cout << *it << " ";
}
cout << endl;//h e l l o w o r l d
}
void test_string3()
{
string s1("hello world");
s1 += "abc";
for (auto& ch : s1)
{
cout << ch << " ";
}
cout << endl;//h e l l o w o r l d a b c
s1 += "xyz";
for (auto& ch : s1)
{
cout << ch << " ";
}
cout << endl;//h e l l o w o r l d a b c x y z
}
void test_string4()
{
string s1("hello world");
s1 += '#';
for (auto ch : s1)
{
cout << ch << " ";
}
cout << endl;//hello world#
s1 += "xyz";
for (auto ch : s1)
{
cout << ch << " ";
}
cout << endl;//hello world#xyz
s1 += "!!!!!!!!!!!!!!!!!!!!";
for (auto ch : s1)
{
cout << ch << " ";
}
cout << endl;//hello world#xyz!!!!!!!!!!!!!!!!!!!!
}
void test_string5()
{
string s1("hello world");
s1.resize(3);
cout << s1.c_str() << endl;//hel
}
void test_string6()
{
string s1("hello");
s1.resize(6, 'a');
cout << s1.c_str() << endl;//helloa
}
void test_string7()
{
string s1("hello");
s1.resize(9, 'o');
cout << s1.c_str() << endl;//helloooo
}
void test_string8()
{
string s1("hello");
s1.insert(0, 'u');
cout << s1.c_str() << endl;//uhello
}
void test_string9()
{
string s1("hello");
s1.erase(0, 2);
cout << s1.c_str() << endl;//llo
string s2("world");
s2.erase(1);//如果不给len，那么npos=-1，无符号数为4294967295，删除从位置为1-4294967295的字符，把后面的字符全部删除了
cout << s2.c_str() << endl;//w
}
void test_string10()
{
string s1("hello world");
cout << s1.find("rl",6) << endl;//8,从s1中的第6个位置开始查找"rl"字符串
}
void test_string11()
{
std::string s("hello");
cin >> s;
cout << s << endl;
}
}
int main()
{
//delia::test_string1();
//delia::test_string2();
//delia::test_string3();
//delia::test_string4();
//delia::test_string5();
//delia::test_string6();
//delia::test_string7();
//delia::test_string8();
//delia::test_string9();
//delia::test_string10();
delia::test_string11();
return 0;
}二、在线OJ题
替换空格?OJ链接
分析：（1）如果使用string的replace或erase+insert都要挪动数据，效率低
? ? ? ? ? ?（2）考虑直接用新串，用新串需要分配多大空间？一个空格占1个字节，‘%20’占3个字节，替换后，每个空格都比原来多两个字节，新串空间应为：原串长度+2*空格数
class Solution {
public:
string replaceSpace(string s) {
//1.计算空格数
size_t spaceCount = 0;
for(auto ch:s)
{
if(ch == ' ')
{
spaceCount++;
}
}
//2.声明新串
string ret;
//3.为新串分配空间：从空格变为%20,长度增加2
ret.reserve(s.size()+2*spaceCount);
//4.将空格替换为%20
for(auto ch:s)
{
if(ch != ' ')
{
ret += ch;
}
else
{
ret += "%20";
}
}
return ret;
}
};
