【C++】手撕STL系列——string篇

文章导读

本章我们将参照STL源码，来模拟实现string类，但不一定非要与库中完全相同。我们将其中重要的、常用的接口进行模拟实现，旨在加深string类的学习与记忆。

为了代码更好地复用，本篇模拟的函数接口的顺序大概为构造类——》内存类——》迭代器——》修改类——》构造类

定义string类

为了区别于标准库中的string类，我们这里应该使用自己的命名空间来进行定义

string类包含以下三种成员

• char*_str  字符数值
• size_t _size  大小
• size_t _capacity  容量

注意：capacity的大小不包含\0，_size指的是\0的位置

另外还需要一个static的size_t成员npos，值为-1，表示数组末尾

构造函数

string的构造函数有很多种写法，由前面类和对象的学习中了解到全缺省的构造函数是最优的写法，所以这里我们也采纳全缺省的写法

注意：初始化列表是根据成员的定义顺序来进行初始化的，所以这里_str不能放到初始化列表进行初始化，因为放到初始化列表中会第一个初始化_str，但这是还不知道_capacity的大小

        /*string()
			:_str(new char[1]{ '\0' })
			,_size(0)
			,_capacity(0)
		{}*/
 
		//全缺省的构造函数更优
		string(const char* s="")
			:_size(strlen(s))
			, _capacity(_size)
		{
			_str = new char[_capacity + 1];
			strcpy(_str, s);
		}

内存类函数接口

size_t size()const——返回大小

size_t size()
{
    return _size;
}

size_t capacity()const——返回容量大小

size_t capacity()const
{
    return _capacity;
}

void reserve（size_t n）——扩容函数

n大于capacity才会发生扩容，开辟另一块空间并将原来的空间拷贝过去，再销毁原来的空间；n小于等于capacity的时候不会有所作为

不会修改_size值

void reserve(size_t n)
		{
			if (n > _capacity)
			{
				char* tmp = new char[n + 1];//多出来的一个位置放\0
				strcpy(tmp, _str);
				delete[]_str;
 
				_str = tmp;
				_capacity = n;
			}
		}

void resize(size_t n，char ch)——修改大小

如果n<=size就减小_size的值，并在对应处放'\0'

如果n>size位置，就扩容（复用reserve函数），并将size 位置到n位置的元素初始化为ch，最后一个位置放\0

void resize(size_t n,char c='\0')
		{
			if (n <= _size)
			{
				_str[n] = '\0';
				_size = n;
			}
			else
			{
				reserve(n);
				while (_size < n)
				{
					_str[_size] = c;
					_size++;
				}
				_str[_size] = '\0';
			}
		}

迭代器

先实现迭代器是为了方便遍历数组（范围for）并将元素打印，方便我们后期进行调试并检验其他函数接口的正确性

这里的迭代器可以简单地认为是原生指针（其他类可能不是原生指针）

        iterator begin()
		{
			return _str;
		}
		iterator end()
		{
			return _str + _size;
		}
		const_iterator begin()const
		{
			return _str;
		}
		const_iterator end()const
		{
			return _str+_size;
		}

为了使string类可以像数组一样可以访问，增强代码的可读性，可以先实现一个[]的运算符重载

实现两个，一个是只能读不能修改，一个是可读可修改

        char operator[](size_t i)
        {
            assert(i <= _size);
 
            return *(_str + i);
        }
        const char operator[](size_t i)const
        {
            assert(i <= _size);
 
            return *(_str + i);
        }

修改类

注意：strcpy以\0为结束标志，会拷贝\0；strncpy自己决定拷贝个数，不会自动拷贝\0

经过初阶数据结构与算法的学习，我们知道顺序表的优势在与尾插尾删以及随机访问，所以第一个修改类的实现当然是尾插push_back啦

push_back

       void push_back(const char ch)//插入一个字符
		{
			//满了先扩容
			if (_size = _capacity)
			{
				reserve(_capacity==0?4:2*_capacity);
			}
			_str[_size] = ch;
			_size++;
			_str[_size] = '\0';
		}

除了插入一个字符，肯定还有插入一个字符串的需求，这里就交给append

如果插入的字符串长度+原本的长度>capacity，就需要扩容

append

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

用函数实现尾插当然可以，但是现实中更多人使用的是+=运算符重载，因为这样可读性很高，也十分生动形象

有了以上两个接口，我们的+=运算符重载当然是手到擒来啦，直接复用即可

+=运算符重载

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

