快来看一看String类内部是如何实现的

刺骨的言语ヽ痛彻心扉 2022-11-16 01:26 151阅读 0赞

# String类内部实现 #

在C语言初识阶段，对于一些字符串的处理，往往做法是将其转换为单个字符通过遍历来进行逐个处理，但此做法需要耗费大量的计算量，如果字符串过长，导致时间甚至内存都会被大量浪费

学习到C++阶段，string类的出现，将发现其所开放的接口使用极为便捷，方便

尤其在大量OJ练习中，有关字符串的题目都以string类的形式出现，无论在以后工作或学习，基于软件体系结构的思想下都会以接口的形式方便底层开发，很少再去调用c库中的字符处理的相关函数

明明有对应的接口，为什么还要去模拟String内部具体实现呢？

只有真正了解内部代码实现后，对于接口的调用才会得心应手，无论是接口的传入参数，还是接口返回值，相比查阅相关手册，在有一定的了解会在算法设计过程中更加简洁

下面就来看一看string类内部实现

*  ### 内部成员变量定义 ###

private:
    	char* _data;
    	size_t _size;
    	size_t _capacity;
    	static const size_t npos;

定义了私有成员变量，包括存储数据的字符指针，以及字符串实际长度和字符串开辟空间大小

除此之外还定义了静态成员变量 作为无效返回值的最大值（-1），但此处需要注意静态成员变量类外初始化

const size_t String::npos = -1;//静态变量类外初始化

*  ### 构造函数 ###

String(const char* str = "")//全缺省 构造
    	{
    		_data = new char[strlen(str) + 1];
    		_size = strlen(str);
    		_capacity = _size;
    		strcpy(_data, str);
    	}

构造函数采用全缺省构造函数，内部赋值操作，其中\_data默认开辟一个字节空间，\_size大小为1，同时将传入的字符串通过strcpy拷贝到新开辟的内存空间

*  ### 拷贝构造函数的现代写法 ###

void Swap(String &str)
    	{
    		swap(str._data,_data);
    		swap(str._size, _size);
    		swap(str._capacity, _capacity);
    	}
    	String(const String& str)//深拷贝
    		:_data(nullptr),
    		_size(0),
    		_capacity(0)
    	{
    		String tmp(str._data);
    		Swap(tmp);
    	}

浅拷贝仅仅改变了指针的指向，没有实现内存空间上的拷贝，为了实现深拷贝，需要通过new开辟内存空间实现赋值拷贝

String(const String& str)//深拷贝
    		:_data(new char[strlen(str._data) + 1])
    	{
    		strcpy(_data, str._data);
    	}

现代写法中，通过调用拷贝构造函数创建临时对象，完成新空间开辟和内容拷贝，通过swap交换，交换隐藏this指针指向，临时对象资源地址变为this地址指向

同时，随着临时对象的析构 资源被释放

根据现代写法的思路，完成赋值运算符重载

String& operator=(String str)
    	{
    		Swap(str);
    		return *this;
    	}

其实，赋值运算符此处也类似于完成了一次深拷贝，传参的过程调用拷贝构造函数创建临时对象，完成新空间开辟和内容拷贝，再通过swap交换，交换隐藏this指针指向，临时对象资源地址变为this地址指向

为了验证现代写法是否可靠，测试如下：

![c46c9d4251954a905b1a67991c167f2b.png][]

拷贝构造函数的现代写法。拷贝相同大小空间，并赋值拷贝，保证深拷贝完成

![691a74c74ad254e84adf73a7b80581a9.png][]

赋值运算符重载也类似，拷贝相同大小空间，并赋值拷贝，保证深拷贝完成

*  ### 重载\[\]运算符 ###

【】运算符主要目的是为了获取某个位置上的字符，【】运算符获取字符时间复杂度为O（1）

char& operator[](size_t pos)
    	{
    		assert(pos < _size);
    		return _data[pos];
    	}
    	const char& operator[](size_t pos)const
    	{
    		assert(pos < _size);
    		return _data[pos];
    	}

