• 【STL】容器 - string的模拟实现


    目录

    框架

    一.构造函数

    1.string();与string(const char* s);

    2.string(const char* s, size_t n);

    二.拷贝构造

    0.深浅拷贝、写时拷贝

    0.1.深浅拷贝

    0.2.浅拷贝的危害

    0.3.写时拷贝

    1.string(const string& str);

    1.1.旧版写法

    1.2.新版写法(包含类内swap实现)

    2.string(const string& str, size_t pos, size_t len = npos); 

    三.赋值运算符重载

    1.string& operator=(const string& s);

    1.1.旧版写法

    1.2.新版写法1

    1.3.新版写法2 

    2.string& operator= (const char* s);

    3.string& operator= (char c);

    四.迭代器iterator、operator[]、范围for

    1.迭代器iterator

    2.operator[]

    3.范围for

    五.增删查改

    0.扩容(reserve)

    1.增(push_back、append、operator+=、insert)

    2.删(erase)

    3.查(find)

    六.流输入/输出、兼容C接口c_str

    1.operator<<

    2.operator>>(重点讲解,利用了缓冲区的原理)

    2.0.clear

    2.1错误版本

    2.2正确版本(效率低)

    2.3改进版本(类似于缓冲区,高效)

    3.c_str

    4.operator<<与c_str的区别

    七.字符串比较

    八.其他函数

    1.substr

    2.resize

    3.析构函数~string()

    九.在vs中对于string的特殊处理


    框架

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include
    3. using namespace std;
    4. namespace zsl
    5. {
    6. //string类模拟实现
    7. class string
    8. {
    9. public:
    10. //模拟实现
    11. //... ...
    12. private:
    13. char* _str;
    14. size_t _size;
    15. size_t _capacity;//可存放数据的容量,实际容量还要加1,因为有'\0'
    16. public:
    17. //迭代器
    18. typedef char* iterator;
    19. //第一种实现方式,必须加const修饰的static变量才可以在类内初始化
    20. //static const size_t npos = -1;//此时这里不再是声明,而是定义,属于C++的特殊处理
    21. //第二种方式
    22. static size_t npos;
    23. };
    24. //第二种实现方式,不加const,static变量必须在类外初始化
    25. size_t zsl::string::npos = -1;
    26. }

    npos是无符号整型,初始化为-1就是无符号整型的最大值

    一.构造函数

    1.string();与string(const char* s);

    string();与string(const char* s);合并,加缺省参数即可

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

    2.string(const char* s, size_t n);

    参数

            s:字符串首地址

            n:字符串s中的前n个字符

    1. string(const char* s, size_t n)
    2. {
    3. size_t size = strlen(s);
    4. _str = new char[size + 1];
    5. _capacity = size;
    6. strcpy(_str, s);
    7. _str[n] = '\0';
    8. _size = n;
    9. }

    string(size_t n, char c);

    参数

            n:字符c的个数

            c:一个字符

    1. string(size_t n, char c)
    2. {
    3. _str = new char[n + 1];
    4. size_t i = 0;
    5. for (; i < n; i++)
    6. {
    7. _str[i] = c;
    8. }
    9. _str[i] = '\0';
    10. _size = _capacity = n;
    11. }

    二.拷贝构造

    0.深浅拷贝、写时拷贝

    0.1.深浅拷贝

    假设现在有一个指针指向一块堆区空间

    浅拷贝:重新拷贝一个指针2,与原指针指向同一块堆区空间

    深拷贝:重新在堆区开辟一块大小相同的空间,并且拷贝原空间的数据,同时拷贝一个指针2指向该空间

    对于在堆区开辟的空间拷贝,一定要使用深拷贝!(特例:写时拷贝不一定必须用深拷贝)

    0.2.浅拷贝的危害

    对于在堆区开辟的空间拷贝,浅拷贝的危害

    1.若改动拷贝后的空间数据,则会连带原空间数据一起改动

    2.指针销毁时调用析构函数,同一块堆区空间会被析构两次

    0.3.写时拷贝

    这里只讲一下写时拷贝的思路,因为每一次的深拷贝都是要付出一定代价的,那么可不可以尽量减少深拷贝的次数,能用浅拷贝就用浅拷贝呢?那么就需要避免以上浅拷贝的两个危害!

    如何避免危害1

    如果我拷贝了一份数据,并且不会改动数据,那么浅拷贝的危害(1)就会被避免,所以默认都对数据进行浅拷贝,如果数据需要写入或修改,此时我再将这个拷贝的数据进行一个深拷贝

    如何避免危害2

    在析构的时候使用计数法,定义一个计数变量,在第一次构造时将计数变量初始化为1,随后每有一个对象使用该资源,就把计数变量+1,在析构的时候需要对此变量检查,如果计数变量等于1,说明此时是最后一个使用此资源的对象了,则可以对空间进行清理;反之如果计数变量大于1,则每一次调用析构函数不能对空间进行清理,而是将计数变量-1

    关于写时拷贝还有许多细节,由于本章节只是针对string的模拟实现,在后续篇章中将会对写时拷贝进行展开研究

    1.string(const string& str);

    1.1.旧版写法

    思路:在初始化列表初始化时直接开辟空间,初始化_size与_capacity,然后将字符串拷贝进去,完成深拷贝。

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

    1.2.新版写法(包含类内swap实现)

    类内实现的swap函数

    类内的swap函数与std域中的swap不一样,对于内置类型而言用哪个都没有区别,对于容器类而言用类内实现的效率会有显著提升(其实类内实现也是把类内的每一个成员变量依次调用std域中的swap,也就是将一个自定义类型的每个成员变量拆开分别交换),因为std域的swap函数调用了1次拷贝构造2次赋值重载,这3次都是深拷贝,效率低消耗大。

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

    思路:不自己去开空间拷贝,而是构造一个tmp,然后将和新创建的对象进行交换。

    注意:因为tmp出作用域销毁是要调用析构的,而新创建的对象不进行初始化的话就交换了一堆随机值给tmp,会导致tmp调用析构崩溃,所以一定要在初始化列表对新创建的对象进行初始化,这里_str是可以给空指针的因为析构函数底层operator delete调用free时会对空指针进行检查。

    1. string(const string& str)
    2. :_str(nullptr),_size(0),_capacity(0)
    3. {
    4. string tmp(str._str);
    5. //1.调用全局的swap
    6. //swap(_str, tmp._str);
    7. //swap(_size, tmp._size);
    8. //swap(_capacity, tmp._capacity);
    9. //2.调用自己写的swap进行一步封装
    10. swap(tmp);
    11. }

    2.string(const string& str, size_t pos, size_t len = npos); 

    参数

            str:字符串的引用,别名

            pos:从下标为pos的位置开始

            len:拷贝len个字符,如果不输入len,则默认为缺省参数npos,如果len大于从pos下标开始(包含pos)之后的剩余字符长度,则默认为最大长度

    1. string(const string& str, size_t pos, size_t len = npos)
    2. {
    3. if (len > str._size - pos)//如果len大于剩余长度,则将剩余的全部拷贝
    4. {
    5. //len被强制修正到 最大长度-初始位置
    6. len = str._size - pos;
    7. }
    8. _str = new char[str._capacity + 1];
    9. strcpy(_str, str._str + pos);
    10. _size = len;
    11. _capacity = str._capacity;
    12. _str[len] = '\0';
    13. }

    三.赋值运算符重载

    1.string& operator=(const string& s);

    1.1.旧版写法

    1. string& operator=(const string& s)
    2. {
    3. //防止自己给自己赋值
    4. if (this != &s)
    5. {
    6. char* tmp = new char[s._capacity + 1];//开辟新空间
    7. strcpy(tmp, s._str);//拷贝数据
    8. delete[] _str;
    9. _str = tmp;
    10. _size = s._size;
    11. _capacity = s._capacity;
    12. }
    13. return *this;
    14. }

    1.2.新版写法1

    思路:与拷贝构造一致

    1. string& operator=(const string& s)
    2. {
    3. if (this != &s)
    4. {
    5. string tmp(s._str);
    6. //::swap(*this, tmp);//死循环
    7. //死循环的原因:全局的swap函数交换string类对象时会调用string的拷贝构造与赋值重载
    8. //而这两者本身的实现是调用了全局swap函数的,只不过将对象分离成了n个内置类型分开交换
    9. //如果在类内实现的赋值重载就需要调用全局swap且交换的是对象(自定义类型),将发生死循环
    10. swap(tmp);
    11. }
    12. return *this;
    13. }

    1.3.新版写法2 

    思路:不需要新创建tmp用于拷贝的对象,而是直接通过形参的拷贝来直接进行交换

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

    2.string& operator= (const char* s);

    这里仍然是可以使用上面的新版写法的,由于重复性很大,就只演示了旧版写法

    1. string& operator= (const char* s)
    2. {
    3. //防止自己给自己赋值
    4. if (_str != s)
    5. {
    6. size_t size = strlen(s);
    7. char* tmp = new char[size + 1];//开辟新空间
    8. strcpy(tmp, s);//拷贝数据
    9. delete[] _str;
    10. _str = tmp;
    11. _size = _capacity = size;
    12. }
    13. return *this;
    14. }

    3.string& operator= (char c);

    1. string& operator= (char c)
    2. {
    3. char* tmp = new char[2];
    4. delete[] _str;
    5. _str = tmp;
    6. _size = _capacity = 1;
    7. _str[0] = 'c';
    8. _str[1] = '\0';
    9. return *this;
    10. }

    四.迭代器iterator、operator[]、范围for

    1.迭代器iterator

    iterator在string中其实就是char*类型

    1. //正向迭代器
    2. iterator begin()
    3. {
    4. return _str;
    5. }
    6. iterator end()
    7. {
    8. return _str + _size;
    9. }

    2.operator[]

    1. char& operator[](size_t pos)
    2. {
    3. return _str[pos];
    4. }
    1. const char& operator[](size_t pos) const
    2. {
    3. return _str[pos];
    4. }

    3.范围for

    当我们支持了迭代器,其实也就支持了范围for,在汇编层面来看,范围for的底层就是迭代器

    1. string s9("hello iterator");
    2. string::iterator it = s9.begin();
    3. while (it != s9.end())
    4. {
    5. cout << (*it)++ << " ";
    6. it++;
    7. }
    8. cout << endl;
    9. for (auto ch : s9)
    10. {
    11. cout << ch << " ";
    12. }
    13. cout << endl;

    五.增删查改

    0.扩容(reserve)

    reserve

    扩容函数只能扩大不能缩小,也就是说如果第一次reseve(100),第二次reserve(20),那么容量仍然是100

    1. void reserve(size_t n = 0)
    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. }

    1.增(push_back、append、operator+=、insert)

    push_back

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

    append

    注意:如果strcpy改成使用strcat(追加字符串)的话strcat(_str+_size,str)是可以的

    如果strcat(_str,str)这是一个很差的写法,因为strcat的时间复杂度是O(n),而且如果字符串本身就包含\0就会出错

    因此,尽量使用strcpy来代替strcat

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

    operator+=

    +=操作符重载实际就是push_back与append的复用

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

    insert

    参数

            pos:要插入的位置(下标)

            ch:要插入的字符

            str:要插入的字符串

    string& insert(size_t pos, char ch);

    1. string& insert(size_t pos, char ch)
    2. {
    3. assert(pos <= _size);
    4. //扩容
    5. if (_size == _capacity)
    6. {
    7. reserve(_capacity == 0 ? 4 : 2 * _capacity);
    8. }
    9. //移动数据
    10. //size_t end = _size;
    11. size_t end = _size + 1;
    12. while (end > pos)
    13. {
    14. //_str[end + 1] = _str[end];
    15. //这样的写法当pos等于0时,end==pos,
    16. //当下一次循环end--,end等于-1由于end是无符号数,会越界
    17. _str[end] = _str[end - 1];
    18. end--;
    19. }
    20. //插入数据
    21. _str[pos] = ch;
    22. ++_size;
    23. return *this;
    24. }

    string& insert(size_t pos, const char* str);

    注意:拷贝数据时不要用strcpy,因为会把'\0'一起拷贝过来,用strncpy可以控制拷贝长度

    同时在极端情况的处理:以下注释部分代码可读性高但在极端情况会死循环,但这个极端情况大概率不会发生,非注释部分对极端情况进行了处理,在理解这一块的时候一定要画图,就一目了然了

    1. string& insert(size_t pos, const char* str)
    2. {
    3. assert(pos <= _size);
    4. size_t len = strlen(str);
    5. if (_size + len > _capacity)
    6. {
    7. reserve(_size + len);
    8. }
    9. //便于理解但是极端情况会死循环
    10. //极端情况:在pos为0处插入空字符串""
    11. //size_t end = _size + len;
    12. //while (end >= pos + len)
    13. //{
    14. // _str[end] = _str[end - len];
    15. // end--;
    16. //}
    17. //基于以上极端情况的修改
    18. size_t end = _size + len + 1;
    19. while (end > pos + len)
    20. {
    21. _str[end - 1] = _str[end - len - 1];
    22. end--;
    23. }
    24. strncpy(_str + pos, str, len);
    25. _size += len;
    26. return *this;
    27. }

    2.删(erase)

    void erase(size_t pos, size_t len = npos);

    参数

            pos:要删除的起始位置(下标)

            len:从起始位置开始,要删除的字符串长度

            缺省参数npos:如果长度超过剩余字符个数,则全部删除;如果不指明个数,默认全部删除

    1. void erase(size_t pos, size_t len = npos)
    2. {
    3. assert(pos < _size);
    4. //如果len超出范围或者为默认npos
    5. if (len == npos || pos + len >= _size)
    6. {
    7. //从pos位置起全部删除(包含pos)
    8. _str[pos] = '\0';
    9. _size = pos;
    10. }
    11. else
    12. {
    13. //整体拷贝
    14. strcpy(_str + pos, _str + pos + len);
    15. _size -= len;
    16. }
    17. }

    3.查(find)

    参数

            ch:要查找的字符

            str:要查找的字符串

            pos:从pos位置开始找(下标)默认为0

    返回值

            size_t:返回查找的字符的位置(下标)

            没找到就返回npos

    注意:find与rfind都是找到第一个匹配的就停下

    size_t find(char ch, size_t pos = 0) const;

    1. size_t find(char ch, size_t pos = 0) const
    2. {
    3. assert(pos < _size);
    4. for (size_t i = pos; i < _size; i++)
    5. {
    6. if (ch == _str[i])
    7. return i;
    8. }
    9. return npos;
    10. }

    size_t find(const char* str, size_t pos = 0) const;

    方法一:

    1. size_t find(const char* str, size_t pos = 0) const
    2. {
    3. assert(pos < _size);
    4. size_t strsize = strlen(str);
    5. size_t cur = 0;//str的元素下标
    6. size_t i = pos;//每次查找的起始位置
    7. size_t findcur = i;//要查找的字符串的元素下标
    8. while (i < _size && cur < strsize)
    9. {
    10. if (_str[findcur] != str[cur])
    11. {
    12. cur = 0;
    13. i++;
    14. findcur = i;
    15. }
    16. else
    17. {
    18. cur++;
    19. findcur++;
    20. }
    21. }
    22. //找到了
    23. if (cur == strsize)
    24. {
    25. return i;
    26. }
    27. return npos;
    28. }

    方法二:

    1. size_t find(const char* str, size_t pos = 0) const
    2. {
    3. assert(pos < _size);
    4. const char* p = strstr(_str + pos, str);
    5. if (p == nullptr)
    6. {
    7. return npos;
    8. }
    9. else
    10. {
    11. return p - _str;
    12. }
    13. }

    六.流输入/输出、兼容C接口c_str

    1.operator<<

    1. ostream& operator<<(ostream& out, const string& s)
    2. {
    3. for (size_t i = 0; i < s.size(); i++)
    4. {
    5. out << s[i];
    6. }
    7. return out;
    8. }

    2.operator>>(重点讲解,利用了缓冲区的原理)

    2.0.clear

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

    2.1错误版本

    注意流提取<<,是以空格为间隔的,比如说cin>>a>>b;输入n m,这个空格只是告诉a,只需要读取到空格就结束了,然后b读取到换行就结束了,实际并不会将空格或换行读取进来,所以以下的代码就会发生死循环,ch永远读取不到' '和'\n'就一直循环读取 

    1. istream& operator>>(istream& in, string& s)
    2. {
    3. s.clear();
    4. char ch;
    5. in >> ch;
    6. while (ch != '\n' && ch != ' ')
    7. {
    8. s += ch;
    9. in >> ch;
    10. }
    11. return in;
    12. }

    2.2正确版本(效率低)

    用到了istream流的get成员函数,可以读取空格或者换行

    但是这种写法效率低,每次读取一个字符调用一次+=重载

    1. istream& operator>>(istream& in, string& s)
    2. {
    3. s.clear();
    4. char ch;
    5. ch = in.get();
    6. while (ch != '\n' && ch != ' ')
    7. {
    8. s += ch;
    9. ch = in.get();
    10. }
    11. return in;
    12. }

    2.3改进版本(类似于缓冲区,高效)

    1. istream& operator>>(istream& in, string& s)
    2. {
    3. s.clear();
    4. char ch;
    5. ch = in.get();
    6. //定义一个可以存放16个字符的缓冲区
    7. const size_t N = 16;
    8. char tmp[N + 1];
    9. size_t i = 0;
    10. while (ch != '\n' && ch != ' ')
    11. {
    12. tmp[i++] = ch;
    13. //缓冲区满了,拷贝出去,然后无效化
    14. if (i == N)
    15. {
    16. tmp[i] = '\0';
    17. s += tmp;
    18. i = 0;
    19. }
    20. ch = in.get();
    21. }
    22. //将缓冲区剩余全部拷贝出去
    23. tmp[i] = '\0';
    24. s += tmp;
    25. return in;
    26. }

    3.c_str

    const char* c_str() const;

    1. const char* c_str() const
    2. {
    3. return _str;
    4. }

    4.operator<<与c_str的区别

    operator<<是流输出的重载,对于string而言打印的字符串是受_size限制的

    c_str是返回字符串首地址的函数,对于string而言以'\0'为结束标志的

    对于一些只兼容C语言的接口来讲,不认识string类,这时就需要用到c_str,将string类转换成字符串首地址来进行操作

    七.字符串比较

    bool operator>(const string& s) const;

    bool operator<(const string& s) const;

    bool operator==(const string& s) const;

    bool operator!=(const string& s) const;

    bool operator>=(const string& s) const;

    bool operator<=(const string& s) const;

    1. bool operator>(const string& s) const
    2. {
    3. return strcmp(_str, s._str) > 0;
    4. }
    5. bool operator<(const string& s) const
    6. {
    7. return strcmp(_str, s._str) < 0;
    8. }
    9. bool operator==(const string& s) const
    10. {
    11. return strcmp(_str, s._str) == 0;
    12. }
    13. bool operator!=(const string& s) const
    14. {
    15. return strcmp(_str, s._str) != 0;
    16. }
    17. bool operator>=(const string& s) const
    18. {
    19. return !(strcmp(_str, s._str) < 0);
    20. }
    21. bool operator<=(const string& s) const
    22. {
    23. return !(strcmp(_str, s._str) > 0);
    24. }

    八.其他函数

    1.substr

    参数

            pos:从pos位置开始(下标)

            len:截取len个字符(包含pos)

    1. string substr(size_t pos = 0, size_t len = npos) const
    2. {
    3. assert(pos < _size);
    4. size_t reallen = len;
    5. if (len == npos || pos + len > _size)
    6. {
    7. reallen = _size - pos;
    8. }
    9. string ans;
    10. for (size_t i = 0; i < reallen; i++)
    11. {
    12. ans += _str[pos + i];
    13. }
    14. return ans;
    15. }

    2.resize

    这里的实现就将void resize(size_t n)与void resize(size_t n, char ch)合并起来了

    void resize(size_t n, char ch = '\0');

    注意:resize是在开空间的同时并且初始化,如果没给初始化内容默认就是'\0'

    如果第一次resize(20)第二次resize(10)最终_size等于10

    如果第一次resize(20,'x')第二次resize(10,'a')最终_size等于10,且_str是20个'x'

    总结:_capacity不会减小,_size是会减小的,已经被resize初始化好的空间的值,不能再次用resize覆盖

    多次resize只能删除之前的数据个数或者在之前的数据个数基础上扩容并且初始化新的数据

    1. void resize(size_t n, char ch = '\0')
    2. {
    3. //开空间并且初始化数据
    4. if (n > _size)
    5. {
    6. //扩容
    7. reserve(n);
    8. for (size_t i = _size; i < n; i++)
    9. {
    10. _str[i] = ch;
    11. }
    12. }
    13. _str[n] = '\0';
    14. _size = n;
    15. }

    3.析构函数~string()

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

    九.在vs中对于string的特殊处理

    1. string s1("111111111");
    2. string s2("11111111111111111111111111111111111111");
    3. cout << "s1:" << sizeof(s1) << endl << "s2:" << sizeof(s2) << endl;

     根据对于string的学习,我们知道string类的成员变量有 _str _capacity _size,但是这样不应该是12字节吗?为什么上面打印出来的是28字节?

    实际上,vs对于string做了单独的处理,多加了一个char _Buf[16]

    当<16个字节的字符串,存在_Buf数组上,当>=16个字节的字符串,就存在_str指向的堆空间上

    缺点:使原本实例化的string对象多占用了16字节

    优点:小空间的对象不再向堆区申请空间,效率有一定提升

  • 相关阅读:
    日常渗透刷洞的一些小工具
    2022十三届蓝桥杯国赛题解
    双十一来临,仓储物流快递安全保障解决方案
    【SIMULINK】全网最牛逼自制感应电机simulink模型,基于原始方程
    MySQL常见问题
    [含文档+PPT+源码等]精品基于Uniapp+SSM实现的Android的校园新闻管理系统实现的App[包运行成功]计算机毕业设计Android项目源码
    Springboot基于ElasticSearch全文搜索引擎策略实现
    MySQL主/从-主/主集群安装部署
    php水果百科动态网站毕业设计-附源码060917
    使用Docker搭建Npm私服Verdaccio
  • 原文地址:https://blog.csdn.net/Hello_World_213/article/details/126452481