在C语言中读取和存储字符串列表的最节省内存的方法是什么？

Question

我想知道在C语言中读取和存储字符串列表的最节省内存的方法。

每个字符串的长度可能不同，因此预先分配一个大的二维数组将是浪费的。我也想避免为每个字符串单独进行malloc，因为可能有很多字符串。

这些字符串将从一个大缓冲区中读入到我所询问的列表数据结构中。

能否以恰好正确的大小进行单次分配来分别存储所有字符串？

我的一个想法是将它们连续地存储在缓冲区中，然后有一个char *数组指向缓冲区中的不同部分，其中将有'\0'来定界。但我希望还有更好的方法。

struct list {
  char *index[32];
  char buf[];
};

数据结构和字符串将严格只读。

- cloudhead

---

@amdixon 不想为每个字符串使用 malloc。 - RedX

@amdixon 是的，问题在于我希望能够尽可能使用一个单独的free()函数来释放整个内容。 - cloudhead

如果您从未打算更改任何字符串的长度，那么您的想法非常优雅。 - Bathsheba

解决方案在很大程度上取决于存储的字符串列表是否是静态且只读的，或者您是否希望能够添加/删除/更新字符串。因此，在创建字符串列表之后，应该提供哪些操作？ - Flovdis

@Flovdi 它们是只读的。 - cloudhead

Answer 1

假设您事先知道所有字符串的长度，这是一种稍微有效的格式：

|| total size |  string 1 | string 2 | ........ | string N | len(string N) | ... | len(string 2) | len(string 1) ||

你可以将长度存储在定宽整数或变宽整数中，但要点是你可以跳到末尾并相对高效地扫描所有 长度，而从长度总和可以计算字符串的偏移量。当没有剩余空间时，你就知道已经到达了最后一个字符串。

- Kerrek SB

---

有趣，但这在C中怎么样？我仍然希望能够使用工作的char *来处理字符串，而不是完全不透明的缓冲区。 - cloudhead

你可以存储连续的以NUL分隔的字符串，这样你就可以将偏移量（buffer[offset]）传递给期望char*类型参数的函数。 - Aktau

@cloudhead：正如Aktau所说，是否包含空终止符取决于您。这当然是一个选项。而计算第k个字符串的偏移量是很便宜的。 - Kerrek SB

Answer 2

找出所有字符串的数量和总长度：

int num = 0;
int len = 0;
char* string = GetNextString(input);
while (string)
{
    num += 1;
    len += strlen(string);
    string = GetNextString(input);
}
Rewind(input);

然后，分配以下两个缓冲区：

int*  indexes = malloc(num*sizeof(int));
char* strings = malloc((num+len)*sizeof(char));

最后，填充这两个缓冲区：

int index = 0;
for (int i=0; i<num; i++)
{
    indexes[i] = index;
    string = GetNextString(input);
    strcpy(strings+index,string);
    index += strlen(string)+1;
}

然后，您可以简单地使用 strings[indexes[i]] 来访问第i个字符串。

- barak manos

Answer 3

最高效和内存高效的方法是两次遍历解决方案。在第一次遍历中，您计算所有字符串的总大小，然后分配总内存块。在第二次遍历中，您使用大缓冲区读取所有字符串。

您可以为字符串创建一个指针数组，并计算指针之间的差异以获取字符串的大小。这样，您就可以节省空字节作为结束标记。

以下是一个完整的示例：

#include <stdio.h>
#include <memory.h>
#include <stdlib.h>

struct StringMap
{
    char *data;
    char **ptr;
    long cPos;
};


void initStringMap(StringMap *stringMap, long numberOfStrings, long totalCharacters)
{
    stringMap->data = (char*)malloc(sizeof(char)*(totalCharacters+1));
    stringMap->ptr = (char**)malloc(sizeof(char*)*(numberOfStrings+2));
    memset(stringMap->ptr, 0, sizeof(char*)*(numberOfStrings+1));
    stringMap->ptr[0] = stringMap->data;
    stringMap->ptr[1] = stringMap->data;
    stringMap->cPos = 0;
}


void extendString(StringMap *stringMap, char *str, size_t size)
{
    memcpy(stringMap->ptr[stringMap->cPos+1], str, size);
    stringMap->ptr[stringMap->cPos+1] += size;
}


