C++ STL string类模拟实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了C++ STL string类模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

string类成员变量

一.构造函数

二.析构函数

三.拷贝构造

四.size(),capacity()

五.operator [ ]

六. operator =

七.字符串比较

八.reserve（）

九.push_back（），append（）

十.operator+=

十一.insert（）

十二.迭代器

十二.erase（）

十三.swap（）

十四.find（）

十五.流提取，流输出

十六.对比库string和我们的String

上期我们已经对string类进行了简单的介绍，大家只要能够正常使用即可。在面试中，面试官总喜欢让学生自己来模拟实现string类，最主要是实现string类的构造、拷贝构造、赋值运算符重载以及析构函数。同时模拟实现string类对我们自身对类与对象的理解由进一步的提高。

string类成员变量

对于一个String类要有基本的存储体，和存储字符个数，还有存储容量。

class String
{
public:
    //成员函数
private:
	char* _str;   //存储字符串
	int _size;    //字符个数
	int _capacity;//容量
    static const size_t npos = -1;
};

一.构造函数

在实现构造函数的时候，我们需要知道一般一个类要有一个默认构造函数，同时string类也要支持常量字符串初始化。

	//默认构造函数
    String()
		:_str(new char[1]),_size(0),_capacity(0)
	{
		_str[0] = '\0';
	}
    //支持常量字符串初始化
	String(const char* str)
		:_size(strlen(str))
	{
		_capacity = _size == 0 ? 3 : _size;
		_str = new char[_capacity + 1];//在实际开辟空间的时候，多开一个字节，用于存储‘\0’
		strcpy(_str, str);
	}

这然写当然是没有问题的，但是其实还有更好的写法：


	//既是默认构造，又能接收常量字符串构造
	String(const char* str = "")
		:_size(strlen(str))
	{
		_capacity = _size == 0 ? 3 : _size;
		_str = new char[_capacity+1];//在实际开辟空间的时候，多开一个字节，用于存储‘\0’
		//将str数据拷贝到_str里
		strcpy(_str, str);
	}

注意：在设置_capacity时候，如果刚开始的时候，容量尽量不要是0。以免后面在进行倍数扩容是出现不必要的麻烦和判断。

二.析构函数

析构函数没有什么好介绍的大家直接看吧

    ~String()
	{
		delete[] _str;
		_size = _capacity = 0;
 	}

注意：虽然我们不写析构函数，编译器自己也会生成一个析构函数，但是今天这里编译器自己生成的不靠谱，因为我们由需要释放申请的堆空间。如果我们不去写那就会造成内存泄漏。

三.拷贝构造

拷贝构造就是使用一个已经有的String对象来初始化另一个String对象。

当然如果我们不写编译器也会自动生成一个，但是生成的这一个也是不靠谱的，因为编译器生成的只会做浅拷贝。

C++ STL string类模拟实现,C++,c++,开发语言

注意：显然底层的_str 地址是一样的，那么就会导致对其中一个的操作必然会影响到另外一个。而且析构的时候会对同一块空间释放两次，导致出现出现一些内存问题。

深拷贝：

	//拷贝构造:使用一个已经有的String对象来初始化另一个String对象。
	//1.注意深拷贝
	String(const String& s)
	{
		_capacity = s._capacity;
		_size = s._size;
        //深拷贝重新开的空间
		_str = new char[_capacity+1];
		strcpy(_str, s._str);
	}

C++ STL string类模拟实现,C++,c++,开发语言

底层存储的地址不同，自然两者不再有任何影响。

四.size(),capacity()

一个String由对字符个数（长度）的管理，由于在类里面是私有成员，我们就要提供成员函数以供外部获取，也不能让外部修改——返回值const。针对普通对象和 const 对象分别提供。

	//普通对象调用
    const int size() 
	{
		return _size;
	}

    const int capacity() 
	{
		return _capacity;
	}
    
    
    //const对象调用
    const int size() const
	{
		return _size;
	}

	const int capacity() const
	{
		return _capacity;
	}

五.operator [ ]

[ ]运算符的重载是使得String类能够像数组一样去访问字符串的每一个成员字符。在重载时针对const 对象也要有考虑。考虑到越界的检查。

	//operator[]普通对象调用
	char& operator[](const int index)
	{
		assert(index >= 0 && index < _size);
		return _str[index];
	}
	//operator[] const 对象调用,且不允许修改
	const char& operator[](const int index) const
	{
		assert(index >= 0 && index < _size);
		return _str[index];
	}

C++ STL string类模拟实现,C++,c++,开发语言

