标题:【C++ :: STL】手撕 STL _string
@水墨不写bug
(图片来源于网络)
C++标准模板库(STL)中的string是一个可变长的字符序列,它提供了一系列操作字符串的方法和功能。
本篇文章,我们将模拟实现STL的string类的部分功能,以增强对STL的熟练度,了解STL容器的工作原理,积累项目经验,也为将来自主实现和改造容器奠定坚实的基础。
STL的string类是一个模板,而我们为了方便实现,以达到练习的目的,我们暂时先实现一个成员变量为(下图示)的string类。
char* _str;
size_t _size;//字符串长度,不加上\0
size_t _capacity;
C++ STL的string类提供了以下常用的成员函数和接口:
构造函数和赋值操作函数接口:
- 默认构造函数:创建一个空字符串。
- 带string参数的构造函数:将一个string对象复制到另一个string对象中。
- 带字符数组参数的构造函数:将字符数组转换为string对象。
- 带整数参数的构造函数:将整数转换为字符串。
- 赋值操作符:用另一个string对象、字符数组或字符来赋值。
访问字符串内容相关函数接口:
- at():返回指定位置的字符。
- operator[]:返回指定位置的字符。
- front():返回第一个字符。
- back():返回最后一个字符。
- c_str():返回一个以空字符结尾的字符数组。
修改字符串内容接口:
- insert():在指定位置插入字符、字符串或字符数组。
- erase():删除指定位置的字符。
- replace():替换指定位置的字符串或字符。
- append():在字符串末尾添加字符、字符串或字符数组。
- clear():清空字符串。
字符串操作接口:
- size() 或 length():返回字符串的长度。
- empty():判断字符串是否为空。
- find():查找指定字符串或字符的位置。
- substr():返回指定位置和长度的子字符串。
- compare():比较两个字符串
(具体用法在上一篇讲解:【Cpp::STL】标准模板库_ string详解)
(一)头文件
我们在C语言阶段实现声明和定义分离的时候,只是单一的把函数的定义放在.c(源)文件,把函数的声明,头文件的包含,宏定义等放在.h(头)文件。
但是,在C++,不仅要遵守以上的规则,由于类的出现,需要域作用限定符(::)来限定方位;由于成员的访问权限的出现,需要考虑访问权限的问题;此外不同类型的成员的定义的位置也有讲究,比如静态成员尽量不要直接定义在头文件中,因为这会引发 多次包含多文件 在链接时的 头文件内的对象的重定义问题。
本文根据STL标准模板库的功能,给出头文件,包括string类的定义,众多成员函数,部分非成员函数(流插入,流提取的重载),并在后半节详细讲解各个函数的实现思路。
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include<iostream> #include<cstring> #include<cassert> using namespace std; namespace ddsm { class string { friend ostream& operator<<(ostream& out, const string& s1); public: //迭代器 typedef char* iterator; typedef const char* const_iterator; iterator begin(); const_iterator begin() const; iterator end(); const_iterator end() const; //传参构造,默认构造,给默认值为空串,巧妙 string(const char* str = ""); string(const string& s);//copy constructor //string& operator=(const string& s);传统写法 string& operator=(const char* s); string& operator=(string s);//现代写法 //析构 ~string(); //C类型字符串 const char* c_str() const; //保留 void reserve(int n); string& push_back(const char ch);//尾插字符 string& append(const char* str);//尾插字符串 string& operator+=(char ch); string& operator+=(const char* str); string& insert(size_t pos, const char ch); string& insert(size_t pos, const char* str); //缺省值代表最一般的情况 string& erase(size_t pos = 0,size_t len = npos); //找一个字符 size_t find(const char ch, size_t pos = 0); //找一个子串 size_t find(const char* str, size_t pos = 0); void swap(string& s); string substr(size_t pos = 0,size_t len = npos); string& clear(); private: char* _str; size_t _size;//字符串长度,不加上\0 size_t _capacity; //特例,const静态整形对象可声明定义和一,但是可能造成链接时的错误 static size_t npos; }; istream& operator>>(istream& in, string& s); };
(二)string类的功能实现
(1)默认成员函数
i,构造函数
我们知道,构造函数的作用是在对象实例化时初始化对象,对于string类对象,含有三个基本成员变量:
char* _str; size_t _size;//字符串长度,不加上\0 size_t _capacity;
经过分析,我们得知在构造函数内部,需要申请动态的堆区空间给_str;需要根据_str的长度变化来动态更新_size;同时根据申请的动态空间的长度来更新_capacity。
于是,我们理所当然的想到这样写构造函数:
string::string(const char* str = "") // 缺省参数为一个空字符串,如果不传参,空字符串就是一个单独的'\0' :_size(strlen(str)) ,_capacity(strlen(str)) { _str = new char[_size + 1]; strcpy(_str, str); }
但是,这种简单易懂的写法也暴露出了弊端:多次无意义的重复调用strlen,这会造成额外的消耗。于是,为了减少strlen的调用次数,我们考虑这样修改:
string::string(const char* str) :_size(strlen(str)) ,_capacity(_size) { _str = new char[_size + 1]; strcpy(_str, str); }
这样修改虽然解决了strlen重复无意义调用的问题,但是也带来了新的问题:
程序稳定性下降的问题:
¥¥我们知道:初始化列表的初始化顺序是成员函数在类中的声明顺序:按照此例:
char* _str; size_t _size;//字符串长度,不加上\0 size_t _capacity;
先初始化_size,再初始化_capacity;在这种背景下,如果代码有一些微小的改变,或许就会造成意想不到的问题。
如果改变成员变量的顺序,那么初始化列表就会按照不同的顺序初始化。具体来说,如果_capacity在_size之前,初始化列表就会先初始化_capacity:
char* _str; size_t _capacity; size_t _size;//字符串长度,不加上\0
这时_size还没有初始化,是随机值,那么就造成了_capacity为随机值的问题。
解决这个问题其实很简单,将对_capacity的初始化放入函数体:
string::string(const char* str) //strlen较低效,调用一次用size记录返回值 //size/capacity不包含\0,但是其需要存储 :_size(strlen(str)) { _str = new char[_size + 1]; _capacity = _size; strcpy(_str, str); }
这样就确定了是先初始化_size,再初始化_capacity。¥¥
(将声明和定义分离,需要将缺省参数放在声明处,同时函数名之前需要加上域作用限定符,表示这个函数在你实现的string类里面声明过。)
ii,析构函数
析构函数的作用是:清理资源。
由于比较简单,这里直接给出实现:
//析构 string::~string() { if(_str) delete[] _str; _size = _capacity = 0; _str = nullptr; }
(函数名之前需要加上域作用限定符,表示这个函数在你实现的string类里面声明过。)
iii,拷贝构造
拷贝构造,完成创建对象时的初始化。
一般情况下,我们会这样写:
//拷贝构造 string::string(const string& s) { char* tem = new char[s._capacity+1];//多开一个,存储'\0' strcpy(tem, s._str); delete[] _str;//销毁原空间 _str = tem; _size = s._size; _capacity = s._capacity; }
但是,其实有更简单的写法:
void string::swap(string& s) { //调用模板swap交换内置类型,损失不大 std::swap(_str, s._str); std::swap(_capacity, s._capacity); std::swap(_size, s._size); } //拷贝构造的现代写法 string::string(const string& s) :_str(nullptr) { string tem(s._str); swap(tem); }
仔细分析,我们其实在无形之中让构造函数给我们“打工”了:
string tem(s._str);
就是用拷贝对象的字符串来构造一个tem对象,而这个tem对象就是我们需要的,所以我们实现一个swap函数,将*this与tem完全交换,同时tem在出作用域时也会自动析构,同样也达到了拷贝构造的目的。
iv,赋值重载
赋值重载:实现对象之间的赋值。
我们一般会这样实现:
//赋值重载 string& string::operator=(const char* s) { int len = strlen(s); char* tem = new char[len + 1]; strcpy(tem, s); delete[] _str; _str = tem; _size = _capacity = len; return *this; }
但是,同样也有更简单的写法:
void string::swap(string& s) { //调用模板swap交换内置类型,损失不大 std::swap(_str, s._str); std::swap(_capacity, s._capacity); std::swap(_size, s._size); } //赋值重载的现代写法 string& string::operator=(string tem) { //自动调用拷贝构造 swap(tem); //出作用域自动完成析构 return *this; }
在无形之中,我们让拷贝构造为我们“打工”。
我们通过传值传参,拷贝构造一个临时对象tem,这个tem就是我们需要的,所以完全交换*this就得到了构造的对象,同时tem出作用域也会自动析构。
(2)迭代器
对于迭代器,本质上是一个指针,也可以是一个类(对指针的封装),在这里,我们不妨用指针来作为迭代器:
//声明: typedef char* iterator; typedef const char* const_iterator; iterator begin(); const_iterator begin() const; iterator end(); const_iterator end() const;
//定义 string::iterator string::begin() { return _str; } string::const_iterator string::begin() const { return _str; } string::iterator string::end() { return _str + _size; } string::const_iterator string::end() const { return _str + _size; }
const迭代器用于const对象调用;普通迭代器用于普通迭代器调用。
普通迭代器可读可写,const迭代器只可读不可写。
(3)容量和长度
i.reserve()
改变string的容量,若要求值n大于现在的容量,则容量扩大到n;若要求值小于等于现有容量,则改变容量。
reserve对于size没有影响,不会改变string的内容。
实现如下:
//保留指定容量,容量只增不减 void string::reserve(int n) { //要求保留的大于现有容量,需要扩容 if (n > _capacity) { char* tem = new char[n + 1]; // 申请新空间完毕,转移数据 strcpy(tem, _str); delete[] _str; _str = tem; _capacity = n; //reserve不改变size } }
ii,resize()
//resize()不改变capacity,可能改变size void string::resize(int size,int ch) //size为设定值,_size为现有值 { if (size < _size) { _size = size; _str[size] = '\0'; } else if (size > _size) { if (size > _capacity) { reserve(size); } int i = _size; while (i != size) { _str[i++] = '\0'; } _size = size; _str[_size] = '\0'; } }
如果设定值小于现有值,减小_size,相当于截断_str;
如果设定值等于现有值,不做处理;
如果设定值大于现有值,有三种情况:
size <_capacity: 不扩容,并在[ _size,size)之间补0;
size == _capacity: 不扩容,并在[ _size,size)之间补0;
size > _capzcity: 扩容,并在[ _size,size)之间补0;
(4)元素访问
i,operator[]
下标的随机访问:
//声明 char& operator[](size_t pos); const char& operator[](size_t pos) const;
//定义 char& string::operator[](size_t pos) { assert(pos >= 0 && pos < _size); return _str[pos]; } const char& string::operator[](size_t pos) const { assert(pos >= 0 && pos < _size); return _str[pos]; }
对于at,front,back可以复用operator[]来实现。
(5)修改方式
i,push_back()
实现尾插字符,实现如下:
//尾插字符,由于是一个一个插入,扩容不能太频繁,所以采用二倍扩容 string& string::push_back(const char ch) { if (_size == _capacity) //不一定需要扩容,若长度等于容量,再次插入需要扩容 { int Newcapacity = _capacity == 0 ? 4 : 2 * _capacity; reserve(Newcapacity); } //扩容完毕,尾插字符 _str[_size++] = ch; _str[_size] = '\0'; return *this; }
这里使用了一个扩容技巧,就是二倍扩容。
ii,append()
追加,这里简化为追加一段字符串。
//尾插字符串,直接reserve到指定长度字符串 string& string::append(const char* str) { int len = strlen(str); if (len + _size > _capacity) { reserve(len + _size);//不改变size } //扩容完毕 strcpy(_str + _size, str); _size += len; return *this; }
首先要先保存原来的len,这样如果需要扩容,在扩容完毕之后,只需更新_size为原_size+=len即可。
否则,如果不保存len,在需要扩容的情况下,就会出现问题了:
##
()
##
iii,operator+=复用上两函数即可
尾插一个字符
string& string::operator+=(char ch) { push_back(ch); return *this; }
尾插一个字符串
string& string::operator+=(const char* str) { append(str); return *this; }
iv,insert()
在任意位置插入一个字符
//插入一个字符 //用push_back逻辑来扩容 string& string::insert(size_t pos, const char ch) { assert(pos >= 0 && pos <= _size); if (_size == _capacity) { int Newcapacity = _capacity == 0 ? 4 : 2 * _capacity; reserve(Newcapacity);//不改变size } int end = _size+1; //细节问题,int与size_t参与比较, //int隐式类型转化为size_t //size_t(-1)会变成很大的整数 while(end>pos) { _str[end] = _str[end-1]; --end; } _str[pos] = ch; _size += 1; return *this; }
在任意位置插入一个字符串//插入一个字符串 //用reserve逻辑扩容 string& string::insert(size_t pos, const char* str) { assert(pos >= 0 && pos <= _size); int len = strlen(str); if (len + _size > _capacity) { reserve(len+_size); } int end = _size + len; while (end>pos+len-1) { _str[end] = _str[end - len]; --end; } memmove(_str + pos, str, len); _size += len; return *this; }
v,erase()
在任意位置处删除长度为len的字符串:
string& string::erase(size_t pos, size_t len) //两种情况;删除部分string,pos之后全删 { assert(pos >= 0 && pos <= _size); if ((len == npos) ||(pos + len >= _size))//全删的情况 { _str[pos] = '\0'; _size = pos; } else //删除部分string { int end = pos + len; while (_str[end]!='\0') { _str[end - len] = _str[end]; ++end; } _str[end-len] = '\0'; } return *this; }
(6)串操作
i,find()
找字符
size_t string::find(const char ch, size_t pos) { for (size_t i = pos; i < _size; ++i) { if (_str[i] == ch) { return i; } } return npos; }
找字符串
用到了strstr():字符串匹配函数。
size_t string::find(const char* str, size_t pos) { char* ret = strstr(_str, str); return (size_t)(ret - _str); }
ii,c_str()
返回C类型的字符串:
const char* string::c_str() const { return _str; }
iii,substr()
得到字符串的子串:
string string::substr(size_t pos, size_t len) { assert(pos >= 0 && pos <= _size); if ((len == npos) || (pos + len >= _size)) { string sub(_str + pos); return sub; } else { string sub; sub.reserve(len); for (size_t i = 0; i < len; ++i) { sub._str[i] = _str[pos + i]; } sub._str[len] = '\0'; sub._size =sub._capacity = len; return sub; } }
(7)成员常量
//特例,const静态整形对象可声明定义和一,但是可能造成链接时的错误 const static size_t npos = -1;
无符号整数size_t(-1)是一个很大的整数。
(8)流插入和流提取
i,operator<<()
ostream& operator<<(ostream& out, const string& s) { for (size_t i = 0; i < s._size; ++i) { cout << s._str[i]; } cout << endl; return out; }
ii,operator>>()
cin的get()函数可以提取空白字符和‘\n’,这也是循环逻辑结束的条件。
//流提取改进,用buf临时数组,防止string频繁扩容 istream& operator>>(istream& in,string& s) { s.clear(); char buff[128] = { 0 }; char ch = in.get(); int i = 0; while(ch != ' ' && ch != '\n') { buff[i++] = ch; ch = in.get(); if (i == 127) { buff[i] = '\0'; s += buff; i = 0; } } buff[i] = '\0'; if (i != 0) { s += buff; } return in; }
整体使用了用临时栈区数组的方式来减少扩容次数,提高效率。
完~
未经作者同意禁止转载