【C++】深度解析:用 C++ 模拟实现 string 类,探索其底层实现细节
P_M_P 2024-06-12 13:05:02 阅读 99
目录
了解string类
string的内存管理
VS下string的结构
g++下string的结构
string的模拟实现
string的构造函数
浅拷贝
深拷贝
string的遍历
重载 [] 下标访问
迭代器访问
reserve
resize
增删查改
push_back()
append和+=
insert和erase
find
substr
swap
流插入和流提取
getline
string其他基本功能
⭐了解string类
1. 字符串是表示字符序列的类 2. 标准的字符串类提供了对此类对象的支持,其接口类似于标准字符容器的接口,但添加了专门用于操作单字节字符字符串的设计特性。 3. string 类是使用 char( 即作为它的字符类型,使用它的默认 char_traits 和分配器类型 ( 关于模板的更多信息,请参阅basic_string) 。 4. string 类是 basic_string 模板类的一个实例,它使用 char 来实例化 basic_string 模板类,并用 char_traits和allocator 作为 basic_string 的默认参数 ( 根于更多的模板信息请参考 basic_string) 。 5. 注意,这个类独立于所使用的编码来处理字节 : 如果用来处理多字节或变长字符 ( 如 UTF-8) 的序列,这个类的所有成员( 如长度或大小 ) 以及它的迭代器,将仍然按照字节 ( 而不是实际编码的字符 ) 来操作。 总结: 1. string 是表示字符串的字符串类 2. 该类的接口与常规容器的接口基本相同,再添加了一些专门用来操作 string 的常规操作。 3. string 在底层实际是: basic_string 模板类的别名, typedef basic_string<char, char_traits, allocator> string; 4. 不能操作多字节或者变长字符的序列。 在 使用 string 类时,必须包含 #include 头文件以及 using namespace std ;⭐string的内存管理
✨VS下string的结构
string总共占28个字节 ,内部结构稍微复杂一点,先是 有一个联合体,联合体用来定义 string 中字 符串的存储空间 : 当字符串长度小于16时,使用内部固定的字符数组来存放 当字符串长度大于等于16时,从堆上开辟空间union _Bxty{ // storage for small buffer or pointer to larger one value_type _Buf[_BUF_SIZE]; pointer _Ptr; char _Alias[_BUF_SIZE]; // to permit aliasing} _Bx;
大多数情况下字符串的长度都小于16,当string对象创建好之后,内部已经有了16个字符数组的固定空间,不需要通过堆创建,效率高。 还有 一个 size_t 字段保存字符串长度,一个 size_t 字段保存从堆上开辟空间总的容量 还 有一个指针做一些其他事情。 故总共占16+4+4+4=28个字节。
✨g++下string的结构
g++ 下, string 是通过写时拷贝实现的, string对象总共占4个字节 ,内部只包含了一个指针,该指 针将来指向一块堆空间,内部包含了如下字段: 空间总大小 字符串有效长度 引用计数 指向堆空间的指针,用来存储字符串。struct _Rep_base{ size_type _M_length; size_type _M_capacity; _Atomic_word _M_refcount;};
⭐string的模拟实现
private:char* _str = nullptr;size_t _size = 0;size_t _capacity = 0;
✨string的构造函数
// 为了和标准库区分,此处使用Stringclass String{public: /*String() :_str(new char[1]) {*_str = '\0';} */ //String(const char* str = "\0") 错误示范 //String(const char* str = nullptr) 错误示范 String(const char* str = "")//默认包含 \0 { // 构造String类对象时,如果传递nullptr指针,可以认为程序非法 if (nullptr == str) { assert(false); return; } _str = new char[strlen(str) + 1]; strcpy(_str, str); } ~String() { if (_str) { delete[] _str; _str = nullptr; } }private: char* _str;};// 测试void TestString(){ String s1("hello bit!!!"); String s2(s1);}
上述 String 类没有显式定义其拷贝构造函数与赋值运算符重载,此时编译器会合成默认的,当用 s1 构 造 s2 时,编译器会调用默认的拷贝构造。最终导致的问题是, s1 、 s2 共用同一块内存空间,在释放时同一块 空间被释放多次而引起程序崩溃 ,这种拷贝方式,称为 浅拷贝 。
📖浅拷贝
浅拷贝:也称位拷贝,编译器只是将对象中的值拷贝过来 。如果 对象中管理资源 ,最后就会 导致多个对象共 享同一份资源,当一个对象销毁时就会将该资源释放掉,而此时另一些对象不知道该资源已经被释放,以为 还有效,所以当继续对资源进项操作时,就会发生发生了访问违规。举个例子,如果一个家庭里面有两个孩子,但是父母只给他们买了一个玩具,如果两个孩子都愿意玩这一个玩具,那就相安无事,否则就会鸡飞狗跳。 要解决这个问题,就可以直接给他们一人买一个玩具,这样各自安逸。 所以,要想解决浅拷贝的问题,可以使用深拷贝的方法, 每个对象都有一份独立的资源,不要和其他对象共享 。
📖深拷贝
如果一个类中涉及到资源的管理,其拷贝构造函数、赋值运算符重载以及析构函数必须要显式给出。一般情况都是按照深拷贝方式提供。
✨string的遍历
📖重载 [] 下标访问
char& operator[](size_t pos)//可读可写{assert(pos < _size);return _str[pos];}//重载一个constconst char& operator[](size_t pos) const//只读{assert(pos < _size);return _str[pos];}
首先访问之前需要判断pos是否再合法访问之内,即小于等于size,然后直接返回字符串数组中对应的元素。由于存在const对象和非const对象,所以需要写两个重载版本。
📖迭代器访问
//迭代器typedef char* iterator;typedef const char* const_iterator;iterator begin(){return _str;}iterator end(){return _str + _size;}const_iterator begin()const{return _str;}const_iterator end()const{return _str + _size;}
其实底层就是指针,所以直接返回对应的地址就可以了。
✨reserve
void reserve(size_t n){if (n > _capacity){char* tmp = new char[n+1];strcpy(tmp, _str);//释放旧空间,指向新空间delete[] _str;_str = tmp;//修改capacity,不用修改size_capacity = n;}}
reserve是提前预留部分空间,它接收的空间大小不能比本来就有的容量小,如果n合法,则需要将原数组从旧空间移向一块更大的新空间,并释放掉旧空间。
✨resize
void resize(size_t n,char ch='\0'){if (n <= _size){_str[n] = '\0';_size = n;}else{reserve(n);for (int i = _size; i < n; i++){_str[i] = ch;}_str[n] = '\0';_size = n;}}
resize是设置字符串的大小,如果n比字符串原来的大小小,则会发生截断;如果比原来的大小大,则会reserve一块n大小的空间。
✨增删查改
📖push_back()
void push_back(char ch){//扩容2倍if (_size == _capacity){reserve(_capacity==0 ? 4 : 2 * _capacity);}_str[_size] = ch;_size++;_str[_size] = '\0';}
直接尾插就可以,需要先判断空间是否足够,最后更新size的大小。
📖append和+=
void append(const char* str){//扩容//根据追加的字符串的长度扩容size_t len = strlen(str);if (_size + len > _capacity){reserve(_size + len);}strcpy(_str + _size, str);_size += len;}// += string& operator+=(char ch){push_back(ch);return *this;} string& operator+=(const char* str){append(str);return *this;}string& operator+=(const string s){append(s._str);return *this;}
append和+=都是在字符串的尾部追加字符或者字符串,需要先判断容量是否足够,不够则需要扩容, 根据追加的字符串的长度扩容。
📖insert和erase
对于insert,0位置的插入可能产生问题,end是int类型,pos是size_t类型,end变成-1与pos比较时会发生整型提升,所以pos需要先进行强制类型转换;也可以使用另一种解决方法,将end的初始值赋值为size+1,每次使用这种方法后移字符串 _str[end] = _str[end - 1];,则end最后不会变成-1。
//在pos之前插入//插入字符void insert(size_t pos,char ch){assert(pos <= _size);if (_size == _capacity){reserve(_capacity == 0 ? 4 : 2 * _capacity);}//int end = _size;0位置的插入可能产生问题,end变成-1与pos比较时会发生整型提升,所以pos需要先进行强制类型转换//while (end >= (int)pos)//{//_str[end+1] = _str[end];//end--;//}//第二种解决方法int end = _size + 1;while (end > pos){_str[end] = _str[end - 1];end--;}_str[pos] = ch;_size++;}//在pos之前插入//插入字符串void insert(size_t pos,const char* str){assert(pos <= _size);int len = strlen(str);if (_size +len > _capacity){reserve(_size + len+1);}//int end = _size;0位置的插入可能产生问题,end变成-1与pos比较时会发生整型提升,所以pos需要先进行强制类型转换//while (end >= (int)pos)//{//_str[end+1] = _str[end];//end--;//}//第二种解决方法//在pos之前插入int end = _size + len;//pos 1 2 endwhile (end > pos+len-1){_str[end] = _str[end - len];end--;}strncpy(_str + pos,str,len);_size+=len;}//释放删除void erase(size_t pos, size_t len = npos){assert(pos < _size);// pos+len 存在溢出风险//if (len == npos || pos + len >= _size)if (len == npos ||len >= _size-pos){_str[pos] = '\0';_size = pos;}else{strcpy(_str + pos, _str + pos + len);_size -= len;}}
对于erase,需要根据传递的参数的大小来判断需要删除多少个字符。
📖find
//寻找匹配size_t find(char ch,size_t pos = 0) const{for (size_t i = pos; i < _size; i++){if (_str[i] == ch)return i;}return npos;}size_t find(const char* sub, size_t pos = 0) const{assert(pos <= _size);const char* p=strstr(_str+pos, sub);if (p){return p - _str;}elsereturn npos;}
实现方法比较简单,就是普通的暴力查找。
📖substr
截取子串,需要注意len的大小。
string substr(size_t pos = 0, size_t len = npos){string sub;if (len == npos|| len >= _size - pos){for (size_t i = pos; i < _size; i++){sub += _str[i];}}else{for (size_t i = pos; i < pos + len; i++){sub += _str[i];}}return sub;}
✨swap
众所周知,C++算法库里面存在swap这个函数模板,但是为什么string内部自己也有一个swap呢?
如果用std::swap交换两个string对象,将会发生1次构造和2次赋值,也就是三次深拷贝;
而string内部的swap仅仅只交换成员,代价较小。
//交换void swap(string& s){std::swap(_str, s._str);std::swap(_size, s._size);std::swap(_capacity, s._capacity);}
为了符合算法库里面swap的用法,可以再将swap重载成全局函数。
void swap(string& x, string& y){x.swap(y);}
✨ 流插入和流提取
//重载成全局是为了调整顺序//流插入ostream& operator<<(ostream& out, const string& s){//这里不需要写成友元函数,因为不需要直接访问私有成员for (auto ch:s){cout << ch;}return out;}//流提取//C++ 流插入,流提取可以支持自定义类型使用istream& operator>>(istream& in, string& s){s.clear();char ch;char buff[128];//in >> ch;//默认把空格当作分隔符、换行,不读取ch = in.get();//C++中读取一个字符size_t i = 0;while (ch != ' ' && ch != '\n'){buff[i++] = ch;if (i == 127){buff[127] = '\0';s += buff;i = 0;}//s += ch;//重复+=,会重复扩容,消耗较大ch = in.get();}if (i > 0){buff[i] = '\0';s += buff;}return in;}
因为在这里不需要直接访问类的私有成员,所以流插入和流提取可以不用重载成string类的友元函数。
对于流提取,如果频繁的尾插,会造成频繁扩容。而且C++的扩容和C语言的扩容不一样,C++使用new不能原地扩容,只能异地扩容,异地扩容就会导致新空间的开辟、数据的拷贝、旧空间释放。为了防止频繁扩容,我们可以创建一个可以存储128字节的数组,作为缓冲,如果数组满了,则将这个字符数组追加到s上,如果没慢,但是遇到空格或者换行了也需要追加。
另外由于C++的标准输入流默认把空格和换行当作分隔符,不读取,所以这里要用in.get()来接收字符。
✨getline
基本上可以直接复用流提取的代码。
//读取空格istream& getline(istream& in, string& s){s.clear();char ch;//in >> ch;//默认把空格当作分隔符、换行,不读取ch = in.get();//C++中读取一个字符while ( ch != '\n'){s += ch;ch = in.get();}return in;}
✨string其他基本功能
size_t size() const{return _size;}size_t capacity() const{return _capacity;} void clear(){_size = 0;_str[_size] = '\0';}
重载运算符,要写成全局的函数。
bool operator==(const string& a ,const string& b){int ret = strcmp(a.c_str(), b.c_str());return ret == 0;}bool operator<(const string& a, const string& b){int ret = strcmp(a.c_str(), b.c_str());return ret < 0;}bool operator<=(const string& s1, const string& s2){return (s1 < s2) || (s1 == s2);}bool operator>(const string& s1, const string& s2){return !(s1 <= s2);}bool operator>=(const string& s1, const string& s2){return !(s1 < s2);}bool operator!=(const string& s1, const string& s2){return !(s1 == s2);}
____________________
⭐感谢你的阅读,希望本文能够对你有所帮助。如果你喜欢我的内容,记得点赞关注收藏我的博客,我会继续分享更多的内容。⭐
声明
本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。