六. operator =

operator=重载赋值运算符，是使用一个已经有的String对象赋值给另一个String对象。这里我们需要考虑，左操作数容量的大小。如果左操作数容量足够还好，就算多了也即是浪费一点空间的问题，不够就会很麻烦，需要扩容。所以为了设计简单，无论左操作数容量是否足够，我们都直接重新开空间。


	// operator=重载赋值运算符
	void operator=(const String& s)
	{
		char* tmp = new char[s.capacity() + 1];
		_size = s.size();
		_capacity = s.capacity();
		strcpy(tmp, s._str);
		delete[] _str;
		_str = tmp;
	}

C++ STL string类模拟实现,C++,c++,开发语言

连续赋值，我们得operator[]返回值就要是赋值的左操作数本身。

	// operator=重载赋值运算符
	String& operator=(const String& s)
	{
		if (this != &s)//str=str时无需多余的运算
		{
			char* tmp = new char[s.capacity() + 1];
			_size = s.size();
			_capacity = s.capacity();
			strcpy(tmp, s._str);
			delete[] _str;
			_str = tmp;
			return *this;
		}
    }

C++ STL string类模拟实现,C++,c++,开发语言

注意：

这里不可以使用realloc来扩容，因为我们使用new来开辟的空间，直接new新的空间进行拷贝。

我们要尽量先将数据拷贝到临时的tmp里，再将_str释放掉，如果使用首先将_str释放了，如果在new的结果出现差错，就会触发异常，导致原数据丢失。而且如果面对同一个对象相互赋值时也会出现同样的问题。

七.字符串比较

字符串比较我们只需要实现一个等于，和大于或者小于，其他的直接复用。

//相等
	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);
	}
	//小于等于
	bool operator<=(const String& s)const
	{
		return  *this == s || *this < s;
	}
	//大于
	bool operator>(const String& s)const
	{
		return  !( * this == s || *this < s);
	}
	//大于等于
	bool operator>=(const String& s)const
	{
		return  *this == s || *this > s;
	}

八.reserve（）

重新设置容量，我们采取的方案也是，重新开空间，拷贝原来的数据。

	//重新设置容量
	void reserve(size_t capacity)
	{
		if (capacity > _capacity)//不允许容量的缩减
		{
			char* tmp = new char[capacity + 1];
			_capacity = capacity;
			strcpy(tmp, _str);
			delete[] _str;
			_str = tmp;
		}
	}

注意：可以使得容量变大，但是一般不允许容量减小。

九.push_back（），append（）

push_back 尾部插入一个字符，append（）尾部插入一个字符串。注意每次进行插入，都需要容量判断，以保证正常的插入。

//重新设置容量
	void reserve(int capacity)
	{
		char* tmp = new char[capacity + 1];
		_capacity = capacity;
		strcpy(tmp, _str);
		delete[] _str;
		_str = tmp;
	}

	void push_back(char ch)
	{
		//容量不足时
		if (_size + 1 >= _capacity)
		{
			reserve(_capacity * 2);
		}
		_str[_size++] = ch;
		_str[_size] = '\0';
	}

	void append(const char* s)
	{
        容量不足时
		int len = strlen(s);
		if (len + _size >= _capacity)
		{
			reserve(_capacity + len);
		}
		strcpy(_str + _size, s);
		_size += len;
	}

注意：

append的扩容，不能采取2倍扩容。因为有可能插入的字符串本身长度就超过了原容量的二倍。

十.operator+=

可以+=一个字符，或者+=一个字符串，或者+=一个String对象。运算符重载+=的效果和append和push_back基本一致，但是用起来的感觉却大不相同。这里我们复用append和push_back。

    String& operator+=(char ch)
	{
		push_back(ch);
		return *this;
	}

	String& operator+=(const char* s)
	{
		append(s);
		return *this;
	}

	String& operator+=(const String& s )
	{
		append(s._str);
		return *this;
	}

C++ STL string类模拟实现,C++,c++,开发语言

十一.insert（）

