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

    目录

    一、string模拟实现

    1.1构造析构

    1.2迭代器

    1.3修改

    1.4查找

    1.5substr 深浅拷贝的区别

    1.6比较函数与流插入流提取

    二、string类的拷贝

    2.1浅拷贝与深拷贝

    2.2传统版与现代版区别

    2.3写时拷贝（了解）

    三、vs和g++下string结构的说明

    3.1vs下的string结构

    3.2g++下的string结构

    一、string模拟实现

    想要模拟实现自己的string类，主要的是构造、拷贝构造、迭代器、修改、查找等功能。

    实现一个简单的string 不考虑模板等一些复杂的优化结构

    1. namespace xc
    2. {
    3. 	class string
    4. 	{
    5. 	public:
    6.  
    7.  
    8.  
    9. 	private:
    10. 		char* _str;
    11. 		size_t _size;
    12. 		size_t _capacity;
    13. 	};
    14. }

    1.1构造析构

    简单的构造函数：

    1. class string
    2. {
    3. public:
    4. 	string()
    5. 		:_str(nullptr)
    6. 		,_size(0)
    7. 		,_capacity(0)
    8. 	{}
    9. 	string(const char*str)
    10. 	{
    11. 		_size = strlen(str);
    12. 		_capacity = _size;//定义的容量就是有效数据个数 new的话需要考虑 \0
    13. 		_str = new char[_capacity + 1];
    14. 		strcpy(_str, str);
    15. 	}
    16.  
    17. 	const char* c_str()//暂时没有写流提取，流插入所以转换为 _str打印
    18. 	{
    19. 		return _str;
    20. 	}
    21. private:
    22. 	char* _str;
    23. 	size_t _size;
    24. 	size_t _capacity;
    25. };

    程序崩溃，无法打印，原因是 string的无参构造 _str 初始化为 nullptr，转换为字符串打印时候会解引用知道遇到\0终止 但是这里对空指针进行了解引用 所以程序崩溃

    优化合并一下：

    1. class string
    2. {
    3. public:
    4. 	/*string()
    5. 		:_str(new char[1]{""})
    6. 		,_size(0)
    7. 		,_capacity(0)
    8. 	{}*/
    9. 	string(const char*str="")
    10. 	{
    11. 		_size = strlen(str);
    12. 		_capacity = _size;//定义的容量就是有效数据个数 new的话需要考虑 \0
    13. 		_str = new char[_capacity + 1];
    14. 		strcpy(_str, str);
    15. 	}
    16. 	~string()
    17. 	{
    18. 		delete[]_str;
    19. 		_str = nullptr;
    20. 		_size = _capacity = 0;
    21. 	}
    22. 	const char* c_str()//暂时没有写流提取，流插入所以转换为 _str打印
    23. 	{
    24. 		return _str;
    25. 	}
    26. private:
    27. 	char* _str;
    28. 	size_t _size;
    29. 	size_t _capacity;
    30. };

    一些频繁调用的短小函数可以直接在类里面定义实现 默认为 内联inline

    1. const char* c_str()const //暂时没有写流提取，流插入所以转换为 _str打印
    2. {
    3. 	return _str;
    4. }
    5. size_t size()const
    6. {
    7. 	return _size;
    8. }
    9. size_t capacity()const
    10. {
    11. 	return _capacity;
    12. }
    13. char& operator[](size_t pos)
    14. {
    15. 	assert(pos < _size);
    16. 	return _str[pos];
    17. }
    18. const char& operator[](size_t pos)const
    19. {
    20. 	assert(pos < _size);
    21. 	return _str[pos];
    22. }

    1.2迭代器

    实现基本的迭代器（正向迭代器和const正向迭代器）功能以支持 范围for，迭代器遍历

    1. public:
    2. 	typedef char* iterator;
    3. 	typedef char* const_iterator;
    4.  
    5. 	iterator begin()
    6. 	{
    7. 		return _str;
    8. 	}
    9.  
    10. 	iterator end()
    11. 	{
    12. 		return _str + _size;
    13. 	}
    14.  
    15. 	const_iterator begin()const
    16. 	{
    17. 		return _str;
    18. 	}
    19.  
    20. 	const_iterator end()const
    21. 	{
    22. 		return _str + _size;
    23. 	}

    1.3修改

    声明定义分离的模式，可能涉及扩容可以先处理一个 reserve 函数

    1. //.h
    2. void reserve(size_t n);
    3. void push_back(char ch);
    4. void append(const char*str);
    5. string& operator+=(char ch);
    6. string& operator+=(const char*str);
    7. //.cpp
    8.  
    9. void string::reserve(size_t n)
    10. {
    11. 	if (n > _capacity)
    12. 	{
    13. 		char* tmp = new char[n + 1];
    14. 		strcpy(tmp, _str);//拷贝内容
    15. 		delete[]_str;
    16. 		_str = tmp;//交换指针
    17. 		_capacity = n;
    18. 	}
    19.  
    20. }
    21. void string::push_back(char ch)
    22. {
    23. 	if (_capacity == _size)
    24. 	{
    25. 		reserve(_capacity == 0 ? 4 : _capacity * 2);
    26. 	}
    27. 	_str[_size++] = ch;
    28. }
    29. string& string::operator+=(char ch)
    30. {
    31. 	push_back(ch);
    32. 	return *this;
    33. }
    34.

    显然是因为没有\0终止符才出现了乱码

    1. void string::push_back(char ch)
    2. {
    3. 	if (_capacity == _size)
    4. 	{
    5. 		reserve(_capacity == 0 ? 4 : _capacity * 2);
    6. 	}
    7. 	_str[_size++] = ch;
    8. 	_str[_size] = '\0';
    9. }

    接下来实现字符串的插入

    1. void string::append(const char* str)//加的字符串可能需要扩容 需要if判断
    2. {
    3. 	size_t len = strlen(str);
    4. 	if (_size + len > _capacity)
    5. 	{
    6. 		//大于2倍 就需要多少开多少 少于2倍就开2倍空间
    7. 		reserve(_size + len > 2 * _capacity ? _size + len : 2 * _capacity);
    8. 	}
    9. 	strcpy(_str + _size, str); //第一个参数为\0地址
    10. 	_size += len;
    11. }
    12.  
    13. string& string::operator+=(const char* str)
    14. {
    15. 	append(str);
    16. 	return *this;
    17. }

    指定位置的插入删除 

    1. 	void insert(size_t pos, char ch);
    2. 	void insert(size_t pos, const char*str);
    3. 	void erase(size_t pos, size_t len=npos);
    4.  
    5. private:
    6. 	char* _str;
    7. 	size_t _size;
    8. 	size_t _capacity;
    9. 	static const size_t npos;

    增加了一个新成员变量 npos 该静态成员变量需要声明定义分离

    1. void string::insert(size_t pos, char ch)
    2. {
    3. 	assert(pos <= _size);
    4. 	if (_capacity == _size)
    5. 	{
    6. 		reserve(_capacity == 0 ? 4 : _capacity * 2);
    7. 	}
    8.  
    9. 	移动数据 需要单独处理\0
    10. 	//for (int i = _size-1; i >=(int)pos; i--)
    11. 	//{
    12. 	//	_str[i+1] = _str[i];
    13. 	//}
    14. 	//_str[pos] = ch;
    15. 	//_str[++_size] = '\0';
    16. 	
    17. 	//直接将 \0 也视为字符 移动开来
    18. 	for (int i = _size; i >= pos; i--)
    19. 	{
    20. 		_str[i + 1] = _str[i];
    21. 	}
    22. 	_str[pos] = ch;
    23. 	++_size;
    24. }

    程序崩溃？

    可以看到 i 小于0仍然进入循环，补充当 两个数据类型不同进行比较等操作时 范围小的会向范围大的进行整形提升 在这里 i 变为了无符号整数 解决办法 将 pos进行强制转换为 int 即可 

    1. void string::insert(size_t pos, char ch)
    2. {
    3. 	assert(pos <= _size);
    4. 	if (_capacity == _size)
    5. 	{
    6. 		reserve(_capacity == 0 ? 4 : _capacity * 2);
    7. 	}
    8. 	直接将 \0 也视为字符 移动开来
    9. 	//for (int i = _size; i >=(int)pos; i--)
    10. 	//{
    11. 	//	_str[i + 1] = _str[i];
    12. 	//}
    13. 	//_str[pos] = ch;
    14. 	//++_size;
    15.  
    16. 	for (int i = _size + 1; i > pos; i--)
    17. 	{
    18. 		_str[i] = _str[i - 1];
    19. 	}
    20. 	_str[pos] = ch;
    21. 	++_size;
    22. }
    23. //可以对比插入一个字符的逻辑 只是 len值为1的特殊情况 画图理解 临界条件
    24. void string::insert(size_t pos, const char* str)
    25. {
    26. 	assert(pos <= _size);
    27. 	size_t len = strlen(str);
    28. 	if (_size + len > _capacity)
    29. 	{
    30. 		reserve(_size + len > 2 * _capacity ? _size + len : 2 * _capacity);
    31. 	}
    32. 	for (int i = _size + len; i > len+pos-1; i--)
    33. 	{
    34. 		_str[i] = _str[i - len];
    35. 	}
    36.  
    37. 	for (int i = 0; i < len; i++)
    38. 	{
    39. 		_str[pos + i] = str[i];
    40. 	}
    41. 	_size += len;
    42.  
    43. }
    44. void string::erase(size_t pos, size_t len)
    45. {
    46. 	assert(pos < _size);//pos等于 _size 那么会删掉\0
    47.  
    48. 	//判断 len大于剩余的所有 就直接修改 \0的位置
    49. 	if (len >= _size - pos)
    50. 	{
    51. 		_str[pos] = '\0';
    52. 		_size = pos;
    53. 	}
    54. 	else
    55. 	{
    56. 		for (int i = pos + len; i <= _size; i++)
    57. 		{
    58. 			_str[i - len] = _str[i];
    59. 		}
    60. 		_size -= len;
    61. 	}
    62. }

    Tip:插入多个数据可以类比插入一个数据的逻辑关系 特殊到一般的思想转换，最重要的是不能凭自己的感觉思考，认真画图分析

    1.4查找

    1. size_t string::find(char ch, size_t pos)
    2. {
    3. 	for (int i = pos; i <_size; i++)
    4. 	{
    5. 		if (_str[i] == ch)
    6. 			return i;
    7. 	}
    8. }
    9. size_t string::find(const char* str, size_t pos)
    10. {
    11. 	assert(pos < _size);
    12. 	const char* ptr=strstr(_str + pos, str);
    13. 	if (ptr == nullptr)
    14. 	{
    15. 		return npos;
    16. 	}
    17. 	else
    18. 		return ptr - _str;//指针相减得到下标
    19. }

    1.5substr 深浅拷贝的区别

    1. string string::substr(size_t pos, size_t len)
    2. {
    3. 	assert(pos < _size);
    4. 	//判断 len大于剩余元素 更新一下len
    5. 	if (len > _size - pos)
    6. 	{
    7. 		len = _size - pos;
    8. 	}
    9. 	string sub;
    10. 	sub.reserve(len);
    11. 	for (int i = 0; i < len; i++)
    12. 	{
    13. 		sub += _str[pos + i];
    14. 	}
    15. 	return sub;
    16. }

    如果编译器优化激烈一点或者  release版本将直接 修改 suffix 省去拷贝构造

    因为没有显示实现拷贝构造，编译器的拷贝构造是浅拷贝

    实现一下拷贝构造和赋值重载

    1. //s2(s1)
    2. string(const string& s)
    3. {
    4. 	_str = new char[s._capacity + 1];
    5. 	strcpy(_str, s._str);
    6. 	_capacity = s._capacity;
    7. 	_size = s._size;
    8. }
    9.  
    10. //s2=s1
    11. //s1=s1
    12. string& operator=(const string& s)
    13. {
    14. 	if (this != &s)
    15. 	{
    16. 		delete[]_str;
    17. 		_str = new char[s._capacity + 1];
    18. 		strcpy(_str, s._str);
    19. 		_capacity = s._capacity;
    20. 		_size = s._size;
    21. 	}
    22. 	return *this;
    23. }

    1.6比较函数与流插入流提取

    比较逻辑

    1. .h
    2. ......
    3. private:
    4. 	char* _str;
    5. 	size_t _size;
    6. 	size_t _capacity;
    7. 	static const size_t npos;
    8. };
    9.  
    10. //定义在类外
    11. bool operator<(const string& s1, const string& s2);
    12. bool operator<=(const string& s1, const string& s2);
    13. bool operator>(const string& s1, const string& s2);
    14. bool operator>=(const string& s1, const string& s2);
    15. bool operator==(const string& s1, const string& s2);
    16. bool operator!=(const string& s1, const string& s2);
    17.  
    18. .cpp
    19. //利用 strcmp 函数比较
    20. bool operator<(const string& s1, const string& s2)
    21. {
    22. 	return strcmp(s1.c_str(), s2.c_str())<0;
    23. }
    24. bool operator<=(const string& s1, const string& s2)
    25. {
    26. 	return s1 < s2 || s1 == s2;
    27. }
    28. bool operator>(const string& s1, const string& s2)
    29. {
    30. 	return !(s1 <= s2);
    31. }
    32. bool operator>=(const string& s1, const string& s2)
    33. {
    34. 	return !(s1 < s2);
    35. }
    36. bool operator==(const string& s1, const string& s2)
    37. {
    38. 	return strcmp(s1.c_str(), s2.c_str()) == 0;
    39. }
    40. bool operator!=(const string& s1, const string& s2)
    41. {
    42. 	return !(s1 == s2);
    43. }

    流插入与流提取

    1. ostream& operator<<(ostream& out, const string& s)
    2. {
    3. 	for (auto ch : s)
    4. 	{
    5. 		out << ch;
    6. 	}
    7. 	return out;
    8. }
    9. istream& operator>>(istream& in, string& s)
    10. {
    11. 	char ch;
    12. 	ch = in.get();
    13. 	while (ch != ' ' && ch != '\n')
    14. 	{
    15. 		s += ch;
    16. 		ch = in.get();
    17. 	}
    18. }

    Tip：如果是 in>>ch 的话有分隔符的概念 不能提取到空格

    注意到 +=  存在扩容概念 难道一次一个 += 吗？ 优化一下

    1. istream& operator>>(istream& in, string& s)
    2. {
    3. 	s.clear();
    4. 	const int N = 256;
    5.  
    6. 	//创一个字符数组 以数组为整体单元进行+= 提高扩容效率
    7. 	char buff[N];
    8. 	int i = 0;
    9. 	char ch = in.get();
    10. 	while (ch != ' ' && ch != '\n')
    11. 	{
    12. 		buff[i++] = ch;
    13. 		if (i == N - 1)
    14. 		{
    15. 			buff[i] = '\0';
    16. 			s += buff;
    17. 			i = 0;
    18. 		}
    19. 	}
    20. 	//提前结束了 buff里面还有字符
    21. 	if (i > 0)
    22. 	{
    23. 		buff[i] = '\0';
    24. 		s += buff;
    25. 	}
    26. }

    二、string类的拷贝

    2.1浅拷贝与深拷贝

    浅拷贝：也称位拷贝，编译器只是将对象中的值拷贝过来。如果对象中管理资源，最后就会导致 多个对象共享同一份资源，当一个对象销毁时就会将该资源释放掉，而此时另一些对象不知道该 资源已经被释放，以为还有效，所以当继续对资源进项操作时，就会发生发生了访问违规。

    在这里即一个一个字节的拷贝，动态申请资源时候如果浅拷贝会指向同一块资源，会有着程序崩溃的问题

    同一块空间析构了两次 程序崩溃

    深拷贝即调用拷贝构造，编译器生成的拷贝构造是浅拷贝，需要我们自己显示实现拷贝构造来进行深拷贝

    1. //s2(s1)
    2. string(const string& s)
    3. {
    4. 	_str = new char[s._capacity + 1];
    5. 	strcpy(_str, s._str);
    6. 	_capacity = s._capacity;
    7. 	_size = s._size;
    8. }
    9.  
    10. //s2=s1
    11. //s1=s1
    12. string& operator=(const string& s)
    13. {
    14. 	if (this != &s)
    15. 	{
    16. 		delete[]_str;
    17. 		_str = new char[s._capacity + 1];
    18. 		strcpy(_str, s._str);
    19. 		_capacity = s._capacity;
    20. 		_size = s._size;
    21. 	}
    22. 	return *this;
    23. }

    2.2传统版与现代版区别

    库里的string拷贝构造赋值重载如何实现的呢？ 可以直接交换成员变量 但是需要初始化成员变量

    1. void swap(string& s)
    2. {
    3. 	std::swap(_str, s._str);
    4. 	std::swap(_capacity, s._capacity);
    5. 	std::swap(_size, s._size);
    6. }
    7. string(const string& s)
    8. {
    9. 	string tmp(s.c_str());
    10. 	swap(tmp);
    11. }
    12.  
    13. ......
    14. private:
    15. 	char* _str=nullptr;
    16. 	size_t _size=0;
    17. 	size_t _capacity=0;
    18. 	static const size_t npos;
    19. };//需要初始化一下 否则随机值交给tmp存在潜在风险

    这里的巧妙点在于 tmp 出了作用域会自己调析构函数此时不需要手动析构s2 借用了编译器的作用规则，局部变量出了作用域自动销毁  这也是为什么需要初始化局部变量，因为销毁随机值存在风险

    赋值重载：

    1. 	//s2=s1
    2. 	//s1=s1
    3. /*	string& operator=(const string& s)
    4. 	{
    5. 		if (this != &s)
    6. 		{
    7. 			delete[]_str;
    8. 			_str = new char[s._capacity + 1];
    9. 			strcpy(_str, s._str);
    10. 			_capacity = s._capacity;
    11. 			_size = s._size;
    12. 		}
    13. 		return *this;
    14. 	}*/
    15.  
    16. 	string& operator=(const string& s)
    17. 	{
    18. 		if (this != &s)
    19. 		{
    20. 			string tmp(s.c_str());
    21. 			swap(tmp);
    22. 		}
    23. 		return *this;
    24. 	}

    对比一下传统版的赋值重载， 可以看到现代版不需要手动 delete 了  利用编译器自动销毁了

    可以看到与拷贝构造相比 tmp 并没有存在的必要性，并不需要保留 s1的数据 优化一下

    1. /*string& operator=(const string &s)
    2. {
    3. 	if (this != &s)
    4. 	{
    5. 		string tmp(s.c_str());
    6. 		swap(tmp);
    7. 	}
    8. 	return *this;
    9. }*/
    10.  
    11. //最终版 s1=s3
    12. string& operator=(string tmp)
    13. {
    14. 	swap(tmp);
    15. 	return *this;
    16. }

    为什么算法库有swap 我们仍需要手动实现一个成员函数 swap呢？

    算法库里的自定义类型会进行多次拷贝构造（深拷贝），效率低

    事实上 库里面已经实例化了一个模板swap函数

    所以最终还是会调用成员函数提高效率

    2.3写时拷贝（了解）

    析构两次的另外一种解决方法——写时拷贝（引用计数法）

    引用计数代表有几个对象指向同一块资源

    当计数为0时候才执行析构函数，如果要修改拷贝的对象，那么还是需要进行深拷贝！

    不同编译器底层采取的方案是不同的

    可以看到 gcc 采用了引用计数写时拷贝

    三、vs和g++下string结构的说明

    注意：下述结构是在32位平台下进行验证，32位平台下指针占4个字节。

    3.1vs下的string结构

    string总共占28个字节，内部结构稍微复杂一点，先是有一个联合体，联合体用来定义

    string中字符串的存储空间：

    ●  当字符串长度小于16时，使用内部固定的字符数组来存放

    ●  当字符串长度大于等于16时，从堆上开辟空间

    1. union _Bxty
    2.  
    3. { // storage for small buffer or pointer to larger one
    4.  
    5.  value_type _Buf[_BUF_SIZE];
    6.  pointer _Ptr;
    7.  char _Alias[_BUF_SIZE]; // to permit aliasing
    8.  
    9. } _Bx;

    这种设计也是有一定道理的，大多数情况下字符串的长度都小于16，那string对象创建
    好之后，内部已经有了16个字符数组的固定空间，不需要通过堆创建，效率高。
    其次：还有一个size_t字段保存字符串长度，一个size_t字段保存从堆上开辟空间总的
    容量
    最后：还有一个指针做一些其他事情。
    故总共占16+4+4+4=28个字节。

    3.2g++下的string结构

    G++下，string是通过写时拷贝实现的，string对象总共占4个字节（32位）/ 8字节（64位），内部只包含了一个指针，该指针将来指向一块堆空间，内部包含了如下字段：
    ● 空间总大小
    ● 字符串有效长度
    ● 引用计数

    1. struct _Rep_base
    2.  
    3. {
    4.  size_type               _M_length;
    5.  size_type               _M_capacity;
    6.  _Atomic_word            _M_refcount;
    7. };


    ● 指向堆空间的指针，用来存储字符串。

  • 相关阅读:
    Docker 编译 Go 项目
    C++lambda表达式
    四元数简要理解（主要针对计算机图形学）
    SpringBoot集成Nacos动态读取配置文件及服务发现
    深入理解强化学习——强化学习的例子
    【开发日记】ElementUI表单使用原生@submit提交表单数据
    STM32的BOOT1和BOOT0查找及配置-都有BOOT1引脚的
    GPT-4V：AI在医疗领域的应用
    项目常遇到的问题
    HTML中name和class，id的区别和联系
  • 原文地址：https://blog.csdn.net/2402_82668782/article/details/142070946