网站icp备案需要多久,都有什么网站,乐清装修网站哪个好,华硕固件做网站6文章目录 前言string的成员变量成员函数构造函数拷贝构造赋值重载 模拟实现string各种接口print迭代器普通迭代器const迭代器 string比较大小push_backinsert 和 eraseinserterase reserve和resizereserveresize swapfindcout和cincoutcin 前言
今天要讲string的底层实现… 文章目录 前言string的成员变量成员函数构造函数拷贝构造赋值重载 模拟实现string各种接口print迭代器普通迭代器const迭代器 string比较大小push_backinsert 和 eraseinserterase reserve和resizereserveresize swapfindcout和cincoutcin 前言
今天要讲string的底层实现通过自己来实现string,我们对string的理解才能更加的深刻。 我们对string其实既熟悉又陌生熟悉sting其实就是字符串陌生是在于管理字符串这样一个类。
string的成员变量
namespace but
{class string{private:char* _str;size_t _capaicty;size_t _size;};
}我们为了避免自己定义的string于库里面的傻傻分不清这里我们自己用了一个命名空间把自己写的string封装起来。
成员函数
构造函数
namespace but
{class string{public:string():_str(nullptr),_capaicty(0),_size(0){}string(const char* str):_str(str),_capaicty(strlen(str)),_size(strlen(str))//容量不包括\0{}private:const char* _str;//加上const,防止写构造函数时权限放大编译不通过size_t _capaicty;size_t _size;};
}简简单单写了上面的构造函数其实这里面存在两个问题下面我们通过一些使用来看一下。 第一个问题。
写个c_str,思考一下为什么程序会崩?
const char* c_str()
{return _str;
}string s1;
string s2(hello world)
cout s1.c_str() endl;//上述代码都是写在类里面
cout s2.c_str() endl;流插入是自动识别类型它识别出const char* 然后去解引用然后遇到‘\0’结束这样空指针的问题就暴露出来了。
继续看第二个问题
const char operator[](size_t pos)//按照之前写的构造函数必须加上const
{assert(pos _size);return _str[pos];
}这里面有个很坑的问题我们是呆会是要修改pos位置的字符并且如果空间不够还需要扩容比如那这里就变得非常矛盾。
这是什么原因呢
string s2(hello world)s2在常量区无法修改扩容也无法扩。
如何解决这两个问题呢 其实根源还是在于初始化列表我们大多数情况下都是推荐把所有成员变量直接放到初始化列表初始化这里比较特殊。 其次我们要想修改pos位置的字符还想扩容在初始化的时候空间就不能直接赋值过去最好new出来。
那经过修改之后我们的代码
namespace but
{class string{public:string():_str(new char[1]),//要解决第一个问题这里就不能是空_capacity(0),_size(0){_str[0] \0;}string(const char* str):_capacity(strlen(str)){_size _capacity;//没有必要重复用strlen,strlen是o(N)的接口_str new char[_capacity 1];//扩容的时候应该1包括\0strcpy(_str, str);}~string(){delete[] _str;_str nullptr;_capacity _size 0;}const char* c_str(){return _str;}char operator[](size_t pos){assert(pos _size);return _str[pos];}private:char* _str;//加上const,防止写构造函数时权限放大编译不通过size_t _capacity;size_t _size;};void test_string1(){string s1;string s2(hello world);cout s1.c_str() endl;cout s2.c_str() endl;s2[0];cout s2.c_str() endl;}
}至此把上面的问题都解决了。
拷贝构造还可以继续优化一下优化成只有一个全缺省的构造函数。
//string(const char* str nullptr) //不可以等下strlen解引用会崩
//string(const char* str \0)//不可以类型不匹配
//string(const char* str \0)//可以
string(const char* str )//可以:_size(strlen(str))
{_capaicty _size 0 ? 3 : _size;_str new char[_capaicty 1];strcpy(_str, str);
}拷贝构造
void test_string2()
{string s2(hello world);string s3(s2);cout s2.c_str() endl;cout s3.c_str() endl;
}我们之前说过拷贝构造是默认成员函数我们不写编译器会自动生成一个对自定义类型不做处理对内置类型做值拷贝或浅拷贝。那我们看一下自动生成的拷贝构造。 这个是经典的值拷贝或浅拷贝问题我们之前也讲过接下来既然有一个具体的场景就用调试带大家看一下。 看两个地址完全一摸一样。 这样会带来两个问题。 1.一个修改影响另外一个。 2.同一块空间会析构两次。 那我们需要自己写一个深拷贝的拷贝构造怎么写呢
//拷贝构造也有初始化列表
string(const string s):_size(s._size), _capaicty(s._capaicty){_str new char[s._capaicty 1];strcpy(_str, s._str);}赋值重载
赋值重载和拷贝构造也一摸一样我们不写的话编译器自动生成的会出问题。 写成这样那就考虑的太不全面了
string operator(const string s)
{_size s._size;_capacity s._capacity;_str new char[s._capacity 1];strcpy(_str, s._str);return *this;
}我们知道拷贝构造是一块已经存在的空间给另一块还没存在的空间。 而赋值重载是两块都已经存在的空间所以赋值重载还需要从空间的角度去分析问题。
从空间大小考虑总共有三种情况
但是存在一个问题如果s3空间特别大s1又非常小把s1直接赋值过去s3就会浪费很多空间所以比较好的方式就是再开一块空间。 我们库里面的string实现不会这么麻烦直接把旧的空间释放掉开一块一样大的空间。
还要处理自己给自己赋值以免造成不必要的麻烦。
string operator(const string s){if (this ! s){//这种写法稍微不好一点//抛异常的时候会把s1给破坏掉/*delete[] _str;_str new char[s._capaicty 1];strcpy(_str, s._str);_size s._size;_capaicty s._capaicty;*/char* tmp new char[s._capaicty 1];strcpy(tmp, s._str);delete[] _str;_str tmp;_size s._size;_capaicty s._capaicty;}
模拟实现string各种接口
print
这里为什么报错
这也涉及到我们之前讲过的。** cosnt成员变量不能调用非const成员函数这样会权限放大。** 紧接着这里报错又怎么解决 这说明我们需要两个【】,一个是给const对象调用的不允许修改。 一个是给普通对象调用的可以修改。它们构成函数重载因为它们函数名相同参数不一样。 虽然普通对象也可以调用const成员函数但是编译器非常聪明他会调用最匹配的哪个。
迭代器
遍历的方式我们还可以用迭代器这里我们再写一个迭代器
普通迭代器 要实现一个迭代器其实不难。
我们支持了迭代器其实也就支持了范围for
for (auto ch : s1)
{cout ch ;
}const迭代器
const迭代器能不能修改 可以修改只是指向的内容不能修改。
string::const_iterator it s1.begin();
while (it ! s1.end())
{//*it x;//不能修改只能读不能改it;
}
cout endl;反向迭代器这里先不讲后面再讲要用一个适配器来实现。
string比较大小
怎样比较大小 比较ascll值一个一个比。
// 不修改成员变量数据的函数最好都加上constbool operator(const string s) const{return strcmp(_str, s._str) 0;}bool operator(const string s) const{return strcmp(_str, s._str) 0;}bool operator(const string s) const{//return *this s || *this s;return *this s || s *this;}bool operator(const string s) const{return !(*this s);}bool operator(const string s) const{return !(*this s);}bool operator!(const string s) const{return !(*this s);}push_back
空间不够扩容的时候不能用realloc那就和c交叉了容易出问题。
void push_back(char ch)
{if (_size 1 _capaicty){reserve(_capaicty * 2);}_str[_size] ch;_size;_str[_size] \0;
}void append(const char* str)
{size_t len strlen(str);if (_sizelen _capaicty){reserve(_size len);}strcpy(_str _size, str);//strcat(_str, str);//为什么不用strcat?strcat很挫自己要去找\0\0就在size位置能不用就不用_size len;
}我们喜欢使用的还是直接复用push_back;
string operator(char ch)
{push_back(ch);return *this;
}string operator(const char* str)
{append(str);return *this;
}凡是你的扩容析构上代码崩了一般都是内存问题。 insert 和 erase
问个小小的问题静态成员变量能不能给缺省值 不能因为缺省值是给初始化列表用的。静态列表不是在初始列表初始化的。 它属于整个类不是属于某个对象。
insert
插入字符 insert有个巨坑给大家看一下下面的代码 程序运行结果。
调试的时候发现这样扯淡了。 因为end的类型是size_t;
void insert(size_t pos, char ch)
{assert(pos _size);if (_size 1 _capacity){reserve(2 * _capacity);}//int end_size;//这样也不行会发生类型转换一般有符号转化为无符号。//改pos也不好,pos的类型一般规定都是size_tsize_t end _size;//while(endpos(int))//强转也不推荐//while (end pos)//{// _str[end 1] _str[end];// --end;//}size_t end _size 1;while (end pos){_str[end] _str[end-1];--end;}_str[pos] ch;_size;
}我们最好的解决思路巧妙的避开了小于0
插入字符串
一定要画图不然很容易出错。
string insert(size_t pos, const char* str)
{assert(pos _size);size_t len strlen(str);if (_size len _capacity){reserve(_size len);}// 挪动数据size_t end _size len;while (end pos len - 1)//强烈不建议用大于等于{_str[end] _str[end - len];--end;}//这个比较简单完美避开了循环结束条件的难题/*size_t end _size;for (size_t i 0; i _size 1; i){_str[end len] _str[end];--end;}*/// 拷贝插入strncpy(_str pos, str, len);_size len;return *this;}erase
erase比较简单从pos位置删除数据就可以了。
我们浅浅分析一下所有的情况
erase也是不考虑缩容的。
string erase(size_t pos, size_t len npos)
{assert(pos _size);if (len npos || pos len _size){_str[pos] \0;_size pos;}else{strcpy(_str pos, _str pos len);//不需要考虑覆盖的问题所以可以直接用strcpy_size - len;}return *this;}
白盒测试把三种情况都验证一遍
reserve和resize
reserve
看一下我们之前写的扩容有什么问题
它是没有考虑缩容的。继续看这样子就报错了。 为什么报错呢 strcp的时候越界了。
简单修改一下代码就变成这样了。
void reserve(size_t n)
{if (n _capacity){char* tmp new char[n 1];strcpy(tmp, _str);delete[] _str;_str tmp;_capacity n;}
}resize
resize缩容吗 不缩容。缩荣的代价还是很大的首先是异地缩先开另一块空间然后把数据拷贝过去接着把之前的空间释放掉。 待会插入数据空间不够又要扩容这样就很麻烦。
接下来实现resize我们得分情况讨论以及明白resize功能上的一些细节。
void resize(size_t n, char ch \0)
{if (n _size){// 删除数据--保留前n个_size n;_str[_size] \0;}else if (n _size){if (n _capacity){reserve(n);}//如果调用系统的接口我们可以用memsetsize_t i _size;while (i n){_str[i] ch;i;}_size n;_str[_size] \0;}
}swap
我们实现 一下swap,其实就知道库里面的swap和类里面的效率差距有多大
//swap(s1, s2);
//s1.swap(s2);
void swap(string s)
{std::swap(_str, s._str);std::swap(_capacity, s._capacity);std::swap(_size, s._size);
}find
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;}}cout和cin
现在我有一个问题cout和cin必须实现成友元函数这句话对不对 不对我们可以写一些函数来访问私有成员变量。
cout
首先我们实现cout, 它不是成员函数。
能不能直接这样搞 我们之前说过c_str()和cout是有区别的它们最大的区别就是c_str()打印时是遇到\0终止cout是根据size来打印的。
ostream operator(ostream out, const string s)
{for (auto ch : s){out ch;}return out;
}cin 这样为什么不行 调试一下就知道了空格和换行不会进入缓冲区。为什么 它会认为你输入的时候多个字符之间的间隔。
我们可以改成这样 仔细看一下上面的代码功能是完善了但还有什么弊端。 这是没有把之前的数据清理掉。
还有一个问题有个流插入的数据比较长那它会影响效率那有没有什么方法能解决这个问题 开小了不够开多了浪费。这里有一个参考方式。 相当于换成字符串可以这样理解。
istream operator(istream in, string s)
{s.clear();char ch in.get();char buff[128];size_t i 0;while (ch ! ch ! \n){buff[i] ch;if (i 127){buff[127] \0;s buff;i 0;}ch in.get();}//防止还有数据没有进去if (i ! 0){buff[i] \0;s buff;}return in;
}
