C++ STL-string类底层实现过程

目录

• 实现框架
• 一、默认成员函数
• 1.默认构造函数
• 2.构造函数
• 3.拷贝构造函数(重点)
• 4.赋值运算符重载函数
• 5.析构函数
• 二、迭代器相关函数
• begin和end
• 三、容量和大小相关函数
• size和capacity
• reserve和resize
• 四、与修改字符串相关的函数
• push_back
• append
• operator+=
• insert
• erase
• clear
• swap
• 五、访问字符串相关函数
• operator[ ]
• c_str
• 小知识点- npos
• find函数
• substr函数
• 六、关系运算符重载函数
• >、>=、<、<=、==、!=
• >>和<<运算符的重载
• 总结

实现框架

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

namespace lzg
{
	class string
	{
	public:
		//typedef char* iterator;
		using iterator = char*;
		using const_iterator = const char*;

		//一、默认成员函数
		string(const char* str = "");       //默认构造
		string(const string& s);            //拷贝构造
		string& operator=(const string& s); //赋值重载
		~string();                          //析构函数
		
		//二、迭代器相关函数
		iterator begin()
		{
			return _str;
		}
		iterator end()
		{
			return _str + _size;
		}
		const_iterator begin() const
		{
			return _str;
		}
		const_iterator end() const
		{
			return _str + _size;
		}

		//三、容量和大小相关函数
		void reserve(size_t n);
		size_t size() const
		{
			return _size;
		}
		size_t capacity() const
		{
			return _capacity;
		}
		void resize(size_t n, char ch = '\0');

		//四、与修改字符串相关的函数
		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);
		void erase(size_t pos, size_t len = npos);
		void clear()
		{
			_str[0] = '\0';
			_size = 0;
		}
		
		//五、访问字符串相关函数
		char& operator[](size_t i)
		{
			assert(i < _size);

			return _str[i];
		}

		const char& operator[](size_t i) const
		{
			assert(i < _size);

			return _str[i];
		}
		const char* c_str() const
		{
			return _str;
		}
		size_t find(char ch, size_t pos = 0);
		size_t find(const char* str, size_t pos = 0);
		string substr(size_t pos, size_t len = npos);
	
	private:
		char* _str = nullptr;
		size_t _size = 0;
		size_t _capacity = 0;

	public:
		static const size_t npos;
	};
	//六、关系运算符重载函数
	bool operator== (const string& lhs, const string& rhs);
	bool operator!= (const string& lhs, const string& rhs);
	bool operator> (const string& lhs, const string& rhs);
	bool operator< (const string& lhs, const string& rhs);
	bool operator>= (const string& lhs, conswww.devze.comt string& rhs);
	bool operator<= (const string& lhs, const string& rhs);

	ostream& operator<<(ostream& os, const string& str);
	istream& operator>>(istream& is, string& str);
}

一、默认成员函数

1.默认构造函数

string()
	:_str(new char[1] {'\0'}),
	_size(0),
	_capacity(0)
{}

为_str开辟1字节空间来存放'\0'_capacity不记录\0的大小，这样调用c_str()就不会报错

2.构造函数

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

注意在private中的声明顺序，这里初始化列表只走_size(大小为str的长度)，让_str和_capacity在函数体内初始化(这样保证了不会出错，比如三者都在初始化列表的话，会先初始化_str这样有风险)，同样的，_str开辟空间时，为'\0'多开辟1字节

构造函数有一个默认构造就行了，写1个就行，把1注释掉，并把2改为全缺省

string(const char* str="")//不要写成" "这是非空
	:_size(strlen(str))
{
	_capacity = _size;
	_str = new char[_size + 1];
	strcpy(_str, str);
}

3.拷贝构造函数(重点)

在模拟实现拷贝构造函数前，我们应该首先了解深浅拷贝：

我们不写拷贝构造，编译器默认生成的拷贝构造是值拷贝也叫浅拷贝

• 浅拷贝：拷贝出来的目标对象的指针和源对象的指针指向的内存空间是同一块空间。其中一个对象的改动会对另一个对象造成影响。
• 深拷贝：深拷贝是指源对象与拷贝对象互相独立。js其中任何一个对象的改动不会对另外一个对象造成影响。

很明显，我们并不希望拷贝出来的两个对象之间存在相互影响，因此，我们这里需要用到深拷贝。

	//s2(s1)             s1
	string(const string& s)
	{
		_str = new char[s._capacity + 1];
		strcpy(_str, s._str);
		_capacity = s._capacity;
		_size = s._size;

	}

