Конкатенация строк

Сначала пробежаться в цикле и сделать strlen, потом выделить память, а потом только конкатенировать в новую строку.

А вообще - не нужно

Вопрос — как избавиться от фиксированного ограничения длины результирующей строки

Посчитать сначала длины всех исходных строк. ВРИО кэпа

Ну, ты нуб. http://www.akkadia.org/drepper/optimtut1.ps.gz

Попробую, просто думал что можно сделать как-то проще. На счёт ненужно — предлагаешь для каждой пары строк использовать strcat? Представь какая будет каша в коде если количество таких строк, например, больше 5.

стандартные функции C убоги до невозможности

Если так кажется, может стоит как основной использовать язык более высокого уровня?

Что это за набор байт?

предлагаешь для каждой пары строк использовать strcat?

предлагаю использовать strncat и snprintf(foo,foo_len,«%s %s %s», ...)

Поскольку стандартные функции C убоги до невозможности

Аргументируй =)

Веревки, дедупликация
http://en.wikipedia.org/wiki/Rope_(data_structure)
Сишные сточки с 0 это печаль из глубины веков. Наверное си проги были бы быстрее не считай они длинну каждый раз за линейное время

Представь какая будет каша в коде если количество таких строк, например, больше 5.

ты о чём? Тебе предлагают два цикла: в одном ты длинну высчитываешь и выделяешь память под результат, а во втором уже строки соединяешь. С realloc можно и одним циклом обойтись :)

К стандартным функциям можно относиться по-разному, но Ваша - эталон быдлокода.

К стандартным функциям можно относиться по-разному, но Ваша - эталон быдлокода.

Почему?

За отступ пред фигурной скобкой вообще убивав бы...

Строку удалять кто будет и когда?

ну и будет реаллок заново память выделять нафига оно надо, а впокобще можно аналог LBS из hacskell

Сделал пока так:

char* str_concat(char *str_arr[])
	{
	int n;
	int size = 0;
	for (n=0; ; n++)
		{
		size += strlen(str_arr[n]);
		if (str_arr[n+1] == NULL) break;
		}
	char *str = (char*)malloc(sizeof(char)*size+1);
	for (int i=0; i <= n; i++)
		{
		//printf("%s", str_arr[i]);
		strcat(str, str_arr[i]);
		}
	//printf("%s", str);
	return str;
	}

За отступ пред фигурной скобкой вообще убивав бы...

Фанатик одного единственно правильного™ стиля детектед.

Строку удалять кто будет и когда?

Зачем её удалять если её нужно вернуть в main()?

ты о чём?

Об использовании strcat многоуровневой вложенности, т.к. аноним выше заявил что моё решение ненужно.

Тебе предлагают два цикла: в одном ты длинну высчитываешь и выделяешь память под результат, а во втором уже строки соединяешь

Так и сделал, спасибо.

%s %s %s

Зачем мне считать количество строк если это может сделать компьютер?

Аргументируй =)

Без велосипеда тут не выедешь.

stpcpy() еще не предлагали, ускоритель ты наш?

stpcpy()

И чем оно принципиально отличается от strcat? Всё равно только два аргумента умеет.

ускоритель ты наш

На сишечке ничего сложнее хелловорлда не писал

char *
str_concat(char *ss[])
{
  int n = 0, size = 0, toff = 0;

  for (; ss[n]; n++) {
    size += strlen(ss[n]);
    if (n == 0) toff = size;
  }

  char *s = malloc(size+1);
  char *t = &str[toff];

  for (int i = 0; i < n; i++)
    t = stpcpy(t, ss[i]);

  s[size] = 0;
  return s;
}

Не тестил, границы страдают, важна лишь идея.

strcat() каждый раз пробегает по строке в поисках ее конца, и только потом начинает копировать. Т.о. тормоза увеличиваются с каждой дополнительной входящей строкой. stpcpy() возвращает указатель на конец только что завершенной операции.

s/i < n/i <= n/ конечно же

ну и будет реаллок заново память выделять нафига оно надо

