3

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

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

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

是否可以使用大小正确的单个分配单独存储所有字符串？

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

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

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

4

5 回答 5

2

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

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

您可以将长度存储在固定宽度整数或可变宽度整数中，但关键是您可以跳到末尾并相对有效地扫描所有长度，并且从长度总和中您可以计算字符串的偏移量. 当没有剩余空间时，您知道何时到达最后一个字符串。

于 2014-03-12T11:38:06.553 回答
0

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

于 2014-03-12T11:37:55.127 回答
0

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

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

这里有一个完整的例子：

#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调用。一个用于指针数组，一个用于 sting 块。

于 2014-03-12T12:36:42.497 回答
0

求所有字符串的个数和总长度：

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 个字符串。

于 2014-03-12T11:53:43.267 回答
0

如果它是严格只读的，正如您所描述的，您可以将整个字符串列表及其偏移量存储在一个内存块中，并通过一次读取来读取整个内容。

第一个sizeof(long) bytes存储字符串的数量，n。接下来的nlong 将偏移量存储到从string buffer位置 (n+1)*sizeof(long) 开始的每个字符串中。您不必为每个字符串存储尾随零，但如果这样做，您可以使用 &str_buffer[offset[i]] 访问每个字符串。如果您不存储尾随的 '\0'，那么您将不得不复制到一个临时缓冲区并自己附加它。

于 2016-12-28T12:36:47.303 回答