c - 如何在 C 中实现可变长度 ‘string’ -y

Question

我在谷歌上搜索了很多，但我找不到关于在高级语言中通常如何实现可变长度字符串的信息。我正在创建自己的此类语言，但不确定从哪里开始使用字符串。

我有一个结构描述 string键入，然后输入 create分配这样一个“字符串”的函数:

/* A safer `strcpy()`, using `strncpy()` and `sizeof()` */
#define STRCPY(TO, FROM) \
  strncpy(TO, FROM, sizeof(TO)); TO[sizeof(TO) - 1] = '\0'

struct string {
  // …
  char  native[1024];
};

string String__create(char native[]) {
  string this = malloc(sizeof(struct string));

  // …
  STRCPY(this->native, native);

  return this;
}

但是，这将只允许 1kb 长的字符串。这有点愚蠢，而且在大多数情况下会浪费大量内存。

鉴于我必须以某种方式声明要使用的内存……我该如何实现一个可以(有效)存储(有效)无限数量字符的字符串？

Answer 1

许多 C++ std::string实现现在使用“小字符串优化”。在伪代码中:

struct string {
    Int32 length
    union {
        char[12] shortString
        struct {
           char* longerString
           Int32 heapReservedSpace
        }
    }
}

这个想法是将最多 12 个字符的字符串存储在 shortString 中。大批。整个字符串将是连续的，并且只使用一个缓存行。更长的字符串存储在堆上。这使您在字符串对象中有 12 个空闲字节。指针不会占用所有这些，因此您还可以记住在堆上分配了多少内存 ( >=length )。这有助于支持以小增量增长字符串的场景。