Не факт, malloc/realloc могут выделять с запасом. Недавно на лоре писали про это, не помню тред. Правда, постоянное дёрганье realloc выглядит немного костыльно.

Если только ты не в начале main()'а, то realloc будет выделять откуда попало, а не с запасом. И вообще realloc надо дергать умножая(деля) на фактор. realloc на инкремент слишком кучеряво встанет.

Почему?

• Пустое условие в цикле for, хотя внутри цикла оно присутствует
• В первой версии функции был возможен выход за пределы локального массива: применять strcat() в случае, когда нет гарантии того, что вся строка поместится в буфер, нельзя
• Во второй версии функции Вы внесли новый баг - при нулевом числе строк будет разыменование нулевого указателя, а затем выход за пределы передаваемого массива
• strcat() таким образом применять неэффективно: эта функция каждый раз в цикле будет искать конец строки от её начала. Нужно запоминать текущую позицию конца строки
• Двойного пробега по строкам (strlen ищет конец строки, как и strcat), как сделано во второй версии функции, тоже желательно избегать, т.к. на это расходуется существенное время. Можно сделать за один пробег, при необходимости довыделяя память реаллоком
• Эта функция вообще не нужна, т.к. если планируется много работать со строками, то нужно сделать так, чтобы их длины не пересчитывались каждый раз, то есть, передавались бы вместе с самими строками. И раз они будут передаваться, то вместо strcat нужно будет использовать memcpy, но это уже совсем другая история

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

ну как повезет, а функция работабщая как повезет это не круто.

Реаллок не всегда копирует память. Но даже если копирует, то по тяжести эта операция, если реаллок применять не часто, в итоге может получиться легче поиска нулевого байта.

И ещё забыл упомянуть:

• strlen() возвращает беззнаковое size_t, а Вы без надобности приводите его к типу int

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

int
main(int argc, char *argv[])
{
    size_t size = 1;
    void *p = NULL;
    void *q;

    // продырявим кучу
    void *m[2000] = { 0 };
    for (int i = 0; i < 2000; i++)
        m[i] = malloc(rand() % 500);
    for (int i = 0; i < 2000; i++)
        if (rand() % 2) free(m[i]);

    for (int i = 0; i < 200; i++) {
        if (p != (q = realloc(p, size += 22))) {
            printf("%d %u: moved!\n", i, (unsigned)size);
            p = q;
        }
    }
}

0 23: moved!
14 331: moved!
15 353: moved!
31 705: moved!
32 727: moved!
33 749: moved!
34 771: moved!
35 793: moved!
36 815: moved!
37 837: moved!
38 859: moved!
39 881: moved!
42 947: moved!
43 969: moved!
44 991: moved!
45 1013: moved!
46 1035: moved!
47 1057: moved!
49 1101: moved!
50 1123: moved!
51 1145: moved!
52 1167: moved!
53 1189: moved!
54 1211: moved!
56 1255: moved!
57 1277: moved!
58 1299: moved!
59 1321: moved!
60 1343: moved!
62 1387: moved!
65 1453: moved!
67 1497: moved!
69 1541: moved!
70 1563: moved!
71 1585: moved!
77 1717: moved!
80 1783: moved!
127 2817: moved!

Боюсь нужна просто идеальная куча (которой не бывает). Если в ней есть хотя бы две дырки, по величине сравнимые с исходным объемом, реаллок проиграет.

а функция работабщая как повезет это не круто.

я как раз люблю на эту тему подумать. Надо бы тесты написать.

А вообще, недетерминизм это

1) часть нашей жизни

2) почему бы и нет если на это не завязаны критические участки кода

смотрите на код великого мастера и учитесь ))))

#include <stdlib.h>
#include <stdarg.h>
#include <string.h>

#define STR_BLOCK 4096

char *str_concat(const char *first, ...)
{
int m,n;
char *p, *q;
va_list args;

if (!first)
        return NULL;

n = strlen(first);

m = (n/STR_BLOCK+1)*STR_BLOCK;

p = (char*)malloc(m);

if (!p)
        return NULL;

memcpy(p, first, n);
p[n] = '\0';

va_start(args, first);

while((q = va_arg(args, char*)))
        {
        while(*q)
                {
                p[n++] = *q++;

                if (n == m)
                        {
                        char *np = (char*)realloc(p, m += STR_BLOCK);
                        if (!np)
                                {
                                free(p);
                                p = NULL;
                                break;
                                }
                        p = np;
                        }
                }

        p[n] = '\0';
        }

va_end(args);

return p;
}


