【C++】模拟实现string类

模拟实现string类

链接: 认识使用string类

前文已经讲解过如何使用string类，下面主要讲解如何模拟实现常用的string类函数，以及对深拷贝和浅拷贝的讲解。

模拟实现string类

namespace imitate
{classstring{};}

首先创建一个命名空间域，这个域被用来模拟string类。

classstring{private:char* _str;
        size_t _size;
        size_t _capacity;};

类中的私有成员变量同顺序表一样，包括字符数组、无符号整型_size和_capcity。

public:string(constchar* str =""){
            _size =strlen(str);
            _capacity =strlen(str);
            _str =newchar[_capacity +1];memcpy(_str, str, _size +1);}

类中模拟实现默认构造函数，内置成员变量类型未写在初始化列表是因为_str的初始化需要动态开辟。

~string(){delete[] _str;
            _str =nullptr;
            _size = _capacity =0;}

模拟实现默认析构函数。

constchar*c_str()const{return _str;}

模拟实现返回c字符串函数，方便后续验证。

        size_t size()const{return _size;}

模拟实现size函数，可以获取字符串的长度

char&operator[](size_t pos){assert(pos <= _size);return _str[pos];}

constchar&operator[](size_t pos)const{assert(pos <= _size);return _str[pos];}

模拟实现operator[ ]函数，可以用于遍历字符串；前者是用于可以修改的字符串；后者是用于不可修改的字符串。

typedefchar* iterator;typedefconstchar* const_iterator;

        iterator begin(){return _str;}
        iterator end(){return _str + _size;}
        const_iterator begin()const{return _str;}
        const_iterator end()const{return _str + _size;}

模拟实现迭代器，可以用于遍历或者范围for的使用。

voidreserve(size_t n =0){if(n > _capacity){char* tmp =newchar[n +1];memcpy(tmp, _str, _size);delete[] _str;
                _capacity = n;
                _str = tmp;}}

模拟实现reserve()函数，用于请求字符串容量，new char[n+1]是为了后续扩容时，保证可以将’\0’录入

voidpush_back(char c){if(_capacity == _size){//二倍扩容:判断_capacity是否为空reserve(_capacity ==0?4: _capacity *2);}
            _str[_size]= c;++_size;
            _str[_size]='\0';}

模拟实现push_back()函数，后增一个字符。

        string&append(constchar* s){
            size_t len =strlen(s);if(_size + len > _capacity){reserve(_size + len);}memcpy(_str + _size, s, _size + len +1);
            _size += len;return*this;}

模拟实现append()函数，后增字符串。

        string&operator+=(char c){push_back(c);return*this;}
        string&operator+=(constchar* str){append(str);return*this;}

模拟实现operator+=()函数，方便字符串的后增。

classstring{public:conststatic size_t npos;};const size_t string::npos =-1;

模拟一个静态成员变量，静态成员变量的初始化需要在类外面。

voidinsert(size_t pos, size_t n,char c){assert(pos <= _size);if(_size + n > _capacity){reserve(_size + n);}//挪动数据
            size_t end = _size;//end不等于npos是为了防止原字符串为空while(end >= pos && end != npos){
                _str[end + n]= _str[end];--end;}//添加数据for(size_t i = pos; i < n + pos;++i){
                _str[i]= c;}
            _size += n;}

voidinsert(size_t pos,constchar* str){assert(pos <= _size);
            size_t len =strlen(str);if(_size + len > _capacity){reserve(_size + len);}//挪动数据
            size_t end = _size;//end不等于npos是为了防止原字符串为空while(end >= pos && end != npos){
                _str[end + len]= _str[end];--end;}//添加数据for(size_t i =0; i < len;++i){
                _str[i + pos]= str[i];}
            _size += len;}

模拟实现insert()函数，用于插入n个字符或者字符串。

voiderase(size_t pos, size_t len = npos){assert(pos <= _size);if(pos + len >= _size || len == npos){
                _str[pos]='\0';
                _size = pos;}else{
                size_t end = pos + len;while(end <= _size){
                    _str[pos++]= _str[end++];}
                _size -= len;}}

模拟实现erase()函数，用于实现擦除字符串。

        size_t find(char c, size_t pos =0){assert(pos <= _size);for(int i = pos; i < _size;++i){if(_str[i]== c){return i;}}return npos;}

