C 中的零拷贝就地字符串分割

假设你有一个字符串：

split_examples.cpp

char* s = "1,23,456,7890";

char* s = "1,23,456,7890";

你想在每个逗号处分割该字符串，以将其部分作为 C 字符串获取（部分数量可变）：

boost_split_example.cpp

char* s1 = "1";
char* s2 = "23";
char* s3 = "456";
char* s4 = "7890";

char* s1 = "1";
char* s2 = "23";
char* s3 = "456";
char* s4 = "7890";

Boost

One simple strategy is to use boost::algorithm::split like\u0000this:

boost_split_snippet.cpp

std::vector<std::string> strs;
boost::split(strs, s, boost::is_any_of(","));

std::vector<std::string> strs;
boost::split(strs, s, boost::is_any_of(","));

完整示例

虽然简单，但此方法有严重缺点。它不仅在 C++ 中可用，还由于引入了 boost 库的很大一部分而显著增加编译时间和二进制大小，尽管 boost::algorithm 是纯头文件库。

但更重要的是，特别是对于嵌入式和工业系统，它创建了大量中间对象：字符串每个部分的多个副本加上 std::string 元数据，std::vector<std::string>。虽然有时由于各种原因这是可接受的甚至是期望的，但在 CPU 和内存使用方面非常低效。

此外，即使交换前两个参数这样的简单错误：boost::split(s, strs, boost::is_any_of(",")) 也会产生可怕的错误消息列表，即使对经验丰富的开发者来说也难以理解。

就地策略

让我们看看更高效的策略。注意上面的 s 类型是 char*（而不是 const char*）。

这意味着我们可以修改字符串的内容，例如提高算法的效率。在许多情况下，我们不需要复制字符串（或其部分）来处理它。

使用此策略的算法称为就地算法。请注意，使用此类算法时，字符串很可能由于大量修改而被破坏，因此可能无法用于其他算法。过去未能正确使用就地算法多次导致安全问题和错误。

零拷贝算法

在查看高效的分割算法之前，我们必须查看算法的另一个有利属性

记住当我们定义

pointer_example.c

char* s3 = "456";

char* s3 = "456";

这里，s3 指向字符串 "456" — 然而，此 "456" 与原始字符串中的 456 不相同：

count_delimiters.cpp

//              |||
char* s = "1,23,456,7890";

//              |||
char* s = "1,23,456,7890";

虽然两者包含相同的三个字符，"456" 在内存中存储多次 — 因此浪费内存。

虽然 3 字节的浪费内存不多，但许多实际用例由于同一字符串被多次存储而导致数百千字节到千兆字节的浪费空间。这在内存稀缺的嵌入式应用中更为严重。

零拷贝算法通过避免复制内存（除非绝对必要）来避免此效率问题。由于它们通常比经典对应物更复杂，它们主要用于效率和延迟重要的应用，如网络协议栈和科学软件。

零拷贝就地字符串分割

这是基本想法：我们的前提是 C 字符串由 NUL 字符分隔（即它们在第一个 NUL 字符处结束）。

我们可以通过使用指针算术将 s3 指向 s 内的 "456" 实例来创建零拷贝算法。

split_result_example.c

char* s3 = s + 5;

char* s3 = s + 5;

然而，当我们打印 s3 时：

split_zero_copy_impl.c

printf("%s", s3)

printf("%s", s3)

我们得到 456,7890 而不是 456。这是因为 s + 5 之后的第一个 NUL 字符不在 456 的末尾，而在 s 的末尾。

We can solve this issue by using an in-place algorithm to replace every occurrence of our delimiter (,) by a NUL character, resulting in sbeing equivalent\u0000to

split_example_escaped.cpp

char* s = "1\023\0456\07890";

char* s = "1\023\0456\07890";

像之前一样定义 s3：

split_pointer_example.c

char* s3 = s + 5;

char* s3 = s + 5;

我们可以看到 s + 5 之后的第一个 NUL 字符正好在 "456" 的末尾。

但我们也说部分数量是可变的 - 那么我们如何用 C 数据类型（即 C++ std::vector 的粗略等价物）表示分割操作的结果。

std::vector 实例通过简单地重新分配更大的内存数组来调整大小 — 这非常方便，但由于超出本文范围的原因，它也效率低下。

编写高效 C 时，我们不能这样方便地做到。我们的结果类型是 char**：它包含 char* 列表，每个指向原始字符串的一部分。该列表中的元素数量存储在单独的变量中。

但为了分配正确大小的 char**，我们首先需要计算分隔符的数量

count_delimiters.cpp

int numDelimiters = 0;
char* pos = s;
while(*pos++ != '\0') { //Until the end of the string
    if(*pos == ',') {
        numDelimiters++;
    }
}

int numDelimiters = 0;
char* pos = s;
while(*pos++ != '\0') { //Until the end of the string
    if(*pos == ',') {
        numDelimiters++;
    }
}

使用此信息，我们确切知道需要多少元素 — 因此我们可以分配数组

allocate_split_result.c

char** splitResult = (char**)malloc((numDelimiters + 1) * sizeof(char*));

char** splitResult = (char**)malloc((numDelimiters + 1) * sizeof(char*));

由于算法的零拷贝性质，这是我们需要的唯一内存（除了 s）！

注意 C 没有自动堆管理，因此你需要在完成后调用 free(splitResult)。

现在我们可以实现最后（也是最困难的）部分：将分隔符替换为 NUL 字符并为每个点找到正确的起始索引 — 一次性完成。

一个重要的子任务是在 s 或其后缀中查找分隔符字符的出现。幸运的是，有一个标准 C 库函数用于此目的：strchr。