这里还有一个现代(偷懒)写法

string(const string& s)
	{
		string tmp(s._str);
		swap(tmp);
	}

现代写法与传统写法的思想不同：先构造一个tmp对象，然后再将tmp对象与拷贝(s)对象的数据交换即可。

4.赋值运算符重载函数

与拷贝构造函数类似，赋值运算符重载函数的模拟实现也涉及深浅拷贝问题，我们同样需要采用深拷贝

再强调一下赋值和拷贝的区别，赋值是两个已创建的对象之间完成赋值操作，拷贝是指一个已创建的对象调用拷贝构造生成一个新的对象

// s1 = s3                      s3
string& operator=(const string& s)
{
	if (this != &s)//避免自己给自己赋值
	{
		delete[] _str;  //释放掉s1的旧空间，开辟一个和s3容量的新空间
		_str = new char[s._capacity + 1];
		strcpy(_str, s._str);
		_size = s._size;
		_capacity = s._capacity;
	}

	return *this;
}

同样的赋值也有现代写法

// 现代写法
	// s1 = s3
	string& operator=(string s)
	{
		swap(s);
		return *this;
	}

赋值运算符重载函数的现代写法是通过采用“值传递”接收右值的方法，让编译器自动调用拷贝构造函数，然后我们再将拷贝出来的对象与左值进行交换即可

5.析构函数

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

二、迭代器相关函数

string类中的迭代器实际上就是字符指针，只是给字符指针起了一个别名叫iterator而已。

typedef char* iterator;
typedef const char* const_iterator;

begin和end

iterator begin()
{
	return _str; //返回字符串中第一个字符的地址
}

const_iterator begin()const
{
	return _str; //返回字符串中第一个字符的const地址
}

iterator end()
{
	return _str + _size; //返回字符串中最后一个字符的后一个字符的地址
}

const_iterator end()const
{
	return _str + _size; //返回字符串中最后一个字符的后一个字符的const地址
}

其实范围for的底层就是调用了begin()和end()迭代器，当你模拟实现了迭代器，范围for自然就能使用

string s("hello world!!!");
//编译器将其替换为迭代器形式
for (auto e : s)
{
	cout << e << " ";
}
cout << endl;

注：自己写的begin()和end()函数名必须是这样的，不能有任何大小写否则范围for就报错

三、容量和大小相关函数

size和capacity

因为string类的成员变量是私有的，我们并不能直接对其进行访问，所以string类设置了size和capacity这两个成员函数，用于获取string对象的大小和容量。

size函数用于获取字符串当前的有效长度（不包括’\0’）。

size_t size() const
{
	return _size;
}

capacity函数用于获取字符串当前的容量。（不包括’\0’）。

size_t capacity() const
{
	return _capacity;
}

reserve和resize

reserve和resize这两个函数的执行规则一定要区分清楚。

reserve规则：

• 1、当n大于对象当前的capacity时，将capacity扩大到n或大于n。
• 2、当n小于对象当前的capacity时，什么也不做。

void reserve(size_t n)
{
	if (n > _capacity)
	{
		char* tmp = new char[n + 1];//多开一个空间用于存放'\0'
		strcpy(tmp, _str);
		delete[] _str;

		_str = tmp;
		_capacity = n;

	}
}

resize规则：

• 1、当n大于当前的size时，将size扩大到n，扩大的字符为ch，若ch未给出，则默认为’\0’。
• 2、当n小于当前的size时，将size缩小到n。

//改变大小
void resize(size_t n, char ch = '\0')
{
	if (n <= _size) 
	{
		_size = n; 
		_str[_size] = '\0'; 
	}
	else 
	{
		if (n > _capacity) 
		{
			reserve(n); 
		}
		for (size_t i = _size; i < n; i++) 
		{
			_str[i] = ch;
		}
		_size = n; 
		_str[_size] = '\0'; 
	}
}

四、与修改字符串相关的函数

push_back

void push_back(char c)
{
	if (_size == _capacity)
	{
		reserve(_capacity == 0 ? 4 : 2 * _capacity);
	}
	_str[_size] = c;    // 在结尾位置写入新字符（覆盖原'\0'）
    _size++;            // 增加长度
    _str[_size] = '\0'; // 在新结尾补终止符
}

实现push_back还可以直接复用下面即将实现的insert函数。

//尾插字符
void push_back(char ch)
{
	insert(_size, ch); //在字符串末尾插入字符ch
}

append