*  ### 迭代器实现及使用 ###

//string 迭代器  功能类似指针  即迭代器实质就是一个字符指针
    	typedef char* iterator;
    	typedef const char* const_iterator;
    
    
    	iterator begin()//第一个元素位置
    	{
    		return _data;
    	}
    
    	iterator end()//最后一个元素的下一个位置
    	{
    		return _data + _size;
    	}
    	
    	void printiterator(String& str)
    	{
    		String::const_iterator it = str.begin();
    		while (it != str.end())
    		{
    			cout << *it <<" ";
    		}
    		cout << endl;
    	}

由于 迭代器 功能类似指针 即迭代器实质就是一个字符指针，在进行打印时，通过迭代器移动完成每一个字符遍历并打印输出，此处创建了const类型迭代器和非const类型的迭代器，如果使用const类型迭代器将只读，无法修改迭代器所指向内容

*  ### resize实现 ###

void resize(size_t n)
    	{
    		if (n <= _size)
    		{
    			_size = n;
    			_data[_size] = '\0';
    		}
    		else
    		{
    			if (n > _capacity)
    			{
    				reserve(n);
    			}
    			memset(_data + _size, '\0', (n - _size)*sizeof(char));//在size 和cap之间 用‘\0’填充
    
    		}
    	}

resize的实现主要需要分情况，考虑传入参数n和size以及capacity大小关系，是否需要进行填充，此处默认填充'\\0'

*  ### reserve实现 ###

//改变容量
    	void reserve(size_t cap)
    	{
    		if (cap > _capacity)
    		{
    			//申请新空间
    			char* tmp = new char[cap + 1];
    			//拷贝
    			strcpy(tmp,_data);
    			//释放原空间
    			delete[] _data;
    
    			_data = tmp;
    			_capacity = cap;
    		}
    	}

reserve实现都只需注意三个步骤

1.  申请新空间
2.  拷贝原有空间到新空间
3.  释放新空间
4.  关系指针（迭代器）指向或size，capacity大小

*  ### 尾插 ###

**string类尾插过程需要注意，为了保证字符串合法 需要在结尾加入“\\0”**

//尾插
    	void push_back(const char& ch)
    	{
    		if (_size == _capacity)
    		{
    			size_t newcap = _capacity == 0 ? 15 : 2 * _capacity;
    			reserve(newcap);
    		}
    		_data[_size++] = ch;
    		//为了保证字符串合法  需要在结尾加入“\0”
    		_data[_size] = '\0';
    	}

测试结果如下：

![6d70a7ba3c4e8dc726d56d69d8d51d2f.png][]

push\_back为一个尾插字符的功能函数，基于此完成append函数，尾插一个字符串，与push\_bcak步骤类似，不同之处在于需要考虑插入字符串长度的问题

//尾插一个字符串操作
    	void append(const char* str)
    	{
    		//检查容量
    		int len = strlen(str);//strlen截取'\0'之前的数据
    		if (_size + len > _capacity)
    		{
    			reserve(_size+len);
    		}
    		//尾插
    		//内存拷贝 不会拷贝结尾'\0'memcpy
    		//strcpy拷贝会将结尾'\0'拷贝过来  strcpy(_data + _size, str);
    		memcpy(_data+_size,str,sizeof(char)*len);
    		//更新
    		_size += len;
    		_data[_size] = '\0';//将没有拷贝过来的'\0'进行尾部赋值
    
    	}

测试结果如下：

![b703b940d244d89bc4ea18f23c991c0f.png][]

*  ### \+=运算符重载 ###

\+=运算符重载函数，重载不同传入参数类型 （包括string类，字符串，字符） 在基于push\_back和append的基础上，实现起来就很简单，+=就类似于一个尾插操作，尾部连接

String& operator+=(const String& str)
    	{
    		append(str._data);
    		return *this;
    	}
    
    	String& operator+=(const char* str)
    	{	
    		append(str);
    		return *this;
    	}
    
    	String& operator+=(const char ch)
    	{
    		push_back(ch);
    		return *this;
    	}

