您现在的位置是：首页 >其他 >【C++】string的模拟实现网站首页其他

【C++】string的模拟实现

LinAlpaca 2024-06-14 17:20:28
简介【C++】string的模拟实现

目录

前言

结构解析

构造与析构

构造

拷贝构造

析构

运算符重载

赋值重载

下标访问

逻辑判断

迭代器

容量操作

查看大小和容量

容量修改

增删查改

尾插

push_back

append

+=

尾删

清空内容 

任意位置插入删除

insert

erase

查找

IO重载

<<

>>

其他函数

c_str

swap

源码

前言

上一篇文章中讲了如何使用string，这次讲讲 string 的模拟实现。由于 string 的接口实在是太多了，这里只实现一些常用的接口。

话不多说，我们直接开始。

结构解析

?我们知道，string 的本质还是一个顺序表，只不过限定了里面存的是字符。我们模拟实现主要还是为了学习设计容器的思想，今天这个 string 就不写成类模板了，因此现在这个类的成员变量基本上就确定下来了。我还将其写到了自己的命名空间中避免冲突。

namespace Alpaca
{
	class String
	{
	public:
    private:
		char* _str;      //字符串
		size_t _sz;         //大小
		size_t _capacity;   //容量

		static const size_t npos;
	};
	static const size_t npos = -1;
}

?虽然 npos 是静态成员变量，但是加了 const 之后便可以在类中初始化。注意: 静态成员变量只有整型才能在类中初始化。

?此外数据的大小与容量不可能是负数，便可以将其设置为无符号整数。

构造与析构

构造

?在 string 中支持无参构造，还支持传字符串构造。我们不妨设置一个缺省值将二者结合起来。

String(const char* ptr = "")
			:_sz(strlen(ptr))
		{
			_capacity = _sz == 0 ? 3 : _sz;    //若是无参构造初始容量为3
			_str = new char[_capacity + 1];    //给''留位置
			strcpy(_str, ptr);
		}

?虽然之前说过，尽量在初始化列表中进行初始化。但在这里不同，调用一次 strlen 的时间复杂度是 O(n) ，若要将其他两个变量也写进初始化列表中，则又要多增加两个 O(n) 的消耗。 最好也不要在初始化列表中进行复用，万一下方声明的顺序错了就会造成一方是随机值的情况。

?这里初始化使用的是一个空串，因为 " " 中便自带了一个 ，接着为 _str 动态开辟内存空间。虽然有效字符并不包含 ，但是在之后我们还会调用库中的字符串函数，因此需要在空间内保留 作为识别的标志。所以开辟空间时要为 预留一个位置。

?最后用库函数拷贝原串到 _str 中即可。

拷贝构造

String(const String& S)
	:_capacity(S._capacity) 
	,_sz(S._sz)
{
	_str = new char[_capacity + 1];  //开辟新空间
	strcpy(_str, S._str);        //复制字符串内容
}

?拷贝构造就是对相同类型的深拷贝，因此需要对类内部的容量和大小进行拷贝，由于数值是现成的便可以直接在初始化列表初始化。

?之后还需要为_str开辟一个新的空间，最后再拷贝字符串内容即可。

析构

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

?也是为了这里能够统一用 delete [ ] 释放内存，因此在构造的时候，即便初始化字符串内容只有 1 个也要使用new [ ] 来开辟空间。

?之后指针置空，容量与大小置 0 即可。

运算符重载

赋值重载

?写赋值重载的时候，我们得考虑到几个问题。

  • 当前容量是否足够
  • 万一空间开辟失败是否会影响到原空间

?因此我们不妨依照赋值的那个 string 的容量先开辟一段空间，将内容拷贝进去后，再释放原来的空间，最后更改指向的指针。

?这样即不用担心容量是否足够的问题，同时避免还能申请空间失败，影响原来的数据。

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

		_sz = S._sz;
		_capacity = S._capacity;
	}
	return *this;
}

?为了避免自己赋值给自己，所以实际处理前还要判断下当前 this 指针，跟 S 的地址是否相等。相等直接返回即可。 

下标访问

?要想访问数据，那必不可少的就是下标访问了。对 [ ] 进行重载，先限定访问的区间，最后返回该位置的字符即可。

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

?值得注意的一点就是，返回的是该字符的引用，若返回的只是 char ，那当我们用下标对 string 进行修改时，由于返回的字符只是原字符的拷贝。因此对返回的字符进行修改并不会影响到原 string 之中的内容。 

逻辑判断

?只要调用库函数进行判断即可，根据 strcmp 的返回值进行判断，写出 == 和 大于小于其中之一，之后就都可以复用上面两个函数了。

