[C++](10)C++的string类如何实现？

文章目录

构造析构及一些简单函数
深浅拷贝(拷贝构造、赋值重载)
- 传统写法
- 现代写法、swap
reserve、insert、push_back、append、+=
erase
resize
比较运算符重载(非成员函数)
迭代器
find
流插入、流提取运算符重载、clear
完整代码

构造析构及一些简单函数

string 类包含3个成员变量，_str 指针指向对应的字符串，_size 表示有效字符的个数（不包括）,_capacity 表示有效容量的大小（不包括存的空间）。

class String
{
public:

private:
	char* _str;
	size_t _size;
	size_t _capacity;
};

构造函数和析构函数：

String(const char* str = "") //构造函数提供全缺省的更好，默认传入空字符串。
	:_size(strlen(str))
	, _capacity(_size)
{
	_str = new char[_capacity + 1]; //+1是为了给开空间
	strcpy(_str, str);
}

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

c_str operator[] size capacity：

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

char& operator[](size_t pos) //记得传引用返回，支持修改
{
	assert(pos < _size);
	return _str[pos];
}
const char& operator[](size_t pos) const //也要提供const版本
{
	assert(pos < _size);
	return _str[pos];
}

size_t size() const
{
	return _size;
}

size_t capacity() const
{
	return _capacity;
}

深浅拷贝(拷贝构造、赋值重载)

拷贝构造我们可以不写吗，直接用编译器自动生成的？

答案是不可以，因为默认生成的完成的是浅拷贝，仅仅是把指针拷贝过去，导致两个对象的 _str 指向的是同一块空间，程序运行时会出现：1.析构两次 2.一个对象的修改影响另外一个

所以我们要写一个深拷贝，为新的对象在堆上开辟空间：

传统写法

String(const String& s)
	:_size(s._size)
	, _capacity(_size)
{
	_str = new char[_capacity + 1];
	strcpy(_str, s._str);
}

赋值重载也面临同样的问题，同样要我们自己写深拷贝：

赋值是在两个对象都已经存在的情况下进行的，所以有些人容易想当然地以为直接 strcpy 就可以了，其实不然，如果被赋值的对象 _str 所指向的空间较小，要拷贝的内容就存不进去，如果空间较大，会造成浪费。

考虑到上述问题，这里可以简单粗暴地直接把原空间释放，重新开辟空间进行拷贝：

String& operator=(const String& s)
{
	if (this != &s)
	{
		char* tmp = new char[s._capacity + 1];
		strcpy(tmp, s._str);
		delete[] _str;
		_str = tmp;
		_size = s._size;
		_capacity = s._capacity;
	}
	return *this;
}

：记得考虑同一个对象自己给自己赋值的问题。

：先开空间后释放比先释放后开空间好。

现代写法、swap

拷贝构造

先完成成员函数swap

然后直接拿原对象里的 _str 去构造一个 tmp 对象，然后对 tmp 对象“夺舍”。

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

String(const String& s)
	:_str(nullptr)
	, _size(0)
	, _capacity(0)
{
	String tmp(s._str);
	swap(tmp);
}

注意：交换前应该先初始化，否则 tmp 拿到的 _str 指针是随机值，析构时会出错

赋值重载

同样的思路：

String& operator=(const String& s)
{
	if (this != &s)
	{
		String tmp(s._str);
		swap(tmp);
	}
	return *this;
}

其实传值传参就是现成的 tmp，代码还可以写得更简洁：

String& operator=(String s)
{
    swap(s);
    return *this;
}

reserve、insert、push_back、append、+=

为了方便扩容，我们先写reserve

void reserve(size_t n)
{
	if (n > _capacity)
	{
		char* tmp = new char[n + 1];
		strcpy(tmp, _str);
		delete[] _str;
		_str = tmp;
		_capacity = n;
	}
}

insert 插入一个字符，要注意检查是否需要扩容，这里采用2倍扩容：

String& insert(size_t pos, char ch)
{
	assert(pos <= _size);
	if (_size == _capacity)
		reserve(_capacity == 0 ? 4 : _capacity * 2);
    
	for (size_t end = _size + 1; end >= pos + 1; --end)
	{
		_str[end] = _str[end - 1];
	}
	_str[pos] = ch;
	++_size;
	return *this;
}

：传返回值是为了模仿标准库，实际没什么用。

：这里的插入算法如果写成下列形式可能会出现死循环：

for (size_t end = _size; end >= pos; --end)
{
    _str[end + 1] = _str[end];
}

：因为我们用的是 size_t (无符号整型)，当 pos 为0(头插)时，end < 0 的终止条件无法达成，形成死循环

insert 插入一个字符串：

插入字符串和插入字符不同，插入字符串的扩容要特别计算一下，因为对于插入字符串来说，无脑2倍扩不一定够：

String& insert(size_t pos, const char* str)
{
	assert(pos <= _size);
	size_t len = strlen(str);
	if (_size + len > _capacity)
		reserve(_size + len);

	for (size_t end = _size + len; end > pos + len - 1; --end)
	{
		_str[end] = _str[end - len];
	}
	strncpy(_str + pos, str, len);
	_size += len;
	return *this;
}

