devbox
我家自动化
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

string模拟实现

作者：我家自动化 | 2024-04-24 11:00:37

赞

踩

string模拟实现

string是C++里面对于字符串处理非常方便的容器，不仅支持方括号加下标的访问，还内置各种接口，用起来嘎嘎爽。

前置注意事项：

在模拟实现的时候，我们需要自己开一块命名空间，避免跟库里的string发生冲突

需要对类和对象的相关知识有一定的了解，可翻阅我之前的文章

1. string成员变量

有点类似顺序表的实现（可看这篇文章），有一个size(数组大小)和capacity(数组容量)，而string的本质是字符数组，有char*来记录数据

  1. namespace myString
  2. {
  3. 	class string
  4. 	{
  5. 	public:
  6. 		typedef char* iterator;
  7. 		typedef const char* const_iterator;
  8.         
  9.         // 提供接口来访问第一个元素和最后一个元素的下一位
  10.         iterator begin()
  11.         {
  12.             return _str;
  13.         }
  14.  
  15.         const_iterator begin() const
  16.         {
  17.             return _str;
  18.         }
  19.  
  20.         iterator end()
  21.         {
  22.             return _str + _size;
  23.         }
  24.  
  25.         const_iterator end() const
  26.         {
  27.             return _str + _size;
  28.         }
  29.  
  30. 		const_iterator begin() const
  31. 		{
  32. 			return _str;
  33. 		}
  34.  
  35. 		const_iterator end() const
  36. 		{
  37. 			return _str + _size;
  38. 		}
  39.         
  40.         // 获取大小和容量的接口
  41.         // 这里要用const修饰成员函数，保证const对象也可以调用
  42. 		size_t size() const
  43. 		{
  44. 			return _size;
  45. 		}
  46.  
  47. 		size_t capacity() const
  48. 		{
  49. 			return _capacity;
  50. 		}
  51.         
  52.         bool empty() const
  53.         {
  54.             return _size == 0;
  55.         }
  56.  
  57.         //获取C类型的字符串
  58.         const char* c_str() const
  59.         {
  60. 	        return _str;
  61.         }
  62.  
  63.  
  64. 	private:
  65. 		char* _str = nullptr;
  66. 		size_t _size = 0;
  67. 		size_t _capacity = 0;
  68.     public:
  69.         static const size_t npos;
  70.     };
  71. }

【补充】这里的npos一般赋值为-1，用来表示字符串的末尾，因为-1在无符号整型中为2^32-1，大小约为4G，所以一般不会达到，所以用来表示末尾，通常作缺省值使用。或者在查找不到需要的字符(字符串)时作为返回值表示查找失败。

2. 构造和析构

（1）构造函数

  1. string(const char* str = "")
  2.     :_size = strlen(str)
  3. {
  4. 	_capacity = _size; 
  5. 	_str = new char[_capacity + 1]; 
  6. 	strcpy(_str, str); 
  7. }

（2）拷贝构造

注意要新开一块空间再将数据拷贝过来，否则两个指针指向同一块空间时，当其中一个发生改变另一个也会变，而且在析构时同一块空间析构两次会引发程序的崩溃，而这也就是我们常说的浅拷贝。

而深拷贝就是先开一块新的空间，再将数据依次拷过去，可以有效地避免上述情况的发生。

  1. // 版本一
  2. string(const string& s)
  3. {
  4.     _str = new char[s.capacity() + 1];
  5.     strcpy(_str, s._str);
  6.     _size = s._size;
  7. 	_capacity = s._capacity;
  8. }

版本二复用了（1）构造函数，同时写了一个swap函数

Q：有小伙伴就问了，为什么不直接用库里的swap呢？

可以看到这里要调用一次拷贝构造，两次赋值，还得调用析构把c析构掉

代价太大，所以我们不如自己实现一个

这里要用std限定住范围是因为swap会先从就近的swap开始找，但是由于参数个数不匹配，所以就会报错。 

  1. // 版本二
  2. void swap(string& s)
  3. {
  4.     std::swap(_str, s._str);
  5.     std::swap(_size, s._size);
  6.     std::swap(_capacity, s._capacity);
  7. }
  8.  
  9. string(const string& s)
  10. {
  11.     string tmp(s._str);
  12.     swap(tmp);
  13. }

（3）析构函数

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

3. reserve和resize

【区分reserve和resize】