insert支持在 index 位置插入一个字符，插入一个字符串。

    void insert(size_t index, char ch)
	{
		//判断位置是否合法
		assert(index >= 0 && index < _size);
		//判断是否需要扩容
		if (_size + 1 >= _capacity)
		{
			reserve(_capacity * 2);
		}
		//挪动数据
		int end = _size+1;//end=_size+1,将‘\0’一起拷进去。
		//注意:这里的end时int，index是size_t类型，进行比较的时候
		//会发生类型提升，int --> size_t,当index=0，循环结束的条件是end为-1，
		// 但是由于类型提升，end实际在比较的时候的值是一个很大的数。因此仍会进入循环。
		//int end = _size;
		//while (end >= index)
		//{
		//	_str[end + 1] = _str[end];
		//}
		//如果我们代码这样写就会避免当index=0时，end的结束条件是-1。
		while (end >= index+1)
		{
			_str[end] = _str[end - 1];
			end--;
		}
		//插入数据ch	
		_str[index] = ch;
		_size++;
	}

	void insert(size_t index, const char* str)
	{
		//判断位置是否合法
		assert(index >= 0 && index < _size);
		int len = strlen(str);
		if (len + _size >= _capacity)
		{
			reserve(_capacity + len);
		}
		//挪动数据
		int end = _size+len;
		while (end >= index + len)
		{
			_str[end] = _str[end-len];
			end--;
		} 
		//插入数据
		int j = 0;
		for (int i = index; i < index + len; i++)
		{
			_str[i] = str[j++];
		}
		_size += len;
		
	}

C++ STL string类模拟实现,C++,c++,开发语言

十二.迭代器

string的迭代器，底层就是指针。迭代器提供了一种通用的遍历容器的手段。

	typedef char* iterator;
	typedef const char* const_iterator;
    //普通对象调用
	iterator begin()
	{
        //返回字符数组的第一个位置
		return _str;
	}
	iterator end()
	{
        //返回字符数组最后一个字符的下一个位置，与begin形成前闭后开。
		return _str + _size;
	}

    //const 对象调用，返回值const_iterator-->const char*
	const_iterator begin()const
	{
		return _str;
	}
	const_iterator end()const
	{
		return _str + _size;
	}

注意：

const_iterator-->const char* 迭代器，迭代器本身可以修改，但是迭代器所指向的内容不允许修改。

范围for的底层即使借助了迭代器实现遍历的。

C++ STL string类模拟实现,C++,c++,开发语言

十二.erase（）

erase支持从某一个位置开始删除后面的len个字符。


	//删除pos位置之后的len个字符
	void erase(size_t pos, size_t len = npos)
	{
		assert(pos >= 0 && pos < _size);
		if (pos + len > _size || len == npos)
		{
			_str[pos] = '\0';
			_size = pos;
			return;
		}
		//1.挪动数据
		strcpy(_str + pos, _str + pos + len);
		//2.挪动数据
		//int index = pos;
		//while (index + len < _size)
		//{
		//	_str[index] = _str[index + len];
		//	index++;
		//}
		_size -= len;
	}

注意：erase仅仅只是删除字符，减少了字符串的长度，但是并不会影响到容量的。

十三.swap（）

string类自己也提供了一个，swap交换函数。上期我们在介绍string接口的时候也是介绍了这个接口，还特意提到了，string提供的swap要比std的swap效率高的多。

	//string提供的
    void swap(String &str)
	{
		std::swap(_size, str._size);
		std::swap(_capacity, str._capacity);
		std::swap(_str, str._str);
	}


    //std提供的交换函数
    template<class T>
    void swap(T& e1,T& e2)
    {
	    T tmp = e1;
	    e1 = e2;
        e2 = tmp;
    }

注意：string提供的swap之所以效率要比std提供的高，因为string提供的是一个类的成员函数，仅仅做类的私有成员变量的交换就可以了。而std提供的swap函数，是一个全局函数，交换的过程需要经过三次深拷贝。

十四.find（）

是string提供了从字符串中的某一位置开始查找一个字符，和查找字符串的功能。

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

	size_t find(const char* str, size_t pos = 0)
	{
		assert(pos < _size);
		char* pindex = strstr(_str + pos, str);
		if (pindex == nullptr)
		{
			return npos;
		}
		else
		{
			return pindex - _str;
		}
	}

注意：strstr就是一个查找字串的函数，底层是一个暴力的查找算法。找到字串返回字串的手字符地址，没找到就返回nullptr。我们仅仅只要用的字串首字符地址，减去存储的首地址就是中间间隔的字符数，也就是找到的字串首字符的下标。

十五.流提取，流输出

//1.重载流输入
istream& operator>>(istream& in, String& str)
{
	str.clear();
	char ch = in.get();
	while (ch != ' ' && ch != '\n')
	{
		str.push_back(ch);
		ch = in.get();
	}

	return in;
}
//2.重载流输入
istream& operator>>(istream& in, String& str)
{
	str.clear();
	char buffer[128];
	char ch = in.get();
	int i = 0;
	while (ch != ' ' && ch != '\n')
	{
		buffer[i++] = ch;
		if (i == 127)
		{
			buffer[i] = '\0';
			str += buffer;
			i = 0;
		}
		ch = in.get();
	}
	if (i != 0)
	{
		buffer[i] = '\0';
		str += buffer;
	}

	return in;
}