测试结果如下：

![e4d54997a00f21329a48265b1a69f3df.png][]

*  ### 任意位置插入 ###

任意位置的插入需要考虑插入字符前，后续字符的移动问题，为了保证字符在移动过程中不被覆盖，从后向前移动，给插入字符腾出一个空位插入

类似地，任意位置的字符串插入需要考虑插入字符前，后续字符的移动问题，为了保证字符在移动过程中不被覆盖，从后向前移动，给插入字符腾出strlen（str）个空位插入

//插入一个字符：从后向前移动
    	void insert(size_t pos,const char& ch)// pos索引位置前插入ch
    	{
    		assert(pos>=0&&pos <=_size);
    		//检查容量
    		if (_capacity == _size)
    		{
    			size_t newcap = _capacity == 0 ? 15 : 2 * _capacity;
    			reserve(newcap);
    		}
    		//后移
    		size_t end = _size + 1;
    		while (end > pos)
    		{
    			_data[end] = _data[end - 1];
    			end--;
    		}
    
    		/*size_t end = _size;
    		while (end >= pos)
    		{
    			_data[end+1] = _data[end];
    			end--;//头插  由于无符号size_t  end<0变为最大值  
    		}*/
    
    		//插入  更新size
    		_data[pos] = ch;
    		_size++;
    	}
    
    	//插入字符串：从后向前移动
    	void insert(size_t pos, const char* str)// pos索引位置前插入ch
    	{
    
    		assert(pos >= 0 && pos <= _size);
    		int len = strlen(str);
    		//检查容量
    		if (_size + len > _capacity)
    		{
    			reserve(_size + len);
    		}
    		//后移
    		size_t end = _size + len;
    		while (end > pos+len-1)
    		{
    			_data[end] = _data[end - len];
    			end--;
    		}
    
    		//插入  更新size
    		memcpy(_data + pos, str, sizeof(char)*len);
    		_size+=len;
    		
    	}

测试结果如下：

![bca28642ad6e0c28a00c70da320f297f.png][]

### ![19b1d87ae74491a5acf97d4c6cbfb646.png][] ###

*  ### 任意位置删除 ###

与插入相反，任意位置的删除需要考虑后，如何通过字符的移动问题进而以覆盖前一字符的方式 隐式删除字符或字符串，为从前向后移动，覆盖前一（或前len长度）字符

//删除len个字符：从前向后移
    	void erase(size_t pos, size_t len)
    	{
    		assert(pos >= 0 && pos < _size);
    
    		if (pos + len >= _size)//如果删除元素个数  超过pos位置后剩余元素个数  全部删除  末尾（pos位置）给'\0'
    		{
    			_size = pos;
    			_data[_size] = '\0';
    		}
    		else
    		{
    			size_t start = pos + len;
    			for (; start <= _size; start++)//结尾的'\0'
    			{
    				_data[pos++] = _data[start];
    				//或者  写法如下：
    				//_data[start-len]=_data[start];
    				//start++;
    			}
    			_size -= len;
    		}
    	}

测试结果如下：

![9018ae8195077d32efca1555c2d4a871.png][]

![8744e6f6e3c6e36ffd5720b3f45a89ac.png][]

*  ### 类外重载+运算符，返回值为string类对象 ###

String operator+(const String& str1, const String& str2)
    {
    	String tmp;
    	tmp+=str1;
    	tmp+=str2;
    	return tmp;
    }
    
    String operator+(const String& str1, const char* str2)
    {
    	String tmp;  //通过默认构造函数  新对象值为 空字符串  连续两次添加即可 
    	tmp += str1;
    	tmp += str2;
    	return tmp;
    }
    
    String operator+(const String& str1, const char ch)
    {
    	String tmp(str1);//通过拷贝构造函数  使得创建的新对象值为拷贝参数对象值
    	tmp += ch;
    	return tmp;
    }

