【C++】C++STL 揭秘:Strng背后的底层逻辑（一）-阿里云开发者社区

一、模拟现实string准备工作

在模拟实现string过程中，为了避免跟库中string发生冲突，需要创建个命名空间，在命名空间中实现string。

namespace str
{
  class string
  {
  };
}

string底层是动态字符串顺序表，对此string中需要这个四个成员变量作为支架。

_str:指向动态开辟的空间

_size:有效数据个数

_capacity：容量空间的大小(不包括\0，实际空间包括)

npos：静态成员变量，表示最大值(属于整个类)

namespace str
{
  class string
  {
  private:
    char* _str;
    size_t _size;
    size_t _capacity;
    static const size_t npos;
  };
    //在类外初始化
    const size_t string:: npos = -1;
}

二、构造函数

2.1 无参构造函数

string()
    :_str(new char[1])//为'\0'开一块空间
        :_size(0)
            :_capacity(0)
            {
                _str[_size] = '\0';
            }

2.2 有参构造函数

string(const char* str)
    :_size(strlen(str))
        ,_capacity(strlen(str))
    {
        _str = new char[_capacity + 1];
        strcpy(_str, str);
    }

先确定str有效字符串长度，再决定申请多大空间，最后将str中内容拷贝给该对象

2.3 全缺省构造函数

【瑕疵版本】：

string(const char *str = nullptr)
    :_size(strlen(str))
        ,_capacity(strlen(str))
    {
        _str = new char[_capacity + 1];
        strcpy(_str, str);
    }

不足在于：当缺省值为nullptr时，strlen计算大小会报错，strlen会对参数部分解引用操作。同时这里strlen函数调用多次，效率降低。

【完善版本】：

string(const char *str="")
    :_size(strlen(str))
    {
        _capacity = _size;
        _str = new char[_capacity + 1];
        strcpy(_str, str);
    }

缺省值给""空字符串，编译器会自动填充\0，达到了无参的要求。无参调用时，调用strlen()函数计算大小为0。虽然缺省值可以直接给\0，但是没有必要，会导致有两个\0存在。

小结：在实践中推荐只保留一个全缺省构造函数。

三、析构函数

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

清空_str指向动态空间中的资源，delete[] _str会调用析构函数和free释放空间。

四、交换函数Swap

//string类中
void swap(string& s)
{
    std::swap(_str, s._str);
    std::swap(_size, s._size);
    std::swap(_capacity, s._capacity);
}
//string类外
void swap(string& x,string &y)
{
    x.swap(y);
}

这里实现了在string类外和string类中的交换函数swap，但是类外的本质还是调用类中的swap。虽然算法库有swap函数模板，但是需要走深拷贝，代价很大，这里需要重现实现swap函数。

实现一个成员函数，通过交换属性(值拷贝)，代价较少。虽然本质还是调用算法库中库函数，但是使用方式不同，付出的代价也不同。

小结:在使用swap函数时，需要根据自己的需求来使用，不然会弄巧成拙的

五、拷贝构造函数

5.1 传统写法

string(const string& s)
{
    _str = new char[s._capacity + 1];
    strcpy(_str, s._str);
    _size = s._size;
    _capacity = s._capacity;
}

具体流程：_str指向空，该对象没有被实例化。先开辟一块跟被拷贝对象等大的空间，再将数据拷贝一份。拷贝构造是将其他对象数据，拷贝到新的对象中。这本身是不影响被拷贝对象。

5.2 现代写法

string(const string& str)
{
    string ss(str._str);
    swap(ss);
}

具体流程：_ str指向空，该对象没有被实例化。先调用string ss(str. _str)构造函数，得到一份str._str相同数据跟_str交换。相当于就是 _str和打工仔ss进行交互，完成拷贝操作。

这不采用string ss(s)拷贝构造，在拷贝构造中调用拷贝构造，本身就是闭环。

小结：

无论是现代写法还是传统写法，在效率上是一样的，主要在于书写行数的关系

现代写法和传统写法参数相同，不能构成函数重载，只能选择一个使用

六、operator[] (下标方括号)

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

具体分析:

首先operator[]是调用函数，并且有两个函数重载

其次operator[]是个大进步，对于检查越界的情况

如果是数组的话，很难检查是否有越界情况发生(越界检查是一种抽查，在容易越界的地方，放几个值，看这个值是否被修改)。越界读的话，很难发现越界，是很危险的

operator[]实现中，有assert判断是否出现有越界的情况。

关于const char& operator[](size_t pos) const情况，是为了对于被const修饰对象，也可以访问其元素，并且仅限于读权限