//重载流输出
ostream& operator<<(ostream& out,const String& str)
{
	for (auto e : str)
	{
		cout << e;
	}
	return out;
}

C++ STL string类模拟实现,C++,c++,开发语言

注意：流插入选取一个就可以，第一种实现的容易产生容量的浪费，第二种加入一个缓冲区，对容量利用更好。

十六.对比库string和我们的String

C++ STL string类模拟实现,C++,c++,开发语言

我们能够看到，库里面的string要比我们的多16字节。这是因为库里面的string多包涵了一个16字节的字符数组。当我们存储的字符串小于16字节时，就直接存储在数组中。如果大于了16字节，再向堆上开辟空间存储。

//std库中实现的string类私有成员变量
class string
{
public:
	//....
private:
	char* _str;
	size_t _size;
	size_t _capacity;
	char __str[16];
};

在g++中的实现方式也是不一样。在g++中除了必要的长度，容量，指针以外还会有一个引用计数。

//g++下string类私有成员
class string
{
public:
	//...
private:
	char* _str;
	size_t _size;
	size_t _capacity;
	size_t _refcount;//引用计数
};

在拷贝时，g++下不会首先使用深拷贝，而是首先使用浅拷贝，并且引用计数加一。只有其中一个对象发生写入改变时才会开辟新的空间进行深拷贝，我们称这种机制也叫做，写时拷贝。这种机制普遍存在linux中，一定程度上可以节省空间和提升效率。文章来源地址https://www.toymoban.com/news/detail-634358.html

十七.完整代码示例

#pragma once
#include<cstring>
#include<iostream>
#include<cassert>
using namespace std;

//g++下string类私有成员
class string
{
public:
	//...
private:
	char* _str;
	size_t _size;
	size_t _capacity;
	size_t _refcount;//引用计数
};
class string
{
	//....
private:
	char* _str;
	size_t _size;
	size_t _capacity;
	char __str[16];
};