bool operator == (const String& S) const
{
	return !strcmp(_str, S._str);
}
bool operator > (const String& s) const
{
	return strcmp(_str, s._str) > 0;
}

bool operator >= (const String& s) const
{
	return *this > s || s == *this;
}
 
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);
}

迭代器

?由于 string 中对于迭代器的要求并不高，我们直接使用原生指针作为迭代器即可。

typedef char* iterator;
typedef const char* const_iterator;

iterator begin()
{
	return _str;
}

const_iterator begin() const  //const迭代器
{
	return _str;
}

iterator end() 
{
	return _str + _sz;
}

const_iterator end() const
{
	return _str + _sz;
}

?之后我们便可以使用这个迭代器访问 string ，也可以使用范围 for 了。

 

容量操作

查看大小和容量

?由于 _sz 和 _capacity 是属于私有的，所以外部无法直接访问其内容的，但我们可以实现一个接口实现对二者的访问。

?本质上就是以只读的形式返回，外部依旧无法对 string 内部的变量进行写入。

int size() const
{
	return _sz;
}

int capacity() const
{
	return _capacity;
}

容量修改

?关于容量的修改自然就是 reserve 和 resize 两个函数了。

reserve

?同样为了避免函数开辟内容失败，导致原数据丢失，因此我们先在外开辟，之后再修改类中的指针。

?值得注意的是，若输入的值比当前的容量还小的话，则不做处理。

void reserve(size_t n)
{
	if (n > _capacity)
	{
		char* tmp = new char[n + 1];  //多为申请一个空间
		strcpy(tmp, _str);
		delete[] _str;
		_str = tmp;                   //更新指针
		_capacity = n;                //更新容量
	}
}

resize

? resize 与 reserve 不同于它还会对开辟的空间根据传入的值进行初始化，因此我们额外使用 memset 进行初始化设置。

?一定是先 memset 再进行拷贝，若是先拷贝再 memset 就会把原来的数据全部初始化掉。

void resize(size_t n, char c = '')
{
    if (n > _capacity - 1)
	{
		char* tmp = new char[n + 1];
		memset(tmp, c, n + 1);
		strcpy(tmp, _str);
		delete[] _str;
		_str = tmp;
		_sz = n;
		_capacity = n + 1;
	}
	else
	{
		_capacity = n;
		_str[_capacity] = '';
	}
}

增删查改

尾插

push_back

?值得注意的细节就在于，是否需要扩容的判断。_sz 表示的是当前已有字符的数量，从下标的角度看就是下一个要尾插的字符的下标。

?当 _sz + 1 > _capacity 时就代表空间已经不足，需要扩容，若不扩容在插入 时就会越界。

?这是因为 _sz 代表的是有效字符的数量，而 _capacity 代表的是有效字符的容量，而此时要尾插，操作完的有效字符数量为 _sz+1 ，因此需要保证此时的容量要大于 _sz+1。

void push_back(const char c)
{
	if (_sz + 1 > _capacity)
	{
		reserve(_capacity * 2);
	}

	_str[_sz] = c;      //尾插字符
	++_sz;
    _str[_sz] = '';   //恢复
}

append

?与 push_back 类似，append 也要先查看空间是否够用。再用 strcpy 拷贝进来，且 strcpy 会连带 一起拷贝，因此不用恢复 。

String& append(const char* p)
{
	int len = strlen(p);
	if (_sz + len > _capacity)
	{
		reserve(_sz + len);
	}
	strcpy(_str + _sz, p);
	_sz += len;
	return *this;
}

+=

?写完上面两个函数后，实现 += 就可以对其直接进行复用了。

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

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

尾删

?若 _sz 等于 0 则说明当前 string 内已无数据，不能再继续删除了。

?否则 _sz-- 即可，下次再插入数据就会直接将其覆盖了。

void pop_back()
{
	if (_sz == 0)
	{
		cout << "已无数据，无法继续删除" << endl;
		return;
	}
	_sz--;
}

清空内容 

?清空内容只需要将 _sz 置 0，使第一位是 即可。

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

任意位置插入删除

insert

?对于在任意位置的插入，不可避免的都是挪动数据，首先要限定下标的范围，自然是要在 _sz 之内，因为这个插入也支持尾插，因此 pos 等于 _sz 也是允许的。之后从 _sz 的下一位 () 开始移位，end 不可以等于 pos ，若等于 pos 则代表会挪动 pos-1 的字符到 pos 之中，并不符合要求。

  