reserve：只是开空间，

  1. void reserve(size_t n)
  2. {
  3.     if(n > _capacity)
  4.     {
  5.         char* tmp = new char[n + 1];
  6.         strcpy(tmp, _str);
  7.         delete[] _str;
  8.         _str = tmp;
  9.         _capacity = n;
  10.     }
  11. }
  12.  
  13. void resize(size_t n, char c = '\0')
  14. {
  15.     if(n <= _size)
  16.     {
  17.         _str[n] = '\0';
  18.         _size = n;
  19.     }
  20.     else
  21.     {
  22.         reserve(n);
  23.         for(size_t i = _size; i < n; i++)
  24.             _str[i] = c;
  25.         _str[n] = '\0';
  26.         _size = n;
  27.     }
  28. }

4. find

查找不需要修改对应的成员函数，所以使用const成员函数

strstr返回的就是在某个位置之后找某个对应的子串，返回首元素的地址

  1. // 返回c在string中第一次出现的位置
  2.  
  3. size_t find (char c, size_t pos = 0) const
  4. {
  5.     assert(pos < _size);
  6.  
  7.     for(size_t i = pos; i < _size; i++)
  8.     {
  9.         if(_str[i] == c)
  10.             return i;
  11.     }
  12.     return npos;
  13.     
  14. }
  15.  
  16. // 返回子串s在string中第一次出现的位置
  17.  
  18. size_t find (const char* s, size_t pos = 0) const
  19. {
  20.     assert(pos < _size);
  21.  
  22.     const char* p = strstr(_str + pos, s);
  23.     if(p)
  24.         return p - _str; // 指针减指针得两者之间的元素个数
  25.     else
  26.         return npos;
  27. }

5. insert和erase

  1. void insert(size_t pos, char c)
  2. {
  3.     if(_size == _capacity)
  4.     {
  5.         reserve(_capacity == 0 ? 4 : _capacity * 2);
  6.     }
  7.  
  8.     int end = _size + 1;
  9.     while(end > pos)
  10.     {
  11.         _str[end] = _str[end - 1];
  12.         end--;
  13.     }
  14.     _str[pos] = c;
  15.     _size++;
  16. }
  17.  
  18. void insert(size_t pos, const char* str)
  19. {
  20.     assert(pos <= _size);
  21.     size_t len = strlen(str);
  22.     if(_size + len > _capacity)
  23.         reserve(_size + len);
  24.  
  25.     size_t end = _size + len;
  26.     while(end > pos + len - 1)
  27.     {
  28.         _str[end] = _str[end - len];
  29.         end--;
  30.     }
  31.     strncpy(_str + pos, str, len);
  32.     _size += len;
  33. }
  34.  
  35.  
  36. // 删除pos位置上的元素，并返回该元素的下一个位置
  37.  
  38. void erase(size_t pos, size_t len = npos)
  39. {
  40.     aasert(pos < _size);
  41.     if(len == npos || pos + len >= _size)
  42.     {
  43.         _str[pos] = '\0';
  44.         _size = pos;
  45.     }
  46.     else
  47.     {
  48.         strcpy(_str + pos, _str + pos + len);
  49.         _size -= len;
  50.     }
  51. }

6. push_back和append

老思路，扩容扩二倍；记得加回 '\0'

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

【版本二】复用insert

  1. void push_back(char c)
  2. {
  3.     insert(_size, c);
  4. }

append：不要忘记扩容！！因为传进来的是c类型字符串，所以直接使用strlen

  1. void append(const char* str)
  2. {
  3.     size_t len = strlen(str);
  4.     if (_size + len > _capacity)
  5.         reserve(_size + len);
  6.  
  7.     strcpy(_str + _size, str);
  8.     _size += len;
  9. }

7. 重载

（1）方括号重载

  1. char& operator[](size_t index)
  2. {
  3.     assert(index < _size);
  4.     return _str[index];
  5. }
  6.  
  7. const char& operator[](size_t index) const
  8. {
  9.     assert(index < _size);
  10.     return _str[index];
  11. }

（2）比较大小

