C++初阶 | [七] (下) string类模拟实现

摘要：string类的模拟实现【设计思路+代码示例】；string类底层设计的补充说明【sizeof(string)，string类设计上的效率问题：深拷贝的浪费】；扩展【写时拷贝】

1. 创建命名空间

目的：为了和 std 中的 string 区分。

namespace Bottle
{
	class string
	{
	public:

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

    size_t string::npos = -1;
}

2. Constructor

• 无参的：_str(new char[1] {'\0'}) 这里用?new char[1] {'\0'} 而不是 new char('\0') 是为了和析构函数中的 delete[] 匹配使用。
• 全缺省的：参数缺省值 →?const char* str = ""??空字符串(不含空格) —— 缺省值给空字符串同样默认以 '\0' 字符串结尾，如果这里缺省值给 "\0" 字符串会有两个 '\0' 字符，结尾默认跟 '\0'。

注意：capacity 不算结尾的 '\0' ，但开空间要预留 '\0' 的位置。

示例：?

//Constructor
string()//无参的构造函数
	:_str(new char[1] {'\0'})
	, _size(0)
	, _capacity(0)
{

}

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

3. Destructor

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

4. 遍历string_iterator

1）capacity() ，size()

2）operator[] and const 版本（ps.检查下标的合法性）

3）iterator ：用指针实现 → typedef char* iterator;

4）范围for：对 iterator 有严格的要求，本质上就是简单地替换成 iterator ，例如——如果对 begin() 函数改名为 Begin() 都会使范围for不支持。

示例：?

typedef char* iterator;
typedef const char* const_iterator;


///
size_t capacity()const
{
	return _capacity;
}

size_t size()const
{
	return _size;
}
///

//operator[]
char operator[](size_t i)
{
	if (i < _size)
		return _str[i];
	else
	{
		std::cout << "非法下标" << std::endl;//也可以选择用asset暴力检查
		exit(-1);
	}
}

char operator[](size_t i)const
{
	if (i < _size)
		return _str[i];
	else
	{
		std::cout << "非法下标" << std::endl;
		exit(-1);
	}
}
///

//iterator
iterator begin()
{
	return _str;
}

iterator end()
{
	return _str + _size;
}

const_iterator cbegin()const
{
	return _str;
}
const_iterator cend()const
{
	return _str + _size;
}

5. 增删查改

1）尾插：

插入数据肯定涉及到要扩容的问题，为了先解决扩容的问题——实现 reserve?函数：

• reserve

  

