STL中string类的实现(细节避坑)

发布时间:2022-10-16 15:00

C++中的string类 翻译过来就是字符串类型 但是它可不是一个平平无奇的字符串 它具有像线性表一样的增删查改的功能 会自动扩容 还支持迭代器遍历 功能可谓十分齐全 下面就来实现它

STL中string类的实现(细节避坑)_第1张图片

STL中string类的实现(细节避坑)_第2张图片

目录

一、构造函数

二、拷贝构造函数(传统写法和现代写法)

三、析构函数

四、按下标访问或修改

五、赋值操作(传统写法和现代写法)

六、尾插pushback

七、加等字符和加等字符串操作

八、扩容(reserve)

九、扩容并初始化(resize)

十、获取有效字符个数

十一、获取成员变量_str的函数c_str()

十二、插入数据的三种方法详解及相关细节(两种下标法 一种指针法)

十三、删除数据

十四、查找单个字符和子串

十五、简易迭代器遍历的实现

十六、类的直接比较

十七、类的直接输入输出

十八、标准库中getline简易的实现

补充、std::swap  和 string 自带的swap 的区别


类的结构:

类的结构包括三个成员变量 _str 、_size、_capacity 以及目录中的相关方法_str是字符指针指向一块用来存储字符串的空间 、_size是用来记录字符串的有效字符的个数、_capacity是用来记录当前空间可以存放多少个字符(容量)

一、构造函数

上面介绍了string 类的成员变量 那么构造函数就要对其进行初始化咯

实参传过来的必须是字符串,所以用字符指针接收,细节一点,就是用const修饰一下*str这样实参就不能在构造函数中被改变

然后就用strlen函数计算出传过来的字符串的长度,让该类中的成员变量(属性)_size和_capacity都等于该长度,然后再开辟出比容量大一的空间来存储我们要所要构造的字符串。最后一步就是把实参的字符串拷贝到我们新开辟的空间中;这一波操作下来就构造好了一个string对象,该对象(字符串)的内容,空间大小,长度都是和我们初始化时给的参数一样的了

关于这里为什么要开辟_capacity+1个字符的空间,也不一定非得是这样,只要逻辑上走得通都可以;这里我定义的_capacity 是可以存储有效字符的个数,不包括\0在内,但是字符串是以\0 作为结尾标志的,所以要多开辟一个字节的空间用来存放\0。

string(const char* str = "")
{
	_size = strlen(str);
	_capacity = _size;
	_str = new char[_capacity + 1];
	strcpy(_str, str);
}

二、拷贝构造函数(传统写法和现代写法)

拷贝构造函数就是拿一个已经创建了初始化好了的对象,去初始化新定义的对象。

注意:这里的拷贝够造必须是深拷贝(所有的内容相同,但是原来的和拷贝的是并不是同一个),不能是浅拷贝(光是值的拷贝)。(自身理解,若有考虑不周,还望体谅)

例如:

string a("hello world");//这是定义了一个对象a 并且拿“hello world”进行初始化

string b(a);//这种方式就是拷贝构造了 因为b是刚定义的对象
            // 拿以及定义且初始化的对象a对其进行初识化

但是这里的拷贝构造有两种写法 传统写法及现代写法

1.传统写法

思路:开辟空间,把用来构造的对象的数据一一复制给自己

以上面的例子为例说明:

string a("hello world");

string b(a);

这里的a初始化后其成员变量_str存的是“hello world” 、_size是11、_capacity是11。那么那a来构造b就是把b里的_str指向的空间放“hello world” 、_size等于a的_size、_capacity等于a的_capacity 

代码实现:

	//传统写法
		string(const string& str)
		{
			_str = new char[str._capacity + 1];
			strcpy(_str, str._str);
			_size = str._size;
			_capacity = str._capacity;
		}

2.现代写法

思路:与传统方法不同,传统方法是自己一一去实现拷贝,但是现代方法比较懒,它调写好的构造函数去帮自己构造出一个与传过来的对象一样的对象,在将构造出来的对象的数据和自己交换。

