如何在C中实现一个可变长度的'string'-y

Question

我已经google了很多,但我找不到有关如何在高级语言中实现可变长度字符串的信息.我正在创建自己的语言,并且不确定从字符串开始的位置.

我有一个描述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
        }
    }
}

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