如何在 C 中实现变长“字符串”-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）。这有助于支持以小增量增长字符串的场景。

Answer 2

常见的方法是有一个长度字段和一个指向动态分配的内存区域的指针来保存字符。

typedef struct string {
    size_t length;
    unsigned char *native;
} string_t;

string_t String__create(char native[]) {
    string_t this;
    this.length = strlen(native);
    this.native = malloc(this.length+1);
    if (this.native) {
        strncpy(this.native, native, this.length+1);
    } else {
        this.length = 0;
    }
    return this;
}

如果您想动态分配string_t：

string_t* String__create(char native[]) {
    string_t* this;
    if (this = malloc(sizeof(*this))) {
        this->length = strlen(native);
        this->native = malloc(this->length+1);
        if (this->native) {
            strncpy(this->native, native, this->length+1);
        } else {
            free(this);
            this=NULL;
        }
    }
    return this;
}
void String__delete(string_t** str) {
    free((*str)->native);
    free((*str));
    *str=NULL;
}

Answer 3

除了其他人告诉你的之外，我还包括“容量”的概念：
不可能知道内存中分配的向量的大小，您必须存储它。如果您执行 String 结构的 sizeof，它将返回 4 个字节 * 3 个数字字段 = 12 个字节（由于结构中使用的填充，可能会更大）。另外，你无法通过sizeof获取分配的内存的长度。

typedef struct _mystring {
        char * native;
        size_t size;
        size_t capacity;
} String;

这样，容量始终代表字符串所在块的实际大小。假设您的字符串变短了：您不必重新分配即可获得字符串的容量和大小之间的精确匹配。此外，您可以从头开始分配您期望字符串具有的字符，而不是初始字符串具有的字符。最后，您可以模仿 C++ 字符串 char 动态向量，并在每次字符串增长超出容量限制时将容量加倍。所有这些都会将内存操作保持在最低限度，这将转化为更好的性能（您也会浪费一些内存，但不会超过 1Kb）。

String String__create(char native[], size_t capacity) {
  String this;

  this.size = strlen( native );
  if ( capacity < ( this.size + 1 ) )
        this.capacity = this.size + 1;
  else  this.capacity = capacity;

  this.native = (char *) malloc( capacity * sizeof( char ) );
  strcpy( this.native, native );

  return this;
}

String * String__set(String *this, char native[]) {
    this->size = strlen( native );

    if ( this->size >= this->capacity ) {
        do {
            this->capacity <<= 1;
        } while( this->size > this->capacity );

        this->native = realloc( this->native, this->capacity );
    }

    strcpy( this->native, native );

    return this;
}

void String__delete(String *this)
{
    free( this->native );
}

Answer 4

realloc 会将您的内存重新定位到更大的缓冲区 - 只需使用此命令即可调整字符串的大小。对字符串使用以下结构：

struct mystring
{
    char * string;
    size_t size;
};

重要的部分是跟踪字符串的大小，并让每个字符串操作函数测试该大小是否有意义。

您可以预先分配一个大缓冲区并不断向其中添加内容，并且只有在该缓冲区已满时才重新分配 - 您必须为此实现所有功能。通过从一个不可变字符串移动到另一个（使用 realoc 语义）来改变字符串是更可取的（更不容易出错，也更安全）。

Answer 5

有些人喜欢使用“rope”数据结构来存储字符串无限长度，而不是连续的字符串（C 字符串）。

简化的绳索可以这样定义：

#include <stdio.h>

struct non_leaf_rope_node{
    char zero;
    union rope* left_substring;
    union rope* right_substring;
    // real rope implementations have a few more items here
};
#define rope_leaf_max ( sizeof( struct non_leaf_rope_node ) )

typedef union rope {
    char rope_data[ rope_leaf_max ];
    struct non_leaf_rope_node pointers;
} rope;

void print( union rope *node ){
    if( node->rope_data[0] != '\0' ){
        // short literal data
        fputs( node->rope_data, stdout );
    }else{
        // non-root node
        print( node->pointers.left_substring );
        print( node->pointers.right_substring );
    };
};
// other details involving malloc() and free() go here

int main(void){
    rope left = { "Hello," };
    rope right = { " World!" };
    rope root = {0,0,0};
    root.pointers.left_substring = &left;
    root.pointers.right_substring = &right;
    print( &root );

    return 0;
};

少于 rode_leaf_max 字符的绳索的存储方式与以 null 结尾的 C 字符串相同。
包含超过rope_leaf_max字符的绳索被存储为指向左子串和右子串的根non_leaf_rope_node，（它可能依次指向左子子串和右子子串），
最终指向叶子节点，
每个叶节点至少包含完整字符串的一个字符。

一根绳子总是至少存储一个字符，所以我们总是可以知道：
如果绳节点的第一个字节非零，则该节点是存储文字字符的叶节点。
如果绳节点的第一个字节为零，则该节点存储指向左子串和右子串的指针。
（真正的绳索实现通常具有第三种绳索节点）。

通常使用绳索比使用 C 字符串需要更少的总 RAM 空间。
（包含“纽约市”等短语的节点
可以在一根绳索中多次重复使用，或者在某些实现中在两根绳索之间共享）。
有时使用绳索比使用 C 弦更快。