如何在C中实现可变长度的’string’-y
我已经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长的字符串。 这有点愚蠢,在大多数情况下会浪费大量内存。
鉴于我必须以某种方式声明要使用的内存…我如何实现一个能够(有效地)存储(有效)无限数量的字符的字符串?
许多C ++ std::string
实现现在使用“小字符串优化”。 在伪代码中:
struct string { Int32 length union { char[12] shortString struct { char* longerString Int32 heapReservedSpace } } }
我们的想法是在shortString
数组中存储最多12个字符的字符串。 整个字符串将是连续的,并且只使用一个缓存行。 较长的字符串存储在堆上。 这会在字符串对象中留下12个备用字节。 指针不会占用所有这些,因此您还可以记住您在堆上分配了多少内存( >=length
)。 这有助于支持以小增量增长字符串的场景。
常见的方法是有一个长度字段和一个指向动态分配的内存区域的指针来保存字符。
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; }
除了别人告诉你的内容之外,我还要包括“容量”的概念:不可能知道内存中分配的矢量的大小,你必须存储它。 如果你执行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 ); }
realloc会将你的内存重新定位到更大的缓冲区 – 只需使用此命令就可以调整字符串的大小。 对字符串使用以下结构:
struct mystring { char * string; size_t size; };
重要的部分是跟踪字符串的大小,并让每个字符串操作函数测试大小是否有意义。
您可以预先分配一个大缓冲区并继续添加它,并且只在所述缓冲区已满时重新分配 – 您必须为此实现所有function。 通过从一个immutable string
移动到另一个immutable string
(使用realoc的语义)来改变字符串是优选的(更不容易出错且更安全)。
有些人喜欢使用“rope”数据结构来存储无限长度的字符串,而不是连续的字符串(C string)。
简化的绳索可以定义为:
#include 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; };
绳索少于rope_leaf_max的绳索与以null结尾的C字符串相同。 包含多个rope_leaf_max字符的绳索存储为指向左右子字符串的根non_leaf_rope_node(其可以指向左和右子子字符串),最终指向叶节点和叶节点每个包含完整字符串的至少一个字符。
一根绳子总是存储至少一个字符,所以我们总是可以告诉:如果一个绳索节点的第一个字节非零,那么该节点就是一个存储文字字符的叶子节点。 如果rope节点的第一个字节为零,则该节点存储指向左右子字符串的指针。 (真正的绳索实施通常具有第三种绳索节点)。
通常使用绳索比使用C字符串需要更少的总RAM空间。 (包含诸如“纽约市”之类的短语的节点可以在一根绳索中多次重复使用,或者在两条绳索之间共享的一些实现中重复使用)。 有时使用绳索比使用C字符串更快。