string(const string& str)
		:_str(nullptr)//必须初始化为空指针 否则后面调用析构函数会出错 野指针问题
		,_size(0)
		,_capacity(0)
		{
			string tmp(str._str);
			::swap(_str, tmp._str);//::表示调用的是全局域里的swap
			::swap(_size, tmp._size);
			::swap(_capacity, tmp._capacity);
			
		}

注:代码中的三个swap可以合并成一个函数简化代码(标准库里也是这样的):

void swap(string& str)
{
	::swap(_str,str._str);
	::swap(_size, str._size);
	::swap(_capacity, str._capacity);
}

//现代写法
string(const string& str)
	:_str(nullptr)
	,_size(0)
	,_capacity(0)
	{
		string tmp(str._str);
		/*::swap(_str, tmp._str);
		::swap(_size, tmp._size);
		::swap(_capacity, tmp._capacity);*/
		swap(tmp);
	}

这里需要注意的是自身的_str必须要初始化,不能是随机的!!!

因为利用构造函数构造出来的对象临时tmp出来作用域会自动销毁,那么就会去调用析构函数,但是这里我们把本身对象和临时对象的_str交换了,所以tmp调用析构函数的时候,就是去释放本身对象中_str指向的空间,那么如果本身对象的_str没有初始化指向的就是随机空间是野指针,释放野指针指向的空间是会报错的,所以必须初始化_str 为空指针,这样就不会出错了。

最后对两者进行对比一下:传统写法比较呆板,现代写法比较新颖,也比较简洁

三、析构函数

析构函数就比较简单了 ,释放掉_str指向的空间,并将_str置空即可

~string()
{
	delete[] _str;
	_str = nullptr;
}

四、按下标访问或修改

这里的按下标访问或者修改就是运算符重载的知识了

const char& operator[](size_t pos) const// 只能读 const对象的遍历专属 返回的引用也得是const引用
{
	assert(pos < _size);
	return _str[pos];
}

char& operator[](size_t pos)//可读可写
{
	assert(pos < _size);
	return _str[pos];
}

利用[]的运算符重载即可实现按下标访问或者修改

要分两种情况

一、访问的是非const对象

对于非const对象我们可读可写 那么就是返回的就是非const的引用类型

二、访问的是const对象

1、对于const对象,只能读,不能写,那么其[]的运算符重载函数就要用const修饰,const修饰的函数或者接口,修饰的是隐含的this指针指向的对象(*this),所指向对象的成员变量不可以通过该函数或接口改变,起到了保护作用。

2、既然是只读,而返回的是引用,但又不能通过返回的引用去改变对象成员变量,所以引用也要用const来修饰

五、赋值操作(传统写法和现代写法)

赋值操作可以实现可以拿对象赋值给对象

例如:

string a("hello world");
string b("nice");
a=b;//把对象b赋值给对象a

也分传统写法和现代写法,传统写法就是按部就班的走,现代写法就是借助构造函数构造对象在交换

一、传统写法

 //传统写法
string& operator=(const string& str)
{
	delete[] _str;
	_str = new char[str._size + 1];
	strcpy(_str, str._str);
	_size = str._size;
	_capacity = str._capacity;
}

思路:先释放原来的空间,在开辟新的空间,把str对象的_str里的数据拷贝到自己的_str里,再让_size和_capacity都与str对象的_size和_capacity相同

二、现代写法

string& operator=(string str)
{
	/*::swap(str._str, _str);
	::swap(str._capacity, _capacity);
	::swap(str._size, _size);*/
	swap(str);//把这三个swap合并成了一个成员函数简化了一下代码
	return *this;
}

思路:让形参是一个值而不是引用,那么传参的时候编译器就会调用上面的拷贝构造(深拷贝)去构造出与实参有着相同属性的形参,绕后再让自身对象的各个成员变量(属性)一一交换就好了,并且不用去释放空间,因为形参是局部变量出来定义域会自动调用析构函数清理数据,而我们经过交换把自己的各个属性都给了形参,形参就会帮我们调用析构函数自动清理原来的数据了,很棒!

