string模拟实现:
上一篇博客,我们对String类有了一个基本的认识,本篇博客我们来从0~1去模拟实现一个String类,当然我们实现的都是一些常用的接口。
❓我们这里定义了一个string类型,然后STL标准库里面也有string,两个名字一样我们分不清楚怎么办呢?
- 为了跟库的string区分开,我们可以定义一下命名空间
namespace st
{class string{public:private:char* _str;size_t _size;size_t _capacity;};
}
有了类的成员变量,我们需要对这些成员变量进行初始化和释放,我们来写一下string的构造函数和析构函数
首先来观察一下string类的成员变量,string类有三个成员变量_str(字符指针)、__size和 _capacity。
_size和 _capacity都比较容易初始化,直接置为0就好。
_str作为字符指针比较麻烦,具体的原因往下看!
1深浅拷贝:
我们来写一下我们自己string类的构造和析构函数
class string{public:string(const char* str):_str(str),_size(str._size), _capacity(str._capacity){}private:char* _str;size_t _size;size_t _capacity; }
❓上面这种构造函数我们调用的时候是否能编译通过呢?
💡这是不行的,因为你初始化这个 string 时,比如我们通常情况会这么写:
string s1("hello world");
❓我们为string的初始化提供构造函数,这里为什么报错呢?
💡原因是这里权限放大了,str是一个const char *类型,而_str只是一个char * 类型,这里赋值过来会直接权限放大报错了,同理可得:常量字符串是不可以直接赋值给char *类型的(
char*b="bcd";
)解决方法将_str也设为const char*就好啦
- 🔥
const char*
类型这里是只允许读,不允许写的
但是我们写的String类需要有增删查改的功能,因此上述的写法不可以的
我们可以这样写:
string(const char* str): _str(new char[strlen(str) + 1]) { // 开strlen大小的空间strcpy(_str, str);
}
- 🔥strlen函数是计算字符串的有效长度,是不含
\0
的!!!!!
我们这里strlen+1是为了给字符串的\0
预先留一个位置的
析构函数:
~string(){delete[] _str;_str = nullptr;_size = _capacity = 0;}
拷贝构造函数:
void TestString()
{String s1("hello xiaolu!!!");String s2(s1);
}
我们来运行一下,通过s1来拷贝构造s2
🚩 运行结果如下:
❓这里显示strcpy是unsafe(不安全的)的,这是为什么呢?如何解决呢?(当前完整代码如下)
#include<string.h>
namespace xiaolu
{class string{public:string(const char* str): _str(new char[strlen(str) + 1]){ // 开strlen大小的空间strcpy(_str, str);}~string(){delete[] _str;_str = nullptr;_size = _capacity = 0;}private:char* _str;size_t _size;size_t _capacity;};void TestString(){string s1("hello xiaolu!!!");string s2(s1);}
}
int main()
{xiaolu::TestString();return 0;
}
🔑详细解析:
首先我们先来了解一下strcpy函数,strcpy函数是一个值拷贝函数,她将hello xiaolu的字符一个一个按字节拷贝到s1
这里其实不是strcpy函数的问题,而是
当string s2(s1);
这里是发生拷贝构造,而这里我没有写拷贝构造,因此编译器调用的就是默认拷贝构造,也就是浅拷贝,因为_str是char*类型,它发生值拷贝将地址直接拷贝过去,因此s1和s2指向同一块地址
解决方法:我们这里写一个拷贝构造,来进行深拷贝!
因为这里涉及到深浅拷贝的问题,因此我们来探讨一下深浅拷贝:
深浅拷贝的区别:
简单来说:
- 🔥浅拷贝就是编译器自己执行值拷贝(按照字节,一个一个字节拷贝)
举个例子
当发生拷贝的是指针,编译器会将指针的4个字节依次拷贝另外一个变量,这样会导致两个变量指向一个地址,而当delete的时候,这一块地址会被释放两次地址,就会报错了!!!
当一个类有动态内存的时候,类的拷贝有构造函数、赋值运算符重载以及析构函数基本上不可以用浅拷贝,会出现上面的问题,要用到深拷贝。
- 🔥深拷贝:深拷贝就是让编译器按照我们的想法进行拷贝或者赋值,一般来说是(开一块一样大的空间,再把数据拷贝下来,指向我自己开的空间)
我们自己需要写一个string的深拷贝:
string(const string& str):_size(str._size), _capacity(str._capacity){_str = new char[str._capacity + 1];strcpy(_str, str._str);}
void TestString(){string s1("hello xiaolu!!!");string s2;s2 = s1;}
这里的我们没有提供默认的构造函数,当我们需要创建一个新的空白的string对象的时候,就会报错,我们可以给构造函数提供缺省值
string(const char* str = ""):_size(strlen(str)){_capacity = _size == 0 ? 3 : _size;_str = new char[_capacity + 1];strcpy(_str, str);}
深拷贝的常用情景,不止经常在拷贝构造,在赋值下也很经常!
赋值的深拷贝:
赋值的深拷贝思路跟拷贝构造一样是否可以呢?他们都是拿一个已有的变量来定义一个新的变量
string& operator=(const string& str){delete[] _str; _str = new char[strlen(str._str) + 1]; strcpy(_str, str._str); }
显然这里报错了,我们来分析一下:
🔑详细解析:
这里我们先释放了原来的_str,然后new了一块新的对象,再strcpy
首先我们new了一块新的空间,new失败了会怎么样?
会抛异常!抛异常!抛异常!无关紧要
失败了没问题,也不会走到 strcpy,但问题是我们已经把原有的空间释放掉了,
神不知鬼不觉地,走到析构那里二次释放可能会炸,所以我们得解决这个问题!
我们将开辟空间的步骤提前,然后释放向后移动
string& operator=(const string& str){if (&str == this)return *this;//防止自己给自己赋值char* tmp = new char[str._capacity + 1];//防止开辟失败strcpy(tmp, str._str);delete[] this->_str;_str = tmp;_size = str._size;_capacity = str._capacity;return *this;}
再提供一种相对现代一点的写法:
String& operator=(String s){swap(_str, s._str);return *this;}
写时拷贝
在我们经常使用的STL标准模板库中的string类,也是一个具有写时才拷贝技术的类。C++曾在性能问题上被广泛地质疑和指责过,为了提高性能,STL中的许多类都采用了Copy-On-Write技术。这种偷懒的行为的确使使用STL的程序有着比较高要性能。
Copy-On-Write一定使用了“引用计数”,是的,必然有一个变量类似于RefCnt。当第一个类构造时,string的构造函数会根据传入的参数从堆上分配内存,当有其它类需要这块内存时,这个计数为自动累加,当有类析构时,这个计数会减一,直到最后一个类析构时,此时的RefCnt为1或是0,此时,程序才会真正的Free这块从堆上分配的内存。
是的,引用计数就是string类中写时才拷贝的原理!
2.string类常用接口的实现:
size()和capacity()
size_t size()const
{return _size;
}
size_t capacity()const
{return _capacity;
}
clear函数
对于 clear() 而言就是去清除当前对象的数据,我们直接在_str[0]
这个位置放上一个\0即可,并且再去修改一下它的_size = 0即可
- 不过这个接口来说我们不要去加【const成员】,因为修改了其成员变量
_size
void clear()
{_str[0] = '\0';_size = 0;
}
c_str函数
返回一个指向数组的指针,该数组包含一个以空字符结尾的字符序列(即C-string),表示string对象的当前值。
这个数组包含的字符序列与string对象的值相同,另外还包含一个以空字符(‘\0’)结尾的字符串。
- 🔥c_str返回的是一个const char*的数组指针,只读不写
const char* c_str()const
{return _str;
}
❓调试到这个地方就直接崩了,不应该直接打印null吗?
如果我们换成std中的string,不会报错,说明我们初始化存在问题
namespace st
{class string{public:string():_str(nullptr), _size(0), _capacity(0){}string(const char* str):_str(str), _size(strlen(str)), _capacity(strlen(str)){}const char* c_str(){return _str;}private:const char* _str;size_t _size;size_t _capacity;};void test_string1(){string s1;string s2("hello world");std::cout << s1.c_str() << std::endl;std::cout << s2.c_str() << std::endl;}
}
int main()
{st::test_string1();return 0;
}
2.1全缺省构造函数
我们还要考虑不带参数的构造函数,如下:
void test_string1() {string s1("hello world"); // 带参string s2; // 不带参
}
当我们要给一个空的字符串定义时,s2应该是‘\0’,我们可以直接在缺省值上设置
string(const char* str = ""):_size(strlen(str)){_capacity = _size == 0 ? 3 : _size;_str = new char[_capacity + 1];strcpy(_str, str);}
🔥这里值得注意的是缺省值,我们给了一个“”
🔑详细解析:
str是一个char*类型,正常情况下,我们会给缺省值为nullptr
string(const char* str = nullptr)
这里运行后会崩!!!
strlen是不会去检查空的,它是一直找到 \0为止的
也就相当于直接对这个字符串进行解引用了,这里的字符串又是空,所以会引发空指针问题。
所以我们这里给的是一个空的字符串 " ",常量字符串默认就带有 \0,这样就不会出问题:
string(const char* str = "")
❓为什么我们用new char[1]而不是直接用new char,都是一个啊为什么啊?
🔥为了跟有参构造那里匹配析构函数,这样就方便释放
string():_str(new char[1]), _size(0), _capacity(0){_str[0] = '\0';}string(const char* str):_size(strlen(str)){_capacity = _size;_str = new char[_capacity + 1];strcpy(_str, str);}
❓这里可以优化吗?
string(const char*str=nullptr) string(const char* str = '\0')
🔑详细解析:
这两个都不可以,不可以解引用空指针
string(const char* str = "\0")
这样是可以的,给常量字符串,但是没必要这样,可以下面这样
string(const char* str = "")
如果我们不写拷贝构造函数,默认生成了一个拷贝构造函数,会报错!
void test_string2(){string s1;string s2("hello world");string s3(s2);std::cout << s1.c_str() << std::endl;std::cout << s2.c_str() << std::endl;std::cout << s3.c_str() << std::endl;}
这里发生浅拷贝,同一块空间会被释放两次
string(const string& str):_size(str._size),_capacity(str._capacity){_str = new char[str._capacity+ 1];strcpy(_str, str._str);}
2.2拷贝构造函数
2.3operator[]的实现
❓[]重定向,这里有什么问题呢?
char& operator[](size_t pos){assert(pos < _size);return _str[pos];}
//成员变量
private:const char* _str;size_t _size;size_t _capacity;
普通对象可以调用,但是 const 对象呢?所以我们还要考虑一下 const 对象。
我们可能会修改pos位置的字符,也可能加字符,这里会报错,因为str为const char*类型
const char& operator[](size_t pos)const{assert(pos < _size);return _str[pos];}char& operator[](size_t pos)//构成函数重载{assert(pos < _size);return _str[pos];}
2.4operator=的实现及其必要性
赋值的话,不写拷贝构造的话也是值拷贝(浅拷贝)
s1 = s3;
下图拷贝构造分为三种:
第一种:s1的空间和s3的空间一样大
第二种:s1的空间比s3的空间大
第三种:s1的空间比s3的空间小
显然:这里第三种情况内存不够,要先释放防止内存泄漏,第二种是内存浪费,干脆全部都重新开空间就好了
string& operator=(const string& str){if (&str == this)return *this;//防止自己给自己赋值char*tmp = new char[str._capacity + 1];//防止开辟失败strcpy(tmp, str._str);delete[] this->_str;_str = tmp;_size = str._size;_capacity = str._capacity;return *this;}
2.5Print函数
这里权限放大了
const char& operator[](size_t pos)const{assert(pos < _size);return _str[pos];}size_t size()const {return _size;}
const函数,修饰this指针,但是这样另外一个地方又报错了
构成函数重载就可以解决问题了,各调用各的,这里调用第二个就可以了,this没有const修饰,并且返回类型没有const,就可以进行++等修改操作了
const char& operator[](size_t pos)const{assert(pos < _size);return _str[pos];}char& operator[](size_t pos)//构成函数重载{assert(pos < _size);return _str[pos];}
3.迭代器的实现
我们先来看看STL库中的string类的迭代器
3.1begin和end的实现
typedef char* iterator;iterator begin(){return _str;}iterator end(){//返回迭代器最后一个位置的下一个位置return _str + _size;}
3.2迭代器的扩展引用——范围for
for (auto ch : s1){std::cout << ch << " ";}std::cout << std::endl;
这里可以支持范围for,范围for的底层是迭代器实现的
🔥范围for遇上const类型的对象,会报错,因此要提供const迭代器
typedef const char* const_iterator;
const迭代器,自己可以修改,指向的对象不可以修改,有点像const指针
4.一些常用的运算符重载
bool operator>(const string&str){return strcmp(_str, str._str) > 0;}bool operator==(const string& str){return strcmp(_str, str._str) == 0;}bool operator>=(const string& str){return *this > str || *this == str;}bool operator<(const string& str){return !(*this >= str);}bool operator<=(const string& str){return !(*this > str);}
5.string类的增删查改
5.1reserve函数
reserve是一个增容函数
我们先来实现一下reserve函数,再来检验一下实用性
void reserve(size_t n){if (n > _capacity){char* tmp = new char[n + 1];strcpy(tmp, _str);delete[] _str;_str = tmp;_capacity = n;}}
5.2push_back函数
这是一个增加字符到字符串的函数
首先检查是否需要增容,如果需要就调用我们上面实现的 reserve 函数,
参数传递可以用三目操作符,防止容量是0的情况,0乘任何数都是0从而引发问题的情况。
然后在 \0 处插入要追加的字符 append_ch,然后 _size++ 并手动添加一个新的 \0 即可。
void push_back(char ch){if (_size + 1 > _capacity){reserve(_capacity * 2);}_str[_size] = ch;++_size;_str[_size] = '\0';}
5.3append函数
append函数是追加字符串的函数
void append(const char* str){size_t len = strlen(str);if (_size + len > _capacity){reserve(_size + len);}strcpy(_str + _size, str);_size += len;}
5.4 operator+= 的实现
比起push_back和append函数,我们更加喜欢用+=运算符来追加字符串或字符
string& operator+=(char ch){push_back(ch);return *this;}string& operator+=(const char* str){append(str);return *this;}
5.5insert函数
🔥如果npos是const可以在类内初始化,这种情况只能出现在整形的情况,double不可以
static const size_t npos=-1;
但是不推荐这样写,推荐老老实实写,这里语法有点冲突,但是不会报错
void insert(size_t pos, char ch){assert(pos <= _size);if (_size + 1 > _capacity){reserve(2 * _capacity);}size_t end = _size;//size_t是一个无符号整数while (end >= pos){_str[end + 1] = _str[end];--end;}_str[pos] = ch;++_size;}
🔑详细解析:
上面代码是错的,end是一个无符号整数,-1的话变为max-1了,这里是等号两边的类型不同,会发生整形提升,有符号会变成无符号的
string& insert(size_t pos, char ch){assert(pos <= _size);if (_size == _capacity){size_t newcapacity = _capacity == 0 ? 3 : 2 * _capacity;reserve(newcapacity);}//int cur = pos;size_t end = _size + 1;//size_t是一个无符号整数while (end > pos){_str[end] = _str[end - 1];--end;}_str[pos] = ch;++_size;return *this;}string& insert(size_t pos, const char* str){assert(pos <= _size);size_t len = strlen(str);if (_size + len > _capacity){size_t newcapacity = _capacity == 0 ? 3 : 2 * _capacity;reserve(newcapacity);}size_t str_cur = 0;//str的下标size_t end = _size + 1;return *this;}
5.6resize函数
n有三种情况
void resize(size_t n, char ch = '\0'){if (n <= _size){_size = n;_str[n] = '\0';}else {if (n > _capacity){reserve(n);}size_t i = _size;while (i < n){_str[i] = ch;++i;}_size = n;_str[n] = '\0';}}
5.7erase函数
erase的三种情况
string& erase(size_t pos, size_t len = npos){assert(pos < _size);if (pos + len >= _size || len == npos){_str[pos] = '\0';_size = pos;}else{strcpy(_str + pos, _str + pos + len);_size -= len;}return *this;}
5.8find函数
size_t find( char ch,size_t pos=0){assert(pos < _size);for (size_t i = pos; i < _size; ++i){if (_str[i] == ch)return i;}return npos;}size_t find(const char* str, size_t pos = 0){assert(pos < _size);char* p = strstr(_str + pos, str);if (p == nullptr){return npos;}else{return p - _str;}}
在这里插入代码片