//尾插字符串
void append(const char* str)
{
	size_t len = strlen(str);
	if (_size + len > _capacity)
	{
		size_t newCapacity = 2 * _capacity;
		// 扩2倍不够，则需要多少扩多少
		if (newCapacity < _size + len)
			newCapacity = _size + len;
		reserve(newCapacity);
	}//避免尾插字符串时如果字符串大于二倍_capacity时的多次扩容

	strcpy(_str + _size, str);
	_size += len;
}

operator+=

• +=运算符的重载是为了实现字符串与字符、字符串与字符串之间能够直接使用+=运算符进行尾插。
• +=运算符实现字符串与字符之间的尾插直接调用push_back函数即可。

//+=运算符重载
string& operator+=(char ch)
{
	push_back(ch); //尾插字符串
	return *this; //返回左值（支持连续+=）
}

+=运算符实现字符串与字符串之间的尾插直接调用append函数即可。

//+=运算符重载
string& operator+=(const charcjekX* str)
{
	append(str); //尾插字符串
	return *this; //返回左值（支持连续+=）
}

insert

insert函数的作用是在字符串的任意位置插入字符或是字符串。

void insert(size_t pos, char ch);
void intsert(size_t pos,const char* str);

void intsert(size_t pos, char ch)
{
	if (_size == _capacity)
	{
		reserve(_capacity == 0 ? 4 : 2 * _capacity);
	}
	size_t end = _size;
	while (end >=(int)pos)
	{
		_str[end + 1] = _str[end];
		end--;
	}
	_str[pos] = ch;
	_size++;
}

insert函数插入字符串时也是类似思路

void intsert(size_t pos, const char* str)
{
	size_t len = strlen(str);
	if (_size + len > _capacity)
	{
		size_t newCapacity = 2 * _capacity;
		// 扩2倍不够，则需要多少扩多少
		if (newCapacity < _size + len)
			newCapacity = _size + len;
		reserve(newCapacity);
	}
	size_t end = _size + len;
	while (end > pos + len - 1)
	{
		_str[end] = _str[end - len];
		--end;
	}

	for (size_t i = 0; i < len; i++)
	{
		_str[pos + i] = str[i];
	}

	_size += len;
}

erase

erase函数的作用是删除字符串任意位置开始的n个字符。

void erase(size_t pos, size_t len)
{
	assert(pos < _size);
	if (len >= _size - pos)
	android{
		_str[pos] = '\0';
		_size = pos;
	}
	else
	{   //从后往前挪
		size_t end = pos + len;
		while (end <= _si编程ze)
		{
			_str[end-len] = _str[end];//覆盖pos及后len长度的值，完成删除
			end++;
		}
		_size -= len;
	}
}

clear

clear函数用于将对象中存储的字符串置空，实现时直接将对象的_size置空，然后在字符串后面放上’\0’即可

//清空字符串
void clear()
{
	_size = 0; //size置空
	_str[_size] = '\0'; //字符串后面放上'\0'
}

swap

有三个swap，有两个是string里的swap函数，另外一个是算法库的swap函数

std::swap
template <class T> void swap (T& a, T& b);
std::string::swap

void swap (string& str);
void swap (string& x,sring& y);

算法库中的swap也能交换自定义类型，但代价非常大

我们自己实现swap完全不用这么复杂，直接把s1、s2指针及数据交换一下就行了

//交换两个对象的数据
void swap(string& s)
{
	//调用库里的swap
	::swap(_str, s._str); //交换两个对象的C字符串
	::swap(_size, s._size); //交换两个对象的大小
	::swap(_capacity, s._capacity); //交换两个对象的容量
}

还有一个swap存在的意义是什么呢？

void swap(string& s1,string& s2)
{
    s1.swap(s2);
}

这样在类外面调用swap函数时就不会调到算法库的swap函数了(模板实例化会走上面的swap函数)

五、访问字符串相关函数

operator[ ]

[ ]运算符的重载是为了让string对象能像C字符串一样，通过[ ] +下标的方式获取字符串对应位置的字符。

//[]运算符重载（可读可写）
char& operator[](size_t i)
{
	assert(i < _size); //检测下标的合法性
	return _str[i]; //返回对应字符
}

在某些场景下，我们可能只能用[ ] +下标的方式读取字符而不能对其进行修改。

例如，对一个const的string类对象进行[ ] +下标的操作，我们只能读取所得到的字符，而不能对其进行修改。所以我们需要再重载一个[ ] 运算符，用于只读操作。

//[]运算符重载（可读可写）
const  char& operator[](size_t i)const
{
	assert(i < _size); //检测下标的合法性
	return _str[i]; //返回对应字符
}
		

c_str