剩下的函数直接复用 insert 即可：

void push_back(char ch)
{
    insert(_size, ch);
}
void append(const char* str)
{
    insert(_size, str);
}
String& operator+=(char ch)
{
    insert(_size, ch);
    return *this;
}
String& operator+=(const char* str)
{
    insert(_size, str);
    return *this;
}

erase

首先定义一个静态成员变量npos，类内声明，类外定义。

class String
{
    //...
private:
	//...
	const static size_t npos;
};
const size_t String::npos = -1;

erase的实现，分两种情况：

从 pos 位置开始，删到最后，这种情况直接把 pos 位置的值设为即可
从 pos 位置开始，没有删到最后，那就要把后面的往前移

void erase(size_t pos, size_t len = npos)
{
	assert(pos < _size);
	if (len == npos || pos + len >= _size)
	{
		_str[pos] = '';
		_size = pos;
	}
	else
	{
		for (size_t begin = pos + len; begin <= _size; ++begin)
		{
			_str[begin - len] = _str[begin];
		}
		_size -= len;
	}
}

resize

void resize(size_t n, char ch = '')

分三种情况：

n > capacity：扩容并将字符追加至n个
size < n < capacity：不扩容，直接将字符追加至n个
n < size：不扩容，缩减字符至n个

void resize(size_t n, char ch = '')
{
	if (n < _size)
	{
		_size = n;
		_str[_size] = '';
	}
	else
	{
		if (n > _capacity)
			reserve(n);
		for (size_t i = _size; i < n; ++i)
		{
			_str[i] = ch;
		}
		_size = n;
		_str[_size] = '';
	}
}

比较运算符重载(非成员函数)

字符串比较直接用 strcmp，先写 < 和 == ，其他的复用即可。

bool operator<(const String& s1, const String& s2)
{
	return strcmp(s1.c_str(), s2.c_str()) < 0;
}
bool operator==(const String& s1, const String& s2)
{
	return strcmp(s1.c_str(), s2.c_str()) == 0;
}
bool operator<=(const String& s1, const String& s2)
{
	return s1 < s2 || s1 == s2;
}
bool operator>(const String& s1, const String& s2)
{
	return s2 < s1;
}
bool operator>=(const String& s1, const String& s2)
{
	return !(s1 < s2);
}
bool operator!=(const String& s1, const String& s2)
{
	return !(s1 == s2);
}

迭代器

string 的迭代器其实就是指针：

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 test_string5()
{
	String s1("hello world");
	String::iterator it = s1.begin();
	while (it != s1.end())
	{
		cout << *it << ' ';
		++it;
	}
	cout << endl;
}
//结果：h e l l o   w o r l d

有了迭代器，范围for也就可以用了，因为范围for的底层实现其实就是迭代器：

void test_string5()
{
	String s1("hello world");
	for (auto& ch : s1)
	{
		cout << ch << ' ';
	}
	cout << endl;
}
//结果：h e l l o   w o r l d

find

查找字符：

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

查找字符串，用 strstr：

size_t find(const char* str, size_t pos = 0) const
{
    const char* p = strstr(_str + pos, str);
    if (p == nullptr) return npos;
    return p - _str;
}

流插入、流提取运算符重载、clear

为了保证 cout 是第一操作数，流插入运算符重载要实现在类外面。

通过 c_str 函数，我们也不需要访问私有成员变量，也就不需要设置友元函数。

ostream& operator<<(ostream& out, const String& s)
{
	for (auto ch : s)
	{
		out << ch;
	}
	return out;
}

注意：不能把范围for写成 out << s.c_str() 。因为如果字符串中间有，这种写法打印到就结束了

如下，两种方式的结果是不同的：

void test_string7()
{
	String s("hello");
	s += '';
	s += " world";
    
	cout << s.c_str() << endl;
	//结果：hello
	for (auto& ch : s)
	{
		cout << ch;
	}
	cout << endl;
    //结果：hello world
}

流提取之前需要把原有数据清空，所以先实现 clear：

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

流提取：

一个字符一个字符地读取，遇到空格或换行符停止。

in.get() 用来读取空格和换行符。

istream& operator>>(istream& in, String& s)
{
    s.clear();
	char ch;
	ch = in.get();
	while (ch != ' ' && ch != 'n')
	{
		s += ch;
		ch = in.get();
	}
	return in;
}

如果输入的字符串很长，频繁+=的扩容有一点影响效率，优化版本：

给一个大小为128的缓冲数组，满了再+=

istream& operator>>(istream& in, String& s)
{
    s.clear();
	char ch;
	ch = in.get();
	char buff[128] = { 0 };
	size_t i = 0;
	while (ch != ' ' && ch != 'n')
	{
		buff[i++] = ch;
		if (i == 127)
		{
			s += buff;
			memset(buff, '', 128);
			i = 0;
		}
		ch = in.get();
	}
	s += buff;
	return in;
}