  //reserve
  		void reserve(size_t n)//可以存储的有效数据个数为'n'个
  		{
  			if (n > _capacity)
  			{
  				char* tmp = new char[n + 1];//多开一个给''\0'
  				strcpy(tmp, _str);//拷贝数据到新空间(ps.strcpy 会 copy 结尾的'\0')
  				delete[]_str;//释放旧空间
  				_str = tmp;//指向新空间
  				_capacity = n;
  			}
  		}

①push_back(char c)

关于扩容的问题：

• reserve(_size + 1);?//每插入一个数据就多开一个数据的空间，可能导致频繁扩容。但是这样写不会出现给 reserve 传的参数为 0 而不扩容的情况。
• reserve(_capacity * 2);//如果 _capacity == 0，就会没扩容，没扩容后面再执行插入数据的操作，会导致访问越界，越界访问会导致delete处崩溃。

综上，最终选择如下这样的写法：

//push_back
		void push_back(char c)
		{
			if (_size == _capacity)//check capacity
			{
				reserve((_capacity == 0) ? 4 : (_capacity * 2));
			}

			_str[_size] = c;//push data
			++_size;
			_str[_size] = '\0';
		}

②append(const char* str)

//append
		void append(const char* str)
		{
			size_t len = strlen(str);
			reserve(_size + len);//check capacity

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

③operator+=

复用 push_back 和 append 函数即可。

//operator+=
		string& operator+=(const char c)
		{
			push_back(c);
			return *this;
		}

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

2）insert

思路：①检查 pos 位置的有效性；②检查容量；③挪动数据；④插入数据（strncpy）。

特殊情况：头插（pos==0）ps.下面的 pos 和 end 都是指下标

①size_t end 是无符号整型，-1即为整型的最大值，以 end >= pos 作为循环判断条件，在 pos ==0 时会出现?“-1>0”?的情况，于是进入死循环；
②即使定义?int end，仍以 end >= pos 作为循环判断条件，>=操作符左右操作数的类型不同，会发生类型转换，通常是比较范围小的向范围大的转换，即在该情况下，有符号整型一般转化为无符号整型。

有两种方式解决上述情况：
①强制类型转换成 int 进行比较；(int)end>=(int)pos;
②让 end 所指数据?将要被挪动到的位置?而不是指将要被挪动的数据。_str[end+len] = _str[end]? ?_str[end] = _str[end - len]

代码示例：?

//insert
		string& insert(size_t pos, const char c)//在pos位置插入c
		{
			//check
			assert(pos < _size);

			//capacity
			reserve(_size + 1);

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

			//insert 
			_str[pos] = c;

            _size += 1;
			return *this;

		}

		string& insert(size_t pos, const char* str)//在pos位置插入串str
		{
			//check
			assert(pos < _size);

			//capacity
			size_t len = strlen(str);
			reserve(_size + len);

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

			//insert 
			strncpy(_str + pos, str, len);

            _size += len;
            return *this;

		}

3）erase

//erase
		string& erase(size_t pos, size_t len = npos)
		{
			//check
			assert(pos < _size);

			if ((pos + len >= _size) || (npos == -1))//如果len足够长，长到删完pos位置后面所有的数据
			{
				_size = pos;
			}
			else
			{	//数据从后往前挪动覆盖删除
				for (size_t i = pos + len; i < _size; ++i)
				{
					_str[i - len] = _str[i];
				}
				_size -= len;
			}

			_str[_size] = '\0';
            return *this;
		}

注意：?(pos + len >= _size) || (npos == -1) 这两个情况 pos + len >= _size?与?npos == -1?要分开判断，因为 -1已经是无符号整型的最大值，再在其上加上数据会溢出——超出无符号整型能存储的最大数值。

4）操作符重载

• 比较操作符重载

这些比较操作符库里实现的是全局函数，而非成员函数，是考虑到除了 string类(char) 以外还要匹配其他的类型(Types)，这里我们简单地实现为成员函数。

代码示例：

//Compare
		bool operator==(const string& s)const
		{
			return (strcmp(this->_str, s._str) == 0);
		}

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

		bool operator>(const string& s)const
		{
			return (strcmp(this->_str, s._str) > 0);
		}

		bool operator>=(const string& s)const
		{
			return ((*this > s) || (*this == s));
		}

		bool operator<= (const string& s)const
		{
			return (!(*this > s));
		}

• 流插入和流提取重载

不一定要写成友元函数，因为这里不用访问私有函数。

1. 流插入重载代码示例：

   namaspace Bottle
   {
       class string
       {
           //……
       };
   
   	std::ostream& operator<<(std::ostream& out, const string& s)
   	{
   		for (size_t i = 0; i < s.size(); ++i)
   		{
   			out << s[i];
   		}
   
   		return out;
   	}
   }

2. ?流提取重载
   注意：cin 和 scanf 都是以空格和换行为一段输入的间隔，如下图所示。为了解决下示问题，可以采用 get 函数。get - C++ Reference (cplusplus.com)

   ?

   流提取代码示例：（注意：流提取之前要清空string对象中原有的数据，不然就会变成?流提取重载?就会变成?尾插数据?）

   	std::istream& operator>>(std::istream& in, string& s)
   	{
   		s.clear();//clear existing data
   
   		char ch = in.get();
   		while (ch != ' ' && ch != '\n')
   		{
   			s += ch;
   			ch = in.get();
   		}
   
   		return in;
   	}

流提取中关于扩容的问题：可以通过创建缓冲区数组优化频繁扩容的问题。先把读到的数据存到缓冲区数组，如果缓冲区数据满了就插入到原本要插入的string类对象中，这样就避免了每次单个单个插入字符而导致的频繁扩容。代码示例如下：

	std::istream& operator>>(std::istream& in, string& s)
	{
		s.clear();//clear existing data

		char buff[129] = { 0 };

		size_t i = 0;
		char ch = in.get();

		while (ch != ' ' && ch != '\n')
		{
			buff[i] = ch;//读到的数据先存到buff数组中
			++i;
			if (i == 128)//buff数组存满后插入到string& s中
			{
				buff[i] = '\0';
				s += buff;
				i = 0;
			}
		}
		if (i != 0)//如果缓冲区数据内还有剩余数据，记得把剩下的数据插入string& s中
		{
			buff[i] = '\0';
			s += buff;
		}
		return in;
	}

5）resize

resize 改变 size 的大小，分以下三种情况讨论：

1. new_size <= now_size：delete data
2. new_size > now_size && new_size < capacity：insert data
3. new_size >= capacity：reserve and inser data

后两种情况可以合并，因为即使?reserve(new_size) 当 new_size < capacity 时也不会缩容。

代码示例：

		//resize
		void resize(const size_t sz, const char c = '\0')
		{
			if (sz < _size)
			{
				//delete
				_str[_size] = '\0';
				_size = sz;
			}
			else
			{
				reserve(sz);//检查容量，必要时扩容
				//insert
				for (size_t i = _size; i < sz; ++i)
				{
					_str[i] = c;
				}
				_str[_size] = '\0';
				_size = sz;
			}

		}

6）find

• 找某一个元素：size_t find(const char c, size_t pos = 0) const
• 找字串：size_t find(const char* s, size_t pos = 0) const
  ?? ? ? ? ? ? ?①暴力匹配：挨个找? → strstr；（示例代码采用暴力匹配）
  ? ? ? ? ? ? ? ②kmp(算法)：理论上效率高，但现实中很少用，实际上实现效率没有很高；
  ? ? ? ? ? ? ? ③BM(算法)：好用，但难。
  ? ? ? ? ? ? ?

代码示例：?

		// 返回c在string中第一次出现的位置

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

			return -1;
		}

