C++标准库中string的底层实现方式

码农世界 2024-05-29 前端 80 次浏览 0个评论

对于C++中 std::string 的一些基本功能和用法，我们应该都很熟悉。但它底层到底是如何实现的呢? 其实在 std::string 的历史中，出现过几种不同的方式。下面我们来一一揭晓。我们可以从一个简单的问题来探索，一个 std::string 对象占据的内存空间有多大，即 sizeof(std::string) 的值为多大？如果我们在不同的编译器（VC++, GNU, Clang++）上去测试，可能会发现其值并不相同；即使是GNU，不同的版本，获取的值也是不同的。

虽然历史上的实现有多种，但基本上有三种方式：

Eager Copy(深拷贝)
COW（Copy-On-Write 写时复制）
SSO(Short String Optimization-短字符串优化)
每种实现，std::string都包含了下面的信息：
- 字符串的大小
- 能够容纳的字符数量
- 字符串内容本身
  1、Eager Copy
  
  最简单的就是深拷贝了。无论什么情况，都是采用拷贝字符串内容的方式解决。这种实现方式，在需要对字符串进行频繁复制而又并不改变字符串内容时，效率比较低下。所以需要对其实现进行优化，之后便出现了下面的COW的实现方式。
  
  2、COW(Copy-On-Write)
  
  Copy-On-Write的原理是什么？
  
  有一定经验的程序员一定知道，Copy-On-Write一定使用了“引用计数”，那么必然有一个变量类似于RefCnt。当第一个类构造时，string的构造函数会根据传入的参数从堆上分配内存，当有其它类需要这块内存时，这个计数为自动累加，当有类析构时，这个计数会减一，直到最后一个类析构时，此时的RefCnt为1或是0，此时，程序才会真正的Free这块从堆上分配的内存。
  是的，引用计数就是string类中写时才拷贝的原理！
  不过，这个RefCnt该存在在哪里呢？如果存放在string类中，那么每个string的实例都有各自的一套，根本不能共有一个RefCnt，如果是声明成全局变量，或是静态成员，那就是所有的string类共享一个了，这也不行。那么我们应该如何解决呢？
  
  string类在什么情况下触发写时复制（Copy-On-Write）?
  
  当共享同一块内存的类发生内容改变时，才会发生Copy-On-Write。比如string类的[]、=、+=、+、操作符赋值，还有一些string类中诸如insert、replace、append等成员函数,包括类的析构时。
  修改数据才会触发Copy-On-Write，不修改当然就不会改啦。这就是托延战术的真谛，非到要做的时候才去做。
  
  Copy-On-Write的实现
  
  当两个 std::string 发生复制构造或者赋值时，不会复制字符串内容，而是增加一个引用计数，然后字符串指针进行浅拷贝，其执行效率为O(1)。只有当需要修改其中一个字符串内容时，才执行真正的复制。其实现的示意图，有下面两种形式：
  std::string 的数据成员就是：
```
class string {
private:
    Allocator _allocator;
    size_t size;
    size_t capacity;
    char * pointer;
};
```
  第二种形式为：
  std::string 的数据成员就只有一个了。
```
class string {
private:
    char * _pointer;
};
```
  为了实现的简单，在GNU4.8.4的中，采用的是实现2的形式。从上面的实现，我们看到引用计数并没有与 std::string 的数据成员放在一起，这是为什么呢？
  如果采用第二种方式，可以少一次开辟堆空间的操作，而申请堆空间的行为一定会涉及到系统调用。采用第二种方式可以提高效率。
  
  当执行复制构造或赋值时，引用计数加1， std::string 对象共享字符串内容；当 std::string 对象销毁时，并不直接释放字符串所在的空间，而是先将引用计数减1，直到引用计数为0时，则真正释放字符串内容所在的空间。根据这个思路，大家可以自己动手实现一下。大家再思考一下，既然涉及到了引用计数，那么在多线程环境下，涉及到修改引用计数的操作，是否是线程安全的呢？为了解决这个问题，GNU4.8.4的实现中，采用了原子操作。
  
  3、SSO（Short String Optimization）
  
  目前，在VC++、GNU5.x.x以上、Clang++上， std::string 实现均采用了SSO的实现。通常来说，一个程序里用到的字符串大部分都很短小，而在64位机器上，一个char*指针就占用了8个字节，所以SSO就出现了，其核心思想是：发生拷贝时要复制一个指针，对于小字符串来说，为啥不直接复制整个字符串呢，说不定还没有复制一个指针的代价大。其实现示意图如下：
  std::string 的数据成员就是：
```
class string {
    union Buffer {
        char * _pointer;
        char _local[16];
    };
    Buffer _buffer;
    size_t _size;
    size_t _capacity;
};
```
  当字符串的长度小于等于15个字节时，buffer直接存放整个字符串；当字符串大于15个字节时，buffer
  存放的就是一个指针，指向堆空间的区域。这样做的好处是，当字符串较小时，直接拷贝字符串，放在
  string内部，不用获取堆空间，开销小。
  
  4、最佳策略
  
  以上三种方式，都不能解决所有可能遇到的字符串的情况，各有所长，又各有缺陷。综合考虑所有情况
  之后，facebook开源的folly库中，实现了一个fbstring, 它根据字符串的不同长度使用不同的拷贝策略，最终每个fbstring对象占据的空间大小都是24字节。
  1. 很短的（0~22）字符串用SSO，23字节表示字符串（包括’\0’）,1字节表示长度；
  2. 中等长度的（23~255）字符串用eager copy，8字节字符串指针，8字节size，8字节capacity；
  3. 很长的(大于255)字符串用COW, 8字节指针（字符串和引用计数），8字节size，8字节capacity。
  5、线程安全性
  
  两个线程同时对同一个字符串进行操作的话, 是不可能线程安全的, 出于性能考虑, C++并没有为 string 实现线程安全, 毕竟不是所有程序都要用到多线程。但是两个线程同时对独立的两个 string 操作时, 必须是安全的。COW技术实现这一点是通过原子的对引用计数进行+1或-1操作。
  CPU的原子操作虽然比mutex锁好多了, 但是仍然会带来性能损失, 原因如下：
  - 阻止了CPU的乱性执行。
  - 两个CPU对同一个地址进行原子操作, 会导致cache失效, 从而重新从内存中读数据。
  - 系统通常会lock住比目标地址更大的一片区域，影响逻辑上不相关的地址访问。