• C++ —— 模拟实现string类

    目录

    1.类的声明

    2.成员变量的确定

    3.构造函数与析构函数

    4.赋值运算符重载

    5.流插入运算符重载

    6.reserve()的实现

    7.push_back()的实现

    8.append()的实现

    9.+=运算符重载

    10.[]运算符重载

    11.迭代器的实现

    12.insert()的实现

    13.erase()的实现

    14.find()的实现

    15.拷贝构造与赋值运算符重载的现代写法

    16.完整代码

    1.类的声明

    与C语言模拟实现中的库函数不同，C++中有命名空间的存在，我们只需把我们的代码封到自定义的命名空间即可。为了方便，成员函数的声明和定义不分离，统一放在类内中。

    那么我们的代码可以这么写：

    1. //string.h 头文件
    2. namespace lzw		//使用命名空间与标准库隔离
    3. {
    4. 	class string
    5. 	{
    6. 	public:
    7. 		//成员函数
    8. 	private:
    9. 		//成员变量
    10. 	};
    11. }

    2.成员变量的确定

    我们知道string类是其原生模板被char类型实例化的结果，也就是说我们需要char类型的数组或者指针(指向堆的某块空间)用来存储字符串，像顺序表一样，我们需要可以表示有效字符个数的变量以及表示当前除'\0'以外的容量的变量。

    那么成员变量就确定了：

    1. 		//成员变量
    2. 		char* _str;		//指向堆的某块空间的指针
    3. 		size_t _size;		//表有效字符的个数
    4. 		size_t _capacity;		//除'\0'外的可用容量

    3.构造函数与析构函数

    我们在使用标准库的string类时，最常用的初始化的方式有三种：不使用任何参数构造、使用字符串构造、使用对象构造。

    那么构造函数我们便可以这样实现：

    1.         string(const char* str = "")
    2. 	    {
    3. 			_size = _capacity = strlen(str);
    4. 			_str = new char[_capacity + 1];
    5. 			strcpy(_str, str);
    6. 		}
    7. 		string(const string& s)		//使用对象初始化就变成拷贝构造了
    8. 		{
    9. 			_size = _capacity = s._size;
    10. 			_str = new char[_capacity + 1];		//一定是深拷贝
    11. 			strcpy(_str, s._str);
    12. 		}

    第一个构造函数我们使用了缺省参数，也就是给了一个空字符串。空字符串实际上并不为空，还有一个隐藏的'\0'，后来用 strcpy 拷贝至我们自己设计的成员变量指向的空间中(包括'\0'一起拷贝)，所以我们看似没有给定'\0'实际上我们已经悄悄的给了。

    那么析构函数的设计就是与构造函数的逻辑相反了：

    1. 		~string()
    2. 		{
    3. 			delete[] _str;
    4. 			_size = _capacity = 0;
    5. 		}

    4.赋值运算符重载

    虽然我们可以使用 = 来给给stirng对象赋值一个字符串，这是因为隐式类型转换的缘故，如果构造函数前面加上了 explicit 关键字的话，隐式类型转换就不能使用了。

    即使我们可以使用隐式类型转换来给string对象赋值一个字符串，但我们依然要提供一个 =运算符重载来让对象与对象之间赋值。我么不写不依然可以使用赋值运算符重载吗？记住了，我们不显示定义赋值运算符重载，编译器会自动生成一个进行浅拷贝的赋值运算符重载。

    1. 		string& operator=(const string& s)
    2. 		{
    3. 			if (this != &s)		//确保不是自我赋值
    4. 			{
    5. 				char* tmp = new char[s._capacity + 1];		//开辟空间
    6. 				strcpy(tmp, s._str);		//拷贝字符串
    7.  
    8. 				delete[] _str;		//改变_str,指向新的空间
    9. 				_str = tmp;
    10.  
    11. 				_size = s._size;
    12. 				_capacity = s._capacity;
    13. 			}
    14. 			return *this;
    15. 		}

    5.流插入运算符重载

    这个运算符重载就可以明显感受到C++相比C语言的优越性了，我们不需要像在C语言中输出结构体的成员时那么辛苦了，我们只需要简单的使用一个运算符重载。

    1. 		friend std::ostream& operator<<(std::ostream& out, const string& s)
    2. 		{
    3. 			out << s._str;
    4. 			return out;
    5. 		}

    6.reserve()的实现

    这个函数可谓是极其重要的函数，我们在模拟实现的时候许多地方会用到这个函数。原生reserve()作用是改变对象的容量大小，我们在模拟实现的时候也要实现这个功能。因为很多地方，例如push_back、insert、甚至+=运算符重载时，都会涉及到对象的元素个数变化，一旦变化容量就要随之变化，否则就会出现元素个数多于容量的尴尬场面。

    首先设计这个函数是一个合理并且明智的选择：

    1. 		void reserve(size_t n)
    2. 		{
    3. 			char* tmp = new char[n + 1];		//C++没有类似realloc的函数
    4. 			strcpy(tmp, _str);		//所以统一使用异地扩容办法
    5. 			delete[] _str;
    6. 			_str = tmp;
    7. 			_capacity = n;		//注意我们的_capacity描述的是不包括'\0'的容量
    8. 		}

    7.push_back()的实现

    有了reserve()的支持，那么尾插字符的工作就轻松多了：

    1. 		void push_back(char ch)
    2. 		{
    3. 			if (_size == _capacity)
    4. 			{
    5. 				int newcapacity = _capacity == 0 ? 4 : _capacity * 2;
    6. 				reserve(newcapacity);;
    7. 			}
    8. 			_str[_size++] = ch;
    9. 			_str[_size] = '\0';		//对于尾插字符，我们需要手动放置'\0'
    10. 		}

    现在让我们复习一下顺序表或者说学一个新东西：为什么要定义 newcapacity 这个变量？

    如果我们实例对象时没有给定任何参数，那么成员变量 _capacity 的值就为0。我们的容量变化理念是呈二倍增长。如果贸然使用值为0的 _capacity 作为 reserve() 函数的实参，那么尾插的工作就无法完成。

    1. 	string s1;		//如果直接用 _capacity*2 作为 reserve() 的参数
    2. 	s1.push_back('x');		//那么尾插必定是不行的

    8.append()的实现

    有了尾插字符，我们也要想办法尾插字符串。实际上过程太过于简单，这里直接放代码了：

    1. 		void append(const char* str)
    2. 		{
    3. 			if (_size + strlen(str) > _capacity)
    4. 			{
    5. 				reserve(_size + strlen(str));		//开辟足够的空间
    6. 			}
    7. 			strcat(_str, str);		//巧用函数
    8. 			_size += strlen(str);		//不忘改变有效字符个数
    9. 		}

    9.+=运算符重载

    += 才是最常用的武器。我们已经实现了push_back和append了，剩下的任务就是调用它们了：

    1. 		string& operator+=(const char* str)
    2. 		{
    3. 			append(str);
    4. 			return *this;
    5. 		}
    6. 		string& operator+=(char ch)		//重载
    7. 		{
    8. 			push_back(ch);
    9. 			return *this;
    10. 		}

    10.[]运算符重载

    []运算符也是常用的武器。

    1. 		char& operator[](size_t pos)		
    2. 		{
    3. 			return _str[pos];
    4. 		}
    5. 		char operator[](size_t pos) const		//需要兼顾const 修饰的对象
    6. 		{
    7. 			return _str[pos];
    8. 		}

    11.迭代器的实现

    我们一定要知道：迭代器的很多行为与指针类似。或者说，我们完全可以把迭代器当成指针来用。因为迭代器可以代表指向某个元素，指针也可以；迭代器可以更新到下一个元素的位置，指针也可以；迭代器可以通过解引用来找到指向的元素，指针也可以。

    1.         typedef char* iterator;
    2. 		
    3.         iterator begin()
    4.         {
    5. 	        return _str;		//数组名就是首元素地址
    6.         }
    7.         iterator end()
    8.         {
    9. 	        return _str + _size;		//指向最后一个元素的下一个位置，即'\0'
    10.         }
    11.         iterator begin() const
    12. 		{
    13. 			return _str;		
    14. 		}
    15. 		iterator end() const
    16. 		{
    17. 			return _str + _size;		
    18. 		}

    12.insert()的实现

    兜兜转转又到了顺序表的位置挪动，插入的类型有两个：一是字符，而是字符串。至于代码的算法，还希望读者亲自体会。

    1. string& insert(size_t pos, char ch)
    2. 		{
    3. 			if (_size == _capacity)
    4. 			{
    5. 				int newcapacity = _capacity == 0 ? 4 : _capacity * 2;
    6. 				reserve(newcapacity);
    7. 			}		//检查容量是否足够
    8.  
    9. 			int end = _size + 1;
    10. 			while (end > pos)
    11. 			{
    12. 				_str[end] = _str[end - 1];
    13. 				--end;
    14. 			}		//数据的挪动
    15. 			_str[pos] = ch;
    16. 			_size += 1;
    17. 			return *this;
    18. 		}
    19. 		
    20. 		string& insert(size_t pos, const char* str)
    21. 		{
    22. 			if (_size + strlen(str) > _capacity)
    23. 			{
    24. 				reserve(_size + strlen(str));
    25. 			}
    26.  
    27. 			int end = _size + strlen(str);
    28. 			while (end > pos)
    29. 			{
    30. 				_str[end] = _str[end - strlen(str)];
    31. 				--end;
    32. 			}
    33. 			strncpy(_str + pos, str,strlen(str));
    34. 			_size += strlen(str);
    35. 			return *this;
    36. 		}

    13.erase()的实现

    这个函数的功能与insert()相反。不过这个函数涉及到一个概念——npos。npos是一个无符号的数，是size_t类型的最大值。也就是 size_t 的比特位全为1，所以赋值可以直接给它赋-1(原、反、补规则)。

    如果不加任何修饰地作为成员变量，虽然可以，但还有优化的空间。首先 npos 属于我们的string类，而且它的值不会改变，所以我们可以用const修饰；其次我们完全可以像函数那样把 npos 放在公共空间，也就是使用 static 修饰。不过有人又要问了，static 修饰的成员变量要在类外定义， 我懒得去定义。这里我告诉大家，C++11中，const修饰的static成员变量(只能是整型)，可以直接给定缺省值。

    那么我们的erase就可以出来了：

    1.         string& erase(size_t pos =0, size_t len = npos)		//如果不传参，默认清空字符串
    2. 		{
    3. 			assert(pos < _size);		//删除的起始位置必定在有效字符里
    4. 			if (len >= _size - pos)
    5. 			{
    6. 				_str[pos] = '\0';		//起始位置之后的都要删除
    7. 			}
    8. 			else
    9. 			{
    10. 				size_t end = pos + len;
    11. 				strcpy(_str + pos, _str + end);
    12. 				_size -= len;
    13. 			}
    14. 			return *this;
    15. 		}
    16.  
    17.  
    18. 		const static size_t npos = -1;        //成员变量

    14.find()的实现

    上一篇我们讲过这是个非常实用的接口。原生的string类的find()函数可以查找字符、字符串、对象并返回第一次出现的位置，如果没有就返回npos。我们也要实现这个功能。

    其中的算法是比较简单的，我认为各位读者花三秒钟就能理清楚其中的思路：

    1.         size_t find(char ch, size_t pos = 0) const		//pos是查找的起始位置
    2. 		{
    3. 		    assert(pos < _size);
    4. 			while (pos < _size)
    5. 			{
    6. 				if (_str[pos] == ch)
    7. 				{
    8. 					return pos;
    9. 				}
    10. 				pos++;
    11. 			}
    12. 			return npos;
    13. 		}
    14. 		size_t find(const char* str, size_t pos = 0) const
    15. 		{
    16. 			assert(pos < _size);
    17. 			char* ret = strstr(_str+pos, str);		//注意开始查找的位置
    18. 			if (ret == nullptr)
    19. 			{
    20. 				return npos;
    21. 			}
    22. 			else
    23. 			{
    24. 				return ret - _str;		//指针相减等于元素个数
    25. 			}
    26. 		}
    27. 		size_t find(const string& s, size_t pos = 0) const
    28. 		{
    29. 			assert(pos < _size);
    30. 			char* tmp = strstr(_str+pos, s._str);		//注意开始查找的位置
    31. 			if (tmp == nullptr)
    32. 			{
    33. 				return npos;
    34. 			}
    35. 			else
    36. 			{
    37. 				return tmp - _str;
    38. 			}
    39. 		}

    15.拷贝构造与赋值运算符重载的现代写法

    即使上面的实现的拷贝构造和赋值运算符能够完成任务，但是这样的写法是非常保守的，体现不出我们作为C++程序员的"功力"。所以现在对拷贝构造和赋值运算符进行整改和升级，代码非常简单，大家仔细分析即可：

    1. 		//拷贝构造的现代写法
    2. 		void swap(string& s)		//模拟实现了string类提供的swap接口
    3. 		{
    4. 			std::swap(_str, s._str);
    5. 			std::swap(_size, s._size);
    6. 			std::swap(_capacity, s._capacity);
    7. 		}
    8. 		string(const string& s)
    9. 			:_str(nullptr)
    10. 			,_size(0)
    11. 			,_capacity(0)
    12. 		{
    13. 			string tmp(s._str);		//先使用一个临时对象构造
    14. 			swap(tmp);		//然后交换内容
    15. 			//this->swap(tmp);		//与上面等同的swap调用
    16. 		}
    1. 		//赋值运算符重载的现代写法
    2. 		string& operator=(string s)		//使用传值调用，s就是一个临时对象
    3. 		{
    4. 			swap(s);		//交换,这里的swap等同与拷贝构造的swap
    5. 			return *this;
    6. 		}

    16.完整代码

    因为string类的接口设计的实在是太多了，我们就只挑几个常用来模拟实现一下。如果大家有兴趣，大家可以参照我给的这个头文件，继续往后实现吧！

    1. //string.h 头文件
    2.  
    3. #include 
    4. #include 
    5. namespace lzw		//使用命名空间与标准库隔离
    6. {
    7. 	class string
    8. 	{
    9. 		
    10.  
    11. 	public:
    12. 		//成员函数
    13.  
    14. 		typedef char* iterator;
    15. 		
    16. 		iterator begin()
    17. 		{
    18. 			return _str;		//数组名就是首元素地址
    19. 		}
    20. 		iterator end()
    21. 		{
    22. 			return _str + _size;		//指向最后一个元素的下一个位置，即'\0'
    23. 		}
    24. 		iterator begin() const
    25. 		{
    26. 			return _str;		
    27. 		}
    28. 		iterator end() const
    29. 		{
    30. 			return _str + _size;		
    31. 		}
    32.  
    33. 		string(const char* str = "")
    34. 		{
    35. 			_size = _capacity = strlen(str);
    36. 			_str = new char[_capacity + 1];
    37. 			strcpy(_str, str);
    38. 		}
    39. 		//string(const string& s)		//使用对象初始化就变成拷贝构造了
    40. 		//{
    41. 		//	_size = _capacity = s._size;
    42. 		//	_str = new char[_capacity + 1];		//一定是深拷贝
    43. 		//	strcpy(_str, s._str);
    44. 		//}
    45.  
    46. 		//拷贝构造的现代写法
    47. 		void swap(string& s)		//模拟实现了string类提供的swap接口
    48. 		{
    49. 			std::swap(_str, s._str);
    50. 			std::swap(_size, s._size);
    51. 			std::swap(_capacity, s._capacity);
    52. 		}
    53. 		string(const string& s)
    54. 			:_str(nullptr)
    55. 			,_size(0)
    56. 			,_capacity(0)
    57. 		{
    58. 			string tmp(s._str);		//先使用一个临时对象构造
    59. 			swap(tmp);		//然后交换内容
    60. 			//this->swap(tmp);		//与上面等同的swap调用
    61. 		}
    62.  
    63.  
    64. 		~string()
    65. 		{
    66. 			delete[] _str;
    67. 			_size = _capacity = 0;
    68. 		}
    69. 		friend std::ostream& operator<<(std::ostream& out, const string& s)
    70. 		{
    71. 			out << s._str;
    72. 			return out;
    73. 		}
    74.  
    75. 		//string& operator=(const string& s)
    76. 		//{
    77. 		//	if (this != &s)		//确保不是自我赋值
    78. 		//	{
    79. 		//		char* tmp = new char[s._capacity + 1];		//开辟空间
    80. 		//		strcpy(tmp, s._str);		//拷贝字符串
    81.  
    82. 		//		delete[] _str;		//改变_str,指向新的空间
    83. 		//		_str = tmp;
    84.  
    85. 		//		_size = s._size;
    86. 		//		_capacity = s._capacity;
    87. 		//	}
    88. 		//	return *this;
    89. 		//}
    90.  
    91. 		//赋值运算符重载的现代写法
    92. 		string& operator=(string s)		//使用传值调用，s就是一个临时对象
    93. 		{
    94. 			swap(s);		//交换,这里的swap等同与拷贝构造的swap
    95. 			return *this;
    96. 		}
    97.  
    98. 		~string()
    99. 		{
    100. 			delete[] _str;
    101. 			_size = _capacity = 0;
    102. 		}
    103. 		friend std::ostream& operator<<(std::ostream& out, const string& s)
    104. 		{
    105. 			out << s._str;
    106. 			return out;
    107. 		}
    108.  
    109. 		void reserve(size_t n)
    110. 		{
    111. 			char* tmp = new char[n + 1];		//C++没有类似realloc的函数
    112. 			strcpy(tmp, _str);		//所以统一使用异地扩容办法
    113. 			delete[] _str;
    114. 			_str = tmp;
    115. 			_capacity = n;		//注意我们的_capacity描述的是不包括'\0'的容量
    116. 		}
    117.  
    118. 		void push_back(char ch)
    119. 		{
    120. 			if (_size == _capacity)
    121. 			{
    122. 				int newcapacity = _capacity == 0 ? 4 : _capacity * 2;
    123. 				reserve(newcapacity);;
    124. 			}
    125. 			_str[_size++] = ch;
    126. 			_str[_size] = '\0';		//对于尾插字符，我们需要手动放置'\0'
    127. 		}
    128.  
    129. 		void append(const char* str)
    130. 		{
    131. 			if (_size + strlen(str) > _capacity)
    132. 			{
    133. 				reserve(_size + strlen(str));		//开辟足够的空间
    134. 			}
    135. 			strcat(_str, str);		//巧用函数
    136. 			_size += strlen(str);		//不忘改变有效字符个数
    137. 		}
    138. 		
    139. 		string& operator+=(const char* str)
    140. 		{
    141. 			append(str);
    142. 			return *this;
    143. 		}
    144. 		string& operator+=(char ch)		//重载
    145. 		{
    146. 			push_back(ch);
    147. 			return *this;
    148. 		}
    149.  
    150. 		char& operator[](size_t pos)		
    151. 		{
    152. 			return _str[pos];
    153. 		}
    154. 		char& operator[](size_t pos) const		//需要兼顾const 修饰的对象
    155. 		{
    156. 			return _str[pos];
    157. 		}
    158.  
    159. 		string& insert(size_t pos, char ch)
    160. 		{
    161. 			if (_size == _capacity)
    162. 			{
    163. 				int newcapacity = _capacity == 0 ? 4 : _capacity * 2;
    164. 				reserve(newcapacity);
    165. 			}		//检查容量是否足够
    166.  
    167. 			int end = _size + 1;
    168. 			while (end > pos)
    169. 			{
    170. 				_str[end] = _str[end - 1];
    171. 				--end;
    172. 			}		//数据的挪动
    173. 			_str[pos] = ch;
    174. 			_size += 1;
    175. 			return *this;
    176. 		}
    177. 		
    178. 		string& insert(size_t pos, const char* str)
    179. 		{
    180. 			if (_size + strlen(str) > _capacity)
    181. 			{
    182. 				reserve(_size + strlen(str));
    183. 			}
    184.  
    185. 			int end = _size + strlen(str);
    186. 			while (end > pos)
    187. 			{
    188. 				_str[end] = _str[end - strlen(str)];
    189. 				--end;
    190. 			}
    191. 			strncpy(_str + pos, str,strlen(str));
    192. 			_size += strlen(str);
    193. 			return *this;
    194. 		}
    195.  
    196. 		string& erase(size_t pos =0, size_t len = npos)		//如果不传参，默认清空字符串
    197. 		{
    198. 			assert(pos < _size);		//删除的起始位置必定在有效字符里
    199. 			if (len >= _size - pos)
    200. 			{
    201. 				_str[pos] = '\0';		//起始位置之后的都要删除
    202. 			}
    203. 			else
    204. 			{
    205. 				size_t end = pos + len;
    206. 				strcpy(_str + pos, _str + end);
    207. 				_size -= len;
    208. 			}
    209. 			return *this;
    210. 		}
    211.  
    212. 		size_t find(char ch, size_t pos = 0) const		//pos是查找的起始位置
    213. 		{
    214. 			assert(pos < _size);
    215. 			while (pos < _size)
    216. 			{
    217. 				if (_str[pos] == ch)
    218. 				{
    219. 					return pos;
    220. 				}
    221. 				pos++;
    222. 			}
    223. 			return npos;
    224. 		}
    225. 		size_t find(const char* str, size_t pos = 0) const
    226. 		{
    227. 			assert(pos < _size);
    228. 			char* ret = strstr(_str+pos, str);		//注意开始查找的位置
    229. 			if (ret == nullptr)
    230. 			{
    231. 				return npos;
    232. 			}
    233. 			else
    234. 			{
    235. 				return ret - _str;		//指针相减等于元素个数
    236. 			}
    237. 		}
    238. 		size_t find(const string& s, size_t pos = 0) const
    239. 		{
    240. 			assert(pos < _size);
    241. 			char* tmp = strstr(_str+pos, s._str);		//注意开始查找的位置
    242. 			if (tmp == nullptr)
    243. 			{
    244. 				return npos;
    245. 			}
    246. 			else
    247. 			{
    248. 				return tmp - _str;
    249. 			}
    250. 		}
    251.  
    252. 	private:
    253. 		//成员变量
    254. 		char* _str;		//指向堆的某块空间的指针
    255. 		size_t _size;		//表有效字符的个数
    256. 		size_t _capacity;		//除'\0'外的可用容量
    257. 		const static size_t npos = -1;
    258. 	};
    259. }

  • 相关阅读:
    从文件读取和转换编程
    sqlserver 开启发布订阅模式
    java进程内存分析工具-生成core dump文件，并读取分析：jmap, jhat
    React-2 JSX知识
    【后端速成 Vue】初识指令(下)
    Unity URP 如何写基础的曲面细分着色器
    springboot查看和修改最大上传文件限制
    结构化思维助力Prompt创作：专业化技术讲解和实践案例
    58 练习 1
    基于STM32单片机的简单红外循迹的实现
  • 原文地址：https://blog.csdn.net/weixin_59913110/article/details/127715781