注意strcmp函数是c语言的接口，需要转成const char*才能传参

  1. bool operator==(const string& s1, const string& s2)
  2. {
  3.     int ret = strcmp(s1.c_str(), s2.c_str());
  4.     return ret == 0;
  5. }
  6.  
  7. bool operator<(const string& s1, const string& s2)
  8. {
  9.     int ret = strcmp(s1.c_str(), s2.c_str());
  10.     return ret < 0;
  11. }
  12.  
  13. bool operator<=(const string& s1, const string& s2)
  14. {
  15.     return s1 < s2 || s1 == s2;
  16. }
  17.  
  18. bool operator>(const string& s1, const string& s2)
  19. {
  20.     return !(s1 <= s2);
  21. }
  22.  
  23. bool operator>=(const string& s1, const string& s2)
  24. {
  25.     return !(s1 < s2);
  26. }
  27.  
  28. bool operator!=(const string& s1, const string& s2)
  29. {
  30.     return !(s1 == s2);
  31. }

（3）流提取和流插入

【注意点】

a. 范围for的底层是迭代器，所以需要先定义迭代器 const begin() 和 const end() 之后才能使用

b. 这里的流提取采用了“缓冲数组”的思路，避免了开辟空间不够用的问题

  1. ostream& operator<<(ostream& _cout, const string& s)
  2. {
  3.     for (auto e : s)
  4.     {
  5.         _cout << e;
  6.     }
  7.     return _cout;
  8. }
  9.  
  10. istream& operator>>(istream& _cin, bit::string& s)
  11. {
  12.     s.clear();
  13.     char buff[128];
  14.     char ch = _cin.get();
  15.     size_t i = 0;
  16.     while (ch != ' ' && ch != '\n')
  17.     {
  18.         buff[i++] = ch;
  19.         if (i == 127)
  20.         {
  21.             buff[127] = '\0';
  22.             s += buff;
  23.             i = 0;
  24.         }
  25.         ch = _cin.get();
  26.     }
  27.  
  28.     if (i > 0)
  29.     {
  30.         buff[i] = '\0';
  31.         s += buff;
  32.     }
  33.     return _cin;
  34. }
  35.  
  36. // 获取一行信息（可包含空格）
  37. istream& getline(istream& _cin, string& s)
  38. {
  39.     s.clear();
  40.     char ch = _cin.get();
  41.     while (ch != '\n')
  42.     {
  43.         s += ch;
  44.         ch = _cin.get();
  45.     }
  46.     return _cin;
  47. }

（4）尾插

直接复用push_back和append

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

（5）赋值运算符

【版本一】

  1. string& operator=(const string& s)
  2. {
  3.     char* tmp = new char[s._capacity + 1];
  4.     strcpy(tmp, s._str);
  5.  
  6.     delete[] _str;
  7.     _str = tmp;
  8.     _size = s._size;
  9.     _capacity = s._capacity;
  10.     return *this;
  11. }

【版本二】 

传参时，发生拷贝构造，所以交换之后不对原来的对象产生影响

  1. string& operator=(string s)
  2. {
  3. 	swap(s); 
  4. 	return *this; //返回左值（支持连续赋值）
  5. }

 

8. clear

  1. void clear()
  2. {
  3.     _str[0] = '\0';
  4.     _size = 0;
  5. }

