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

简介: 【C++】C++STL 揭秘:Strng背后的底层逻辑

一、模拟现实string准备工作

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

namespace str
{
  class string
  {
  };
}

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

  1. _str:指向动态开辟的空间
  2. _size:有效数据个数
  3. _capacity:容量空间的大小(不包括\0,实际空间包括)
  4. 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];
}

具体分析:

  1. 首先operator[]是调用函数,并且有两个函数重载
  2. 其次operator[]是个大进步,对于检查越界的情况
  3. 如果是数组的话,很难检查是否有越界情况发生(越界检查是一种抽查,在容易越界的地方,放几个值,看这个值是否被修改)。越界读的话,很难发现越界,是很危险的
  4. operator[]实现中,有assert判断是否出现有越界的情况。
  5. 关于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;
        }
    }

说明:

  1. reserve只有在所需空间超过当前容量才起到扩容作用
  2. 让打工仔tmp开辟满足条件的空间,_str在进行拷贝、销毁、转化指向
  3. 这里需要改动_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;
    }
}

说明:

  1. 使用resize需要考虑三种情况,但是模拟实现可以只考虑两种情况
  2. 提前使用reserve开辟好空间,避免扩容操作,将两种情况处理成一种情况
  3. 当n小于等于当前大小,需要使用\0的形式截断字符串
  4. 当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背后的底层逻辑(二)https://developer.aliyun.com/article/1617336

相关文章
|
1月前
|
存储 算法 C++
C++ STL 初探:打开标准模板库的大门
C++ STL 初探:打开标准模板库的大门
91 10
|
1月前
|
存储 搜索推荐 C++
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器2
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器
48 2
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器2
|
24天前
|
存储 程序员 C++
C++常用基础知识—STL库(2)
C++常用基础知识—STL库(2)
61 5
|
24天前
|
存储 自然语言处理 程序员
C++常用基础知识—STL库(1)
C++常用基础知识—STL库(1)
44 1
|
1月前
|
算法 安全 Linux
【C++STL简介】——我与C++的不解之缘(八)
【C++STL简介】——我与C++的不解之缘(八)
|
1月前
|
存储 编译器 C++
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
50 2
|
26天前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
20 0
|
22天前
|
存储 编译器 对象存储
【C++打怪之路Lv5】-- 类和对象(下)
【C++打怪之路Lv5】-- 类和对象(下)
21 4
|
22天前
|
编译器 C语言 C++
【C++打怪之路Lv4】-- 类和对象(中)
【C++打怪之路Lv4】-- 类和对象(中)
20 4
|
22天前
|
存储 安全 C++
【C++打怪之路Lv8】-- string类
【C++打怪之路Lv8】-- string类
17 1