完整代码

#pragma once
#include 
#include 
using namespace std;

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)
	{
		_str = new char[_capacity + 1];
		strcpy(_str, str);
	}

	//String(const String& s)
	//	:_size(s._size)
	//	, _capacity(_size)
	//{
	//	_str = new char[_capacity + 1];
	//	strcpy(_str, s._str);
	//}

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

	String(const String& s)
		:_str(nullptr)
		, _size(0)
		, _capacity(0)
	{
		String tmp(s._str);
		swap(tmp);
	}

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

	//String& operator=(const String& s)
	//{
	//	if (this != &s)
	//	{
	//		char* tmp = new char[s._capacity + 1];
	//		strcpy(tmp, s._str);
	//		delete[] _str;
	//		_str = tmp;
	//		_size = s._size;
	//		_capacity = s._capacity;
	//	}
	//	return *this;
	//}

	//String& operator=(const String& s)
	//{
	//	if (this != &s)
	//	{
	//		String tmp(s._str);
	//		swap(tmp);
	//	}
	//	return *this;
	//}

	String& operator=(String s)
	{
		swap(s);
		return *this;
	}

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

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

	size_t size() const
	{
		return _size;
	}

	size_t capacity() const
	{
		return _capacity;
	}

	String& operator+=(const char* str)
	{
		insert(_size, str);
		return *this;
	}

	String& operator+=(char ch)
	{
		insert(_size, ch);
		return *this;
	}

	void reserve(size_t n)
	{
		if (n > _capacity)
		{
			char* tmp = new char[n + 1];
			strcpy(tmp, _str);
			delete[] _str;
			_str = tmp;
			_capacity = n;
		}
	}

	void resize(size_t n, char ch = '')
	{
		if (n < _size)
		{
			_size = n;
			_str[_size] = '';
		}
		else
		{
			if (n > _capacity)
				reserve(n);
			for (size_t i = _size; i < n; ++i)
			{
				_str[i] = ch;
			}
			_size = n;
			_str[_size] = '';
		}
	}

	void push_back(char ch)
	{
		insert(_size, ch);
	}
    
	void append(const char* str)
	{
		insert(_size, str);
	}

	String& insert(size_t pos, char ch)
	{
		assert(pos <= _size);
		if (_size == _capacity)
			reserve(_capacity == 0 ? 4 : _capacity * 2);
		for (size_t end = _size + 1; end >= pos + 1; --end)
		{
			_str[end] = _str[end - 1];
		}
		_str[pos] = ch;
		++_size;
		return *this;
	}

	String& insert(size_t pos, const char* str)
	{
		assert(pos <= _size);
		size_t len = strlen(str);
		if (_size + len > _capacity)
			reserve(_size + len);

		for (size_t end = _size + len; end > pos + len - 1; --end)
		{
			_str[end] = _str[end - len];
		}
		strncpy(_str + pos, str, len);
		_size += len;
		return *this;
	}

	void erase(size_t pos, size_t len = npos)
	{
		assert(pos < _size);
		if (len == npos || pos + len >= _size)
		{
			_str[pos] = '';
			_size = pos;
		}
		else
		{
			for (size_t begin = pos + len; begin <= _size; ++begin)
			{
				_str[begin - len] = _str[begin];
			}
			_size -= len;
		}
	}

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

	size_t find(const char* str, size_t pos = 0) const
	{
		const char* p = strstr(_str + pos, str);
		if (p == nullptr) return npos;
		return p - _str;
	}

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

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

ostream& operator<<(ostream& out, const String& s)
{
	for (auto ch : s)
	{
		out << ch;
	}
	return out;
}

//istream& operator>>(istream& in, String& s)
//{
//	char ch;
//	ch = in.get();
//	while (ch != ' ' && ch != 'n')
//	{
//		s += ch;
//		ch = in.get();
//	}
//	return in;
//}

istream& operator>>(istream& in, String& s)
{
	s.clear();
	char ch;
	ch = in.get();
	char buff[128] = { 0 };
	size_t i = 0;
	while (ch != ' ' && ch != 'n')
	{
		buff[i++] = ch;
		if (i == 127)
		{
			s += buff;
			memset(buff, '', 128);
			i = 0;
		}
		ch = in.get();
	}
	s += buff;
	return in;
}

bool operator<(const String& s1, const String& s2)
{
	return strcmp(s1.c_str(), s2.c_str()) < 0;
}
bool operator==(const String& s1, const String& s2)
{
	return strcmp(s1.c_str(), s2.c_str()) == 0;
}
bool operator<=(const String& s1, const String& s2)
{
	return s1 < s2 || s1 == s2;
}
bool operator>(const String& s1, const String& s2)
{
	return s2 < s1;
}
bool operator>=(const String& s1, const String& s2)
{
	return !(s1 < s2);
}
bool operator!=(const String& s1, const String& s2)
{
	return !(s1 == s2);
}

[C++](10)C++的string类如何实现？

C/C++/C#相关栏目本月热门文章