• 从零开始的C++之旅——string类的模拟实现


    1.string类是什么

            在C++中,stirng 类是标准库提供的一个非常强大的字符串处理工具。相比于C语言中的字符
            数组(char[ ]) , string 类提供了更多方便且安全的操作。同时也更符合我们面向对象语言的特
            点。

    2.stirng类的模拟实现

            string类的模拟实现我们就模拟实现一些高频使用的容器操作,在逐步的实现过程中了解其底
            层的实现方式。需要注意地是,我们需要将直接实现的string类与系统中自带的string类分开,
            使用,我将其包在一个自定义的命名空间里面

            同时由于定义声明分离,我们在定义函数时需要指定类域

    2.1 定义成员变量

            string类型的成员变量其实跟我们之前数据结构定义的顺序表十分相似,同时一些操作的实现
            也与顺序表类似,因此实现方式也基本类似,无非就是多了类和对象的相关只是,在实现
            string类的过程中也可以帮助我们对c++的一些相关知识有更好的掌握

            既然和顺序表类似类似,那么其自然是三个成员变量,一个是大小size,一个是存储空间大小
            capacity,一个是char*类型的指针

                    

    2.2 构造函数

    string(const char* str = "")

            构造函数我们实现一个带缺省值的构造函数,使得我们实例化一个对象时,若没有传参则会
            调缺省值生成一个空串,若传参了则按吗传的参数进行初始化。

            所以首先我们的参数类型应该是接受字符串的首元素地址所以是char*类型,同时保证传递参
            数不被修改加上const

            对_str的初始化,自然是使用new 去申请一块空间,需要注意的是申请空间的大小应比字符串
            的大小大一位,因为还需要存储 “ \0  ”。size和capacity自然是初始化为0。

            同时,要调用strcpy函数将传入的字符串拷贝到string类当中

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

    2.3 析构函数 

            有了构造函数,我们自然可以实现对应的析构函数。只需要使用delete[ ]释放掉new[ ]申请的
            空间,并将str=nullptr,size,capacity=0即可

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

    2.4 开辟空间函数

            在实现pushback之前,我们要实现一个函数reserve,实现空间的扩容,避免空间不足。

            首先我们函数的参数是一个size_t类型的参数n,即表示我们需要扩容的大小。我们使用if条件
            判断一下当前扩容的空间n是否是否小于当前的有空间capacity,避免产生缩容

            扩容的第一步自然是申请一片空间,大小为n+1,随后使用strcpy将原对象中的数据拷贝到新
            开辟的空间,随后释放掉原空间申请的内存,再使_str指向新开辟的空间,最后更新capacity

    1. void string::reserve(size_t n)
    2. {
    3. if (n > _capacity)//判断,因为reserve功能不是缩容
    4. {
    5. char* tmp = new char[n + 1];
    6. strcpy(tmp, _str);
    7. delete[] _str;
    8. _str = tmp;
    9. _capacity = n;
    10. }
    11. }

    2.5 迭代器

            string类的迭代器相对比较简单,一位他的数据无论是逻辑顺序还是逻辑顺序都是连续的,因
            此我们简单的用指针的遍历来模拟迭代器。

    1. typedef char* iterator;
    2. typedef const char* const_iterator;

    普通迭代器

    1. iterator begin()
    2. {
    3. return _str;
    4. }
    5. iterator end()
    6. {
    7. return _str + _size;
    8. }

    const 迭代器

    1. const_iterator begin() const
    2. {
    3. return _str;
    4. }
    5. const_iterator end() const
    6. {
    7. return _str + _size;
    8. }

    2.6 插入函数

            有了reserve函数之后,我们便可以实现尾插函数,而尾插函数又分为尾插一个字符和一个字
            符串。插入函数的逻辑与顺序表的插入大致类似。熟悉了顺序表的插入这自然也得心应手。

    尾插一个字符(push_back)

            尾插一个字符逻辑非常简单,只需要先判断一下空间是否需要扩容,之后再尾部加上要插入
            的字符,随后更新size即可

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

    尾插一个字符串(append)

            由于我们扩大逻辑一般为二倍扩容,因此若插入的字符串有可能出现及时扩容后空间依然不
            足的情况,所以我们需要一个if条件判断扩容后的空间只否足够插入字符串。若扩容后的空间
            依然不足插入字符串,则直接扩容至size+len的大小。扩容完毕后只需要使用strcpy将需要插
            入的字符串拷贝到str的末尾即可

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

     指定位置插入(insert)

    指定位置插入单个字符

            首先自然是扩容,其逻辑与append一致,不再过多赘述。

            在扩容完成之后,需要定义一个指针end,将pos位置以后的数据依次往后挪动一位,再将
            字符插入到pos位置即可

    1. void string::insert(size_t pos, char ch)
    2. {
    3. if (_size == _capacity)
    4. {
    5. reserve(_capacity == 0 ? 4 : 2 * _capacity);
    6. }
    7. size_t end = _size + 1;
    8. while (end != pos)
    9. {
    10. _str[end] = _str[end - 1];
    11. end--;
    12. }
    13. _str[pos] = ch;
    14. _size++;
    15. }
    插入一个字符串

            插入字符串则是再扩容之后,需要将一段区间的数据往后挪,这时候我们就需要定义指针end
            end指向末尾之后的len个长度(len为插入字符串的大小),在将依次将原数据的末尾字符从
            头往前挪动,最后使用strcpy将要插入的字符串拷贝到pos位置。

    insert的复用

            在有了指定位置插入insert函数之后,我们便可以复用我们的insert来实现pushback和
            apped。

    1. void string::push_back(char ch)
    2. {
    3. insert(_size, ch);
    4. }
    5. void string::append(const char* str)
    6. {
    7. insert(_size, str);
    8. }

    2.7 删除函数 

    指定位置删除(erase)

            指定位置删除我们要实现的是删除从pos位置开始的n个字符

            因此我们首先要计算出我们需要前移几个数据,,再定义一个end指针指向要移除的元素区间
            的下一元素,将其赋值给(end-n)位置的元素,再让end++,直到将剩余元素移完

    1. void string::erase(size_t pos, size_t len)
    2. {
    3. assert(pos < _size);
    4. if (len >= _size - pos)
    5. {
    6. _str[pos] = '\0';
    7. _size = pos;
    8. }
    9. else
    10. {
    11. size_t end = pos;
    12. while (end + len <= _size)
    13. {
    14. _str[end] = _str[end + len];
    15. end++;
    16. }
    17. _size -= len;
    18. }
    19. }

    2.8 交换函数

            库中虽然有交换函数,但是其行为对于类来说要进行多次深拷贝,代价非常的大,因此我们
            自己实现一个函数,进行拷贝构造,提高其效率。

    swap(string& s)

            在一开始的时候我们就定义了类的成员变量,那么其实我们只要交换两个类的成员变量就可
            以实现两个类的交换,这时候就可以调用库中的swap来进行成员变量的交换,因为其只涉及
            浅拷贝,代价较小

    1. void string::swap(string& s)
    2. {
    3. std::swap(_str, s._str);
    4. std::swap(_size, s._size);
    5. std::swap(_capacity, s._capacity);
    6. }

    2.9 拷贝构造

            由于我们的stirng在构造时候申请了资源,因此编译器自动生成的拷贝构造浅拷贝行为无法完
            成我们的需要,这回导致两个对象指向同一片空间从而析构两次而报错。因此我们就需要自
            己写拷贝构造。

    string(const string& s)

            有了类的交换函数之后我,就可以轻松的实现拷贝构造,我们只需用被拷贝的对象创建一个
            临时变量tmp,再调用我们自己实现的swap函数将其与我们要创建的对象交换即可,并且tmp
            这个临时对象也会在出函数的时候自动销毁不需要我们去手动销毁,一举两得

    1. string::string(const string& s)
    2. {
    3. string tmp(s._str);
    4. swap(tmp);
    5. }

    2.10 赋值重载

            同理于拷贝构造,我们自然也要自己实现那赋值重载。

    string& operator=(string s)

            由于这里的函数参数并不是对象的引用,因此是传递的参数锁构造出来的一个临时对象,我
            们只需调用我们实现的swap函数进行交换最后返回*this即可,临时对象s也会在出函数之后自
            己销毁。

    1. string& string::operator=(string s)
    2. {
    3. swap(s);
    4. return *this;
    5. }

    2.11 运算符重载

            运算符的重载可以复用,这意味着我们只需要实现一两个运算符的重载即可复用从而实现
            其他的。

            由于运算符重载的函数其第一个参数并不是累的this指针,因此我们将其实现在类的外部
            又因为我们的string类是实现在自己的命名空间中,因此不需要将其再重载为友元函数,编译
            器会自己在命名空间中寻找。

     重载+=

            +=的逻辑与插入函数一致,我们只需要复用我的的两个插入函数即可

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

     重载==

            ==运算符的逻辑是字符串的比较,因此我们只需要调用哭函数中的strcmp即可

    1. bool bit::operator==(const string& lhs, const string& rhs)
    2. {
    3. return strcmp(lhs.c_str(), rhs.c_str()) == 0;
    4. }

     重载>

            >的重载本质也是比较字符串,调用strcmp即可实现

    1. bool bit::operator>(const string& lhs, const string& rhs)
    2. {
    3. return strcmp(lhs.c_str(), rhs.c_str()) > 0;
    4. }

     重载>= , != , < , <= 

    1. bool bit::operator<(const string& lhs, const string& rhs)
    2. {
    3. return !(lhs >= rhs);
    4. }
    5. bool bit::operator>=(const string& lhs, const string& rhs)
    6. {
    7. return lhs == rhs || lhs > rhs;
    8. }
    9. bool bit::operator<=(const string& lhs, const string& rhs)
    10. {
    11. return !(lhs > rhs);
    12. }
    13. bool bit::operator!=(const string& lhs, const string& rhs)
    14. {
    15. return !(lhs == rhs);
    16. }

    2.12 流插入流提取重载

             

    1. ostream& operator<<(ostream& os, const string& str)
    2. {
    3. for (size_t i = 0; i < str.size(); i++)
    4. {
    5. os << str[i];
    6. }
    7. return os;
    8. }
    9. istream& operator>>(istream& is, string& str)
    10. {
    11. str.clear();
    12. int i = 0;
    13. char buff[256];//建立临时数组,避免频繁开空间,并且栈上开空间比堆上开空间效率高
    14. char ch;
    15. ch = is.get();
    16. while (ch != ' ' && ch != '\n')
    17. {
    18. buff[i++] = ch;
    19. if (i == 255)
    20. {
    21. buff[255] = '\0';
    22. str += buff;
    23. i = 0;
    24. }
    25. ch = is.get();
    26. }
    27. if (i > 0)
    28. {
    29. buff[i] = '\0';
    30. str += buff;
    31. }
    32. return is;
    33. }

    3. 源代码 

    stirng.h

    1. #pragma once
    2. #include<iostream>
    3. #include<assert.h>
    4. using namespace std;
    5. namespace bit
    6. {
    7. class string
    8. {
    9. public:
    10. typedef char* iterator;
    11. typedef const char* const_iterator;
    12. string(const char* str = "");
    13. ~string();
    14. string(const string& s);
    15. void reserve(size_t n);
    16. void push_back(char ch);
    17. void append(const char* str);
    18. string& operator+=(char ch);
    19. string& operator+=(const char* str);
    20. string& operator=(string s);
    21. void insert(size_t pos, char ch);
    22. void insert(size_t pos, const char* str);
    23. void erase(size_t pos, size_t len = npos);
    24. size_t find(char ch, size_t pos = 0);
    25. size_t find(const char* str, size_t pos = 0);
    26. string substr(size_t pos, size_t len = npos);
    27. void swap(string& s);
    28. const char* c_str() const
    29. {
    30. return _str;
    31. }
    32. size_t size() const
    33. {
    34. return _size;
    35. }
    36. char& operator[](size_t i)
    37. {
    38. assert(i < _size);
    39. return _str[i];
    40. }
    41. char& operator[](size_t i) const
    42. {
    43. assert(i < _size);
    44. return _str[i];
    45. }
    46. iterator begin()
    47. {
    48. return _str;
    49. }
    50. iterator end()
    51. {
    52. return _str + _size;
    53. }
    54. const_iterator begin() const
    55. {
    56. return _str;
    57. }
    58. const_iterator end() const
    59. {
    60. return _str + _size;
    61. }
    62. void clear()
    63. {
    64. _str[0] = '\0';
    65. _size = _capacity = 0;
    66. }
    67. private:
    68. size_t _size;
    69. size_t _capacity;
    70. char* _str;
    71. public:
    72. //static const size_t npos = -1;
    73. //静态成员变量不能给缺省值必须类内定义类外声明
    74. // 但const 整形静态成员可以直接给缺省值,算是特殊处理
    75. static const size_t npos;
    76. };
    77. void swap(string& s1, string& s2);
    78. bool operator==(const string& lhs, const string& rhs);
    79. bool operator!=(const string& lhs, const string& rhs);
    80. bool operator>(const string& lhs, const string& rhs);
    81. bool operator<(const string& lhs, const string& rhs);
    82. bool operator>=(const string& lhs, const string& rhs);
    83. bool operator<=(const string& lhs, const string& rhs);
    84. ostream& operator<<(ostream& os, const string& str);
    85. istream& operator>>(istream& is, string& str);
    86. istream& getline(istream& is, string& str, char delim = '\n');
    87. }


    string.c

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include"string.h"
    3. namespace bit
    4. {
    5. const size_t string::npos = -1;
    6. string::string(const char* str)
    7. :_str(new char[strlen(str) + 1])
    8. , _size(strlen(str))
    9. , _capacity(strlen(str))
    10. {
    11. strcpy(_str, str);
    12. }
    13. string::~string()
    14. {
    15. delete[] _str;
    16. _str = nullptr;
    17. _size = _capacity = 0;
    18. }
    19. //b2(b1)
    20. string::string(const string& s)
    21. {
    22. string tmp(s._str);
    23. swap(tmp);
    24. }
    25. void string::reserve(size_t n)
    26. {
    27. if (n > _capacity)//判断,因为reserve功能不是缩容
    28. {
    29. char* tmp = new char[n + 1];
    30. strcpy(tmp, _str);
    31. delete[] _str;
    32. _str = tmp;
    33. _capacity = n;
    34. }
    35. }
    36. void string::push_back(char ch)
    37. {
    38. /*if (_size == _capacity)
    39. {
    40. reserve(_capacity == 0 ? 4 : 2 * _capacity);
    41. }
    42. _str[_size++] = ch;*/
    43. insert(_size, ch);
    44. }
    45. void string::append(const char* str)
    46. {
    47. //size_t len = strlen(str);
    48. //if (_size + len >= _capacity)
    49. //{
    50. // size_t newcapacity = 2 * _capacity;
    51. // if (newcapacity < _size + len)
    52. // newcapacity = _size + len;
    53. //
    54. // reserve(newcapacity);
    55. //}
    56. //strcpy(_str + _size, str);
    57. //_size += len;
    58. insert(_size, str);
    59. }
    60. string& string::operator+=(char ch)
    61. {
    62. push_back(ch);
    63. return *this;
    64. }
    65. string& string::operator+=(const char* str)
    66. {
    67. append(str);
    68. return *this;
    69. }
    70. void string::insert(size_t pos, char ch)
    71. {
    72. if (_size == _capacity)
    73. {
    74. reserve(_capacity == 0 ? 4 : 2 * _capacity);
    75. }
    76. size_t end = _size + 1;
    77. while (end != pos)
    78. {
    79. _str[end] = _str[end - 1];
    80. end--;
    81. }
    82. _str[pos] = ch;
    83. _size++;
    84. }
    85. void string::insert(size_t pos, const char* str)
    86. {
    87. size_t len = strlen(str);
    88. if (_size + len >= _capacity)
    89. {
    90. size_t newcapacity = 2 * _capacity;
    91. if (newcapacity < _size + len)
    92. newcapacity = _size + len;
    93. reserve(newcapacity);
    94. }
    95. len = strlen(str);
    96. size_t end = _size + len;
    97. while (end != pos + len - 1)
    98. {
    99. _str[end] = _str[end - len];
    100. end--;
    101. }
    102. for (size_t i = 0; i < len; i++)
    103. {
    104. _str[pos + i] = str[i];
    105. }
    106. _size += len;
    107. }
    108. void string::erase(size_t pos, size_t len)
    109. {
    110. assert(pos < _size);
    111. if (len >= _size - pos)
    112. {
    113. _str[pos] = '\0';
    114. _size = pos;
    115. }
    116. else
    117. {
    118. size_t end = pos;
    119. while (end + len <= _size)
    120. {
    121. _str[end] = _str[end + len];
    122. end++;
    123. }
    124. _size -= len;
    125. }
    126. }
    127. size_t string::find(char ch, size_t pos)
    128. {
    129. assert(pos < _size);
    130. for (size_t i = pos; i < _size; i++)
    131. {
    132. if (_str[i] == ch)
    133. return i;
    134. }
    135. return npos;
    136. }
    137. size_t string::find(const char* str, size_t pos)
    138. {
    139. assert(pos < _size);
    140. const char* ptr = strstr(_str + pos, str);
    141. if (ptr == nullptr)
    142. return npos;
    143. else
    144. return ptr - _str;
    145. }
    146. string string::substr(size_t pos, size_t len)
    147. {
    148. if (len > (_size - pos))
    149. {
    150. len = _size - pos;
    151. }
    152. bit::string sub;
    153. sub.reserve(len);
    154. for (size_t i = 0; i < len; i++)
    155. {
    156. sub += _str[pos + i];
    157. }
    158. return sub;
    159. }
    160. string& string::operator=(string s)
    161. {
    162. swap(s);
    163. return *this;
    164. }
    165. void string::swap(string& s)
    166. {
    167. std::swap(_str, s._str);
    168. std::swap(_size, s._size);
    169. std::swap(_capacity, s._capacity);
    170. }
    171. void swap(string& s1, string& s2)
    172. {
    173. s1.swap(s2);
    174. }
    175. bool bit::operator==(const string& lhs, const string& rhs)
    176. {
    177. return strcmp(lhs.c_str(), rhs.c_str()) == 0;
    178. }
    179. bool bit::operator!=(const string& lhs, const string& rhs)
    180. {
    181. return !(lhs == rhs);
    182. }
    183. bool bit::operator>(const string& lhs, const string& rhs)
    184. {
    185. return strcmp(lhs.c_str(), rhs.c_str()) > 0;
    186. }
    187. bool bit::operator<(const string& lhs, const string& rhs)
    188. {
    189. return !(lhs >= rhs);
    190. }
    191. bool bit::operator>=(const string& lhs, const string& rhs)
    192. {
    193. return lhs == rhs || lhs > rhs;
    194. }
    195. bool bit::operator<=(const string& lhs, const string& rhs)
    196. {
    197. return !(lhs > rhs);
    198. }
    199. ostream& operator<<(ostream& os, const string& str)
    200. {
    201. for (size_t i = 0; i < str.size(); i++)
    202. {
    203. os << str[i];
    204. }
    205. return os;
    206. }
    207. istream& operator>>(istream& is, string& str)
    208. {
    209. str.clear();
    210. int i = 0;
    211. char buff[256];//建立临时数组,避免频繁开空间,并且栈上开空间比堆上开空间效率高
    212. char ch;
    213. ch = is.get();
    214. while (ch != ' ' && ch != '\n')
    215. {
    216. buff[i++] = ch;
    217. if (i == 255)
    218. {
    219. buff[255] = '\0';
    220. str += buff;
    221. i = 0;
    222. }
    223. ch = is.get();
    224. }
    225. if (i > 0)
    226. {
    227. buff[i] = '\0';
    228. str += buff;
    229. }
    230. return is;
    231. }
    232. istream& getline(istream& is, string& str, char delim)
    233. {
    234. str.clear();
    235. int i = 0;
    236. char buff[256];
    237. char ch;
    238. ch = is.get();
    239. while (ch != delim)
    240. {
    241. buff[i++] = ch;
    242. if (i == 255)
    243. {
    244. buff[255] = '\0';
    245. str += buff;
    246. i = 0;
    247. }
    248. ch = is.get();
    249. }
    250. if (i > 0)
    251. {
    252. buff[i] = '\0';
    253. str += buff;
    254. }
    255. return is;
    256. }
    257. }

  • 相关阅读:
    C语言scanf_s函数的使用
    面了一个00后测试工程师,问啥啥不会开口就要15k,我也是麻了····
    java 多excel下载 打成zip压缩包 程序中创建文件 响应到浏览器
    sqlalchemy 连接池
    带头的循环双向链表的简单介绍
    Java面试题整理面向对象
    UE4 AI行为树实现随机和跟随移动
    Spring Security -- 前后端分离时的安全处理方案
    Pandas 数据可视化
    ElementUI validate 验证结果错误的问题解决过程
  • 原文地址:https://blog.csdn.net/2302_81813630/article/details/143394582