首頁>技術>

C語言如何實現動態擴容的string

眾所周知，C++ 中的string使用比較方便，關於C++ 中的string原始碼實現可以看我的這篇文章：原始碼分析C++的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;}

輸出：

12345789123459123459123

完整程式碼如下：標頭檔案：

#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;}

8
最新評論

相關內容

  • ∧ BSA-TRITC(10mg/ml) TRITC-BSA 牛血清白蛋白改性標記羅丹明
  • ∨ SpringBoot過濾器禁止ip頻繁訪問