六、尾插pushback

在字符串的尾部插入数据,可以是字符,也可以是字符串。

一、插入单个字符

既然是插入单个字符就是先判断容量够不够,不够就进行扩容,再把结束标准\0设置好,最后把字符插入即可。

string& pushback(char ch)
{
	if (_capacity == _size)
	{
	char* tmp = new char[_capacity == 0 ? 4 : _capacity * 2 + 1];
	strncpy(tmp, _str, _size + 1);
	delete[] _str;
	_str = tmp;
	_capacity *= 2;
	}//也可以复用reserve

	_str[_size] = ch;
	_str[_size + 1] = '\0';
	++_size;
	return *this;
}

下标问题:这里的_size表示的是有效字符的个数,因为小标从0开始,所以最后一个有效字符即使_str[size-1]了,那么_str[_size]就是\0了。我们插入字符就要把\0往后挪一个字符的位置就是上面的 _str[_size + 1] = '\0'; 然后在\0原来的位置放我们插入的字符_str[_size] = ch,最后更新_size。

注意:这里的扩容最好用strncpy 否则特定情况会出bug 下面会详细提到

二、插入字符串

实现一个尾插字符串的函数append(标准库也有的)

string& append(const char* str)
{
	assert(str);
	size_t len = _size + strlen(str);//先算出插入字符串的总长度,
//在与当前容量进行比较,判断是否需要扩容
	if (_capacity < len)
	{
		reserve(len);
	}
	strcpy(_str + _size, str);
	_size += strlen(str);
	return *this;
}

append函数的实现思路也是先判断是否需要扩容,然后把要插入的字符串拷贝到对象的_str中更新_size(插入数据的思路都是大同小异的)

七、加等字符和加等字符串操作

加等字符和加等字符串的操作是和上面的插入字符和字符串的操作一样的 就可以复用上面的pushback 和 append 来实现他们 只是函数名不同,内在的实现逻辑是相同的

1.加等字符

	string& operator+=(char ch)//加等字符
		{
			pushback(ch);
			return *this;
		}
		

2.加等字符串

string& operator+=(const char* str)//加等字符串
{
	assert(str);
	append(str);//复用接口
	return *this;
}

八、扩容(reserve)

因为string是类似线性表的,可以动态扩容,每次插入数据都需要判断是否需要进行扩容,上面那么多的插入,都需要判断是否需要扩容,那么就可以把扩容写成一个成员函数,需要扩容的时候调用它即可。

这里的reserve只是负责开辟空间,不负责初始化空间,只是_capacity会改变,_size是不会改变的

void reserve(size_t len)
{
	if (len > _capacity)
	{
		char* tmp = new char[len + 1];
		strncpy(tmp, _str, _size + 1);//这里要用strncpy 否则再resize后会出现错误 如果填充字符是\0那么就不会被拷贝到新空间 扩容后数据丢失 是个bug
		delete[] _str;
		_str = tmp;
		_capacity = len;
		//_str[_capacity] = '\0';//这个不能少 因为开辟的一块新空间最后要设置成\0 防止在析构的时候会出现错误 不知道到哪里结束 注意 
//上一行的注释是错的 不需要 这是多此一举 因为你如果插入数据或者扩容 本身的\0 都是会被拷进去的 有效字符的结尾都会有一个\0
//不需要你在扩容后为它最后面加上\0 它自己无论怎样都是\0 在有效字符的最后的
	}
}

reserve这里就有细节值得扣了,就是上面讲的最好用strncpy不要用strcpy的原因所在

问题就是:当我们调用了resize之后如果没有个默认的初始化空间的字符,就是默认的'\0';或者说我们自己给的初始化空间的字符就是‘\0’,之后再调用reserve就会出现bug了

STL中string类的实现(细节避坑)_第3张图片

九、扩容并初始化(resize)

与reserve不同的是,resize 是开空间并且初始化的,给一个字符,将开辟出来的多于的空间用给的字符填充,更新_size,更新_capacity.

