• 【C++】string的模拟实现

    需要云服务器等云产品来学习Linux的同学可以移步/-->腾讯云<--/-->阿里云<--/-->华为云<--/官网，轻量型云服务器低至112元/年，新用户首次下单享超低折扣。

     目录

    一、std::swap和std::string::swap的区别

    二、string的存储方式

    1、vs中string对象的大小

    2、vs中string的底层结构

    3、g++中string对象的大小

    4、g++中string的底层结构

    三、string的默认构造函数

    1、构造函数

    2、拷贝构造

    3、赋值运算符重载

    4、析构函数

    四、string中的小接口

    五、遍历接口的实现

    1、对operator[]进行重载

    2、迭代器

    六、reserve和resize

    七、插入删除查找相关接口

    1、push_back、append、+=

    2、insert和erase

    3、find

    八、流插入和流提取

    九、模拟实现的string整体代码

    一、std::swap和std::string::swap的区别

    如果用std::swap交换两个string对象，将会发生1次构造和2次赋值，也就是三次深拷贝；而使用std::string::swap仅交换成员，代价较小。

    二、string的存储方式

    1、vs中string对象的大小

    32位环境下，string大小为28字节，64位下为40字节。

    2、vs中string的底层结构

    1. char _buff[16];
    2. char* ptr;
    3. size_t size;
    4. size_t capacity;

    根据内存对齐规则，32位环境下，string大小为28字节，64位下为40字节。

    当string存储的字符小于16时，存储于_buff中，大于等于16，存储于ptr指向的堆空间里。

    这样的目的是为了减少小块的内存碎片，也是一种以空间换时间的做法。

    3、g++中string对象的大小

    32位环境下，string大小为4字节，64位下为8字节。

    4、g++中string的底层结构

    g++下，string是通过写时拷贝实现的，内部只有一个指针，该指针指向一块堆空间，用于存储字符串，内部包含如下字段。

    1. struct _Rep_base
    2. {
    3. 	size_type _M_length;//空间总大小
    4. 	size_type _M_capacity;//字符串有效长度
    5. 	_Atomic_word _M_refcount;//引用计数
    6. };

    g++中的string和vs中的string完全不一样，g++中拷贝构造一个对象，两个对象存储的字符地址是一模一样的。

    g++中string拷贝时为了提高效率，默认进行浅拷贝，使用引用计数来保证空间不被多次析构。如果其中一个string提出修改，那么将会发生写时拷贝。（赌徒思想，就是赌用户不写，不写就赚）

    三、string的默认构造函数

    1、构造函数

    1. string(const char* s = "")
    2. {
    3.     _size = strlen(s);//_size和_capacity均不包含'\0'
    4.     _capacity = _size;
    5.     _arr = new char[_size + 1];
    6.     memcpy(_arr, s, _size + 1);
    7. }

    构造函数用缺省值，能够满足空串的构造。

    这里设计_size和_capacity均不包含'\0'。_arr的空间多new一个，用于储存'\0'。

    再将形参的内存拷贝至_arr中，即可完成构造。

    2、拷贝构造

    写法1：老老实实的根据string对象的私有变量进行拷贝构造。

    1. string(const string& s)
    2. {
    3.     _size = s._size;//_size和_capacity均不包含'\0'
    4.     _capacity = s._capacity;
    5.     _arr = new char[_capacity + 1];
    6.     memcpy(_arr, s._arr, _capacity + 1);
    7. }

    写法2：通过构造一个临时对象，将这个临时对象的私有变量全部和*this的私有变量交换。

    注意拷贝构造需要先将_arr初始化为nullptr，防止后续tmp拿到随机地址。（tmp销毁将调用析构函数，对一块随机地址的空间进行析构程序将会崩溃）

    1. void swap(string& s)
    2. {
    3.     std::swap(_arr, s._arr);
    4.     std::swap(_size, s._size);
    5.     std::swap(_capacity, s._capacity);
    6. }
    7. string(const string& s)
    8.     :_arr(nullptr)//防止交换后tmp._arr为随机值，析构出错
    9. {
    10.     string tmp(s.c_str());//构造
    11.     swap(tmp);
    12. }

    3、赋值运算符重载

    写法1：同样的老实人写法。这种写法要防止自己给自己赋值！

    1. string& operator=(const string& s)
    2. {
    3.     if (this != &s)//防止自己给自己赋值
    4.     {
    5.         _size = s._size;
    6.         _capacity = s._capacity;
    7.         char* tmp = new char[_capacity + 1];
    8.         delete[] _arr;
    9.         _arr = tmp;
    10.         memcpy(_arr, s._arr, _capacity + 1);
    11.     }
    12.     return *this;
    13. }

    写法2：通过构造临时变量tmp，完成赋值。这种写法无需担心自己给自己赋值的情况，并且_arr无需初始化为nullptr。 

    1. void swap(string& s)
    2. {
    3.     std::swap(_arr, s._arr);
    4.     std::swap(_size, s._size);
    5.     std::swap(_capacity, s._capacity);
    6. }
    7. string& operator=(const string& s)
    8. {
    9.     string tmp(s.c_str());//构造
    10.     swap(tmp);
    11.     return *this;
    12. }

    4、析构函数

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

    四、string中的小接口

    1. //string的size()接口
    2. size_t size()const//右const修饰*this，这样const和非const对象均可调用
    3. {
    4.     return _size;
    5. }
    6. //string的c_str()接口
    7. const char* c_str()const
    8. {
    9.     return _arr;
    10. }
    11. //string的capacity()接口
    12. size_t capacity()const
    13. {
    14.     return _capacity;
    15. }
    16. //string的clear()接口
    17. void clear()
    18. {
    19.     _arr[0] = '\0';
    20.     _size = 0;
    21. }
    22. //string的判空
    23. bool empty()const
    24. {
    25.     return _size == 0 ? false : true;
    26. }

    如果函数形参不发生改变的，无脑加const修饰。

    只有指针和引用会有const权限问题。

    五、遍历接口的实现

    1、对operator[]进行重载

    1. char& operator[](size_t pos)//普通对象，可读可写
    2. {
    3.     assert(pos < _size);
    4.     return _arr[pos];
    5. }
    6. const char& operator[](size_t pos)const//const对象，仅读
    7. {
    8.     assert(pos < _size);
    9.     return _arr[pos];
    10. }

    让字符串进行下标式的访问，需要重载两个operator[]函数，正常对象去调可读可写，const对象调用只读。

    2、迭代器

    1. typedef char* iterator;
    2. iterator begin()
    3. {
    4.     return _arr;
    5. }
    6. iterator end()//end指向字符串的'\0'
    7. {
    8.     return _arr + _size;
    9. }

    string的迭代器是字符指针，写完迭代器就可以用迭代器实现访问、修改了。

    范围for的底层也是一个迭代器，但是范围for底层只认begin()和end(),如果和自己实现的迭代器接口名称对不上，那么范围for将无法使用。

    六、reserve和resize

    1. //sring的reserve接口, 如果预开空间小于现有空间，将不会改变容量。
    2. void reserve(size_t n = 0)
    3. {
    4.     if (n + 1 > _capacity)
    5.     {
    6.         char* tmp = new char[n + 1];
    7.         memset(tmp, '\0', n + 1);
    8.         memcpy(tmp, _arr, _size);
    9.         delete[] _arr;
    10.         _arr = tmp;
    11.         _capacity = n;
    12.     }
    13. }
    14. //sring的resize接口
    15. void resize(size_t n, char c)
    16. {
    17.     //判断n的大小
    18.     if (n > _capacity)
    19.     {
    20.         reserve(n);
    21.         memset(_arr + _size, c, n - _size);
    22.         _size = n;
    23.     }
    24.     else
    25.     {
    26.         _arr[n] = '\0';
    27.         _size = n;
    28.     }
    29. }

    reserve是扩容，可以用于预开空间，防止频繁的空间申请。申请一块n+1大小的空间，将该空间全部初始化'\0'，再将_arr中的数据拷贝至tmp中，释放_arr，_arr指向tmp。

    在resize中需要考虑_size扩容和缩容的问题。

    七、插入删除查找相关接口

    1、push_back、append、+=

    1. string& push_back(const char c)
    2. {
    3.     //判断容量
    4.     if (_size == _capacity)
    5.     {
    6.         size_t newCapacity = _capacity == 0 ? 4 : _capacity * 2;//防止出现空串的情况
    7.         reserve(newCapacity);
    8.     }
    9.     _arr[_size++] = c;
    10.     return *this;
    11. }
    12. string& append(const char* s)
    13. {
    14.     //判断容量
    15.     size_t len = strlen(s);
    16.     if (_size + len > _capacity)
    17.     {
    18.         reserve(_size + len);
    19.     }
    20.     strcpy(_arr + _size, s);
    21.     _size += len;
    22.     return *this;
    23. }
    24. string& operator+=(const char c)
    25. {
    26.     push_back(c);
    27.     return *this;
    28. }
    29. string& operator+=(const char* s)
    30. {
    31.     append(s);
    32.     return *this;
    33. }

    写push_back要考虑到原对象为空串的情况（即_capacity为0）。

    +=可以复用push_back和append。

    2、insert和erase

    1. string& insert(size_t pos, char c)
    2. {
    3.     assert(pos < _size);
    4.     //判断容量
    5.     if (_size == _capacity)
    6.     {
    7.         reserve(_capacity + 1);
    8.     }
    9.     //挪动数据
    10.     for (size_t i = _size; i > pos; --i)
    11.     {
    12.         _arr[i] = _arr[i - 1];
    13.     }
    14.     _arr[pos] = c;
    15.     ++_size;
    16.     return *this;
    17. }
    18. string& insert(size_t pos, const char* s)
    19. {
    20.     size_t len = strlen(s);
    21.     //判断容量
    22.     if (len + _size > _capacity)
    23.     {
    24.         reserve(len + _size);
    25.     }
    26.     //挪动数据
    27.     for (size_t i = _size + len; i > pos + len - 1; --i)
    28.     {
    29.         _arr[i] = _arr[i - len];
    30.     }
    31.     memcpy(_arr + pos, s, len);
    32.     _size += len;
    33.     return *this;
    34. }
    35. string& erase(size_t pos, size_t len = npos)
    36. {
    37.     assert(pos < _size);
    38.     //先判断删到底的情况
    39.     if (len == npos || pos + len >= _size)
    40.     {
    41.         _arr[pos] = '\0';
    42.         _size = pos;
    43.     }
    44.     else
    45.     {
    46.         memcpy(_arr + pos, _arr + pos + len, _size - pos - len);
    47.         _size -= len;
    48.     }
    49.     return *this;
    50. }

    insert接口在挪动数据时，从最后一个元素的后一个（后len个）位置开始覆盖，可以保证不出现size_t 类型越界的情况。

    erase接口，需要分类讨论字符串是否删到底。

    注意，这个pos是const static成员，C++语法中，只有指针和整型的const static成员是可以在类中进行初始化的。

    3、find

    1. size_t find(const char c, size_t pos = 0)const
    2. {
    3.     assert(pos < _size);
    4.     for (size_t i = pos; i < _size; ++i)
    5.     {
    6.         if (_arr[i] == c)
    7.         {
    8.             return i;
    9.         }
    10.     }
    11.     return npos;
    12. }
    13. size_t find(const char* s, size_t pos = 0)const
    14. {
    15.     assert(pos < _size);
    16.     const char* p = strstr(_arr, s);
    17.     if (p != nullptr)
    18.     {
    19.         return _arr - p;
    20.     }
    21.     return npos;
    22. }

    从指定位置找字符或字符串，找到了，返回第一个匹配字符/子串的下标。

    八、流插入和流提取

    1. //流插入和流提取的重载时为了自定义类型的输入输出
    2. inline ostream& operator<<(ostream& out, const string& s)//这里访问的到私有，所以可以不用写成友元函数
    3. {
    4.     for (size_t i = 0; i < s.size(); ++i)//流插入按照_size打印，c_str找到'\0'结束打印
    5.     {                                    //比如我在字符串中间插入一个'\0',打印结果不一样
    6.         out << s[i];
    7.     }
    8.     return out;
    9. }
    10. inline istream& operator>>(istream& in, string& s)
    11. {
    12.     s.clear();//用之前先清空s
    13.     //in >> c;//流提取不会识别空格和换行
    14.     char c = in.get();
    15.     char buff[128] = { '\0' };//防止频繁扩容
    16.     size_t i = 0;
    17.     while (c != ' ' && c != '\n')
    18.     {
    19.         if (i == 127)
    20.         {
    21.             s += buff;
    22.             i = 0;
    23.         }
    24.         buff[i++] = c;
    25.         c = in.get();
    26.     }
    27.     if (i > 0)
    28.     {
    29.         buff[i] = '\0';
    30.         s += buff;
    31.     }
    32.     return in;
    33. }

    因为string提供了访问私有的接口，所以流插入和流提取可以不用重载成string类的友元函数。

    对于流提取，如果频繁的尾插，会造成频繁扩容。而且C++的扩容和C语言的扩容不一样，C++使用new不能原地扩容，只能异地扩容，异地扩容就会导致新空间的开辟、数据的拷贝、旧空间释放。为了防止频繁扩容，我们可以创建一个可以存储128字节的数组，在这个数组中操作，这个数组满了就尾插至对象s中。

    为什么不能用getline，而是要一个字符一个字符尾插呢？因为流提取遇到空格和'\n'会结束提取，剩余数据暂存缓冲区，如果是getline的话，遇到空格是不会停止读取的。

    九、模拟实现的string整体代码

    1. #pragma once
    2. #define _CRT_SECURE_NO_WARNINGS 1
    3. #include 
    4. #include 
    5. using std::cout;
    6. using std::cin;
    7. using std::endl;
    8. using std::ostream;
    9. using std::istream;
    10. namespace jly
    11. {
    12. 	class string
    13. 	{
    14. 	public:
    15. 		void swap(string& s)
    16. 		{
    17. 			std::swap(_arr, s._arr);
    18. 			std::swap(_size, s._size);
    19. 			std::swap(_capacity, s._capacity);
    20. 		}
    21. 		//构造函数
    22. 		string(const char* s = "")
    23. 		{
    24. 			_size = strlen(s);//_size和_capacity均不包含'\0'
    25. 			_capacity = _size;
    26. 			_arr = new char[_size + 1];
    27. 			memcpy(_arr, s, _size + 1);
    28. 		}
    29. 		//拷贝构造
    30. 		//写法1
    31. 		//string(const string& s)
    32. 		//{
    33. 		//	_size = s._size;//_size和_capacity均不包含'\0'
    34. 		//	_capacity = s._capacity;
    35. 		//	_arr = new char[_capacity + 1];
    36. 		//	memcpy(_arr, s._arr, _capacity + 1);
    37. 		//}
    38. 		//写法2
    39. 		string(const string& s)
    40. 			:_arr(nullptr)//防止交换后tmp._arr为随机值，析构出错
    41. 		{
    42. 			string tmp(s.c_str());//构造
    43. 			swap(tmp);
    44. 		}
    45. 		//赋值运算符重载
    46. 		//写法1
    47. 		//string& operator=(const string& s)
    48. 		//{
    49. 		//	if (this != &s)//防止自己给自己赋值
    50. 		//	{ 
    51. 		//		_size = s._size;
    52. 		//		_capacity = s._capacity;
    53. 		//		char* tmp = new char[_capacity + 1];
    54. 		//		delete[] _arr;
    55. 		//		_arr = tmp;
    56. 		//		memcpy(_arr, s._arr, _capacity + 1);
    57. 		//	}
    58. 		//	return *this;
    59. 		//}
    60. 		//写法2
    61. 		string& operator=(const string& s)
    62. 		{
    63. 			string tmp(s.c_str());//构造
    64. 			swap(tmp);
    65. 			return *this;
    66. 		}
    67. 		//析构函数
    68. 		~string()
    69. 		{
    70. 			_size = _capacity = 0;
    71. 			delete[] _arr;
    72. 			_arr = nullptr;
    73. 		}
    74. 		//string的size()接口
    75. 		size_t size()const//右const修饰*this，这样const和非const对象均可调用
    76. 		{
    77. 			return _size;
    78. 		}
    79. 		//string的c_str()接口
    80. 		const char* c_str()const
    81. 		{
    82. 			return _arr;
    83. 		}
    84. 		//string的capacity()接口
    85. 		size_t capacity()const
    86. 		{
    87. 			return _capacity;
    88. 		}
    89. 		//string的clear()接口
    90. 		void clear()
    91. 		{
    92. 			_arr[0] = '\0';
    93. 			_size = 0;
    94. 		}
    95. 		//string的判空
    96. 		bool empty()const
    97. 		{
    98. 			return _size == 0 ? false : true;
    99. 		}
    100. 		//对operator[]进行重载
    101. 		char& operator[](size_t pos)//普通对象，可读可写
    102. 		{
    103. 			assert(pos < _size);
    104. 			return _arr[pos];
    105. 		}
    106. 		const char& operator[](size_t pos)const//const对象，仅读
    107. 		{
    108. 			assert(pos < _size);
    109. 			return _arr[pos];
    110. 		}
    111. 		//迭代器
    112. 		typedef char* iterator;
    113. 		iterator begin()const
    114. 		{
    115. 			return _arr;
    116. 		}
    117. 		iterator end()const//end指向字符串的'\0'
    118. 		{
    119. 			return _arr + _size ;
    120. 		}
    121. 		//string的reserve接口,如果预开空间小于现有空间，将不会改变容量。
    122. 		void reserve(size_t n=0)
    123. 		{
    124. 			if (n + 1 > _capacity)
    125. 			{
    126. 				char* tmp = new char[n + 1];
    127. 				memset(tmp, '\0', n + 1);
    128. 				memcpy(tmp, _arr, _size);
    129. 				delete[] _arr;
    130. 				_arr = tmp;
    131. 				_capacity = n;
    132. 			}
    133. 		}
    134. 		//string的resize接口
    135. 		void resize(size_t n, char c='\0')
    136. 		{
    137. 			//判断n的大小
    138. 			if (n > _capacity)
    139. 			{
    140. 				reserve(n);
    141. 				memset(_arr + _size,c,n-_size);
    142. 				_size = n;
    143. 			}
    144. 			else
    145. 			{
    146. 				_arr[n] = '\0';
    147. 				_size = n;
    148. 			}
    149. 		}
    150. 		//插入删除查找相关接口
    151. 		string& push_back(const char c)
    152. 		{
    153. 			//判断容量
    154. 			if (_size == _capacity)
    155. 			{
    156. 				size_t newCapacity = _capacity == 0 ? 4 : _capacity * 2;//防止出现空串的情况
    157. 				reserve(newCapacity);
    158. 			}
    159. 			_arr[_size++] = c;
    160. 			return *this;
    161. 		}
    162. 		string& append(const char* s)
    163. 		{
    164. 			//判断容量
    165. 			size_t len = strlen(s);
    166. 			if (_size + len > _capacity)
    167. 			{
    168. 				reserve(_size + len);
    169. 			}
    170. 			strcpy(_arr+_size,s);
    171. 			_size += len;
    172. 			return *this;
    173. 		}
    174. 		string& operator+=(const char c)
    175. 		{
    176. 			push_back(c);
    177. 			return *this;
    178. 		}
    179. 		string& operator+=(const char* s)
    180. 		{
    181. 			append(s);
    182. 			return *this;
    183. 		}
    184. 		string& insert(size_t pos, char c)
    185. 		{
    186. 			assert(pos < _size);
    187. 			//判断容量
    188. 			if (_size == _capacity)
    189. 			{
    190. 				reserve(_capacity + 1);
    191. 			}
    192. 			//挪动数据
    193. 			for (size_t i = _size; i > pos; --i)
    194. 			{
    195. 				_arr[i] = _arr[i - 1];
    196. 			}
    197. 			_arr[pos] = c;
    198. 			++_size;
    199. 			return *this;
    200. 		}
    201. 		string& insert(size_t pos, const char* s)
    202. 		{
    203. 			size_t len = strlen(s);
    204. 			//判断容量
    205. 			if (len + _size > _capacity)
    206. 			{
    207. 				reserve(len + _size);
    208. 			}
    209. 			//挪动数据
    210. 			for (size_t i = _size + len; i > pos + len - 1; --i)
    211. 			{
    212. 				_arr[i] = _arr[i - len];
    213. 			}
    214. 			memcpy(_arr + pos, s, len);
    215. 			_size += len;
    216. 			return *this;
    217. 		}
    218. 		string& erase(size_t pos, size_t len = npos)
    219. 		{
    220. 			assert(pos<_size);
    221. 			//先判断删到底的情况
    222. 			if (len == npos || pos + len >= _size)
    223. 			{
    224. 				_arr[pos] = '\0';
    225. 				_size = pos;
    226. 			}
    227. 			else
    228. 			{
    229. 				memcpy(_arr + pos, _arr + pos + len,_size-pos-len);
    230. 				_size -= len;
    231. 			}
    232. 			return *this;
    233. 		}
    234. 		size_t find(const char c, size_t pos = 0)const
    235. 		{
    236. 			assert(pos < _size);
    237. 			for (size_t i = pos; i < _size; ++i)
    238. 			{
    239. 				if (_arr[i] == c)
    240. 				{
    241. 					return i;
    242. 				}
    243. 			}
    244. 			return npos;
    245. 		}
    246. 		size_t find(const char* s, size_t pos = 0)const
    247. 		{
    248. 			assert(pos < _size);
    249. 			const char* p = strstr(_arr, s);
    250. 			if (p != nullptr)
    251. 			{
    252. 				return _arr - p;
    253. 			}
    254. 			return npos;
    255. 		}
    256. 	private:
    257. 		char* _arr;
    258. 		size_t _size;
    259. 		size_t _capacity;
    260. 		const static size_t npos = -1;//只有const static整型、指针成员变量可以在类中定义，其他类型不行
    261. 	};
    262. 	//流插入和流提取的重载时为了自定义类型的输入输出
    263. 	inline ostream& operator<<(ostream& out, const string& s)//这里访问得到私有，所以可以不用写成友元函数
    264. 	{
    265. 		for (size_t i = 0; i < s.size(); ++i)//流插入按照_size打印，c_str找到'\0'结束打印
    266. 		{                                    //比如我在字符串中间插入一个'\0',打印结果不一样
    267. 			out << s[i];
    268. 		}
    269. 		return out;
    270. 	}
    271. 	inline istream& operator>>(istream& in, string& s)
    272. 	{
    273. 		s.clear();//用之前先清空s
    274. 		//in >> c;//流提取不会识别空格和换行
    275. 		char c=in.get();
    276. 		char buff[128] = { '\0' };//防止频繁扩容
    277. 		size_t i = 0;
    278. 		while (c != ' ' && c != '\n')
    279. 		{
    280. 			if (i == 127)
    281. 			{
    282. 				s += buff;
    283. 				i = 0;
    284. 			}
    285. 			buff[i++] = c;
    286. 			c = in.get();
    287. 		}
    288. 		if (i > 0)
    289. 		{
    290. 			buff[i] = '\0';
    291. 			s += buff;
    292. 		}
    293. 		return in;
    294. 	}
    295. 	//测试函数
    296. 	void test1()
    297. 	{
    298. 	
    299. 	}
    300. }


    《 符合学习规律的超详细linux实战快速入门》

  • 相关阅读:
    InnoDB 是如何解决幻读的
    Eclipse中使用Git提交代码到Gitee
    STM32+UART串口+DMA收发
    No module named ‘_sqlite3‘解决，亲测有效
    u8g2 使用IIC驱动uc1617 lcd有时候某些像素显示不正确
    tiup dm reload
    代码随想录第40天|62.不同路径，63. 不同路径 II
    《数据仓库入门实践》
    学个锤子 | .Net零基础逆向教程 第三课（壳与作业）
    同花顺_代码解析_技术指标_M
  • 原文地址：https://blog.csdn.net/gfdxx/article/details/127893255