		// 返回子串s在string中第一次出现的位置

		size_t find(const char* s, size_t pos = 0) const
		{
			assert(pos < _size);//check pos

			size_t len = strlen(s);
			for (size_t i = pos; i + len < _size; ++i)
			{
				char* p = strstr(_str + i, s);
				if (p != nullptr)
				{
					return p - _str;
				}
			}

			return -1;
		}

7）substr

substr：从 pos 位置取 len 长度的字符串

思路：1. pos+len >= size or len == npos：from pos to size
? ? ? ? ? ?2. else：from pos to pos+len

注意：传值返回，需要写 拷贝构造? → 涉及深拷贝的问题(详见下一部分?8）深拷贝?)

代码示例：

//从pos位置取len长度的字符串
		string substr(const size_t pos, const size_t len = npos)const
		{
			if ((len == npos) || (pos + len >= _size))
			{
				string tmp(_str + pos);//从pos往后的数据全部copy
				return tmp;
			}
			else
			{
				string tmp;
				tmp.reserve(len);//check capacity

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

8）深拷贝

copy constructor

代码示例：

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

赋值重载

如下图所示，赋值重载函数的实现思路：①开新空间；②将右操作数的数据拷贝到新空间；③释放旧空间——左操作数原本指向的空间；④让做左操作数指向新空间。
注意：自己给自己赋值的情况！（如果第一步就是释放旧空间，而此时是自己给自己赋值时，会导致错误的结果）

		string& operator=(const string& s)//assign
		{
			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;
			}

		}

补充说明：

1）sizeof(string)

不同平台下 string类 的底层设计不同。

2）string类设计上的效率问题：深拷贝的浪费

?既然深拷贝导致了浪费，那么我们考虑可不可以浅拷贝。

浅拷贝具有两个问题：
①两个对象中的两个指针指向同一块空间，而导致该空间会被析构两次。
②当我们修改其中一个对象的时候会影响另一个对象。

接下来我们针对以上两个问题做讨论。（以下仅作简单粗略的讨论，仅供了解）

1. 析构两次 👉 引用计数
   引用计数：记录有几个对象指向这个空间
   作用过程：引用计数 = 2 → 其中一个对象析构一次之后 → 引用计数减一
   ? ? ? ? ? ? ? ? ? 引用计数 = 1 → 另一个对象不执行析构 → 引用计数减一，并释放这个对象

   

   ?

2. 修改影响 👉 写时拷贝
   写时拷贝：对数据进行修改时进行深拷贝（延迟拷贝）
   作用过程：引用计数 = 1 → 修改行为可以直接进行
   ? ? ? ? ? ? ? ? ? 引用计数 ≠ 1 →? 要进行修改时，进行深拷贝，新开的空间配新的引用计数 → 引用计数减一
   全称：引用计数写时拷贝
   总结：在不需要修改的场景下，写时拷贝会避免很多资源浪费。

（ps.g++采用的是写时拷贝）

END?