Каков наиболее эффективный способ добавления строки C, используя как можно меньше памяти?
Я пытаюсь восстановить путь к файлу в большом дереве каталогов.
Вот идея того, что я делал раньше:
char temp[LENGTH], file[LENGTH];
file = some_file_name;
while (some_condition) {
parent_dir = some_calculation_that_yields_name_of_parent_dir;
sprintf(temp, "%s/%s", parent_dir, file);
strcpy(file, temp);
}
Это кажется немного неуклюжим.
Любая помощь будет оценена по достоинству. Спасибо!
Копирование вряд ли можно избежать, если вы захотите его в одном и том же фрагменте памяти. Если выделенный фрагмент достаточно велик, вы можете использовать memmove, чтобы сдвинуть исходную строку на длину того, что вы хотите добавить, а затем скопировать ее в начало, но я сомневаюсь, что это менее "неуклюжий". Тем не менее, это избавит вас от лишней памяти (опять же, если у оригинального куска достаточно свободного места для них обоих).
Что-то вроде этого:
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>
/* Prepends t into s. Assumes s has enough space allocated
** for the combined string.
*/
void prepend(char* s, const char* t)
{
size_t len = strlen(t);
size_t i;
memmove(s + len, s, strlen(s) + 1);
for (i = 0; i < len; ++i)
{
s[i] = t[i];
}
}
int main()
{
char* s = malloc(100);
strcpy(s, "file");
prepend(s, "dir/");
printf("%s\n", s);
return 0;
}
Если вам не нужна строка, которая будет храниться по порядку, но только выглядит в порядке, тогда используйте вещь, называемую "веревка". (Это сделано из множества "строк", см..)
Я считаю, что это в основном вектор (в терминах C, массив) struct { char *begin; char *end };
В С++ он реализует все функции std::string. В C вам нужно будет написать (или получить библиотеку) функции замены для всех функций strxxx().
Что "веревка" сделала бы, чтобы добавить строку к другой строке, просто вставьте новую начальную, конечную пару, указывающую на новую часть строки. Также может потребоваться скопировать новый фрагмент строки, если это временный указатель. Или он может просто взять на себя ответственность за строку, если это выделенная строка.
Канат очень хорош для больших струн. Но что-то под 8 КБ быстрее справляется с memmove и memcpy.
sprintf() обычно не является "быстрым". Поскольку вы знаете, что предварительно ожидающий memmove() дважды, вероятно, будет предпочтительнее для скорости.
Если вы выделяете строки с помощью malloc(), вы можете использовать realloc() для изменения размеров массивов символов, чтобы они могли содержать новую строку.
char* p = malloc( size_of_first_string );
...
p = realloc( p, size_of_first_string + size_of_prepended_string );
memmove( p + size_of_prepended_string, p, size_of_first_string );
memmove( p, prepended_string, size_of_prepended_string );
Вы можете сохранить строку, начиная с конца. Поскольку вы, кажется, уже знаете maxSize...
Итак, в основном, если файл первоначально был (foo.txt)
[] [] [] [] [] [f] [o] [o] [.] [t] [x] [t] [\0]
^
|
lastEmpty
Теперь, если вы добавите родительский каталог a/, он будет выглядеть как
[] [] [] [a] [/] [f] [o] [o] [.] [t] [x] [t] [\0]
^
|
lastEmpty
Итак, код будет выглядеть примерно так (могут быть ошибки, но вы поняли).
char temp[LENGTH], file[LENGTH];
int lastEmpty = put_at_end(some_file_name, file);
// lastEmpty points to right most empty slot
while (some_condition) {
parent_dir = some_calculation_that_yields_name_of_parent_dir;
int len = strlen(parent_dir);
char *tmp = parent_dir + len -1;
while (lastEmpty > 0) {
file[lastEmpty] = *tmp;
lastEmpty --;
tmp--;
}
}
Так как я предполагаю, что мы могли бы ожидать, что parent_dir будет маленьким, переходить через него дважды должно быть хорошо. Если вы хотите передать строку файла, вы можете просто использовать file+lastEmpty+1.
Вы можете подняться на вершину дерева каталогов, сохраняя имена по мере продвижения, а затем вставляйте имена вместе одновременно. По крайней мере, вы не делаете ненужных копий, нажимая на передний план.
int i = 0;
int j;
char temp*[MAX_DIR_DEPTH], file[LENGTH];
while (some_condition) {
temp[i++] = some_calculation_that_yields_name_of_parent_dir;
}
char *pCurrent = file;
for( j = i-1; j > 0; j-- )
{
strcpy(pCurrent, temp[j]);
pCurrent += strlen(temp[j]);
*pCurrent++ = '\';
}
strcpy(pCurrent, filename);
*pCurrent = 0;
Это решение больше не копирует, чем необходимо. Для этого требуется один strlen, поэтому, если поиск имени каталога может вернуть количество копируемых байтов или если вы можете предварительно вычислить длину родительской строки, вы можете оптимизировать это.
void GetFilename(char *pFile)
{
strcpy(pFile, "someFile");
}
void GetParentDir(char *pDir)
{
strcpy(pDir, "/parentdir");
}
int _tmain(int argc, _TCHAR* argv[])
{
char path[1024];
GetParentDir(path);
int dirSize = strlen(path);
path[dirSize] = '/';
GetFilename(path + dirSize + 1);
printf(path);
return 0;
}
Возможно, я в замешательстве, но я считаю, что preend - это то же самое, что и при добавлении строк. Поэтому вместо добавления "Hello" к "World" строка "World" может быть добавлена в "Hello":
const char world[] = "World";
const char hello[] = "Hello";
// Prepend hello to world:
const unsigned int RESULT_SIZE = sizeof(world) + sizeof(hello) + 2 * sizeof('\0');
char * result = malloc(RESULT_SIZE);
if (result)
{
strcpy(result, hello);
strcat(result, world);
puts("Result of prepending hello to world: ");
puts(result);
puts("\n");
}
Кроме того, основной тратой времени выполнения является поиск конца строки. Если строки были сохранены с длиной, конец мог бы быть рассчитан быстрее.
Я оставляю буфер слева и справа от массива. Вы должны иметь два индекса, но если вам приходится делать это много раз (другое дело, для эффективности не было бы проблем), он его сулит. Два индекса, которые я предлагаю использовать] s; e], один включен, а другой нет:
#define BUFSIZE 256
#define LEFTBUF 20
struct mstring
{
char * string;
unsigned s;
unsigned e;
}
void checkbuf(struct mstring *value, int newstringlen, char leftorright)
{
//have fun here
}
char * concat (struct mstring * value, char * str)
{
checkbuf(value, strlen(value,str), 'r');
int i=0;
while (str[i])
value->string[value->e++]=str[i++];
}
char * set(struct mstring * value, char * str)
{
value->e=LEFTBUF;
value->s=LEFTBUF;
concat( value,str);
}
char * prepend (struct mstring * value, char * str)
{
checkbuf(value, strlen(value,str), 'l');
int i=strlen(value,str)-1;
while (i>=0)
value->string[--value->s]=str[i--];
}
int main()
{
struct mstring * mystring= (struct mstring *) malloc(sizeof(struct mstring) );
mystring->string=(char*)malloc(sizeof(char)*BUFSIZE);
set( mystring,"World");
prepend(mystring,"Hallo")
}
тогда вам нужно подготовить функцию для заполнения подстроки...