C/C++ string模拟实现

1.模拟准备

1.1因为是模拟string，防止与库发生冲突，所以需要命名空间namespace隔离一下，我们来看一下基本内容

namespace yx
{class string{private://char _buff[16];  lunix下小于16字节就存buff里char* _str;size_t _size;size_t _capacity;};
}

1.2我们这里声明和定义分离，分为string.h和string.cpp

最简单的是：把声明和定义都往命名空间里包就可以

        

2.模拟实现

2.1遇到一个类，先来写构造和析构

构造和析构

我们来看一下下面代码对不对

namespace yx
{ string::string(const char* str):_str(str){}
}

既然这么问了，那肯定是不对的，

因为你初始化string的时候，可能为常量字符串初始化的，它是不可以作为初始化对象的，当你扩容、修改就没法改了

yx::string s1("hello world");

应该这样玩：

namespace yx
{ string::string(const char* str):_str(new char[strlen(str) + 1]){}
}

我和你开一样的空间

完整写法👇 

string::string(const char* str):_str(new char[strlen(str) + 1]), _size(strlen(str)), _capacity(strlen(str))
{strcpy(_str, str);
}

但还是有点问题的，strlen的效率还是有点底的，它和sizeof不一样，sizeof是在编译时运行，根据存储规则，内存对齐规则来算，strlen是运行时算的，三个strlen就重复运算了。

我们可以把size放在初始化列表，把其他的放在函数体初始化

string::string(const char* str): _size(strlen(str))
{_str = new char[_size + 1];_capacity = _size;strcpy(_str, str);
}

这是比较传统的写法，我们来看一下同样手法

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

创建一个临时变量tmp，s1给给tmp，然后把s2指向tmp，tmp指向s2的位置.

c_str

const char* c_str() const;

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

加const是为了让const或非const成员都能访问到，c_str()的类型为const char*,相当于常量字符串，遇到\0就会停止

无参string

我们可不可以这样写呢？

string::string()
{_str = nullptr;_size = 0;_capacity = 0;
}

看起来可以，但实际不可以，这里的delete和free是不会出问题的，因为delete是可以空指针的

我们看例子，后定义的先析构，程序崩溃了，为什么呢？

c_str ，类型为const char* 不会按指针打印，是常量字符串，就会解引用找到\0才停止。

但库里不会崩溃

为什么？

因为这个地方不是没有空间，库里面开了一个空间

所以初始化要改为

string::string()
{_str = new char[1] {'\0'};_size = 0;_capacity = 0;
}

new一个空间，而实践中不会这样写，无参的和带参的是可以和成一个的，就是全缺省

如下👇，冒号里的\0是可以不写的 默认就是\0 , 给的是字符串

namespace yx
{class string{public://string(); //无参构造  string(const char* str = "\0");~string();const char* c_str() const;//加上const，const成员和非const成员都可以调用private://char _buff[16];  lunix下小于16字节就存buff里char* _str;size_t _size;size_t _capacity;};
}

遍历：运算符重载[] 和 size()

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

size_t string::size() const
{return _size;
}

测试：可读可写

迭代器：begin 和 end

实现方式有两种，自定义类型的和简单点的，我们这里使用简单的

typedef char* iterator;iterator begin();
iterator end();

string::iterator string::begin()
{return _str;
}
string::iterator string::end()
{return _str + _size;
}

为什么这样写？

注：

        这里必须用typedef，为什么？迭代器体现的是一种封装