class String
{
public:
	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;
	}

	//既是默认构造，又能接收常量字符串构造
	String(const char* str = "")
		:_size(strlen(str))
	{
		_capacity = _size == 0 ? 3 : _size;
		_str = new char[_capacity+1];//在实际开辟空间的时候，多开一个字节，用于存储‘\0’
		//将str数据拷贝到_str里
		strcpy(_str, str);
	}

	//拷贝构造:使用一个已经有的String对象来初始化另一个String对象。
	//1.注意深拷贝
	String(const String& s)
	{
		_capacity = s._capacity;
		_size = s._size;
		_str = new char[_capacity+1];
		strcpy(_str, s._str);
	}

	//operator[]普通对象调用
	char& operator[](const size_t index)
	{
		assert(index >= 0 && index < _size);
		return _str[index];
	}
	//operator[] const 对象调用,且不允许修改
	const char& operator[](const size_t index) const
	{
		assert(index >= 0 && index < _size);
		return _str[index];
	}
	
	// operator=重载赋值运算符
	String& operator=(const String& s)
	{
		if (this != &s)//str=str时无需多余的运算
		{
			//注意：这里不可以使用realloc来扩容，因为我们使用new来开辟的空间，直接new新的空间进行拷贝。
			//细节：我们要尽量先将数据拷贝到临时的tmp里，再将_str释放掉，如果使用首先将_str释放了，
			//如果在new的结果出现差错，就是出发异常，导致原数据丢失。
			char* tmp = new char[s.capacity() + 1];
			_size = s.size();
			_capacity = s.capacity();
			strcpy(tmp, s._str);
			delete[] _str;
			_str = tmp;
			return *this;
		}
	}
	//重新设置容量
	void reserve(size_t capacity)
	{
		if (capacity > _capacity)//不允许容量的缩减
		{
			char* tmp = new char[capacity + 1];
			_capacity = capacity;
			strcpy(tmp, _str);
			delete[] _str;
			_str = tmp;
		}
	}

	void push_back(char ch)
	{
		//容量不足时
		if (_size + 1 >= _capacity)
		{
			reserve(_capacity * 2);
		}
		_str[_size++] = ch;
		_str[_size] = '\0';
	}

	void append(const char* s)
	{
		int len = strlen(s);
		if (len + _size >= _capacity)
		{
			reserve(_capacity + len);
		}
		strcpy(_str + _size, s);
		_size += len;
	}

	String& operator+=(char ch)
	{
		push_back(ch);
		return *this;
	}

	String& operator+=(const char* s)
	{
		append(s);
		return *this;
	}

	String& operator+=(const String& s )
	{
		append(s._str);
		return *this;
	}

	void insert(size_t index, char ch)
	{
		//判断位置是否合法
		assert(index >= 0 && index < _size);
		//判断是否需要扩容
		if (_size + 1 >= _capacity)
		{
			reserve(_capacity * 2);
		}
		//挪动数据
		int end = _size+1;
		//注意:这里的end时int，index是size_t类型，进行比较的时候
		//会发生类型提升，int --> size_t,当index=0，循环结束的条件是end为-1，
		// 但是由于类型提升，end实际在比较的时候的值是一个很大的数。因此仍会进入循环。
		//int end = _size;
		//while (end >= index)
		//{
		//	_str[end + 1] = _str[end];
		//}
		//如果我们代码这样写就会避免当index=0时，end的结束条件是-1。
		while (end >= index+1)
		{
			_str[end] = _str[end - 1];
			end--;
		}
		//插入数据ch	
		_str[index] = ch;
		_size++;
	}

	void insert(size_t index, const char* str)
	{
		//判断位置是否合法
		assert(index >= 0 && index < _size);
		int len = strlen(str);
		if (len + _size >= _capacity)
		{
			reserve(_capacity + len);
		}
		//挪动数据
		int end = _size+len;
		while (end >= index + len)
		{
			_str[end] = _str[end-len];
			end--;
		} 
		//插入数据
		int j = 0;
		for (int i = index; i < index + len; i++)
		{
			_str[i] = str[j++];
		}
		_size += len;
		
	}

	//删除pos位置之后的len个字符
	void erase(size_t pos, size_t len = npos)
	{

		assert(pos >= 0 && pos < _size);
		if (pos + len > _size || len == npos)
		{
			_str[pos] = '\0';
			_size = pos ;
			return;
		}
		//1.挪动数据
		strcpy(_str + pos, _str + pos + len);
		//2.挪动数据
		//int index = pos;
		//while (index + len < _size)
		//{
		//	_str[index] = _str[index + len];
		//	index++;
		//}
		_size -= len;
	}

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

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

	size_t find(const char* str, size_t pos = 0)
	{
		assert(pos < _size);
		char* pindex = strstr(_str + pos, str);
		if (pindex == nullptr)
		{
			return npos;
		}
		else
		{
			return pindex - _str;
		}
	}

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


	//相等
	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);
	}
	//小于等于
	bool operator<=(const String& s)const
	{
		return  *this == s || *this < s;
	}
	//大于
	bool operator>(const String& s)const
	{
		return  !( * this == s || *this < s);
	}
	//大于等于
	bool operator>=(const String& s)const
	{
		return  *this == s || *this > s;
	}

	const size_t size() 
	{
		return _size;
	}

	const size_t size() const
	{
		return _size;
	}

	const size_t capacity() const
	{
		return _capacity;
	}

	const size_t capacity()
	{
		return _capacity;
	}

	const char* c_str()
	{
		return _str;
	}

	~String()
	{
		delete[] _str;
		_size = _capacity = 0;
 	}



private:
	char* _str;
	size_t _size;
	size_t _capacity;
	static const size_t npos = -1;
};

//重载流输出
ostream& operator<<(ostream& out,const String& str)
{
	for (auto e : str)
	{
		cout << e;
	}
	return out;
}

1.重载流输入
//istream& operator>>(istream& in, String& str)
//{
//	str.clear();
//	char ch = in.get();
//	while (ch != ' ' && ch != '\n')
//	{
//		str.push_back(ch);
//		ch = in.get();
//	}
//
//	return in;
//}
//2.重载流输入
istream& operator>>(istream& in, String& str)
{
	str.clear();
	char buffer[128];
	char ch = in.get();
	int i = 0;
	while (ch != ' ' && ch != '\n')
	{
		buffer[i++] = ch;
		if (i == 127)
		{
			buffer[i] = '\0';
			str += buffer;
			i = 0;
		}
		ch = in.get();
	}
	if (i != 0)
	{
		buffer[i] = '\0';
		str += buffer;
	}

	return in;
}

//std提供的交换函数
template<class T>
void swap(T& e1,T& e2)
{
	T tmp = e1;
	e1 = e2;
	e2 = tmp;
}

到了这里，关于C++ STL string类模拟实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！