c_str函数用于获取对象C类型的字符串

//返回C类型的字符串
const char* c_str()const
{
	return _str;
}

小知识点- npos

在 C++ 标准库中，​npos​ 是一个特殊的静态常量成员，主要用于表示“无效位置”或“未找到”的状态

注：只有整形才能在声明中定义

static const size_t npos=-1;

 ​核心用途

(1) ​查找函数失败时的返回值

std::string str = "Hello";
size_t pos = str.find('x');  // 查找不存在字符
if (pos == std::string::npos) {  // 必须用 npos 检查
    std::cout << "Not found!";
}

(2) ​表示“直到字符串末尾”​

std::string sub = str.substr(2, std::string::npos);  // 从索引2到末尾

特性

• ​无符号值​：由于是 size_t类型，避免直接与 -1比较，而应使用 npos。•
• ​足够大​：其值（如 18446744073709551615）保证不会与任何有效索引冲突。

find函数

• find函数是用于在字符串中查找一个字符或是字符串
• find函数：正向查找即从字符串开头开始向后查找

1、正向查找第一个匹配的字符。

size_t find(char ch,size_t pos=0)
{
	//默认从首字符开始查找
	assert(pos<_size);
	for (size_t i = pos; i < _size; i++)
	{
		if (_str[i] == ch)
		{
			return i;
		}
				
	}
	//找不到返回npos
	return npos;
}

2、正向查找第一个匹配的字符串。

这里用到了一个strstr函数

char * strstr (char * str1, const char * str2 );

返回指向 str1 中第一次出现的 str2 的指针，如果 str2 不是 str1 的一部分，则返回空指针。

size_t find(const char* str, size_t pos = 0)
{
	assert(pos < _size);
	const char* ptr = strstr(_str, str);
	if (ptr)//如果找到了
	{
		return ptr - _str;  //下标
	}
	else //为空
	{
		return npos;
	}
}

substr函数

substr函数用来取字符串中的子字符串，位置和长度由自己决定

默认从首字符取，默认取的长度是取到尾

string substr (size_t pos = 0, size_t len = npos) const；

调用拷贝构造，返回pos位后len长度的字符串

string substr(size_t pos, size_t len)
{
	assert(pos < _size);
	//len长度足够大就直接取到尾
	if (len > _size - pos)
	{
		len = _size - pos;
	}
	string sub;
	sub.reserve(len);
	for (size_t i = pos;i < len; i++)
	{
		sub += _str[pos + i];
	}

	return sub;
}

六、关系运算符重载函数

>、>=、<、<=、==、!=

关系运算符有 >、>=、<、<=、==、!= 这六个，但是对于C++中任意一个类的关系运算符重载，我们均只需重载其中的两个，剩下的四个关系运算符可以通过复用已经重载好了的两个关系运算符来实现。

例如，对于string类，我们可以选择只重载 < 和 == 这两个关系运算符。

注：重载在类外面，命名域例：lzg里。这样操作数就不用限定死是string类的

• ​lhs​：代表 ​Left-Hand ​Side (左侧操作数/左侧值)
• ​rhs​：代表 ​Right-Hand ​Side (右侧操作数/右侧值)

//==运算符重载
bool operator== (const string& lhs, const string& rhs)
{
	return strcmp(lhs.c_str(), rhs.c_str()) == 0;
}

//<运算符重载
bool operator< (const string& lhs, const string& rhs)
{
	return strcmp(lhs.c_str(), rhs.c_str()) < 0;
}

剩下的四个关系运算符的重载，就可以通过复用这两个已经重载好了的关系运算符来实现了。

//<=运算符重载
bool operator<= (const string& lhs, const string& rhs)
{
	return lhs < rhs || lhs == rhs;
}

//!=运算符重载
bool operator!= (const string& lhs, const string& rhs)
{
	return !(lhs == rhs);
}

//>运算符重载
bool operator> (const string& lhs, const string& rhs)
{
	return !(lhs <= rhs);
}

//>=运算符重载
bool operator>= (const string& lhs, const string& rhs)
{
	return !(lhs < rhs);
}

>>和<<运算符的重载

>>运算符的重载

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

	return os;
}

<<运算符的重载

istream& operator>>(istream& is, string& str)
{
	str.clear();

	char ch;
	//is >> ch;
	ch = is.get();
	while (ch != ' ' && ch != '\n')
	{
		str += ch;
		ch = is.get();
	}

	return is;
}

总结

以上为个人经验，希望能给大家一个参考，也希望大家多多支持编程客栈(www.devze.com)。