        这里的typedef相当于把char*用iterator封装起来，而且这里的迭代器一定是char*吗，在lunix下是char*吗，不同平台是不同的。

把不同类型，不同平台的类型都封装成Iterator，隐藏的底层的细节。它是一个像指针的东西。iterator的原生类型是不确定的，给了一种简单通用访问容器的方式。

无论哪个容器都重命名为iterator，各个类域也不会发生冲突。

const迭代器

定义及实现

const_iterator begin() const;
const_iterator end() const;

string::const_iterator string::begin() const
{return _str;
}

这里可以直接返回_str，_str类型为char*，begin为const char* ，相当于权限缩小。

string::const_iterator string::end() const
{return _str + _size;
}

这里也是权限缩小，下面我们测试一下

测试成功，而且是不能给常量赋值的，如下👇

如果我们用方括号加size来遍历呢？

这里会报错，为啥？因为s3是常量，所以还需要重载一个const修饰的operator[]

const char& operator[](size_t pos) const;​

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

测试通过。

push_back()  、 append()  和 reserve()

完成了string的基本功能，下面我们来进行string的插入。

push_back()是尾插一个字符，append()插入一个字符串，这里我们会遇到一个问题，push_back()尾插扩容一倍或两倍，不会太大；append()是插入一个字符串，有可能需要扩容，但扩容多少呢？插入字符串长短不定，万一非常长，你扩容二倍？显然扩容多少倍是不确定的。这里我们引入reserve().

reserve()请求保留空间，一般不会缩容，如果空间比capacity大了就会扩容

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;}
}

push_back()

​
void string::push_back(char ch)//插入字符
{if (_size == _capacity)//如果size 等于 容量大小才会扩容{size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2;reserve(newcapacity);//传给reserve，如果比当前capacity大，就扩容}_str[_size] = ch;//_size是最后一个字符的下一个位置_str[_size + 1] = '\0';++_size;
}​

满足扩容条件才扩容，_size是最后一个字符的下一个位置，也就是\0的位置，所以需要把\0也处理一下。

append()

我们来看一下下面代码正确否？