void resize(size_t n,char ch='\0')
{
	if (n > _capacity)
	{
	reserve(n);
	memset(_str + _size,ch, n-_size);
	}
	else
	{
	_str[n] = '\0';
	}
	_size = n;

			
}

这里是复用了reserve进行扩容然后用memset去初始化多余的空间,初始化空间的范围是

(_str + _size,ch, n-_size),还有考虑缩容的情况,如果是n小于_capacity就是缩容了,直接在n下标对应的空间放上一颗零鸭蛋即可,最后更新_size

十、获取有效字符个数

这个就比较简单了 直接写个成员函数,返回_size 即可

size_t retsize()
		{
			return _size;
		}

十一、获取成员变量_str的函数c_str()

这个也比较好实现 写个成员函数返回_str即可

const char* c_str()
		{
			return _str;
		}

十二、插入数据的三种方法详解及相关细节(两种下标法 一种指针法)

随机插入也是string具有的功能,包括插入字符和字符串,插入的方法有三种。

一、字符的随机插入

1、下标法实现插入

通过对下标对数据进行挪动,在哪插入就从哪开始把数据往后挪动,空出位置来插入新数据

1.有缺陷的下标法 (不能是从下标为0的位置插入)

string& insert(size_t pos,char ch)//有问题的写法
		{
			assert(pos <= _size);//可以是等于_size相当于是尾插 但是不能超过_size 否则越界了
			size_t end = _size;
			while (end >= pos)
			{
				_str[end + 1] = _str[end];
				--end;
			}
			_str[pos] = ch;
			_size++;
			return *this;
		}

2.没有缺陷的下标法(可以在任意下标进行插入)

	string& insert(size_t pos, char ch)
		{
			assert(pos <= _size);
			size_t end = _size + 1;
			while (end > pos)
			{
				_str[end] = _str[end - 1];
				--end;
			}
			_str[pos] = ch;
			_size++;
			return *this;
		}

3.指针法

string& insert(size_t pos, char ch)
		{
			assert(pos <= _size);
			char* end = _str + _size;
			while (end >= _str + pos)
			{
				*(end + 1) = *end;
				--end;
			}
			*(_str+pos) = ch;
			_size++;
			return *this;

		}

指针法就直接是对指针指向的数据进行操作了,就没有数的转化了,就不用担心-1的情况了。

注意:

这里的两种下标法只是四条代码不同,方法1 是让end等于_size下标(对应的\0),然后让

 _str[end + 1] = _str[end] 这样的话如果是从0开始插入数据end最后就会变成-1 ,而-1对应的无符号整数是42亿九千万,会照成死循环;方法2是让end等于_size+1(对应的是\0的下一个位置),然后让    _str[end] = _str[end - 1] 这样如果是从0开始插入数据,end最后就会变成0 ,最小的情况即使end变成0 ,是不会到-1去的,所以就很好地避开了-1的情况,就解决了缺陷;

具体步骤可以参考俺画的图(老费劲了)

STL中string类的实现(细节避坑)_第4张图片

下标法2是怎么解决下标法1的缺陷的具体图解(瞧一瞧吧):

 STL中string类的实现(细节避坑)_第5张图片

 

二、字符串的随机插入

也有指针法和下标法

1.指针法

//2.指针法
		string& insert(size_t pos, const char* str)
		{
			assert(pos <=_size);
			
			//char* end = _str + _size;//如果是用的指针法 这里的标记的最后一个指针的位置不能在扩容之前
			//因为扩容后空间就不是原来的空间了 而是新的空间 原来的空间被释放了 那么end所指向的还是原来的空间上的\0是不可以
			//所以把end放在开辟好空间后再赋值 切记不可以放在扩容的前面  又是一个小细节!!
			//printf("%p\n", _str);
			size_t len = strlen(str);
			if (_capacity < _size + len)
			{
				reserve(_size + len);
			}
			//printf("%p\n", _str);

			char* end = _str + _size;

			while (end >= _str + pos)
			{
				*(end + len) = *end;
				--end;
			}
			strncpy(_str + pos, str, len+1);//又疏忽了 这里是拷贝len+1个 len只是长度 还有一个\0 也要
			_size += len;
			return *this;
		}