String& insert(size_t pos, const char ch)
{
	assert(pos <= _sz);    //限定下标范围
	if (_sz + 1 > _capacity) reserve(2 * _capacity); //判断容量大小
	int end = _sz + 1;
	while (end > pos)       //移位
	{
		_str[end] = _str[end - 1];
		end--;
	}
	_str[pos] = ch;         //插入
	_sz++;
	return *this;
}

?若想在指定位置插入字符串，则需要提前算出字符串长度，判断容器的大小是否够用，再进行移位。

?插入的长度为 len ，而 pos 的字符需要挪到 pos+len ，当 end 等于 pos+len-1 时则不需要继续挪动。

String& insert(size_t pos, const char* str)
{
	assert(pos <= _sz);
	size_t len = strlen(str);
	// 挪动数据
	size_t end = _sz + len;
	if (end > _capacity)
	{
		reserve(end);
	}
	while (end > pos + len - 1)
	{
		_str[end] = _str[end - len];
		end--;
	}
	// 拷贝插入
	strncpy(_str + pos, str, len);
	_sz += len;
	return *this;
}

erase

?删除有两种情况，后序部分不保留和后序部分保留。

?后序部分不保留时，直接将 置于 pos 的位置，直接修改 _sz 即可。

?后序部分保留时，将 pos ~ pos+len 这部分忽略，之后的字符从 pos 位置开始覆盖，再修改 _sz。

String& erase(size_t pos, size_t len = npos)
{
	if (len == npos || pos + len >= _sz)    //pos开始到结尾都要删除
	{
		_str[pos] = '';
		_sz = pos;
	}
	else
	{
		memmove(_str + pos, _str + pos + len, len);
		_sz -= len;
	}
	return *this;
}

查找

?查找的函数可以分成对字符查找和对字符串查找，若对字符串查找，则直接遍历查找对应字符，找到返回下标，找不到返回 npos 。

?若对字符串查找，我们不妨使用库函数进行辅助，该函数找到则返回查找串的首地址，找不到返回空指针。

?我们可以通过返回的地址减去 _str 的首地址得到其下标。

size_t find(char c, size_t pos = 0)
{
	for (int i = pos; i < _sz; i++)
	{
		if (_str[i] == c)
		{
			return i;
		}
	}
	return npos;
}

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

IO重载

?若我们也想用 cin 和 cout 对 string 进行输入和输出的话，需要将下面两个符号进行运算符重载。

?但，若这两个运算符重载写在类的里面，那么第一个参数则会默认是该类的 this 指针，因此在使用时，便变成 s>>cin。

?因此，我们需要将这两个重载写在类外，再用友元函数将其于 string 关联起来。

<<

? ostream 就是我们平时使用的 cout ，只要根据我们想要的格式对 string 进行输出即可，最后返回 ostream 保证可以多组输出。

ostream& operator << (ostream& out, const Alpaca::String& S)
{
	for (auto c : S)
	{
		out << c;
	}
	return out;
}

>>

?对 >> 的重载就相较于 << 麻烦，我们根据输入的字符一个个加入到临时的字符数组之中，到输入结束或数组满时再导入 string 。

?当读到空格或是 时便结束读取。

istream& operator >> (istream& in, Alpaca::String& S)
{
	S.clear();
	char buff[128];
	char ch;
	int i = 0;
	ch = in.get();    //不断读取字符
	while (ch != ' ' && ch != '
')
	{
		buff[i++] = ch;
		if (i == 127)
		{
			buff[i] = '';
			S += buff;
			i = 0;
		}
		ch = in.get();
	}
	if (i)
	{
		buff[i] = '';
		S += buff;
	}
	return in;
}

其他函数

c_str

?c_str 可以获取类中的字符串，同时为了避免内容被修改，因此返回的是 const char* 类型的指针。

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

swap

?库中的 swap 函数，实际上进行的是拷贝临时对象进行交换，效率较低，我们只需要交换内置的变量即可。

void swap(String& S)
{
	std::swap(_str, S._str);
	std::swap(_sz, S._sz);
	std::swap(_capacity, S._capacity);
}

?这之后，我们的赋值拷贝就可以使用一种全新的方式进行实现。

String& operator = (String S)
{
	this->swap(S);
	return *this;
}

?通过形参的方式构造一个 string ，之后将其内置的指针于当前的指针交换，函数结束后形参销毁，原来开辟的空间就被释放。

源码

?源码放在这里有需要的可以自取。

string模拟实现

?好了，今天 string 的模拟实现到这里就结束了，如果这篇文章对你有用的话还请留下你的三连加关注

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