模拟实现find()函数，用于查找字符

        string substr(size_t pos =0, size_t len = npos){assert(pos <= _size);

            size_t n = len;if(pos + len >= _size || len == npos){
                n = _size - pos;}
            string tmp;reserve(n);for(int i =0; i < n;++i){
                tmp[i]= _str[pos + i];}return tmp;

模拟实现substr()，用于实现生成子字符串。

voidresize(size_t n,char ch ='\0'){if(n < _size){
                _str[n]='\0';
                _size = n;}else{reserve(n);for(size_t i = _size; i < n;++i){
                    _str[i]= ch;}
                _str[n]='\0';
                _size = n;}}

模拟实现resize()，用于调整字符串。在调整字符串的过程中有三种情况：1.当n小于_size时，不需要扩容；2.当n大于_size时，不需要扩容；3.当n大于_size时，需要扩容。

    std::ostream&operator<<(std::ostream& out,const string& s){for(size_t i =0; i < s.size();++i){
            out << s[i];}return out;}

使用不设置友元的运算符重载函数operator<<()，用于流插入。在使用流提取需要注意流插入是打印全部内容，而c.str()函数可以打印到’\0’。

c的字符数组，以’\0’为终止计算长度。
string不关注’\0’，以_size终止计算长度。

voidclear(){
            _str[0]='\0';
            _size =0;}

模拟实现clear()函数，用于清理字符串。

    std::istream&operator>>(std::istream& in, string& s){
        s.clear();char ch;
        ch = in.get();while(ch ==' '|| ch =='\n'){
            ch = in.get();}char buff[128]="\0";
        size_t i =0;while(ch !=' '&& ch !='\n'){
            buff[i++]= ch;if(i ==127){
                buff[127]='\0';
                s += buff;
                i =0;}
            ch = in.get();}if(i !=0){
            buff[i]='\0';
            s += buff;}return in;}

模拟实现无友元的运算符重载函数operator>>()，用于流提取。
【注意】
1.字符串不能使用const
2.in>>ch无法读取’ ‘以及’\0’，会导致一直处于流提取的状态，所以需要in.get()函数读每一个字符。
3.再次输入数组是，上一次数据尚未清理，导致打印俩次内容，所以需要补充clear()函数。
4.数据太多可以会导致扩容次数太多，推荐设置一个char类型的数据，一次性提取。
5.需要除去字符串前面的’ ’ 和’\n’，所以需要将其循环掉。

booloperator<(const string& s){
            size_t i1 =0;
            size_t i2 =0;while(i1 < _size && i2 << s._size){if(_str[i1]< _str[i2]){returntrue;}elseif(_str[i1]> _str[i2]){returnfalse;}else{++i1;++i2;}}//三种情况：//"hello" "hello"//"helloxxx" "hello"//"hello" "helloxxx"return(_size >= s._size)?false:true;}booloperator==(const string& s){return _size == s._size &&memcmp(_str, s._str, _size)==0;}booloperator<=(const string& s){return*this< s ||*this== s;}booloperator>(const string& s){return!(*this<= s);}booloperator>=(const string& s){return!(*this< s);}

模拟实现用于比较的运算符重载函数，需要注意的是，比较字符串的时候是比较ASCII码值，在模拟实现的过程中需要注意上述的三种情况。

浅拷贝与深拷贝

上述已经模拟实现了实际中常使用的string类，但是有一个核心的知识点没有讲解，就是拷贝构造。

    imitate::string s1("hello world");
    imitate::string s2(s1);

使用上述代码进行测试，如果执行的是编译器实现的默认拷贝构造，则s2的_size、_capacity会与s1相同，但是s2._str并不会自动动态开辟空间，而会指向s1，当结束时，会对这块空间析构俩次。

    imitate::string s1("hello world");
    imitate::string s2("xxxxxxxxxxx");
    s1 = s2;

同样，这段代码也会出现相同的问题，"hello world"这快空间不会被释放，而"xxxxxxxxxx"这块空间会被释放俩次。

上述俩个例子的string类没有显示定义其拷贝构造函数，此时编译器会合成默认的，当s1构造s2时，编译器会调用默认的拷贝构造。最终会导致s1与s2共用同一块内存空间，在释放时同一块空间被释放多次会导致程序崩溃，而这种拷贝方式被称为浅拷贝。

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

string(const string& s){
            _size = s._size;
            _capacity = s._capacity;
            size_t len =strlen(s._str);
            _str =newchar[len +1];memcpy(_str, s._str, len +1);}

我们可以自己实现一个拷贝构造函数，即采用深拷贝的方式解决问题，每一个对象都有一份独立的资源，不要和其他对象共享。

如果一个类中涉及到资源的管理（例如动态开辟空间），其拷贝构造函数、赋值运算符重载以及析构函数必须要显式给出，一般都是按照深拷贝方式提供。

string(const string& s){
            size_t len =strlen(s._str);
            _str =newchar[len +1];memcpy(_str, s._str, len +1);

            _size = s._size;
            _capacity = s._capacity;}

        string&operator=(const string& s){if(*this!= s){delete[] _str;
                _str =newchar[strlen(s._str)+1];
                _size = s._size;
                _capacity = s._capacity;}return*this;}

这俩种方式是传统版写法的string类。

        string&operator=(const string& s){if(*this!= s){
                string tmp(s);
                std::swap(_size, tmp._size);
                std::swap(_capacity, tmp._capacity);
                std::swap(_str, tmp._str);}return*this;}

        string&operator=(string tmp){if(*this!= tmp){
                std::swap(_size, tmp._size);
                std::swap(_capacity, tmp._capacity);
                std::swap(_str, tmp._str);}return*this;}

这俩种方式是现代版本的深拷贝，现代版本的深拷贝利用了每一个函数的析构。

写时拷贝（了解）

进行拷贝构造时，深拷贝和浅拷贝可能存在部分问题。
对于深拷贝而言：如果只是对数据进行拷贝，而并未对数据继续修改等操作，那么深拷贝的代价可能会比较大；
对于浅拷贝而言：核心问题有俩个，其一是会对同一块空间析构俩次，其二是当一个对象被修改时，另外一个对像也会随之修改。

这里可以采用的办法是，先对数据进行浅拷贝，添加一个数据，对一块空间进行引用计数。
引用计数：用来记录资源使用者的个数。在构造时，将资源的计数给成1，每增加一个对象使用改资源，就给计数增加1，当某个对象被销毁时，先给该计数减1，然后再检查是否需要释放资源，如果计数为1，说明该对象此时为资源的最后一个使用者，将该资源释放；否则就不能释放，将计数器减一即可，因为还有其他对象再使用该资源。

这里就可以很好的解决浅拷贝的析构问题，但是当一个对象被修改时，另外一个对象也会修改，此时采取的办法是进行写时拷贝。

写时拷贝，可以看作是一种拖延症，写时拷贝是在引用计数的基础上进行修改的，如果引用计数的值不为1，则进入深拷贝，再对其进行修改。

在gcc环境下，采取的是写时拷贝：

在vs环境下，采取的是深拷贝：

string类的模拟实现代码

#pragmaonce#define_CRT_SECURE_NO_WARNINGS1#include<iostream>#include<assert.h>namespace imitate
{classstring{public:string(constchar* str =""){
            _size =strlen(str);
            _capacity =strlen(str);
            _str =newchar[_capacity +1];memcpy(_str, str, _size +1);}string(const string& s){
            size_t len =strlen(s._str);
            _str =newchar[len +1];memcpy(_str, s._str, len +1);

            _size = s._size;
            _capacity = s._capacity;}//string& operator=(const string& s)//{//    if (*this != s)//    {//        delete[] _str;//        _str = new char[strlen(s._str) + 1];//        _size = s._size;//        _capacity = s._capacity;//    }//    return *this;//}//string& operator=(const string& s)//{//    if (*this != s)//    {//        string tmp(s);//        std::swap(_size, tmp._size);//        std::swap(_capacity, tmp._capacity);//        std::swap(_str, tmp._str);//    }//    return *this;//}
        string&operator=(string tmp){if(*this!= tmp){
                std::swap(_size, tmp._size);
                std::swap(_capacity, tmp._capacity);
                std::swap(_str, tmp._str);}return*this;}~string(){delete[] _str;
            _str =nullptr;
            _size = _capacity =0;}constchar*c_str()const{return _str;}
        size_t size()const{return _size;}char&operator[](size_t pos){assert(pos <= _size);return _str[pos];}constchar&operator[](size_t pos)const{assert(pos <= _size);return _str[pos];}typedefchar* iterator;typedefconstchar* const_iterator;

        iterator begin(){return _str;}
        iterator end(){return _str + _size;}
        const_iterator begin()const{return _str;}
        const_iterator end()const{return _str + _size;}voidreserve(size_t n =0){if(n > _capacity){char* tmp =newchar[n +1];memcpy(tmp, _str, _size);delete[] _str;
                _str = tmp;
                _capacity = n;}}voidpush_back(char c){if(_capacity == _size){//二倍扩容:判断_capacity是否为空reserve(_capacity ==0?4: _capacity *2);}
            _str[_size]= c;++_size;
            _str[_size]='\0';}
        string&append(constchar* s){
            size_t len =strlen(s);if(_size + len > _capacity){reserve(_size + len);}memcpy(_str + _size, s, _size + len +1);
            _size += len;return*this;}
        string&operator+=(char c){push_back(c);return*this;}
        string&operator+=(constchar* str){append(str);return*this;}voidinsert(size_t pos, size_t n,char c){assert(pos <= _size);if(_size + n > _capacity){reserve(_size + n);}//挪动数据
            size_t end = _size;//end不等于npos是为了防止原字符串为空while(end >= pos && end != npos){
                _str[end + n]= _str[end];--end;}//添加数据for(size_t i = pos; i < n + pos;++i){
                _str[i]= c;}
            _size += n;}voidinsert(size_t pos,constchar* str){assert(pos <= _size);
            size_t len =strlen(str);if(_size + len > _capacity){reserve(_size + len);}//挪动数据
            size_t end = _size;//end不等于npos是为了防止原字符串为空while(end >= pos && end != npos){
                _str[end + len]= _str[end];--end;}//添加数据for(size_t i =0; i < len;++i){
                _str[i + pos]= str[i];}
            _size += len;}voiderase(size_t pos, size_t len = npos){assert(pos <= _size);if(pos + len >= _size || len == npos){
                _str[pos]='\0';
                _size = pos;}else{
                size_t end = pos + len;while(end <= _size){
                    _str[pos++]= _str[end++];}
                _size -= len;}}
        size_t find(char c, size_t pos =0){assert(pos <= _size);for(size_t i = pos; i < _size;++i){if(_str[i]== c){return i;}}return npos;}
        string substr(size_t pos =0, size_t len = npos){assert(pos <= _size);

            size_t n = len;if(pos + len >= _size || len == npos){
                n = _size - pos;}
            string tmp;reserve(n);for(size_t i =0; i < n;++i){
                tmp[i]= _str[pos + i];}return tmp;}voidresize(size_t n,char ch ='\0'){if(n < _size){
                _str[n]='\0';
                _size = n;}else{reserve(n);for(size_t i = _size; i < n;++i){
                    _str[i]= ch;}
                _str[n]='\0';
                _size = n;}}voidclear(){
            _str[0]='\0';
            _size =0;}booloperator<(const string& s){
            size_t i1 =0;
            size_t i2 =0;while(i1 < _size && i2 << s._size){if(_str[i1]< _str[i2]){returntrue;}elseif(_str[i1]> _str[i2]){returnfalse;}else{++i1;++i2;}}//三种情况：//"hello" "hello"//"helloxxx" "hello"//"hello" "helloxxx"return(_size >= s._size)?false:true;}booloperator==(const string& s){return _size == s._size &&memcmp(_str, s._str, _size)==0;}booloperator!=(const string& s){return!(_str == s._str);}booloperator<=(const string& s){return*this< s ||*this== s;}booloperator>(const string& s){return!(*this<= s);}booloperator>=(const string& s){return!(*this< s);}private:char* _str;
        size_t _size;
        size_t _capacity;public:conststatic size_t npos;};const size_t string::npos =-1;

    std::ostream&operator<<(std::ostream& out,const string& s){for(size_t i =0; i < s.size();++i){out<< s[i];}return out;}

    std::istream&operator>>(std::istream& in, string& s){
        s.clear();char ch;
        ch = in.get();while(ch ==' '|| ch =='\n'){
            ch = in.get();}char buff[128]="\0";
        size_t i =0;while(ch !=' '&& ch !='\n'){
            buff[i++]= ch;if(i ==127){
                buff[127]='\0';
                s += buff;
                i =0;}
            ch = in.get();}if(i !=0){
            buff[i]='\0';
            s += buff;}return in;}}