void endString(StringMap *stringMap)
{
    stringMap->cPos++;
    stringMap->ptr[stringMap->cPos+1] = stringMap->ptr[stringMap->cPos];
}


long numberOfStringsInStringMap(StringMap *stringMap)
{
    return stringMap->cPos;
}


size_t stringSizeInStringMap(StringMap *stringMap, long index)
{
    return stringMap->ptr[index+1] - stringMap->ptr[index];
}


char* stringinStringMap(StringMap *stringMap, long index)
{
    return stringMap->ptr[index];
}


void freeStringMap(StringMap *stringMap)
{
    free(stringMap->data);
    free(stringMap->ptr);
}


int main()
{
    // The interesting values
    long numberOfStrings = 0;
    long totalCharacters = 0;

    // Scan the input for required information
    FILE *fd = fopen("/path/to/large/textfile.txt", "r");
    int bufferSize = 4096;
    char *readBuffer = (char*)malloc(sizeof(char)*bufferSize);
    int currentStringLength = 0;
    ssize_t readBytes;
    while ((readBytes = fread(readBuffer, sizeof(char), bufferSize, fd))>0) {
        for (int i = 0; i < readBytes; ++i) {
            const char c = readBuffer[i];
            if (c != '\n') {
                ++currentStringLength;
            } else {
                ++numberOfStrings;
                totalCharacters += currentStringLength;
                currentStringLength = 0;
            }
        }
    }

    // Display the found results
    printf("Found %ld strings with total of %ld bytes\n", numberOfStrings, totalCharacters);

    // Allocate the memory for the resource
    StringMap stringMap;
    initStringMap(&stringMap, numberOfStrings, totalCharacters);

    // read all strings
    rewind(fd);
    while ((readBytes = fread(readBuffer, sizeof(char), bufferSize, fd))>0) {
        char *stringStart = readBuffer;
        for (int i = 0; i < readBytes; ++i) {
            const char c = readBuffer[i];
            if (c == '\n') {
                extendString(&stringMap, stringStart, &readBuffer[i]-stringStart);
                endString(&stringMap);
                stringStart = &readBuffer[i+1];
            }
        }
        if (stringStart < &readBuffer[readBytes]) {
            extendString(&stringMap, stringStart, &readBuffer[readBytes]-stringStart);
        }
    }
    endString(&stringMap);
    fclose(fd);

    // Ok read the list
    numberOfStrings = numberOfStringsInStringMap(&stringMap);
    printf("Number of strings in map: %ld\n", numberOfStrings);
    for (long i = 0; i < numberOfStrings; ++i) {
        size_t stringSize = stringSizeInStringMap(&stringMap, i);
        char *buffer = (char*)malloc(stringSize+1);
        memcpy(buffer, stringinStringMap(&stringMap, i), stringSize);
        buffer[stringSize-1] = '\0';
        printf("string %05ld size=%8ld : %s\n", i, stringSize, buffer);
        free(buffer);
    }

    // free the resource
    freeStringMap(&stringMap);
}

这个例子读取一个非常大的文本文件，将其分割成行，并创建一个每行一个字符串的数组。它只需要两个malloc调用。一个是指针数组，另一个是字符串块。

- Flovdis

Answer 4

如果像你所描述的那样严格为只读，你可以将整个字符串列表及其偏移量存储在单个内存块中，并使用单个读取操作读取整个内容。

前sizeof(long)字节存储了字符串的数量n。接下来的n个长整型数值存储了每个字符串相对于字符串缓冲区开头的偏移量，该缓冲区从位置(n+1)*sizeof(long)开始。您不必为每个字符串存储尾随零，但如果这样做，您可以使用&str_buffer[offset[i]]访问每个字符串。如果您不存储尾随'\0'，则必须将其复制到临时缓冲区并自行添加。

- Thomas Jay Rush

Answer 5

您可以创建单个缓冲区并将它们连续存储，使用realloc()根据需要扩展缓冲区。但是，您需要第二个数组来存储字符串位置，可能也需要使用realloc()进行扩展，因此我可能会简单地创建一个动态分配的数组，并单独使用malloc()为每个字符串分配内存。

- Mauren