注意:这里也有细节要扣,end是用来记录原来字符串的\0 的位置的,这里的end的初始化要在判断是否扩容的后面进行,否则会出现野指针的问题。因为如果要扩容的话,就会开辟新的空间然后把原来的数据拷贝到新空间,然后把这块空间赋值给原来的_str,相当于是内容没有变,容量变了,空间地址也变了,扩容前后是两块不同的空间,如果在判断扩容之前就初始化了end,那么如果下面进行了扩容_str就会是另一块新的空间了,那么后面循环里对end进行的操作就是非法的了,为什么呢?

因为扩容后是_str指向的是新空间,end本应该新空间中数据中\0的位置的指针,但是在扩容前就初始化了end的话那么end就是扩容前空间中数据中'\0'位置的指针了,在扩容后end还是指向原来空间中\0的位置,但是原来的空间已经被释放了,你这个时候再用end去访问原来的空间就是非法的,这时的end指针就是大名鼎鼎的“野指针”了!!!

2.下标法

1.下标法
		string& insert(size_t pos, const char* str)
		{
			assert(pos <= _size);
			size_t end = _size + 1;
			size_t len = strlen(str);
			if (_capacity < _size + len);
			{
				reserve(_size + len);
			}
			while (end > pos)
			{
				_str[end + len-1] = _str[end-1];//这里是一个细节 要让两个方括号的差等于len 不能类比上面的插入字符的insert 写成_str[end + len] = _str[end-1] 会出错
				--end;
			}
			strncpy(_str + pos, str, len);
			_size += len;
			return *this;

		}

下标法也有细节:

在写完随机插入字符的函数后,再写随机插入字符串的函数后,会有一个类比的思想,就是把在插入字符函数中的    _str[end] = _str[end - 1];基础之上想着,既然是插入字符串,那么就要从\0开始往前直到pos位置的数据全部往后挪动插入字符串的长度个位置,也就是

_str[end+len] = _str[end - 1];我就是这样想当然地写,然后就错了,再调试调出了问题在哪;

这里是不能想当然地写的,我们要知道把数据往后挪插入字符串长度个距离,两个方括号里的数据差就要是字符串的长度,_str[end+len] = _str[end - 1];中很明显差值不是len 而是len+1

所以要写成_str[end+len-1] = _str[end - 1];才行,这也算是个小细节吧!!!

十三、删除数据

删除数据的思路与插入数据的思路相似,也是通过挪动数据,对要删除的数据进行覆盖处理,这里是用的strcpy来实现数据的挪动

	string& erase(size_t pos, size_t len=::string::npos)
		{
			assert(pos < _size);
			size_t leftlen = _size - pos;//pos 是标从0开始 _size是长度不是从零开始 因为两个长度一剪再加1才是两者之间的个数 所以这里刚刚好减出来就是之间的元素个数
			if (leftlen < len)//1.剩下的元素不足len
			{
				_str[pos] = '\0';
				_size -= len;
			}
			else//2.剩下的元素多于len
			{
				strcpy(_str + pos, _str + pos+len);//利用strcpy把后面的往前面拷贝
				_size -= len;
			}
			return *this;
		}

注意:删除要分情况

1.pos位置后剩下的字符个数小于要删除的字符个数

这种情况直接就把下标为pos的位置放上\0 即可,即使代表把pos位置之后的所有数据全部删除

2.pos位置之后剩下的字符个数大于要删除的字符个数

这种情况就是把从下标从pos+len的位置往后的字符全部拷贝到从pos下标位置开始往后的空间中

可以调用strcpy实现   

即:strcpy(_str + pos, _str + pos+len);//利用strcpy把后面的往前面拷贝

最后不要忘了把_size-=len;更新_size

十四、查找单个字符和子串

这里用到了strstr函数来实现找子串的功能

1.查找单个字符

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

遍历思想,如果找到了就返回下标,否则返回string中的npos (无符号整形的-1 )

2.查找字符串

