字符串的几种实现方式

eager copy

image.png

COW

此种实现方式为写时复制，即 copy-on-write。只有在某个 string 要对共享对象进行修改时，才会真正执行拷贝。

v2-f44c0fb3420c70efad85d8092c44d601_720w.jpg

需要修改时，才会拷贝。

v2-8446993f54365100c3c86c1d256f5b47_720w.jpg

• 检验是否是COW

  #include <string>
  #include <iostream>
  using namespace std;
  
  int main()
  {
      string a = "hello";
      string b = a;
  
      cout << (a.data() == b.data()) << endl;
  
      b.append(1, 'A');
      cout << (a.data() == b.data()) << endl;
  }
  

• 线程安全
  想要实现COW，必须要有引用计数（reference count）：

  1. string初始化时rc=1
  2. 每当该string赋值给了其他sring，rc++。
  3. 当需要对string做修改时，如果rc>1，则重新申请空间并复制一份原字符串的拷贝，rc--，当rc减为0时，释放原内存。

  基于"共享"和”引用计数"的COW在多线程环境下必然面临线程安全的问题，COW为了保证线程安全而使用了原子操作，COW中"共享"的实现，反而影响了多线程环境下string拷贝的性能。

• 失效问题

  std::string a = "some string";
  std::string b = a;
  assert(b.data() == a.data());// We assume std::string is COW-ed
  
  std::cout << b[0] << std::endl;
  assert(b.data() != a.data()); // Oops!
  

  以“只读”的方式访问了 b 中一个字符，但 b 已经进行了一份私有的拷贝，a与b不再共享同一片内容。
  由于string的operator[]和at()会返回某个字符的引用，而判断程序是否更改了该字符实在是超出string本身能力范围的东西，为了保证COW实现的正确性，string只得统统认定operator[]和at()具有修改的“语义”。连begin()/end()也不能幸免，天晓得用户取得迭代器后会做什么！这些无奈的”write alarm“实际上是由于std::string本身接口的定义上没有对"只读"和"修改"语义做严格的区分。

短字符串优化

class sso_string
{
    char* start;
    size_t size;
    static const int kLocalSize = 15;
    union
    {
        char buffer[kLocalSize];
        size_t capacity;
    } data;
};

如果字符串长度比较短，那么直接存放在对象buffer里。

image.png

如果字符串超过15字节，那么就变成如下：

image.png

• 优点：
  短字符串时，无动态内存分配，cache更友好
• 缺点：
  对象本身占用空间大。

#include <string>
#include <new>
#include <cstdio>
#include <cstdlib>

int allocated = 0;

void *operator new(size_t sz)
{
    void *p = std::malloc(sz);
    allocated += sz;
    return p;
}

void operator delete(void *p) noexcept
{
    return std::free(p);
}

int main()
{
    allocated = 0;
    std::string s("length is 15   ");
    std::printf("length is 15 stack space = %d, heap space = %d, capacity = %d, size = %d\n",
                sizeof(s), allocated, s.capacity(), s.size());

    allocated = 0;

    std::string s2("length is 16    ");
    std::printf("length is 16 stack space = %d, heap space = %d, capacity = %d, size = %d\n",
                sizeof(s2), allocated, s2.capacity(), s2.size());
}

在我的环境：
gcc version 7.5.0 (Ubuntu 7.5.0-3ubuntu1~18.04)
测试，输出：

length is 15 stack space = 32, heap space = 0, capacity = 15, size = 15
length is 16 stack space = 32, heap space = 17, capacity = 16, size = 16

说明确实是采用了短字符串优化。

注意capacity不包括Null ternimator，所以在堆上实际分配的大小为 capacity + 1

C++11 之后字符串实现变更

C++11之后实现的就是实时拷贝，因为C++11标准规定：不允许[]导致之前的迭代器失效，这就使得COW的string不再符合C++规范了。

FBString

TODO