int main(int argc, char **argv)
{

//test
//

char *p = str_concat("раз ", "два ", "три ", NULL);
puts(p);
free(p);

return 0;
}

я как раз люблю на эту тему подумать. Надо бы тесты написать.

не взлетит, тут очень сильно от побочных эффектов и особенностей работы программы с памятью поведение зависит, и от версии libc :).

1). есть области где этого стоит избегать

2). зачем, если можно сделать заведомо нормально при той же сложности.

Зачем мне считать количество строк если это может сделать компьютер?

правильно думаешь. может, через полгодика, придёт прозрение и вместо переносимого ассемблера возьмёшь яп.

если можно сделать заведомо нормально при той же сложности.

В данном случае да. Но это не всегда так. Используют же люди питон, перл, руби итп :). А они во многих случаях очень топорно работают.

подозреваю, что для нормальной работы со строками там или билдеры или «правила работы» типа юзайте «str».join(..), т.к. «+» тормозит. Людям вообще часто пофиг на производительность, но, имхо, выбор говорит, что она важна.

выбор говорит, что она важна.

не факт, не факт :). Я тоже пишу на C иногда, но только потому что до многих возможностей ядра и библиотек без C-врапперов не добраться.

Если длина строки уже известна, то для копирования надо использовать memcpy() / mempcpy()

быстрее будет выделить скажем 50 байт для начала, а если не лезет, то удвоить память (man 3 realloc). Кстати, в gnu sed именно так.

Довыделение памяти реаллоком у тебя конечно же не приводит к повторному двойному пробегу.

А ты удваивай память, тогда число реаллоков будет расти как log₂, т.е. ОЧЕНЬ медленно.

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

int
main(int argc, char *argv[])
{
    size_t size = 1, psize = 1, totalmoved = 0;
    void *p = NULL;
    void *q;

    // продырявим кучу
    void *m[2000] = { 0 };
    for (int i = 0; i < 2000; i++)
        m[i] = malloc(rand() % 500);
    for (int i = 0; i < 2000; i++)
        if (rand() % 2) free(m[i]);

    for (int i = 0; i < 200; i++) {
        if (size + 22 >= psize) {
            q = realloc(p, psize *= 2);
            if (p != q) {
                printf("%d %u: moved!\n", i, (unsigned)size);
                totalmoved += size;
                p = q;
            }
        }
        size += 22;
    }
    printf("total moved: %u\n", (unsigned)totalmoved);
    printf("total bytes: %d\n", 200 * 22);
    return 0;
}

0 1: moved!
4 89: moved!
5 111: moved!
6 133: moved!
7 155: moved!
11 243: moved!
23 507: moved!
46 1013: moved!
93 2047: moved!
186 4093: moved!
total moved: 8392
total bytes: 4400

Убедительно?

И не забываем скрытые затраты на поиск нового места.

если задача произвольное число с-строк заданое == как аргумент main слить в одну . то я бы наверно печатал бы в выходной_файл(буферный-самоудаляемый после закрытия :) ) а затем выпечатывал бы файл в строку.

т.е решение с допечаткой строк через sprintf - вполне.

#include<stdio.h>
void main(int args,char * str_arr[]){
	while(--args){
		printf("%s",*++str_arr);
	}
}

ну и обёртку прикрутить

Убедительно?

IRL строчки короче 50 байт, т.ч. реаллок вообще не нужен. Если в твоей задаче много больших строк, то просто выделяй сразу побольше байт. Обычно IRL 95% строк вообще не требуют реаллока, а из оставшихся 5% требуют одного. Т.ч. не убедил.

Убедишь, если покажешь задачу, с каким-то хитрым распределением длин строк, но я даже не представляю, каким оно должно быть.