split_loop.c

//第一个子字符串从 s 的开头开始
splitResult[0] = s;
//查找其他子字符串
int i = 1;
char* hit = s;
while((hit = strchr(hit, ',')) != NULL) { //查找下一个分隔符
    //就地替换分隔符
    *hit++ = '\0';
    //下一个子字符串从命中之后开始
    splitResult[i++] = hit;
}

//第一个子字符串从 s 的开头开始
splitResult[0] = s;
//查找其他子字符串
int i = 1;
char* hit = s;
while((hit = strchr(hit, ',')) != NULL) { //查找下一个分隔符
    //就地替换分隔符
    *hit++ = '\0';
    //下一个子字符串从命中之后开始
    splitResult[i++] = hit;
}

现在我们可以将所有代码放入几个函数中：

split_functions.c

/**
 * 计算 c 在 s 中出现的次数
 */
int countChar(const char* s, char c) {
    int n = 0;
    while(*s++ != '\0') { //Until the end of the string
        if(*s == c) {
            n++;
        }
    }
    return n;
}

/**
 * 使用零拷贝就地算法在分隔符处分割字符串
 * @param s 要分割的字符串（每个分隔符将被 NUL 替换）
 * @param delimiter 要在处分割的分隔符字符
 * @param size 返回数组的大小 w
 * @return char* 列表（大小存储在 *size 中），按顺序指向所有分割结果
 */
char** splitZeroCopyInPlace(char* s, char delimiter, int* size) {
    int numDelimiters = countChar(s, delimiter);
    //分配内存
    char** splitResult = (char**)malloc((numDelimiters + 1) * sizeof(char*));

    //第一个子字符串从 s 的开头开始
    splitResult[0] = s;
    //查找其他子字符串
    int i = 1;
    char* hit = s;
    while((hit = strchr(hit, ',')) != NULL) { //查找下一个分隔符
        //就地替换分隔符
        *hit++ = '\0';
        //下一个子字符串从命中之后开始
        splitResult[i++] = hit;
    }
    *size = numDelimiters + 1;
    return splitResult;
}

/**
 * 计算 c 在 s 中出现的次数
 */
int countChar(const char* s, char c) {
    int n = 0;
    while(*s++ != '\0') { //Until the end of the string
        if(*s == c) {
            n++;
        }
    }
    return n;
}

/**
 * 使用零拷贝就地算法在分隔符处分割字符串
 * @param s 要分割的字符串（每个分隔符将被 NUL 替换）
 * @param delimiter 要在处分割的分隔符字符
 * @param size 返回数组的大小 w
 * @return char* 列表（大小存储在 *size 中），按顺序指向所有分割结果
 */
char** splitZeroCopyInPlace(char* s, char delimiter, int* size) {
    int numDelimiters = countChar(s, delimiter);
    //分配内存
    char** splitResult = (char**)malloc((numDelimiters + 1) * sizeof(char*));

    //第一个子字符串从 s 的开头开始
    splitResult[0] = s;
    //查找其他子字符串
    int i = 1;
    char* hit = s;
    while((hit = strchr(hit, ',')) != NULL) { //查找下一个分隔符
        //就地替换分隔符
        *hit++ = '\0';
        //下一个子字符串从命中之后开始
        splitResult[i++] = hit;
    }
    *size = numDelimiters + 1;
    return splitResult;
}

请参见完整示例获取用法说明。

strtok() 怎么样

实际上有一个标准 C 库函数与我们的算法非常相似：strtok()。它也使用就地方法（原始字符串被修改）。

一个显著的区别是 strtok() 支持在多个分隔符字符处分割，例如 , 和 ;。根据实现，这可能比我们上面手工制作的算法稍慢。

然而，strtok() 并非没有风险：它不是线程安全的。有一个仅 POSIX（相对于 C 标准）版本叫做 strtok_r()，它将状态存储在用户提供的指针中。

还有一个注意事项。引用 manpage：

strtok_behavior.txt

解析字符串中两个或更多连续分隔符字节的序列被视为单个分隔符。

解析字符串中两个或更多连续分隔符字节的序列被视为单个分隔符。

此属性称为标记压缩。通常，这是期望的 - 但在许多实际用例中，它对某些边缘情况是巨大问题，一旦部署可能难以检测。

考虑以下 CSV 字符串（上面算法的结果在注释中）：

strtok_examples.c

const char* a = "1,,2,3,4"; // ["1","","2","3","4"]
const char* b = "1,2,,3,4"; // ["1","2","","3","4"]

const char* a = "1,,2,3,4"; // ["1","","2","3","4"]
const char* b = "1,2,,3,4"; // ["1","2","","3","4"]

使用 strtok()（和 strtok_r()），a 和 b 产生完全相同的结果：

strtok_result.c

["1","2","","3","4"]

["1","2","","3","4"]

此外，字符串开头和结尾的分隔符被忽略。这可能是问题的一个示例：

strtok_edge_cases.c

const char* a = ",1,2,3,4"; // ["","1","2","3","4"]
const char* b = "1,2,3,4,"; // ["1","2","3","4",""]

const char* a = ",1,2,3,4"; // ["","1","2","3","4"]
const char* b = "1,2,3,4,"; // ["1","2","3","4",""]

使用 strtok() 的两个变体的结果是

strtok_edge_result.c

["1","2","3","4"]

["1","2","3","4"]

总之，strtok() 有用例 — 对于某些用例我们的算法不适合 — 但并非没有用户需要了解的主要注意事项。

Check out similar posts by category: C/C++

If this post helped you, please consider buying me a coffee or donating via PayPal to support research & publishing of new posts on TechOverflow

Buy me a coffee