【代码汇总】

  1. namespace myString
  2. {
  3.  
  4.     class string
  5.     {
  6.  
  7.         friend ostream& operator<<(ostream& _cout, const string& s);
  8.  
  9.         friend istream& operator>>(istream& _cin, string& s);
  10.  
  11.     public:
  12.  
  13.         typedef char* iterator;
  14.         typedef const char* const_iterator;
  15.  
  16.     public:
  17.  
  18.         string(const char* str = "")
  19.             :_size(strlen(str))
  20.         {
  21.             _capacity = _size;
  22.             _str = new char[_capacity + 1];
  23.             strcpy(_str, str);
  24.         }
  25.  
  26.         string(const string& s)
  27.         {
  28.             _str = new char[s.capacity() + 1];
  29.             strcpy(_str, s._str);
  30.             _size = s._size;
  31.             _capacity = s._capacity;
  32.         }
  33.  
  34.         string& operator=(const string& s)
  35.         {
  36.             char* tmp = new char[s._capacity + 1];
  37.             strcpy(tmp, s._str);
  38.  
  39.             delete[] _str;
  40.             _str = tmp;
  41.             _size = s._size;
  42.             _capacity = s._capacity;
  43.             return *this;
  44.         }
  45.  
  46.         ~string()
  47.         {
  48.             delete[] _str;
  49.             _str = nullptr;
  50.             _size = _capacity = 0;
  51.         }
  52.  
  53.         //
  54.  
  55.         // iterator
  56.  
  57.         iterator begin()
  58.         {
  59.             return _str;
  60.         }
  61.  
  62.         const_iterator begin() const
  63.         {
  64.             return _str;
  65.         }
  66.  
  67.         iterator end()
  68.         {
  69.             return _str + _size;
  70.         }
  71.  
  72.         const_iterator end() const
  73.         {
  74.             return _str + _size;
  75.         }
  76.  
  77.         /
  78.  
  79.         // modify
  80.  
  81.         void push_back(char c)
  82.         {
  83.             if (_size == _capacity)
  84.                 reserve(_capacity == 0 ? 4 : _capacity * 2);
  85.  
  86.             _str[_size] = c;
  87.             _str[++_size] = '\0';
  88.         }
  89.  
  90.         string& operator+=(char c)
  91.         {
  92.             push_back(c);
  93.             return *this;
  94.         }
  95.  
  96.         void append(const char* str)
  97.         {
  98.             size_t len = strlen(str);
  99.             if (_size + len > _capacity)
  100.                 reserve(_size + len);
  101.  
  102.             strcpy(_str + _size, str);
  103.             _size += len;
  104.         }
  105.  
  106.         string& operator+=(const char* str)
  107.         {
  108.             append(str);
  109.             return *this;
  110.         }
  111.  
  112.         void clear()
  113.         {
  114.             _str[0] = '\0';
  115.             _size = 0;
  116.         }
  117.  
  118.         void swap(string& s)
  119.         {
  120.             std::swap(_str, s._str);
  121.             std::swap(_size, s._size);
  122.             std::swap(_capacity, s._capacity);
  123.         }
  124.  
  125.         const char* c_str() const
  126.         {
  127.             return _str;
  128.         }
  129.  
  130.         /
  131.  
  132.         // capacity
  133.  
  134.         size_t size()const
  135.         {
  136.             return _size;
  137.         }
  138.  
  139.         size_t capacity()const
  140.         {
  141.             return _capacity;
  142.         }
  143.  
  144.         bool empty()const
  145.         {
  146.             return _size == 0;
  147.         }
  148.  
  149.         void resize(size_t n, char c = '\0')
  150.         {
  151.             if (n <= _size)
  152.             {
  153.                 _str[n] = '\0';
  154.                 _size = n;
  155.             }
  156.             else
  157.             {
  158.                 reserve(n);
  159.                 for (size_t i = _size; i < n; i++)
  160.                     _str[i] = c;
  161.                 _str[n] = '\0';
  162.                 _size = n;
  163.             }
  164.         }
  165.  
  166.         void reserve(size_t n)
  167.         {
  168.             if (n > _capacity)
  169.             {
  170.                 char* tmp = new char[n + 1];
  171.                 strcpy(tmp, _str);
  172.                 delete[] _str;
  173.                 _str = tmp;
  174.                 _capacity = n;
  175.             }
  176.         }
  177.  
  178.  
  179.  
  180.         /
  181.  
  182.         // access
  183.  
  184.         char& operator[](size_t index)
  185.         {
  186.             assert(index < _size);
  187.             return _str[index];
  188.         }
  189.  
  190.         const char& operator[](size_t index) const
  191.         {
  192.             assert(index < _size);
  193.             return _str[index];
  194.         }
  195.  
  196.  
  197.  
  198.         /
  199.  
  200.         //relational operators
  201.  
  202.  
  203.  
  204.  
  205.         // 返回c在string中第一次出现的位置
  206.  
  207.         size_t find(char c, size_t pos = 0) const
  208.         {
  209.             assert(pos < _size);
  210.  
  211.             for (size_t i = pos; i < _size; i++)
  212.             {
  213.                 if (_str[i] == c)
  214.                     return i;
  215.             }
  216.             return npos;
  217.  
  218.         }
  219.  
  220.         // 返回子串s在string中第一次出现的位置
  221.  
  222.         size_t find(const char* s, size_t pos = 0) const
  223.         {
  224.             assert(pos < _size);
  225.  
  226.             const char* p = strstr(_str + pos, s);
  227.             if (p)
  228.                 return p - _str;
  229.             else
  230.                 return npos;
  231.         }
  232.  
  233.  
  234.         // 在pos位置上插入字符c/字符串str，并返回该字符的位置
  235.  
  236.         void insert(size_t pos, char c)
  237.         {
  238.             if (_size == _capacity)
  239.             {
  240.                 reserve(_capacity == 0 ? 4 : _capacity * 2);
  241.             }
  242.  
  243.             int end = _size + 1;
  244.             while (end > pos)
  245.             {
  246.                 _str[end] = _str[end - 1];
  247.                 end--;
  248.             }
  249.             _str[pos] = c;
  250.             _size++;
  251.         }
  252.  
  253.         void insert(size_t pos, const char* str)
  254.         {
  255.             assert(pos <= _size);
  256.             size_t len = strlen(str);
  257.             if (_size + len > _capacity)
  258.                 reserve(_size + len);
  259.  
  260.             size_t end = _size + len;
  261.             while (end > pos + len - 1)
  262.             {
  263.                 _str[end] = _str[end - len];
  264.                 end--;
  265.             }
  266.             strncpy(_str + pos, str, len);
  267.             _size += len;
  268.         }
  269.  
  270.  
  271.  
  272.         // 删除pos位置上的元素，并返回该元素的下一个位置
  273.  
  274.         void erase(size_t pos, size_t len = npos)
  275.         {
  276.             assert(pos < _size);
  277.             if (len == npos || pos + len >= _size)
  278.             {
  279.                 _str[pos] = '\0';
  280.                 _size = pos;
  281.             }
  282.             else
  283.             {
  284.                 strcpy(_str + pos, _str + pos + len);
  285.                 _size -= len;
  286.             }
  287.         }
  288.  
  289.     private:
  290.  
  291.         char* _str;
  292.  
  293.         size_t _capacity;
  294.  
  295.         size_t _size;
  296.     public:
  297.         static const size_t npos;
  298.     };
  299.  
  300.     const size_t string::npos = -1;
  301.  
  302.     void swap(string& x, string& y)
  303.     {
  304.         x.swap(y);
  305.     }
  306.  
  307.     bool operator<(const string& s1, const string& s2)
  308.     {
  309.         int ret = strcmp(s1.c_str(), s2.c_str());
  310.         return ret < 0;
  311.     }
  312.  
  313.     bool operator==(const string& s1, const string& s2)
  314.     {
  315.         int ret = strcmp(s1.c_str(), s2.c_str());
  316.         return ret == 0;
  317.     }
  318.  
  319.     bool operator<=(const string& s1, const string& s2)
  320.     {
  321.         return s1 < s2 || s1 == s2;
  322.     }
  323.  
  324.     bool operator>(const string& s1, const string& s2)
  325.     {
  326.         return !(s1 <= s2);
  327.     }
  328.  
  329.     bool operator>=(const string& s1, const string& s2)
  330.     {
  331.         return !(s1 < s2);
  332.     }
  333.  
  334.     bool operator!=(const string& s1, const string& s2)
  335.     {
  336.         return !(s1 == s2);
  337.     }
  338.  
  339.     ostream& operator<<(ostream& _cout, const string& s)
  340.     {
  341.         for (auto e : s)
  342.         {
  343.             _cout << e;
  344.         }
  345.         return _cout;
  346.     }
  347.  
  348.     istream& operator>>(istream& _cin, string& s)
  349.     {
  350.         s.clear();
  351.         char buff[128];
  352.         char ch = _cin.get();
  353.         size_t i = 0;
  354.         while (ch != ' ' && ch != '\n')
  355.         {
  356.             buff[i++] = ch;
  357.             if (i == 127)
  358.             {
  359.                 buff[127] = '\0';
  360.                 s += buff;
  361.                 i = 0;
  362.             }
  363.             ch = _cin.get();
  364.         }
  365.  
  366.         if (i > 0)
  367.         {
  368.             buff[i] = '\0';
  369.             s += buff;
  370.         }
  371.         return _cin;
  372.     }
  373.  
  374.     istream& getline(istream& _cin, string& s)
  375.     {
  376.         s.clear();
  377.         char ch = _cin.get();
  378.         while (ch != '\n')
  379.         {
  380.             s += ch;
  381.             ch = _cin.get();
  382.         }
  383.         return _cin;
  384.     }
  385. };

 

如果你能看到这里，给你点个赞！

如果觉得这篇文章不错的话，不妨点个赞支持一下，你的支持是我持续更新的动力~

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/479024
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号