实现了尾插，接下来就是头插（insert函数取第一个位置即可）啦

我们可以头插一个字符，也可以头插一个字符串，也可以在任意位置插入（写完insert后尾插其实就可以复用insert了，取最后一个位置即可）

注意插入位置pos要在合法区间，如果大于容量则要扩容

insert

void insert(size_t pos, char ch)
		{
			assert(pos <= _size);
 
			if (_size == _capacity)
			{
				reserve(_capacity == 0 ? 4 : 2 * _capacity);
			}
			//size位置指的是‘\0’，也要移动
			size_t end = _size + 1;
			while (end > pos)
			{
				_str[end] = _str[end - 1];
				--end;
			}
 
			_str[pos] = ch;
			_size++;
		}
		void insert(size_t pos, const char* str)
		{
			assert(pos <= _size);
 
			int len = strlen(str);
			if (_size + len > _capacity)
			{
				reserve(_size + len);
			}
			int end = _size;
            //防止发生整形提升
			while (end >=(int) pos)
			{
				_str[end+len] = _str[end];
				--end;
			}
			strncpy(_str + pos, str, sizeof(char) * len);
			_size += len;
		}

实现完插入当然就是删除啦

void clear()——删除所有（在开头处放\0，并不用真正地销毁）

clear()

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

  void erase(size_t pos = 0, size_t len = npos)——删除在pos以及以后的len个元素

   如果没指定len的大小，默认将pos以后的元素全部删完

   指定了就删除len个

 void erase

        void erase(size_t pos = 0, size_t len = npos)
		{
			assert(pos < _size);
 
			if (pos + len >= _size)
			{
				_str[pos] = '\0';
				_size = pos;
			}
			else
			{
				int end = pos + len;
				while (end <_size)
				{
					_str[end - len] = _str[end];
					end++;
				}
				_size -= len;
			}
		}

输入输出运算符重载

为了不破坏权限以及耦合度，这里不使用友元实现，将输入输出的运算符重载放在string的类外，自己的类域里面实现

cout重载

就是一个简单的范围for遍历

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

cin重载

为了避免输入过多字符，s不断扩容，先定义一个buff数组，用空间换取时间

如果buff数组满了，先将数组里的内容尾插到string中，再将buff数组清空，继续往buff数组里输入值，如此反复

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

比较函数

正如字符串可以比较一样，string类（封装的字符串）我们应该也设置成让他们可以比较

只要实现了==和>或者（==和<），其他的函数接口都可以复用这两个函数接口

        bool operator==(const string& s)
		{
			return strcmp(_str, s._str)==0;
		}
		bool operator>(const string& s)
		{
			return strcmp(_str, s._str) >0;
		}
		bool operator>=(const string& s)
		{
			return (*this > s) || (*this == s);
		}
		bool operator<=(const string& s)
		{
			return !(*this > s);
		}
		bool operator<(const string& s)
		{
			return !(*this <= s);
		}
		bool operator!=(const string& s)
		{
			return !(*this == s);
		}

构造类

拷贝构造

        //拷贝构造函数
		string(const string& s, size_t pos=0, size_t len = npos)
		{
			if (len == npos)
			{
				_str = new char[s._size-pos];
				strcpy(_str, s._str + pos);
				_size = _capacity = s._size - pos;
			}
			else
			{
				_str = new char[len];
				strncpy(_str, s._str + pos, len);
				_capacity = _size = len;
				_str[_size] = '\0';
			}
		}

=运算符的重载

这里有两种写法，一种是老老实实地自己写，一种是复用拷贝构造

       //老实写法
        string& operator=(const string& tmp)
		{
			if (*this != tmp)
			{
				//char* s = new char[tmp._capacity ]——这样写下面的delete会报错，越界多拷贝了一个，释放空间的时候会出问题
				char* s = new char[tmp._capacity+1];
				strcpy(s, tmp._str);
				delete[]_str;
				_str = s;
				_size = tmp._size;
				_capacity = tmp._capacity;
			}
			return *this;
		}

复用写法

先需要一个swap函数，调用标准库里的swap函数，由函数重载自动识别是哪种类型并操作

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

传参的时候调用了拷贝构造函数，然后再交换，即可完成拷贝，十分简洁，但效率一样

注意：几乎每个类的赋值重载都可以这样写，十分通用又简洁的写法

string& operator=(string tmp)
		{
			swap(tmp);
			return *this;
		}

至此，string的大概的接口就实现的差不多了，希望对大家能有所帮助