*  ### 重载输入输出运算符 ###

ostream& operator<<(ostream& out, String& str)
    {
    	for (auto& ch : str)
    	{
    		out << ch;
    	}
    	return out;
    }
    
    istream& operator>>(istream& in, String& str)
    {
    	char ch;
    	while (ch=getchar())
    	{
    		if (ch == ' ' || ch == '\t' || ch == '\n')
    			break;
    		str+=ch;
    	}
    	return in;
    }

*  ### 重载比较运算符 ###

bool operator<(const string& s)
    	{
    		int ret = strcmp(_data, s.c_str());
    		if (ret < 0)
    			return true;
    		else
    			return false;
    	}
    
    	bool operator>(const string& s)
    	{
    		int ret = strcmp(_data, s.c_str());
    		if (ret > 0)
    			return true;
    		else
    			return false;
    	}
    
    	bool operator<=(const string& s)
    	{
    		return !operator>(s);
    	}
    
    
    	bool operator>=(const string& s)
    	{
    		return !operator<(s);
    	}
    
    	bool operator==(const string& s)
    	{
    		int ret = strcmp(_data, s.c_str());
    		if (ret == 0)
    			return true;
    		else
    			return false;
    	}
    
    	bool operator!=(const string& s)
    	{
    		return !operator==(s);
    	}

*  ### 查找某一指定元素的位置 ###

查找某一字符采用一次遍历寻找的方式进行比较，查找字符串采用strstr函数获取子串起始地址，通过子串起始地址与字符串起始地址得到指针偏移量来获取位置索引

size_t find(const char& ch, size_t pos = 0)
    	{
    		for (size_t i = pos; i < _size; i++)
    		{
    			if (_data[i] == ch)
    			{
    				return i;
    			}
    		}
    		return npos;
    	}
    
    	size_t find(const char* str, size_t pos = 0)
    	{
    		char* ptr = strstr(_data, str);
    		if (ptr)
    		{
    			return ptr - _data;//指针偏移量 即为位置索引
    		}
    		return npos;
    	}

测试结果如下：如果找不到字符则返回nops（-1） 即也为最大值4G

![37b3199b18bed8cf43bf70c26b2dfe87.png][]

如果找到则返回该字符所在位置的索引

![d81f7f2f1f08b07bceda62c1631c9329.png][]

[c46c9d4251954a905b1a67991c167f2b.png]: /images/20221022/2f6033f96a7f4985b3c051018a8a25c9.png
[691a74c74ad254e84adf73a7b80581a9.png]: /images/20221022/7ac038f098ec4861a2033d5fb6103ba1.png
[6d70a7ba3c4e8dc726d56d69d8d51d2f.png]: /images/20221022/20e845ad4c094c8dbce7c2b6e2e3f12d.png
[b703b940d244d89bc4ea18f23c991c0f.png]: /images/20221022/1c6a255d79eb4184bfb9c114520fb17c.png
[e4d54997a00f21329a48265b1a69f3df.png]: /images/20221022/70e5b4ac1ce04fb1ad82bbe594eaee47.png
[bca28642ad6e0c28a00c70da320f297f.png]: /images/20221022/75f62ac489d04473b69483dfcf9b7f7a.png
[19b1d87ae74491a5acf97d4c6cbfb646.png]: /images/20221022/5d7c8d2349724dbd9b3dfecea9873540.png
[9018ae8195077d32efca1555c2d4a871.png]: /images/20221022/610482a279674dde8daaf55151fe8a64.png
[8744e6f6e3c6e36ffd5720b3f45a89ac.png]: /images/20221022/a2e4466965684655878d060947ed8c85.png
[37b3199b18bed8cf43bf70c26b2dfe87.png]: /images/20221022/216bc5d3613b4231ada5c1bef5bd99fa.png
[d81f7f2f1f08b07bceda62c1631c9329.png]: /images/20221022/fece4223abee4102910e468052fa98f7.png