复用strstr来实现

	//查找字符串
		size_t find(size_t pos, const char* str)const//不改变成员变量的函数最好都加上const 修饰的是this指针指向的对象 使对象的成员不能被修改
		{
			assert(pos < _size);
			char* ret = strstr(_str+pos, str);
			if (ret)
			{
				return ret - _str;//这里要的是下标 所以不用加一 求个数才要加一

			}
			else
			{
				return ::string::npos;
			}
		}

十五、简易迭代器遍历的实现

利用了typedef把iterator 和const_iterator定义为char*和const char*类型

然后各自写两个函数begin()和end()作为迭代器的开始和结束

begin是返回_str   而 end是返回_str+_size ,相当于是头尾指针 

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

在函数中使用实现的简易的迭代器去遍历输出字符串

void testitrator()
	{
		string a("a nice day!");
		string::iterator it = a.begin();
		while (it != a.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

运行结果如下:

STL中string类的实现(细节避坑)_第6张图片

十六、类的直接比较

实现像比较数字一样比较类(字符串)的大小

这里用到了strcmp来实现

//比较两个字符串 可以用函数strcmp
	bool operator>(string& str1, string& str2)
	{
		return strcmp(str1.c_str(), str2.c_str()) > 0;

	}
	bool operator<(string& str1, string& str2)
	{
		return !(str1 > str2);

	}
	bool operator==(string& str1, string& str2)
	{
		return strcmp(str1.c_str(), str2.c_str()) == 0;

	}
	bool operator!=(string& str1, string& str2)
	{
		return !(str1 == str2);

	}
	bool operator>=(string& str1, string& str2)
	{
		return str1>str2||str1==str2;

	}
	bool operator<=(string& str1, string& str2)
	{
		return str1 < str2 || str1 == str2;

	}

实现了大于小于等于,剩下的借口就可以复用他们来实现了 

STL中string类的实现(细节避坑)_第7张图片

十七、类的直接输入输出

实现像基本类型一样直接输出string对象总的字符串

1.输出

ostream& operator<<(ostream& out, string& s)
	{
		for (auto ch : s)
		{
			out << ch;
			//ch++; 因为这里是范围for 所以不用自己写加加 他自己会自动加的
		}
		return out;

	}

这里要返回的是输出流的引用,使得可以连续地输出,out 是ostream的对象。

2.输入

istream& operator>>(istream& in, string& str)
	{
		//如果是本来就有数据的字符串再输入 那就要把原来的数据清理掉 然后size变成0 
		str.clear();
		char ch;
		//in.get(ch);
		ch = in.get();//这样用才是对的 上面的是错的
		while (ch != '\0' && ch != '\n')
		{
			str += ch;
			in.get(ch);
		}
		return in;
	}

 注意这里不能直接用in来输入,因为in遇到字符'\0'和字符'\n'就会自动忽略,然后程序就不动了,崩了。要用ostream类的in对象的get方法来接收输入的值,相当于C语言中的getchar(),可以接收\n 和 \0.除了EOF其他都可以接收。 

十八、标准库中getline简易的实现

getline 是输入一个串 要包括空格在内 cin和cout 都是遇到\n 和 \0 就停止的,根据上面的输入可以改变一下条件实现输入的是一个可以包括空格的字符串,那就是把while里的ch!= '\0' 去掉就可以了。

istream& getline(istream& in, string& str)
	{
		str.clear();
		char ch;
		//in.get(ch);
		ch = in.get();
		while (ch != '\n')
		{
			str += ch;
			in.get(ch);
		}
		return in;
	}
	

补充、std::swqp 和 string 自带的成员函数 swap 的区别

std::swap 的原理是深拷贝,而string自带的swap是交换两个对象的指针,相比较于全局的swap

string自带的swap的效率更高 。

STL中string类的实现(细节避坑)_第8张图片

 

STL中string类的实现(细节避坑)_第9张图片

好了 本文到此就结束了~

如果喜欢的话就留下你来过的痕迹吧!

附上源码:realization of string/string.cpp · 张华/c++code - 码云 - 开源中国 (gitee.com)

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号