【C++/STL】:string类底层的模拟实现

avatar
作者
筋斗云
阅读量:0

目录

引言

点击跳转到文章【string类的基本使用】
上一篇文章已经对string类进行了简单的介绍,大家只要能够正常使用即可。

这篇文章主要是对string类的一些重点接口函数进行模拟实现。本文依然采用多文件的方式,string.h放类的声明,string.cpp放成员函数的定义

string.h

#pragma once  #include <iostream> #include <assert.h> #include <stdbool.h>  using namespace std;  //定义一个叫做bit的命名空间,隔离C++库里的string类  namespace bit { 	 class string 	 { 	 public: 		 //typedef实现二次封装 		 //由于string类是连续的空间,所以可以定义为原生指针 		 typedef char* iterator;  		 //const迭代器,指针指向的内容不能修改 		 typedef const char* const_iterator;  		 //实现迭代器,一定要实现为begin 和end 		 //迭代器屏蔽了底层细节,提供了一种简单通用的访问容器的方式 		 iterator begin(); 		 iterator end();  		 const_iterator begin()const; 		 const_iterator end()const;  		// string();//无参构造 		 	    //有参与无参构造用全缺省进行合并,在声明处给缺省值 		 string(const char* str = "");//传参构造 		 //析构函数 		 ~string(); 		 //拷贝构造 		 string(const string& s);  		 //赋值运算重载(传统) 		 //string& operator=(const string& s);  		 //赋值运算重载(现代) 		 string& operator=(string tmp);   		 const char* c_str() const;  		 //用下标的方式遍历字符串 		 size_t size()const; 		 char& operator[](size_t pos); 		 const char& operator[](size_t pos)const;  		 //用于扩容,一般不缩容 		 void reserve(size_t n);  		 void push_back(char ch);//尾插一个字符 		 void append(const char* str);//尾插字符串  		 //用运算符重载实现尾插 		 string& operator+=(char ch); 		 string& operator+=(const char* str);  		 //在指定位置插入 字符或是字符串 		 void insert(size_t pos, char ch); 		 void insert(size_t pos, const char* str);  		 //在指定位置删除长度为len 		 void erase(size_t pos = 0, size_t len = npos);  		 //从pos位置开始找字符或是字符串 		 size_t find(char ch, size_t pos =0); 		 size_t find(const char* str, size_t pos = 0);  		 //交换函数 		 void swap(string& s);  		 //从pos位置找一个子串 		 string substr(size_t pos = 0, size_t len = npos);  		 //字符串的比较 		 bool operator<(const string& s)const; 		 bool operator>(const string& s)const; 		 bool operator<=(const string& s)const; 		 bool operator>=(const string& s)const; 		 bool operator==(const string& s)const; 		 bool operator!=(const string& s)const;  		 //把当前数据清除,但是不清空间 		 void clear();  	 private: 	 	 //这里的缺省值时给现代写法的构造函数的 		 char* _str = nullptr; 		 size_t _size = 0;//有效数据个数,指向最后一个有效数据的下一个位置\0 		 size_t _capacity = 0;//容量  		 //特例:静态成员变量只有无符号整形才可以在声明时给缺省值 		 //const static size_t npos = -1;//ok  		 //const static double d = 2.2;//err  		 const static size_t npos; 	 };  	 //流插入,流提取  	 //不适合写成成员函数,涉及第一个参数的位置问题 	 istream& operator>> (istream& is, string& str); 	 ostream& operator<< (ostream& os, const string& str); } 

1,构造函数

为了避免多次strlen的计算,并且符合声明的顺序,只把_size放在初始化列表,其余放在函数体中。

