Страницы

Поиск по вопросам

Показаны сообщения с ярлыком strlen. Показать все сообщения
Показаны сообщения с ярлыком strlen. Показать все сообщения

воскресенье, 29 декабря 2019 г.

C/C++, strlen(NULL)

#c #null #strlen


Почему эта функция не проверяет переданный ей аргумент на NULL? 

Самое интересное, что мало где пишут, что strlen(NULL) приводит к сегфолту. Даже
в книжке С.Прата за 2015 год нет ни слова о том, что функция не выполняет названную
проверку. Очень странно.
    


Ответы

Ответ 1



На самом деле ничего странного в этом нет. Средства стандартных библиотек C и C++ часто не используют дополнительных проверок корректности аргументов в угоду эффективности. Многие средства уже предполагают, что программист сделал проверку, либо она вовсе не нужна, т.к. есть какая-то гарантия валидности аргумента. Если же сделать проверку внутри функций, то получим потерю производительности из-за лишних проверок. Возьмем простой пример: if (str) {//Проверка на ноль size = strlen(str);//А внутри strlen была бы еще одна проверка } else { printf("error\n"); } Тоже самое можно отнести, например, к std::vector::operator[]: for(size_type i = 0; i < vec.size(); ++i) { //Мы не выйдем за пределы вектора vec[i] = i;//Но в operator[] всё равно была бы еще одна проверка } И если с вектором всё более менее понятно - есть отдельная функция-член at, проверяющая валидности индекса, то с strlen чуть сложнее. Что должна вернуть эта функция, если ей передали NULL? Нужна была бы какая-то константа для определения факта ошибки и опять же, дополнительные проверки. К слову о том, что об этом нигде не пишут. На самом деле - пишут. Например, на cppreference: https://en.cppreference.com/w/cpp/string/byte/strlen Parameters str - pointer to the null-terminated byte string to be examined Аргументом strlen должен быть указатель на null-terminated byte string, коим NULL не является. Но можно обратиться и к стандарту C. Для strlen никаких требования не указано, поэтому согласно Вырезка из документа N1570 7.24.1 String function conventions ... Unless explicitly stated otherwise in the description of a particular function in this subclause, pointer arguments on such a call shall still have valid values, as described in 7.1.4. аргумент должен иметь валидное значение, согласно описанному в 7.1.4: 7.1.4 Use of library functions Each of the following statements applies unless explicitly stated otherwise in the detailed descriptions that follow: If an argument to a function has an invalid value (such as a value outside the domain of the function, or a pointer outside the address space of the program, or a null pointer, or a pointer to non-modifiable storage when the corresponding parameter is not const-qualified) or a type (after promotion) not expected by a function with variable number of arguments, the behavior is undefined а согласно этому пункту, как видим, передача нулевого указателя приводит к неопределенному поведению.

пятница, 13 декабря 2019 г.

Динамическое выделение памяти с помощью scanf

#c #массивы #память #strlen


Как с помощью scanf выделить память и занести в переменную.

Предположим, что пользователь вводит очень длинный текст и заранее определенный размер
массива обрезает строку. Пробовал не указывать размер массива и присваивать пустую
строку (""), но strlen всегда возвращает 0, а если присутствуют символы в str, то длину
строки.

Где проблема?

char str[] = "";
scanf("%s",str);
printf ("Line size \"%s\" - %d characters\n", str, strlen (str) );

    


Ответы

Ответ 1



Объявление char str[] = ""; эквивалентно объявлению char str[1] = ""; Массив получает размер 1, который после этого уже больше никогда не поменяется. В такой массив невозможно поместить никакую строку, кроме пустой. В любом случае, локальный или статический массив в языке С получает конкретный фиксированный размер в точке определения. Поменять этот размер позже уже невозможно. Поэтому решить задачу чтения строки неизвестной длины с использованием явного объявления массива не получится. Размер массива придется менять по мере необходимости, т.е. "на лету". А изменяться "на лету" может только размер динамически выделенного (через malloc) массива. Однако даже в этом случае какого-либо готового решения в стандартном scanf нет. Для чтения строк неизвестной, заранее неограниченной длины лучше использовать не scanf, а циклический вызов fgets с периодическим realloc-ом динамического буфера, пока не прочитана вся строка. Тем не менее, GNU scanf поддерживает нестандартный модификатор m, реализующий требуемую функциональность. Этот модификатор работает с форматами s и []: char *str = NULL; scanf("%ms", &str); ... free(str); Обратите внимание, что передавать в scanf в этом случае следует указатель на указатель, т.е. аргумент типа char **. Ранее в этой роли выступал модификатор a. Однако начиная с C99 символ a "занят" под один из стандартных форматов. Поэтому если вы захотите воспользоваться этой возможностью, будьте внимательны с версией библиотеки.

среда, 27 ноября 2019 г.

Реализация strlen() на Си в одну строку

#c #strlen #алгоритм


Давеча побывал на собеседовании, одним из заданий было реализовать функционал strlen()
без применения сторонних функций, то есть руками. Как полный дилетант в Си я изобразил
простой цикл. Мне было указано что данная реализация неэкономна, а также что ее можно
записать без лишних переменных и в одну строку. Разумеется не в смысле засовывания
все в одну строку, а именно иной алгоритм. Речь не шла о производительности или оптимизации
с точки зрения практики, и как я понимаю, вопрос носил чисто академический характер.
Это вызвало у меня интерес, так как на собеседовании я сделать этого не смог. Общаясь
с более компетентным коллегой получил от него реализацию:

size_t str_len (const char *str)
{
    return (*str) ? str_len(++str) + 1 : 0;
}


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

PS:
завел также топик на SO на одноименную тему.
Надеюсь будет интересно участвовавшим в дискуссии.
    


Ответы

Ответ 1



Попробую тоже добавить небольшой комментарий к ответу Дож: действительно, если не прибегать к рекурсии, эти самые N итерации должны быть осуществлены с помощью некоего цикла, будь то for, while или do while, откуда возникает принципиальная невозможность сделать алгоритм в одну строку: если бы даже кому-то удалось написать такой однострочник при помощи любого из этих циклов, в любом случае понадобится как минимум ещё одна строка для того, чтобы вернуть результат: size_t custom_strlen(...) { for (крутой однострочник) {} return длина; // от этой строки никуда не убежать } С учётом этого соображения и того, что условие чётко оговаривает лишь "реализовать функционал strlen() без применения сторонних функций", я попробовал немного схитрить: void stanislaw_len(char * str, size_t *len) { for (*len = 0; *str; ++str, (*len)++); } P.S. Я знаю, что это хак, просто попробовал из спортивного интереса. Более интересно другое: я сравнил предложенные здесь методы и strlen между собой: void stanislaw_len(char * str, size_t *len) { for (*len = 0; *str; ++str, (*len)++); } size_t KoVadim_len(char * t) { return (strchr(t, 0) - t) / sizeof(char); } size_t avp_len (const char *str) { register const char *s = str; while(*str++); return (size_t)(str - s - 1); } char *STRING = "This is a rather long string! This is a rather long string! This is a rather long string!"; size_t N = 1000000; size_t M = 10; __block size_t counter = 0; Benchmark(M, ^{ for (int i = 0; i < N; i++) { size_t length; stanislaw_len(STRING, &length); counter += length; } }); NSLog(@"stanislaw_len %ld", counter); ... остальные аналогично Вот результаты для O3: The block have been run 10 times. Average is: 67.163414 milliseconds 2014-03-12 16:59:10.429 SandboxCommandLineApp[17606:303] stanislaw_len() 890000000 The block have been run 10 times. Average is: 72.448875 milliseconds 2014-03-12 16:59:11.156 SandboxCommandLineApp[17606:303] avp_len() 890000000 The block have been run 10 times. Average is: 12.458966 milliseconds 2014-03-12 16:59:11.281 SandboxCommandLineApp[17606:303] KoVadim_len() 890000000 The block have been run 10 times. Average is: 8.514538 milliseconds 2014-03-12 16:59:11.367 SandboxCommandLineApp[17606:303] strlen() 890000000 Вопрос к знатокам: что такого может быть вжато в Apple-овских libc dylib-ах, что такая большая разница есть в скорости? Особенно это непонятно в связи с тем, что последняя опубликованная open source - версия strlen.c содержит очень схожие посимвольные проходы, как у меня и @avp (вариант KoVadim тут не в счёт, так как он опять же полагается на системную библиотеку) ?

Ответ 2



В Си невозможно. Всё, что можно записать в одну строку и без вызова других функций, выполняется за время O(1), а нам нужно написать алгоритм, который работает по крайней мере O(N) (N — длина строки).

Ответ 3



В формулировке сказано "без вызова сторонних функций". А функции стандартной библиотеки являются сторонними функциями? Как по мне, то нет. и мой вариант решения тогда такой: int newlen(char * t) { return (strchr(t, 0) - t) / sizeof(char); } По поводу рекурсивного варианта с вопроса - посмотрел скомпилированный вариант (gcc 4.4-4.9 при уровне оптимизации O2, clang 3) - там нет рекурсии - компилятор разворачивает в цикл. str_len(char const*): # @str_len(char const*) xorl %eax, %eax cmpb $0, (%rdi) je .LBB0_3 xorl %eax, %eax .LBB0_2: # %tailrecurse cmpb $0, 1(%rdi,%rax) leaq 1(%rax), %rax jne .LBB0_2 .LBB0_3: # %tailrecurse._crit_edge ret Код не идеальный, но достаточно хорош. Никакого стека, никаких лишних обращений к памяти.

Ответ 4



int strlen(const char* str) { for (const char* c = str;;c++) if (!*c) return c-str; }

Ответ 5



int str_len(const char* str) { for (char const * a = str, *b = str;;a--,b++) if (!*b) for (int i = 0;; a++, i++) if (a == b) return i / 2; }

Ответ 6



int strlen(const char* str) { for (const char* c = str;;({ if (*c++ == '\0') return c - str - 1; })); }

Ответ 7



Я бы сделал так: size_t SLen(const char *s) { int k = 0; while(s[k++]); return --k; }

среда, 3 октября 2018 г.

Реализация strlen() на Си в одну строку

Давеча побывал на собеседовании, одним из заданий было реализовать функционал strlen() без применения сторонних функций, то есть руками. Как полный дилетант в Си я изобразил простой цикл. Мне было указано что данная реализация неэкономна, а также что ее можно записать без лишних переменных и в одну строку. Разумеется не в смысле засовывания все в одну строку, а именно иной алгоритм. Речь не шла о производительности или оптимизации с точки зрения практики, и как я понимаю, вопрос носил чисто академический характер. Это вызвало у меня интерес, так как на собеседовании я сделать этого не смог. Общаясь с более компетентным коллегой получил от него реализацию:
size_t str_len (const char *str) { return (*str) ? str_len(++str) + 1 : 0; }
Я бы пожалуй пока до такого сам не додумался бы, но теперь вопрос у коллеги - существует ли вариант в одну строку без рекурсии?
PS: завел также топик на SO на одноименную тему. Надеюсь будет интересно участвовавшим в дискуссии.


Ответ

Попробую тоже добавить небольшой комментарий к ответу Дож: действительно, если не прибегать к рекурсии, эти самые N итерации должны быть осуществлены с помощью некоего цикла, будь то for, while или do while, откуда возникает принципиальная невозможность сделать алгоритм в одну строку: если бы даже кому-то удалось написать такой однострочник при помощи любого из этих циклов, в любом случае понадобится как минимум ещё одна строка для того, чтобы вернуть результат: size_t custom_strlen(...) { for (крутой однострочник) {} return длина; // от этой строки никуда не убежать } С учётом этого соображения и того, что условие чётко оговаривает лишь "реализовать функционал strlen() без применения сторонних функций", я попробовал немного схитрить: void stanislaw_len(char * str, size_t *len) { for (*len = 0; *str; ++str, (*len)++); } P.S. Я знаю, что это хак, просто попробовал из спортивного интереса. Более интересно другое: я сравнил предложенные здесь методы и strlen между собой: void stanislaw_len(char * str, size_t *len) { for (*len = 0; *str; ++str, (*len)++); }
size_t KoVadim_len(char * t) { return (strchr(t, 0) - t) / sizeof(char); }
size_t avp_len (const char *str) { register const char *s = str;
while(*str++); return (size_t)(str - s - 1); }
char *STRING = "This is a rather long string! This is a rather long string! This is a rather long string!";
size_t N = 1000000; size_t M = 10;
__block size_t counter = 0;
Benchmark(M, ^{ for (int i = 0; i < N; i++) { size_t length;
stanislaw_len(STRING, &length);
counter += length; } });
NSLog(@"stanislaw_len %ld", counter);
... остальные аналогично Вот результаты для O3: The block have been run 10 times. Average is: 67.163414 milliseconds 2014-03-12 16:59:10.429 SandboxCommandLineApp[17606:303] stanislaw_len() 890000000 The block have been run 10 times. Average is: 72.448875 milliseconds 2014-03-12 16:59:11.156 SandboxCommandLineApp[17606:303] avp_len() 890000000 The block have been run 10 times. Average is: 12.458966 milliseconds 2014-03-12 16:59:11.281 SandboxCommandLineApp[17606:303] KoVadim_len() 890000000 The block have been run 10 times. Average is: 8.514538 milliseconds 2014-03-12 16:59:11.367 SandboxCommandLineApp[17606:303] strlen() 890000000 Вопрос к знатокам: что такого может быть вжато в Apple-овских libc dylib-ах, что такая большая разница есть в скорости? Особенно это непонятно в связи с тем, что последняя опубликованная open source - версия strlen.c содержит очень схожие посимвольные проходы, как у меня и @avp (вариант KoVadim тут не в счёт, так как он опять же полагается на системную библиотеку) ?