C語言如何實現動態擴容的String
作者： 程序喵大人
最近工作中使用C語言，但又苦于沒有高效的字符串實現，字符串的拼接和裁剪都比較麻煩，而且每個字符串都需要申請內存，內存的申請和釋放也很容易出bug，怎么高效的實現一個不需要處理內存問題并且可以動態擴容進行拼接和裁剪的string呢?
本文轉載自微信公眾號「程序喵大人」，作者程序喵大人 。轉載本文請聯系程序喵大人公眾號。
最近工作中使用C語言，但又苦于沒有高效的字符串實現，字符串的拼接和裁剪都比較麻煩，而且每個字符串都需要申請內存，內存的申請和釋放也很容易出bug，怎么高效的實現一個不需要處理內存問題并且可以動態擴容進行拼接和裁剪的string呢?
- 一個好的string應該有以下功能?
- 創建字符串
- 刪除字符串
- 尾部追加字符串
- 頭部插入字符串
- 從尾部刪除N個字符
- 從頭部刪除N個字符
- 裁剪字符串
- 獲取字符串長度
- 獲取完整字符串
下面來看看各個功能的實現：
首先定義一個string的句柄，相當于C++中的實例
- struct c_string;
- typedef struct c_string c_string_t;
在內部string的實現如下：
- // string的初始內存大小
- static const size_t c_string_min_size = 32;
- struct c_string {
- char *str; // 字符串指針
- size_t alloced; // 已分配的內存大小
- size_t len; // 字符串的實際長度
- };
創建字符串：
- c_string_t *c_string_create(void) {
- c_string_t *cs;
- cs = calloc(1, sizeof(*cs));
- cs->str = malloc(c_string_min_size);
- *cs->str = '\0';
- // 初始分配內存大小是32，之后每次以2倍大小擴容
- cs->alloced = c_string_min_size;
- cs->len = 0;
- return cs;
- }
銷毀字符串：
- void c_string_destroy(c_string_t *cs) {
- if (cs == NULL) return;
- free(cs->str);
- free(cs);
- }
內部如何擴容呢：
- static void c_string_ensure_space(c_string_t *cs, size_t add_len) {
- if (cs == NULL || add_len == 0) return;
- if (cs->alloced >= cs->len + add_len + 1) return;
- while (cs->alloced < cs->len + add_len + 1) {
- cs->alloced <<= 1; // 每次以2倍大小擴容
- if (cs->alloced == 0) {
- // 左移到最后可能會變為0，由于alloced是無符號型，減一則會變成UINT_MAX
- cs->alloced--;
- }
- }
- cs->str = realloc(cs->str, cs->alloced);
- }
在尾部追加字符串：
- void c_string_append_str(c_string_t *cs, const char *str, size_t len) {
- if (cs == NULL || str == NULL || *str == '\0') return;
- if (len == 0) len = strlen(str);
- c_string_ensure_space(cs, len); // 確保內部有足夠的空間存儲字符串
- memmove(cs->str + cs->len, str, len);
- cs->len += len;
- cs->str[cs->len] = '\0';
- }
在尾部追加字符：
- void c_string_append_char(c_string_t *cs, char c) {
- if (cs == NULL) return;
- c_string_ensure_space(cs, 1);
- cs->str[cs->len] = c;
- cs->len++;
- cs->str[cs->len] = '\0';
- }
在尾部追加整數：
- void c_string_append_int(c_string_t *cs, int val) {
- char str[12];
- if (cs == NULL) return;
- snprintf(str, sizeof(str), "%d", val); // 整數轉為字符串
- c_string_append_str(cs, str, 0);
- }
在頭部插入字符串：
- void c_string_front_str(c_string_t *cs, const char *str, size_t len) {
- if (cs == NULL || str == NULL || *str == '\0') return;
- if (len == 0) len = strlen(str);
- c_string_ensure_space(cs, len);
- memmove(cs->str + len, cs->str, cs->len);
- memmove(cs->str, str, len);
- cs->len += len;
- cs->str[cs->len] = '\0';
- }
在頭部插入字符：
- void c_string_front_char(c_string_t *cs, char c) {
- if (cs == NULL) return;
- c_string_ensure_space(cs, 1);
- memmove(cs->str + 1, cs->str, cs->len);
- cs->str[0] = c;
- cs->len++;
- cs->str[cs->len] = '\0';
- }
在頭部插入整數：
- void c_string_front_int(c_string_t *cs, int val) {
- char str[12];
- if (cs == NULL) return;
- snprintf(str, sizeof(str), "%d", val);
- c_string_front_str(cs, str, 0);
- }
清空字符串：
- void c_string_clear(c_string_t *cs) {
- if (cs == NULL) return;
- c_string_truncate(cs, 0);
- }
裁剪字符串：
- void c_string_truncate(c_string_t *cs, size_t len) {
- if (cs == NULL || len >= cs->len) return;
- cs->len = len;
- cs->str[cs->len] = '\0';
- }
刪除頭部的N個字符：
- void c_string_drop_begin(c_string_t *cs, size_t len) {
- if (cs == NULL || len == 0) return;
- if (len >= cs->len) {
- c_string_clear(cs);
- return;
- }
- cs->len -= len;
- memmove(cs->str, cs->str + len, cs->len + 1);
- }
刪除尾部的N個字符：
- void c_string_drop_end(c_string_t *cs, size_t len) {
- if (cs == NULL || len == 0) return;
- if (len >= cs->len) {
- c_string_clear(cs);
- return;
- }
- cs->len -= len;
- cs->str[cs->len] = '\0';
- }
獲取字符串的長度：
- size_t c_string_len(const c_string_t *cs) {
- if (cs == NULL) return 0;
- return cs->len;
- }
返回字符串指針，使用的是內部的內存：
- const char *c_string_peek(const c_string_t *cs) {
- if (cs == NULL) return NULL;
- return cs->str;
- }
重新分配一塊內存存儲字符串返回：
- char *c_string_dump(const c_string_t *cs, size_t *len) {
- char *out;
- if (cs == NULL) return NULL;
- if (len != NULL) *len = cs->len;
- out = malloc(cs->len + 1);
- memcpy(out, cs->str, cs->len + 1);
- return out;
- }
測試代碼如下：
- int main() {
- c_string_t *cs = c_string_create();
- c_string_append_str(cs, "123", 0);
- c_string_append_char(cs, '4');
- c_string_append_int(cs, 5);
- printf("%s \n", c_string_peek(cs));
- c_string_front_str(cs, "789", 0);
- printf("%s \n", c_string_peek(cs));
- c_string_drop_begin(cs, 2);
- printf("%s \n", c_string_peek(cs));
- c_string_drop_end(cs, 2);
- printf("%s \n", c_string_peek(cs));
- c_string_destroy(cs);
- return 0;
- }
輸出：
- 12345
- 78912345
- 912345
- 9123
完整代碼如下：頭文件：
- #include <stddef.h>
- struct c_string;
- typedef struct c_string c_string_t;
- c_string_t *c_string_create(void);
- void c_string_destroy(c_string_t *cs);
- void c_string_append_str(c_string_t *cs, const char *str, size_t len);
- void c_string_append_char(c_string_t *cs, char c);
- void c_string_append_int(c_string_t *cs, int val);
- void c_string_front_str(c_string_t *cs, const char *str, size_t len);
- void c_string_front_char(c_string_t *cs, char c);
- void c_string_front_int(c_string_t *cs, int val);
- void c_string_clear(c_string_t *cs);
- void c_string_truncate(c_string_t *cs, size_t len);
- void c_string_drop_begin(c_string_t *cs, size_t len);
- void c_string_drop_end(c_string_t *cs, size_t len);
- size_t c_string_len(const c_string_t *cs);
- const char *c_string_peek(const c_string_t *cs);
- char *c_string_dump(const c_string_t *cs, size_t *len);
源文件：
- #include <ctype.h>
- #include <stdbool.h>
- #include <stdlib.h>
- #include <stdio.h>
- #include <string.h>
- static const size_t c_string_min_size = 32;
- struct c_string {
- char *str;
- size_t alloced;
- size_t len;
- };
- c_string_t *c_string_create(void) {
- c_string_t *cs;
- cs = calloc(1, sizeof(*cs));
- cs->str = malloc(c_string_min_size);
- *cs->str = '\0';
- cs->alloced = c_string_min_size;
- cs->len = 0;
- return cs;
- }
- void c_string_destroy(c_string_t *cs) {
- if (cs == NULL) return;
- free(cs->str);
- free(cs);
- }
- static void c_string_ensure_space(c_string_t *cs, size_t add_len) {
- if (cs == NULL || add_len == 0) return;
- if (cs->alloced >= cs->len + add_len + 1) return;
- while (cs->alloced < cs->len + add_len + 1) {
- cs->alloced <<= 1;
- if (cs->alloced == 0) {
- cs->alloced--;
- }
- }
- cs->str = realloc(cs->str, cs->alloced);
- }
- void c_string_append_str(c_string_t *cs, const char *str, size_t len) {
- if (cs == NULL || str == NULL || *str == '\0') return;
- if (len == 0) len = strlen(str);
- c_string_ensure_space(cs, len);
- memmove(cs->str + cs->len, str, len);
- cs->len += len;
- cs->str[cs->len] = '\0';
- }
- void c_string_append_char(c_string_t *cs, char c) {
- if (cs == NULL) return;
- c_string_ensure_space(cs, 1);
- cs->str[cs->len] = c;
- cs->len++;
- cs->str[cs->len] = '\0';
- }
- void c_string_append_int(c_string_t *cs, int val) {
- char str[12];
- if (cs == NULL) return;
- snprintf(str, sizeof(str), "%d", val);
- c_string_append_str(cs, str, 0);
- }
- void c_string_front_str(c_string_t *cs, const char *str, size_t len) {
- if (cs == NULL || str == NULL || *str == '\0') return;
- if (len == 0) len = strlen(str);
- c_string_ensure_space(cs, len);
- memmove(cs->str + len, cs->str, cs->len);
- memmove(cs->str, str, len);
- cs->len += len;
- cs->str[cs->len] = '\0';
- }
- void c_string_front_char(c_string_t *cs, char c) {
- if (cs == NULL) return;
- c_string_ensure_space(cs, 1);
- memmove(cs->str + 1, cs->str, cs->len);
- cs->str[0] = c;
- cs->len++;
- cs->str[cs->len] = '\0';
- }
- void c_string_front_int(c_string_t *cs, int val) {
- char str[12];
- if (cs == NULL) return;
- snprintf(str, sizeof(str), "%d", val);
- c_string_front_str(cs, str, 0);
- }
- void c_string_clear(c_string_t *cs) {
- if (cs == NULL) return;
- c_string_truncate(cs, 0);
- }
- void c_string_truncate(c_string_t *cs, size_t len) {
- if (cs == NULL || len >= cs->len) return;
- cs->len = len;
- cs->str[cs->len] = '\0';
- }
- void c_string_drop_begin(c_string_t *cs, size_t len) {
- if (cs == NULL || len == 0) return;
- if (len >= cs->len) {
- c_string_clear(cs);
- return;
- }
- cs->len -= len;
- /* +1 to move the NULL. */
- memmove(cs->str, cs->str + len, cs->len + 1);
- }
- void c_string_drop_end(c_string_t *cs, size_t len) {
- if (cs == NULL || len == 0) return;
- if (len >= cs->len) {
- c_string_clear(cs);
- return;
- }
- cs->len -= len;
- cs->str[cs->len] = '\0';
- }
- size_t c_string_len(const c_string_t *cs) {
- if (cs == NULL) return 0;
- return cs->len;
- }
- const char *c_string_peek(const c_string_t *cs) {
- if (cs == NULL) return NULL;
- return cs->str;
- }
- char *c_string_dump(const c_string_t *cs, size_t *len) {
- char *out;
- if (cs == NULL) return NULL;
- if (len != NULL) *len = cs->len;
- out = malloc(cs->len + 1);
- memcpy(out, cs->str, cs->len + 1);
- return out;
- }
責任編輯：武曉燕
來源：
程序喵大人