void string::append(const char* str)//插入字符串
{size_t len = strlen(str);if (_size + len > _capacity){reserve(_size + len);//现在有_size个，我们需要插入长度为len的字符串}strcat(_str, str);_size += len;
}

使用了strcat()，直接在原字符串后面追加，我们测试一下

测试没问题。但是我们用strcat的时候要谨慎一些，他会从头开始找\0，效率低，这里我们采用strcpy(),从指定位置开始拷贝，带\0

void string::append(const char* str)//插入字符串
{size_t len = strlen(str);if (_size + len > _capacity){reserve(_size + len);//现在有_size个，我们需要插入长度为len的字符串}strcpy(_str + _size, str);_size += len;
}

同样测试通过，但效率很高

直接从\0位置开始插入

 

operator+=

说到尾插字符串，那必须得提到+=运算符重载，这里提供俩个版本

这里引用返回，返回对象本身，出了作用域对象还存在。

string& operator+=(char ch);//+=是需要返回值的，用引用返回减少拷贝
string& operator+=(const char ch);

这里我们直接调用push_bakc和append

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

测试

inset() 和 erase()

size_t insert(size_t pos,char ch); //pos位插入字符
size_t insert(size_t pos,const char* ch);//插入字符串
void erase(size_t pos, size_t len = npos);//pos开始删除len个字符

private://char _buff[16];  lunix下小于16字节就存buff里char* _str;size_t _size;size_t _capacity;const static size_t npos;

对于npos，静态成员如何初始化，在类里面声明，在类外定义。

类里的静态成员遍历，相当于全局变量，如果在string.h里定义，在预处理以后，string

.h会在string.cpp和test.cpp里展开，展开两份，俩文件最后生成.o文件，再一链接就出问题了，

声明和定义分离的时候把定义放在.cpp，声明放在.h。

insert()插入一个字符

size_t string::insert(size_t pos, char ch)
{if (_size == _capacity)//空间不够，就扩容{size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2;reserve(newcapacity);}size_t end = _size;while (end >= pos){_str[end + 1] = _str[end];--end;}_str[pos] = ch;++_size;
}

测试

如果我们在0出插入一个字符呢？

显然报错了，为什么？

因为edn >= 0 继续交换，把0之前的哪个未知值也交换进去了，

当end >= pos = 0 时，已将交换完了，但又进入循环了，为什么？因为当操作符两边的操作数类型不同的时候，会发生隐式类型转化，当有符号遇到无符号，有符号转换为无符号，end变为非常大的数，end依据大于pos。那有什么方法来修改呢？

我们是否可以把pos改为int类型呢？答案是不建议，因为我们要与库里的类型一样。

直接把pos强制转为int,运行测试提供。

void string::insert(size_t pos, char ch)
{if (_size == _capacity)//空间不够，就扩容{size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2;reserve(newcapacity);}size_t end = _size;while (end >= (int)pos){_str[end + 1] = _str[end];--end;}_str[pos] = ch;//把字符放进去++_size;
}

那么我们可以不强转可以修改吗？可以

这里最根本的问题点在于end >= pos,只要是无符号遇到>=绝对是坑，无符号最小就是0，无法停止，非常扯淡。

这里我们去掉= ，把end的位置变为_size + 1,把前一个往后挪。

代码修改为：

void string::insert(size_t pos, char ch)
{if (_size == _capacity)//空间不够，就扩容{size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2;reserve(newcapacity);}size_t end = _size + 1;while (end > pos){_str[end] = _str[end - 1];--end;}_str[pos] = ch;//把字符放进去++_size;
}

测试通过

insert()插入一个字符串

void insert(size_t pos,const char* str);//插入字符串

首先pos不能越界，检查是否需要扩容，

把xxx拷贝进去，不能用strcpy，它携带了\0，我们可以用strncpy或memcpy，这里我们采用memcpy

代码：

void string::insert(size_t pos, const char* str)
{ assert(pos <= _size);size_t len = strlen(str);if (_size + len > _capacity){reserve(_size + len);}int end = _size;while (end >= pos){_str[end + len] = _str[end];--end;}memcpy(_str + pos, str, len);_size += len;}

测试通过

这是我们在0出插入，还是会遇到之前的问题

我们只需要把pos强制类型转化为int即可。

如果我们不想用这种方式，我们把=去掉，把前一个往后挪，

到pos + len依旧需要挪动，可以写成end>=pos+len

void string::insert(size_t pos, const char* str)
{ assert(pos <= _size);size_t len = strlen(str);if (_size + len > _capacity){reserve(_size + len);}/*int end = _size;while (end >=(int) pos){_str[end + len] = _str[end];--end;}*/size_t end = _size + len;//len插入字符串长度while (end > pos + len - 1){_str[end] = _str[end - len];--end;}memcpy(_str + pos, str, len);_size += len;}

erase()

void erase(size_t pos, size_t len = npos);//pos开始删除len个字符

代码：第一种情况，删除的长度大于pos后的长度，直接全部删除；第二种情况，直接把不删除的字符覆盖在要删除的字符上。

void string::erase(size_t pos = 0, size_t len = npos)
{assert(pos < _size);if (len == npos || len >= _size - pos)//删除的字符大于pos后的字符{_str[pos] = '\0';_size = pos;}else{strcpy(_str + pos, _str + pos + len);_size -= len; }}

find()

查找一个字符

size_t string::find(char ch, size_t pos = 0)
{for (size_t i = 0; i < _size; i++){if (_str[i] == ch){return i;}}return npos;
}

查找一个子串

size_t string::find(const char* sub, size_t pos = 0)//从pos位置开始查找
{const char* p = strstr(_str + pos, sub);//在_str 种匹配sub子串，，返回对应位置指针return p - _str;//指针相减获取下标
}

测试通过

运算符重载 = 

看下面代码，s1赋值拷贝给s2，s3赋值给s1，下面程序有没有问题呢？

void test5()
{yx::string s1("hello world");yx::string s2(s1);cout << s1.c_str() << endl;cout << s2.c_str() << endl;yx::string s3("yyyy");s1 = s3; // s3赋值给s1cout << s1.c_str() << endl;cout << s3.c_str() << endl;
}

当然是有问题的，当我们没有运算符重载=时，编译器会默认提供一个版本，会执行浅拷贝，当 s2 被创建为 s1 的副本时，s2 实际上可能仅仅是指向 s1 所指向的字符串常量的另一个指针。这意味着，如果改变 s2 所指向的内容，s1 的内容也会随之改变。所以需要我们实现深拷贝版本。

修正：

string& string::operator=(const string& s)
{if (this != &s){char* tmp = new char[s._capacity + 1];strcpy(tmp, s._str);delete[] _str;_str = tmp;_size = s._size;_capacity = s._capacity;}
}

重新开一个空间tmp，把需要拷贝的字符串拷贝进去，然后释放旧空间，把new的空间给给原空间

而且为了避免自己给自己赋值，需要再套一个判断 this ！= &s

优化写法：

s1 = s3，s是s3的别名

	string& string::operator=(const string& s){if (this != &s){string tmp(s._str);this->swap(tmp);}return *this;}

s3拷贝给s1，设置一个临时变量tmp，s3拷贝构造tmp，然后再交换s1和tmp的空间。

而且tmp是个局部对象，出了作用域会析构，免去了释放空间这一步

最简化的写法：

s1 = s3

string& operator=(string tmp);string& string::operator=(string tmp)
{swap(tmp);return *this;
}

和上面最大的区别在于没有引用，s3拷贝构造tmp，然后s1和tmp交换，和上面的道理一样，tmp是临时对象，出了作用域自动销毁，效率并没有提示，只是简化了代码

swap()

如果我们swap一下s1 和 s2呢？库里的swap能否帮我们完成任务呢？答案是可以的，因为他是模板，但是它的代价非常大，

a 拷贝给 c，b 赋值给 a，c赋值给b，都会开空间，拷贝数据，传值传参代价都非常大。

自己实现：

void string::swap(string& s)
{std::swap(_str, s._str);//交换char*指针，size capacitystd::swap(_size, s._size);std::swap(_capacity, s._capacity);
}

通过命名空间，来使用库里的swap，如果不写std，swap就会调用自己，而且这里面交换的都是内置类型

strsub()

从pos位置开始，取len个字符的子串

代码实现：

string string::substr(size_t pos, size_t len)
{if (len > _size - pos)//如果len大于pos后面的长度，有多少取多少{string sub(_str + pos);//_str（开始的指针 ） + pos 从pos位置开始取，然后构造一个子串返回return sub;}else{string sub;sub.reserve(len);//扩容for (size_t i = 0;i< len ;i++){sub += _str[pos + i];}return sub;}
}

运算符重载 < > <= >= == !=

bool string::operator<(const string& s) const //比较大小
{return strcmp(_str, s._str) < 0;
}
bool string::operator>(const string& s) const
{return !(*this <= s);
}
bool string::operator<=(const string& s) const
{return *this < s || *this == s;
}
bool string::operator>=(const string& s) const
{return !(*this < s);
}
bool string::operator==(const string& s) const
{return strcmp(_str, s._str);
}
bool string::operator!=(const string& s) const
{!(*this == s);
}

其实这里写两个，然后取反复用就可以。

流插入和流提取operator<< >> 

istream& operator>>(istream& is, string& str)// is - cin
{char ch = is.get();is >> ch;while (ch != ' ' || ch != '\n')//不等于空格或换行{str += ch;//在io流里提取一个一个的char += 到str里char ch = is.get();}return is;
}
ostream& operator<<(ostream& os, const string& str)//os - cout
{for (size_t i = 0; i < str.size(); i++){os << str[i];//一个一个插入}return os;
}

流插入和流提取的运算符重载不能写成成员函数，且不一定写成友元。

cin是不能获取空格的，而scanf可以 当输入 y 空格 y 时， 写两个cin ，两个cin都会获得y，而忽略空格。

clear()

void string::clear() //请调当前的数据
{_str[0] = '\0';_size = 0;
}