string::string(const char* str) 	:_size(strlen(str)) {     //_str = nullptr;//err 防止对空指针的解引用      	_str = new char[_size + 1];//多开一个是给\0的 	_capacity = _size; 	strcpy(_str, str);//把初始化内容拷贝进空间 } 

2,析构函数

string::~string() { 	delete[] _str;//析构销毁资源 	_str = nullptr;//置空 	_size = _capacity = 0;//置0 } 

3,取出字符串的地址

const char* string::c_str()const { 	return _str;//返回字符串的首地址,用于打印数据 } 

4,计算有效数据个数

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

5,[ ]运算符重载

4.1 [ ]运算符重载有两种类型,可读可写的和可读的(const修饰)。

4.2 模拟[ ]运算符重载的几个问题:
(1) 引用返回的作用:一是减少拷贝,二是修改返回对象。
(2) 为什么可以用引用返回:_str[i]出了作用域还在,因为_str开辟在堆上,它返回的是堆上的一个字符的引用别名。
(3) 重载的底层也是用assert断言的,只要下标越界直接终止报错。

//_str是new出来的,出了这个函数不会销毁,可以用引用返回 char& string::operator[](size_t pos) { 	assert(pos < _size);//防止越界 	return _str[pos]; }  const char& string::operator[](size_t pos)const { 	assert(pos < _size);//防止越界 	return _str[pos]; } 

6,简单迭代器

6.1 迭代器也有有两种类型,可读可写的和可读的(const修饰)。根据声明可知,这里的迭代器可以暂时简单的理解为类似指针的东西

6.2 这里直接利用用原生指针进行实现的原因是:string类底层的物理结构的连续的。

6.3 为什么要用typedef,而不是直接用char*呢?
一是不同编译器底层实现迭代器的方式是不同的。
二是可以实现二次封装,屏蔽了底层的实现细节,统一了上层访问容器的方式(用begin和end)。

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

7,预开空间(扩容)

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

8,尾插一个字符

8.1 先判断容量是否足够,再插入。
8.2 注意\0的处理。

//尾插一个字符 void string::push_back(char ch) { 	if (_size == _capacity) 	{ 		//先计算容量,2倍增 		size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2; 		//再扩容 		reserve(newcapacity); 	}  	_str[_size] = ch;//覆盖\0的位置 	_str[_size + 1] = '\0';//补上\0 	++_size; } 

9,尾插一个字符串

9.1 先判断容量是否足够,再插入。
9.2 插入字符串时strcatstrcpy均可以实现。但是strcat的底层需要遍历找到\0再进行拼接,最后自动补上\0,效率不高;所以推荐使用strcpy。

//尾插字符串 void string::append(const char* str) { 	size_t len = strlen(str); 	if (_size + len > _capacity) 	{ 		reserve(_size + len); 	}  	//strcat:从\0的位置开始追加,最后自动补上\0 	//strcat(_str, str);  	strcpy(_str + _size, str); 	_size += len; } 

10,+=运算符重载

它的功能也是用来尾插字符或是字符串的,而且它比push_back和append使用的更广泛。

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

11,在pos位置插入字符/字符串

11.1 在pos位置插入字符

错误示范:
原因:当pos为0,即头插时,程序崩溃!因为end是无符号整形,减到0再减后会变成整形最大值(40多亿),造成死循环。

猜想解决方法:
只把end的类型改为int,也不行。因为当一个操作符两边的操作数类型不一样时,会产生隐式类型转换,比如有符号与无符号,有符号会隐式转换成无符号类型。

void string::insert(size_t pos, char ch) { 	assert(pos <= _size);//避免下标越界  	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; } 

解决方法1:
把end的类型改为int,end指向最后一位有效位的下一位,把pos也强转为int类型。

//在指定位置插入  void string::insert(size_t pos, char ch) { 	assert(pos <= _size);//避免下标越界  	if (_size == _capacity) 	{ 		size_t newcapacity = _capacity == 0 ? 4 : _capacity * 2; 		reserve(newcapacity); 	}  	int end = _size; 	while (end >= (int)pos) 	{ 		_str[end + 1] = _str[end]; 		--end; 	}  	_str[pos] = ch; 	++_size; } 

解决方法2:
让end指向\0的下一位。

//在指定位置插入  void string::insert(size_t pos, char ch) { 	assert(pos <= _size);//避免下标越界  	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; } 

11.2 尾插一个字符串

遇到的问题与上面的相同。

void string::insert(size_t pos, const char* str) { 	assert(pos <= _size);//避免下标越界  	size_t len = strlen(str); 	if (_size + len > _capacity) 	{ 		reserve(_size + len); 	} 	 	//方式1 	/*int end = _size; 	while (end >= (int)pos) 	{ 		_str[end + len] = _str[end]; 		end--; 	}*/ 	 	//方式2 	size_t end = _size + len; 	while (end > pos+len-1) 	{ 		_str[end] = _str[end - 1]; 		end--; 	}  	memcpy(_str + pos, str, len); 	_size += len; } 

12,从pos位置开始删除长度为len的字符串

注意:
1.此处在声明中两个形参的缺省值,size_t pos = 0, size_t len = npos
npos是const类型的静态成员变量,npos = -1,表示无符号整形的最大值(40多亿)。

2.声明和定义分离时,静态成员变量的初始化。当是const修饰的size_t类型的静态变量时,是可以在声明时给缺省值的!这是个特例! 但是一般不这样,声明和定义分离时,只要在.cpp中初始化即可。

void string::erase(size_t pos, size_t len ) { 	assert(pos  < _size); 	 	//当len大于前面的字符个数时,有多少删多少 	if (pos+len >= _size) 	{ 		_str[pos] = '\0'; 		_size = pos; 	} 	else 	{ 		strcpy(_str + pos, _str + pos + len); 		_size -= len; 	} } 

13,从pos位置开始查找字符/字符串

13.1 查找字符

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

13.2 查找字符串

size_t string::find(const char* str, size_t pos) { 	//strstr:str存在时返回所在位置的指针 	const char* p = strstr(_str + pos, str); 	 	return p - _str; } 

14,拷贝构造(传统)

当我们不显示实现深拷贝时,使用编译器默认的浅拷贝有两个危害:
14.1 s1和s2指向同一块空间,出了作用域时调用两次析构函数,造成程序崩溃。
14.2 修改一个,另外一个也会修改。

//要用深拷贝进行拷贝构造 //s2(s1);把s1拷贝给s2,*this是s2,s是s1的别名 string::string(const string& s) { 	//开一个和要拷贝的一样大小的空间 	_str = new char[s._capacity + 1]; 	strcpy(_str, s._str);//把数据拷贝进新空间 	_size = s._size; 	_capacity = s._capacity; } 

15,=赋值拷贝(传统)

开新空间,拷贝数据,释放原空间,改变指针指向。

//s1 = s3;//s1是*this,s是s3的别名 string& string::operator=(const string& s) { 	//避免自己给自己赋值 	if (this != &s) 	{ 	     //多开一个空间给\0 		char* tmp = new char[s._capacity + 1]; 		strcpy(tmp, s._str); 		delete[] _str; 		_str = tmp; 		_size = s._size; 		_capacity = s._capacity;  		return *this; 	} } 

16,交换函数swap

//s1.swap(s3) void string::swap(string& s) { 	//调用库中的swap函数,交换内置类型 	//不直接交换数据,而是交换两块空间的指针 	std::swap(_str, s._str); 	std::swap(_size, s._size); 	std::swap(_capacity, s._capacity); } 

17,从pos位置开始取len个字符的串

复用了前面的构造函数和+=运算符。

string string::substr(size_t pos, size_t len) { 	//len大于pos后面剩余的字符,有多少取多少 	if (len > _size - pos) 	{ 		string sub(_str + pos);//直接构造子串返回 		return sub; 	} 	else 	{ 		string sub; 		sub.reserve(len); 		for (size_t i = 0; i < len; i++) 		{ 			sub += _str[pos + i]; 		} 		return sub; 	} } 

18. 字符串的比较

只要实现>运算符(或<运算符)和==运算符,其他运算符直接复用即可。

 	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) == 0; 	}  	bool string::operator!=(const string& s)const 	{ 		return !(*this == s); 	} 

19,清除函数clear

清除当前对象里的内容,影响的是_size,不影响_capacity。

void string::clear() { 	_str[0] = '\0'; 	_size = 0; } 

20,流插入,流提取

(1) 不适合写成成员函数,涉及第一个参数的位置问题。
(2) 根据声明可知,这两个函数并没有重载成友元函数,而是放在类外。
(3) 在日期类中写成友元是为了访问私有成员,这里可以不写成友元函数,不访问私有成员,直接访问公有成员。

20.1 流插入

ostream& operator<< (ostream& os, const string& str) { 	for (size_t i = 0; i < str.size(); i++) 	{ 		os << str[i]; 	}  	return os; } 

20.2 流提取

注意:
(1) C语言中的scanf:%c时可以拿到空格,拿不到换行,遇到换行直接忽略; %s时两个都拿不到,遇到直接忽略。

C++中的cin:拿不到空格和换行,遇到直接忽略。

在C++中不能用scanf,因为C++的流和C语言的流缓冲区不同。

(2) 为了避免一次性输入够多导致频繁扩容,开辟一个局部数组buff(类似缓冲区),先把字符存在buff中,到达一定数量后再存入str。

istream& operator>> (istream& is, string& str) { 	str.clear();  	char buff[128]; 	int i = 0; 	char ch = is.get(); 	 	while (ch != ' ' && ch != '\n') 	{ 		buff[i++] = ch; 		//0 - 126 		if (i == 127) 		{ 			buff[i] = '\0'; 			str += buff; 			i = 0; 		}  		ch = is.get(); 	}  	//如果buff没有装满 	if (i != 0) 	{ 		buff[i] = '\0';  		str += buff; 	}  	return is; } 

21,拷贝构造和赋值拷贝的现代写法(重点)

21.1 拷贝构造

复用构造函数,构造一个tmp,再用tmp对象和this交换。此时如果不在声明时给缺省值,刚开始s2是随机值,tmp和s2交换后,tmp就是随机值,tmp出了函数会调用析构函数,此时程序可能会崩溃,所以好给缺省值。

string::string(const string& s) { 	//写法1:常用 	string tmp(s._str); 	swap(tmp);  	//写法2: 	//string tmp(s._str); 	//std::swap(_str, tmp._str); 	//std::swap(_size, tmp._size); 	//std::swap(_capacity, tmp._capacity); } 

21.2 赋值拷贝

写法1:

string& string::operator=(const string& s) { 	//避免自己给自己赋值 	if (this != &s) 	{ 		string tmp(s._str); 		swap(tmp); 	} 	return *this; } 

写法2:常用

这里使用传值传参

(1) 传值传参会进行拷贝构造,s1会拷贝一份给临时变量tmp,tmp里的东西就是s3想要的,再让tmp与s3交换

(2) 当tmp 的生命周期结束时,刚好又会调用析构函数,把原来s3中的东西清理掉

//s3 = s1    //这里的传参不能用引用, string& string::operator=(string tmp) { 	swap(tmp);//一行搞定赋值拷贝 	return *this; } 

    广告一刻

    为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!