七、operator=(赋值运算符重载)

7.1 传统写法

string& operator=(const string& str)
{
    char* tmp = new char[str._capacity + 1];
    strcpy(tmp, str._str);
    delete[]_str;
    _str = tmp;
    _size = str._size;
    _capacity = str._capacity;
    return *this
}

具体说明：

赋值操作是发生于两个对象已经创建完毕，对此被赋值对象自然存在一块空间，需要等着被清除资源。这里赋值拷贝不能影响到赋值对象，可以采用使用一个临时变量进行中间过程交换，开辟跟被拷贝对象等大的空间，将数据拷贝，将_str指向旧空间释放，指向tmp指向空间完成赋值。

tmp是函数内部声明的自动变量(局部变量)，出作用域会自动销毁，但是指向堆上分配的内存不会因为tmp的销毁而释放，导致_str指向那块空间不会被回收，顺便完成了tmp指向空间为空操作。

7.2 现代写法

string& operator=(const string& s)
{
    string ss(s);
    swap(ss);
    return *this;
}

这里不用担心ss对象指向空间没有得到释放，ss对象属于局部对象，出了函数作用域就会调用析构函数和销毁。

7.3 现代写法优化

string& operator=(string ss)
{
    swap(ss);
    return *this;
}

相对于上面的现代写法，这里在传参的过程中完成了拷贝构造。

小结:

无论是现代写法还是传统写法，在效率上是一样的，主要在于书写行数的关系

现代写法和传统写法参数相同，不能构成函数重载，只能选择一个使用

八、Size（获得字符串长度）

size_t size(const string& s) const
    {
      return s._size;
    }

九、Capacity(获得容量大小)

size_t capacity(const string& s) const
    {
        return s._capacity;
    }

十、resever

void reserve(size_t n)
    {
        if (n > _capacity)
        {
            char* tmp = new char[n + 1];
            strcpy(tmp, _str);
            delete[]_str;
            _str = tmp;
            _capacity = n;
        }
    }

说明:

reserve只有在所需空间超过当前容量才起到扩容作用

让打工仔tmp开辟满足条件的空间，_str在进行拷贝、销毁、转化指向

这里需要改动_capacity就行， _size代表是有效个数

十一、resize

void resize(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需要考虑三种情况，但是模拟实现可以只考虑两种情况

提前使用reserve开辟好空间，避免扩容操作，将两种情况处理成一种情况

当n小于等于当前大小，需要使用\0的形式截断字符串

当n大于等当前容量，就是按照ch完成填充新开辟空间

十二、insert

12.1 任意位置插入字符

【瑕疵版本】：

void insert(size_t pos, char ch)
{
    assert(pos <= _size);
    // 扩容2倍
    if (_size == _capacity)
    {
        reserve(_capacity == 0 ? 4 : 2 * _capacity);
    }
    size_t end = _size;
    while (end >= pos)
    {
        _str[end + 1] = _str[end];
        --end;
    }
    _str[pos] = ch;
    ++_size;
}

不足之处:从代码的逻辑来看，感觉是没啥问题。如果选择在首位置插入数据，end进行–操作变成负数。由于end类型为size_t 无符号整数会导致end为最大值，循环不会停下。

【尝试调正】:那么将end设置为符号整型，就可以保证它可以为负数

int end = _size;
while (end >= pos)
{
    _str[end + 1] = _str[end];
    --end;
}

但是end和pos是不同类型的变量，在进行比较时，编译器会执行整型提升，size__t隐式转化为int类型再比较。

【最终方案】:

size_t end = _size + 1;
while (end > pos)
{
    _str[end] = _str[end - 1];
    --end;
}

让end指向结尾下一个位置。在数据移动的时候，解决了首位置插入end等于pos移动导致死循环的问题。

12.2 任意位置插入字符串

void insert(size_t pos, const char* str)
    {
        assert(pos <= _size);
        size_t len = strlen(str);
        if (len + _size > _capacity)
        {
            reserve(_size + len);
        }
        size_t end = _size + len;
        while (end > pos + len)
        {
            _str[end] = _str[end - len];
            --end;
        }
    //通过strncpy将需要插入字符串覆盖，完成插入
        strncpy(_str + pos, str, len);
        _size += len;
    }

具体流程:先提前判断插入字符串长度是否会超过当前容量，这里同上面一致将元素移动备份，将待插入元素进行覆盖操作。需要注意插入在首位置死循环的问题，同样采取上面的解决办法：向后移动N位预留空间。代码逻辑可以参考中两张图片理解。

【C++】C++STL 揭秘:Strng背后的底层逻辑（一）