STL之string模拟实现

1.模拟string类

string本质上是一个char类型的顺序表,实现起来与顺序表相似,所以结构上也相似!

namespace String
{
    class String
    {
    public:
        static const size_t npos; // 全局比较变量 -1
    private: //设置私有,不允许随便访问底层数据
        char* _str; //字符串存储空间首地址指针
        size_t _size; //当前字符数量
        size_t _capacity; //可用容量
    }
}
        

结构上使用命名空间string进行封装,防止与库冲突,使用class封装成为对象string,其中:

_str:指向字符串存放的空间的指针

_size:代表当前所存储的有效字符数量

_capacity:代表当前可存储的最大容量

nops:此值设置为 -1,无符号整型转换就是42亿,且此值为const和静态参数具有全局效应,所以此值是public公开的,这个值常常被用来当作循环结束判断条件和查找时未找到的标志,某些函数设置其为缺省参数

 其中许多整型变量的设定都为size_t无符号整型,但是关于nops,其定义为static const size_t,我们知道在类中定义static变量是在类外初始化的,但是如果该变量被const修饰则可以在类中进行初始化也可以在类外进行初始化,因为此变量的初始化只有一次;且const修饰的静态变量,只允许整型家族在类中设置缺省值(short,int,long,char等)!

所以在类中的static变量,没有被const修饰则需要严格在类外初始化,如果使用const修饰则可以在类中使用缺省参数的形式进行初始化也可以在类外初始化!

对于npos的初始化,以下方式都是可以的:

class string
{
public:
    static const size_t npos = -1;
}
class string
{
public:
    static const size_t npos;
}
const size_t string::npos = -1;

2.string默认成员函数

最主要磨人成员函数:构造函数,拷贝构造函数,赋值运算符重载以及析构函数。

2.1构造函数

在VS下string会多开一些空间且在对象创建时就会先开一部分空间,我们依照此特性进行设计

string(const char* s = "")  //缺省参数默认构造空串
	:_size(strlen(s))
{
	_capacity = _size;
	_capacity = _capacity == 0 ? 4 : _capacity * (1.25);
	_str = new char[_capacity + 1];
	strcpy(_str, s);
}

构造函数接受一个字符串,默认的缺省参数为空串

strlen先求出字符串长度并通过初始化列表初始化_size

通过判断_capacity计算需要的容量,如果0则是空串默认开4字节空间,否则计算字符串长度后多开1.25倍空间

容量确定后开空间,在此基础上多开一字节空间用于存放\0

最终字符串s中的字符通过字符串拷贝函数拷贝到我们所开的空间中 

2.2拷贝构造函数

拷贝构造函数,如果不写,编译器会默认生成一个,但是默认生成的拷贝构造函数只支持浅拷贝,我们需要新构造的对象通过拷贝构造开辟一片新的空间将数据复制过去,但是新构造的对象析构时释放同一片空间的资源势必会导致程序崩溃!

#include <iostream>
#include <assert.h>
using namespace std;

