Привязка к строке

Question

Каков наиболее эффективный способ присоединения к строке 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);
}

Хотя это кажется немного неуклюжим.

Любая помощь будет оценена. Спасибо!

Answer 1

Копирование вряд ли можно избежать, если вы хотите его в том же блоке памяти. Если выделенный фрагмент достаточно велик, вы можете использовать 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;
}

Answer 2

Если вам не нужна строка для сохранения в порядке, а только отображаются в порядке, используйте вещь, называемую «веревка». (Он состоит из множества «строк», см.)

Я считаю, что это в основном вектор (в терминах C, массив) struct { char *begin; char *end };

В C ++ реализованы все функции std :: string. В C вам нужно написать (или получить библиотеку) замещающие функции для всех функций strxxx ().

То, что "веревка" сделала бы, чтобы добавить строку к другой строке, - это просто вставить новую пару начала, конца, указывающую на новый фрагмент строки. Может также потребоваться скопировать новый фрагмент строки, если это временный указатель. Или он может просто стать владельцем строки, если это выделенная строка.

Веревка очень хороша для больших струн. Но все, что меньше 8 КБ, быстрее обрабатывается с помощью memmove и memcpy.

Answer 3

sprintf () обычно не «быстрый». Поскольку вы знаете, что предварительное ожидание memmove () дважды, вероятно, предпочтительнее для скорости.

Если вы выделяете строки с помощью функции malloc (), вы можете использовать realloc () для изменения размера символьных массивов, чтобы они могли содержать новую строку.

   char* p = malloc( size_of_first_string );
   ...
   p = realloc( p, size_of_first_string + size_of_prepended_string + 1 );
   memmove( p + size_of_prepended_string, p, size_of_first_string );
   memmove( p, prepended_string, size_of_prepended_string );

Answer 4

Возможно, я в замешательстве, но я полагаю, что предпредложение - это то же самое, что и добавление с замененными строками. Таким образом, вместо с добавлением"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");
}

Кроме того, основной тратой времени на выполнение является поиск конца строки. Если бы строки были сохранены с длиной, конец мог бы быть вычислен быстрее.

Answer 5

Вы можете подняться на вершину дерева каталогов, сохраняя имена по мере продвижения, а затем вставить имена вместе сразу. По крайней мере, тогда вы не делаете ненужные копии, нажимая на переднюю панель.

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;

Answer 6

Вы можете сохранить строку, начиная с конца. Поскольку вы, кажется, уже знаете maxSize ...

Так что, в принципе, если файл изначально был (foo.txt)

[] [] [] [] [] [f] [o] [o] [.] [t] [x] [t] [\0]
             ^
             |
          lastEmpty           

Теперь, если вы добавите родительский каталог /, он будет выглядеть как

[] [] [] [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.

Answer 7

Я оставляю буфер слева и справа от массива. Вы должны держать два индекса, но если вам придется делать это много раз (в противном случае не было бы проблем с эффективностью), то это нужно. Два индекса, которые я предлагаю, чтобы быть] 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")

  }

тогда вам нужно подготовить функцию для заполнения подстрок ...

Answer 8

Это решение имеет не больше копирования, чем необходимо. Для этого требуется одна строка, поэтому, если поиск по имени каталога может вернуть количество скопированных байтов или если вы можете предварительно рассчитать длину строки родительского каталога, вы можете оптимизировать ее.

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