class String
{
public:
	String(const char* str = "")
	{
		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;
};


int main()
{
	String s1("hello world");
    String s2(s1);
	return 0;
}

注意:此时s1和s2共用同一块空间,s2需要调用String类拷贝构造函数来创建,该类没有显示定义,则使用系统合成的默认拷贝构造函数,当函数结束时,需要将s1和s2销毁掉,先销毁s2,s2将其_pStr所指的空间释放掉,s2对象成功销毁,但是s1中的_pStr成为野指针,当销毁s1时出错。

2.3 赋值重载

赋值重载不同于拷贝构造,需要我们注意自己给自己赋值这种冗余的行为,同时也要控制空间的大小!

string& operator=(const string& s)
{
	if (this != &s) //判断是否是同一个对象
	{

		_size = s._size; //获取
		_capaicty = (_size * (1.25)); //开辟被拷贝字符串长度的1.25倍字节空间
		char* tmp = new char[_capaicty + 1]; //先用临时指针指向开辟空间,防止空间开辟失败丢失原数据
		delete[] _str; //如果开辟成功则释放原空间
		strcpy(tmp, s._str); //拷贝字符数据
		_str = tmp; //交付空间
	}
	return *this; //返回被赋值对象的引用,实现可以连等(例如s1=s2=s3)
}

2.4 析构函数

我们释放内存是因为我们使用new[]申请,所以对应的释放delete[],这里需要注意!

~string()
{
	delete[] _str;  // 释放_str所指向的空间
	_str = nullptr;  //_str指针指向空
	_size = _capacity = 0;  //容量置为0
}

3 容器操作类

3.1获得字符串长度size

首先这个函数比较小,只需要返回size即可,可以写在类中形成内联函数
其次对于这些函数我们不会涉及对字符串的增删查改,可以使用const修饰this增强安全性!

size_t size() const
{
    return _size;
}

3.2 获取当前容量capacity

size_t capacity const
{
    return _capacity;
}

3.3 查询是否为空串empty

bool empty() const
{
    return _size == 0;
}

3.4 reserve 扩容

string支持手动扩容到n字节,这里需要注意的是,扩容函数不支持缩容,所以n必须大于原有的容量大小,否则不会触发扩容机制!

void string::reserve(size_t n) //函数声明定义分离实现
{
	if (n > _capaicty) //判断容量是否大于当前容量
	{
		_capaicty = n; //更新容量大小
		char* tmp = new char[_capaicty + 1]; //开辟新空间
		strcpy(tmp, _str); //将原字符串的数据拷贝到新空间上
		delete[] _str; 释放原空间
			_str = tmp; //交付空间	
	}
}

注意:对于已有字符串扩容时的操作,需要注意内存申请失败的问题,所以在此之前需要保留原空间的数据!

3.5调整字符串大小size

string支持增长或缩小字符串长度,但是该操作与容量无关!

调整字符串大小有两种情况:

1.缩小长度:缩小长度非常简单,只需要将size更新并在size+1处设置\0即可。

2.增长长度:增加长度则需要考虑两方面:增加的长度在容量范围内:只需要将size更新,并将增长的字符串部分设置为指定的字符既可,这里指的字符缺省参数为0,在size+1处设置\0即可;如果增长的长度超过容量:则要先扩容,再操作!

//头文件声明
void resize(size_t n,char c = '\0')

注意:对于函数声明定义分离实现,缺省参数写在声明中,定义是不需要写缺省参数!

void string::resize(size_t n, char c)
{
	if (n > _capacity)  //判断是否需要扩容
	{
		reserve(_capacity + (n - _capacity)); //复用reserve
	}
	if (n > _size)
	{
		for (size_t i = _size; i < n; ++i)
		{
			_str[i] = c;  //迭代将新空间全部设置为字符串c
		}
	}
	_size = n; //更新size
	_str[n] = '\0'; //通过下标访问时size就是size+1处,此处设置\0构成字符串
}

4.字符串访问

4.1 下标访问

下标访问是通过重载[ ]运算符实现的,在下标pos正确的情况下,返回其下标下字符的引用,否则assert报错!

char& operator[](size_t pos)
{
    assert(_size > 0 || pos > _size);  //检查下标
    return _str[pos];  //返回pos位置的字符 
}

注意:因为该函数比较短小,所以在类中实现即可!

4.2 迭代器访问

迭代器是指针对象,是对指针的封装!因为string中迭代器的实现比较简单,所以也在类中直接实现!

首先将指针重命名为迭代器,因为我们实现的string底层是原生指针,通过typedef仍然可以直接操作(即++和-)!

//迭代器声明
typedef char* iterator
typedef const char* const_iterator;

函数在调用时返回迭代器即可!

iterator begin() //返回字符串指针头
{
    return _str;
}
iterator end()  //返回字符串最尾端的下一个
{
    return _str + _size;
}
const_iterator begin() const //const类型的迭代器,无法对数据进行修改
{
    return _str;
}
const_iterator end() const 
{
    return _str+_size;
}

注意:该迭代器在声明后可以与指针一样进行操作!

5.插入/删除类操作

5.1 insert类

在pos位置插入一个字符

首先,需要注意扩容问题,如果容量已满则扩容1.5倍(vs方案),且需要注意pos下标是否规范!其次,在pos位置插入,可能在字符串的任意位置,涉及对现有字符串的挪动,需要计算位置,计算合适的位置后使用memmove进行内存块挪动!

string& string::insert(size_t pos, char c)
{
	assert(pos <= _size); //判断下标是否合法(允许在\0尾端处进行插)
	if (_size + 1 > _capacity) //判断是否需要扩容
	{
		reserve(_capacity * (1.5));
	}
	memmove(begin() + pos + 1, begin() + pos, (end() - (begin() + pos))); //移动字符串
	_str[pos] = c; //将字符串c插入pos位置
	_str[++_size] = '\0'; //为了保证安全性,最后我们海狮要手动将字符串尾置为\0

	return *this;  //返回string对象
}

对于memmove函数,其参数分别是memmove(目标空间,复制源,复制多少字节)

memmove(begin() + pos + 1, begin() + pos, (end() - (begin() + pos()));

说明:

begin() + pos + 1:指向复制内容存放的空间;

begin() + pos:指向复制内容的起始位置

(end() - (begin() + pos)):end相当于size位置,通过计算得出需要复制的字节数(包括\0) 

实际操作使用的是迭代器begin和end,方便获取,尽量避免直接使用成员参数计算,以免损坏数据!

5.2 在pos位置插入一个字符串

首先要判断字符串是否为空指针,其次对原串的挪动上挪动的位置不是一位,而是移动字符串s的长度位,这里我们仍然采用memmove移动内存块和strncpy将字符串s上的字符拷贝到本串!

string& string::insert(size_t pos, const char* s)
{
	assert(s); //判断字符串是否为空指针
	assert(pos <= _size); //判断下标是否合法(允许在\0尾端处进行插入)

	size_t len = strlen(s); //计算插入字符串长度
	if ((_size + len + 1) > _capacity) //判断是否需要扩容
	{
		reserve(_size + len + 1);
	}
	memmove(_str + pos + len, _str + pos, _size - pos + 1); // 挪动原字符串
	strncpy(_str + pos, s, len); //采用strncpy将字符串s拷贝到pos位置
	_size += len - pos; //更新size

	return *this;  //返回string对象
}

5.3 尾插一个字符

函数push_back,用处是在字符串尾插入一个字符,因为我们前面实现了insert,所以复用即可!

void string::push_back(const char c)
{
    insert(_size,c);
}

6. append类

append类是在尾部追加插入一个字符或者字符串,且插入规格有很多种!

对于尾插,相当于insert来说简单许多,不需要挪动数据,不过在插入前需要判断容量问题,且最后插入后一定要设置\0防止越界访问!

6.1 在尾部追加一个string对象

在插入前先检查容量,再从当前字符串尾部开始,将对象的字符串数据拷贝到当前字符串尾部!

string& string::append(const string& str)
{
	if (str._size >= _capacity - _size) //判断是否需要扩容
	{
		reserve(_capacity + str._size + 1); //复用reserve
	}
	strpcy(_str + _size, str._str); //_str+size是当前字符串尾部
	_size += str.max_size; //更新_size
	_str[_size] = '\0'; //手动设置字符串尾部的\0

	return *this; //返回string对象
}

补充:同时可以指定在string对象的pos位置后拷贝n个字符!与前面不同的是,该重载函数如果不指定拷贝的字符数len则默认从pos位置开始拷贝完该string对象后面的所有字符!

函数声明:

//len默认是npos,在函数中会进行检查,确定是否需要从pos位置全部拷贝!
string& append(const string& str, size_t pos, size_t len = npos);
string& string::append(const string& str, size_t pos, size_t len)
{
	assert(pos < str._size); //检查pos下标是否合法
	
	//如果len == npos或从pos位置开始不足n个字符则全部拷贝
	if (len == npos || (pos + len) >= str._size)
	{
		append(str._str + pos); //复用append(const char* s) 
	}
	else //否则拷贝对应条件的字符
	{
		append(str._str + pos, len); //复用append(const char* s,size_t n)
	}
	return *this;
}

6.2在尾部追加一个字符串

我们可以传递一个char*类型指针来进行追加,在追加前仍然要检查其容量,最后也要手动设置\0

string& string::append(const string& str, size_t pos, size_t len)
{
	assert(pos < str._size); //检查pos下标是否合法

	//如果len == npos或从pos位置开始不足n个字符则全部拷贝
	if (len == npos || (pos + len) >= str._size)
	{
		append(str._str + pos); //复用append(const char* s) 
	}
	else //否则拷贝对应条件的字符
	{
		append(str._str + pos, len); //复用append(const char* s,size_t n)
	}
	return *this;
}

 补充:该函数也有其他的重载类型,可以从字符串s开始位置追加n个字符到当前字符串尾部!这里需要注意的是:卡农n大于当前字符串长度,此时默认将字符串s全部拷贝到当前字符串的尾部

string& string::append(const char* s, size_t n)
{
	size_t slen = strlen(s); //获取字符串
	if (n > slen) //判断n是否超过字符串s的最大长度
	{
		n = slen; //超过则矫正为被拷贝字符串的全部长度
	}

	if (n >= _capaicty - _size) //判断是否需要扩容
	{
		reserve(_size + n + 1);
	}
	for (size_t sub = 0; sub < n; ++sub) //利用循环插入指定的字符串
	{
		_str[_size++] = s[sub];
	}
	_str[_size] = '\0'; //手动设置 \0
	return *this;
}

 6.3尾部追加n个c字符

append支持在尾部追加n个c字符,某些初始化场景下很有用!

string& string::append(size_t n, char c)
{
	if (n > _capaicty - _size) //判断扩容问题
	{
		reserve(_size + n + 1);
	}

	for (size_t num = 0; num < n; ++num) //下标访问循环插入n个字符c
	{
		_str[_size++] = c;
	}
	_str[_size] = '\0';手动设置 \0
	return *this;
}

7. 删除类操作

删除类函数一般都是erase函数,用于删除字符或字符串!但是erase函数性能不太好,因为涉及字符串的挪动调整!

7.1 从pos位置删除n个字符

erase支持从pos下标开始删除n个字符,其中n是一个缺省参数,默认是npos,规定是如果pos下标不合法则报错,如果n超过从pos位置开始到字符串尾部的字符个数默认从pos位置开始删除后面的所有字符,且不允许在空串的情况下进行删除!

函数声明:

string& erase(size_t pos,size_t len =npos);

实现函数:

string& string::erase(size_t pos, size_t len)
{
	assert(pos <= _size); //判断下标是否合法
	assert(_size > 0); //_size不允许为0

	//如果len超过从pos位置开始的剩余字符长度则删除后面的所有字符,默认删除pos后面全部字符
	if ((pos + len) >= _size || len == npos)
	{
		_size = pos;
	}
	else //否则通过memmove进行覆盖式拷贝
	{
		memmove(begin() + pos, begin() + pos + len, end() - (begin() + pos + len));
		_size -= len; //更新_size
	}

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

7.2迭代器区间删除

迭代器区间删除需要判断这个迭代器区间是否合法,一旦不合法就终止!
因为迭代器是typedef重命名的指针,这里可以直接使用函数参数进行操作,因为string是顺序表,是一片连续的空间,利用指针相加相减也可以计算需要删除的字符数,这里我们仍然使用memmove函数删除!

string::iterator string::erase(string::iterator first, string::iterator last)
{
	if (first < begin() || first>end() || last <begin() || last > end()) //区间不合法则退出
	{
		cout << "iterator区间存在越界!" << endl;;
		assert(0);
		exit(-1);
	}
	//计算区间然后删除,尾指针减当前区间的尾区间可以得到减去的字符数
	memmove(first, last, end() - last);
	_size -= (last - first);
	_str[_size] = '\0';
	return first;
}

8.其他运算符重载

8.1 +运算符

+运算符的实现,我们构造临时对象进行拼接并返回字符串对象的拷贝,这里不能返回临时对象的引用,其次我们使用当前字符串对象进行构造,不涉及对此对象的修改,所以可以所以const修饰this确保不被篡改!

函数声明:

//注意,对于const修饰this需要声明与定义保持一致,区别于缺省参数!
string operator+(char ch) const;
string operator+(const string& s) const;

函数实现:

string string::operator+(char ch) const
{
	string tmp(*this);
	tmp.push_back(ch);

	return tmp;
}

string string::operator+(const string& s) const
{
	string tmp(*this);
	tmp.append(s._str);

	return tmp;
}

8.2 +=运算符

+=运算符在当前字符串尾部追加字符串,当然在底层复用的是append函数,不过有时候+=运算符比函数用起来更方便!

string& string::operator+= (const string& str) //+=一个string对象
{
	append(str);
	return *this;
}

string& string::operator+= (const char* s) //+=一个char*字符串
{
	append(s);
	return *this;
}

string& string::operator+= (char c) //+=一个字符
{
	insert(_size, c);
	return *this;
}

8.3 逻辑判断运算符

无非就是==,<,>=等,这些运算符都不需要修改可以使用const修饰this指针,且这些函数比较短小,在类中实现,对于字符串的比较,我们复用strcmp即可!

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

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

9. 查找操作

查找函数是find,支持从任意pos位置开始查找,pos是缺省参数默认为0从起始位置开始查找,在string对象中支持查找一个字符和一个字符串,查找到后字符返回下标,字符串返回首字符地址,如果有多个重复的字符或字符串,返回查找到的第一个字符的下标或字符串首的下标;如果没找到则返回npos,对于字符的查找,我们使用变量查找即可,对于字符串的查找,我们复用strstr库函数,strstr函数作用是在目标字符串中寻找是否出现过源字符串,如果出现则返回第一次其在目标字符串中第一次出现的地址,如果没有出现,则返回一个空指针。

函数声明

//pos默认从0下标,字符串起始位置开始查找
// 返回c在string中第一次出现的位置
size_t find(char c, size_t pos = 0) const;

// 返回子串s在string中第一次出现的位置
size_t find(const char* s, size_t pos = 0) const;

函数实现:

size_t string::find(char c, size_t pos) const //查找字符
{
	for (size_t sub = pos; sub < _size; ++sub) //迭代遍历查找
	{
		if (_str[sub] == c)
		{
			return sub; //找到就返回下标
		}
	}
	return npos; //没找到返回npos
}

size_t string::find(const char* s, size_t pos) const //查找字符串
{
	assert(pos <= _size);

	auto sub = strstr(_str + pos, s);
	if (sub)
	{
		return (sub - _str); //返回的地址减去首地址得到对应下标
	}
	return npos; //返回空则该函数返回npos
}

10. 函数补充

10.1 清空字符串

clear函数支持清空一个字符串,但不是释放对象,区别于析构函数!
clear函数清理字符串并不会引起缩容,只是在下标0位置置为 \0 ,_size置为0即可!

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

10.2交换字符串

string对象支持交换字符串,其实底层就是相互交换所指向空间的指针,容量和字节数数据!

void string::swap(string& s)
{
	std::swap(_str, s._str);
	std::swap(_size, s._size);
	std::swap(_capaicty, s._capaicty);
}

10.3获取字符串源指针

有些场景下,例如使用C语言的字符串操作函数,处理字符串时只能使用char*指针去传参,string为了兼容C字符串操作函数,支持获取字符串源指针,为了不破坏string的数据结构,这个返回的源字符串指针不支持修改,只能访问内容,这个函数非常短小,直接在类中实现!

const char* c_str() const
{
    assert(_str);
    return _str;
}

11. 流操作

流操作属于iostream中的对象,所以不需要定义在类中作为成员函数,也不需要声明为友元;因为使用流体去和流插入需要ostream和istream对象作为左操作参数!


11.1流插入

我们可以重载<<运算符使用cout直接输出string字符串,在重载函数内部我们使用范围for直接迭代输出字符串(也可以使用迭代器输出),这里需要注意的是,cout支持连续输出,即cout<<s1<<s2<<s3;所以,我们在使用ostream对象后需要返回对象的引用使其可以继续调用!

ostream& Mystring::operator<<(ostream& out, string& s)
{
	for (auto& ch : s)
	{
		cout << ch;
	}
	return out; //返回ostream对象
}

11.2流提取

我们重载>>运算符使用cin可以直接将输入的字符串输入到string对象中,但是流提取对应string来说有两种输入情况:

首先当string对象为空时,我们无法预知输入字符串的长度,空间无法控制!

–所以为了避免频繁扩容导致性能下降,我们会定义一个缓冲区buff,先将字符串输入到缓冲区中,如果字符串很长则分批写入string字符串中,每次写入string后就刷新缓冲区再继续接收,这样就避免了频繁开辟空间。
如果string对象不为空,则需要先清空字符串再输入!

– 在使用流提取前,无论字符串中有没有数据都调用clear清空!。

istream& Mystring::operator>>(istream& in, string& s)
{
	s.clear(); //先清空字符串
	char buff[256] = { 0 }; //定义缓冲区并初始化 
	char ch = in.get(); //从输入流中获取一个字符
	size_t sub = 0; //缓冲区下标

	while (ch != ' ' && ch != '\n') //碰到缓冲区中有空格和换行就结束提取
	{
		buff[sub++] = ch; //将当前从stdin中获取的字符写入buff
		if (sub == 255) //如果buf下标写到了255则写满了(留一个位置给\0)
		{
			buff[sub] = '\0'; / buf最后一个位置写入\0
				s += buff; //通过+=追加到s
			sub = 0; //buf重新开始缓存
		}
		ch = in.get(); //从stdin中获取一个字符(get()类似于getc())
	}
	if (sub != 0) //如果碰到空格和换行退出则需要刷新存留在缓冲区中的数据
	{
		buff[sub] = '\0'; //当前下标后置为\0避免刷入上一次残留的重复数据
		s += buff;
	}

	return in; //返回istream对象(存在连续输入的情况,例如cin>>s1>>s2)
}

上一篇:Elasticsearch学习笔记(五)Elastic stack安全配置二


下一篇:应用恢复开发指导