Реализация своей функции getline

@JustForStudy · Регистрация: 23.09.2015

Студворк — интернет-сервис помощи студентам

Здравствуйте! Не могу решить задачку.

Постановка:
Реализуйте функцию getline, которая считывает поток ввода посимвольно, пока не достигнет конца потока или не встретит символ переноса строки ('\n'), и возвращает C-style строку с прочитанными символами.

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

Память, возвращенная из функции будет освобождена оператором delete[]. Символ переноса строки ('\n') добавлять в строку не нужно, но не забудьте, что в конце C-style строки должен быть завершающий нулевой символ.

Мой код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
using namespace std;
 
char *getline()
{
    char *m = new char[1];
    char c;
    cin >> c;
    int i = 1;
 
    while ((c != '\n') && (c != '\0')) {
        m = new char[i];
        m[i-1] = c;
        i++;
    }
    
    m[i] = '\0';
 
    return m;
    
}
 
int main(void) {
    char *example = getline();
    system("pause");
    return 0;
}

Вопрос:
В чем ошибка ? Консоль зависает после перехода на новую строку.

@JustForStudy · 16.10.2015, 10:01 **[ТС]**

Сообщение от DrOffset

Вот в прошлом задании у тебя было нужно реализовать resize.

Честно говоря, я и с этим заданием не справился.

Вот, что у меня получилось:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
using namespace std;
 
/*В этой задаче вам нужно реализовать функцию resize. 
Функция resize принимает на вход три аргумента: указатель на область памяти, выделенную с помощью оператора new[], размер области (size) и новый размер (new_size). 
Функция должна выделить память размера new_size, скопировать в нее данные из переданной области памяти, 
освободить старую область памяти и вернуть выделенную область памяти нового размера со скопированными данными.  */
 
char *resize(const char *str, unsigned size, unsigned new_size)
{
    const char *ptr = str;
    str = new char[new_size];
    
    for (int i = 0; i < size; i++) {
        (char)str[i] = ptr[i];
    }
 
    delete[] ptr;
    
    return str;
}
 
int main(void) {
 
    char test[] = { 'a', 'b', 'c', 'd', 'e' };
 
    char *test2 = resize(test, 5, 7);
 
    test2[5] = 'f';
    test2[6] = 'g';
 
    for (int i = 0; i < 7; i++) {
        cout << test[i] << " ";
    }
    cout << endl;
 
    delete[] test2;
    return 0;
}

Не пойму, что делать с const char. Неужели просто переопределить в char ?

@DrOffset · 16.10.2015, 10:49

Сообщение от JustForStudy

Не пойму, что делать с const char. Неужели просто переопределить в char ?

Запомни правило, если в программе требуется приведение типа, с очень большой долей вероятности ты делаешь что-то не так.
Ты все перепутал (источник с приемником, динамическую память с автоматической).

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
using namespace std;
 
/*В этой задаче вам нужно реализовать функцию resize.
Функция resize принимает на вход три аргумента: указатель на область памяти, выделенную с помощью оператора new[], размер области (size) и новый размер (new_size).
Функция должна выделить память размера new_size, скопировать в нее данные из переданной области памяти,
освободить старую область памяти и вернуть выделенную область памяти нового размера со скопированными данными.  */
 
char * resize(const char *str, unsigned size, unsigned new_size)
{
    char * ptr = new char[new_size]; // новая память
    // копируем старые значения в новую память
    // с учетом того, что новая память может занимать меньше, чем старая
    for(unsigned i = 0, len = std::min(size, new_size); i < len; i++) 
    {
        ptr[i] = str[i]; // старая память только для чтения, поэтому const не мешает
    }
    delete[] str; // освобождаем старую
 
    return ptr; // возвращаем новую
}
 
int main(void) {
 
    char * test = new char[6]; // нужна динамическая память
    strncpy(test, "abcde", 6);
 
    cout << test << endl;
 
    char *test2 = resize(test, 6, 8);
    // test после этого невалиден
 
    test2[5] = 'f';
    test2[6] = 'g';
 
    for (int i = 0; i < 7; i++)
    {
        cout << test2[i] << " ";
    }
    cout << endl;
 
    delete[] test2;
    return 0;
}

@JustForStudy · 16.10.2015, 15:32 **[ТС]**

Сообщение от DrOffset

Запомни правило, если в программе требуется приведение типа, с очень большой долей вероятности ты делаешь что-то не так.

Хорошо, спасибо за совет.

Сделал как вы говорили. Но теперь программа не видит переход на новую строку и поэтому требует бесконечный ввод.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
char * getline()
{
    char c = 1;
    int i = 1;
    char *m = new char[i];
    c = cin.get();
    m[0] = c;
 
    c = cin.get();
 
    while (c != 0 || c != '\n') {
        i++;
        m = resize(m, i - 1, i);
        m[i - 1] = c;
 
        c = cin.get();
    }
 
 
 
    return m;
 
}

Тяжело как-то у меня это идет...

@alexvikt · 16.10.2015, 15:48

C++
1
while (c != 0 && c != '\n')

@JustForStudy · 16.10.2015, 16:20 **[ТС]**

Сообщение от alexvikt

while (c != 0 && c != '\n')

Точно.

Добавлено через 11 минут
Многострадальная программа по работе с памятью наконец заработала.

Но есть один нюанс - не проходит проверку. Пишет: Failed test #1. Time limit exceeded.
Что из всего этого кушает так много времени ?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
using namespace std;
int min(int x1, int x2) {
    if (x1 < x2) return x1;
    else return x2;
}
 
char * resize(const char *str, unsigned size, unsigned new_size)
{
    char * ptr = new char[new_size]; // новая память
                                     // копируем старые значения в новую память
                                     // с учетом того, что новая память может занимать меньше, чем старая
    unsigned len = min(size, new_size);
    for (unsigned i = 0; i < len; i++)
    {
        ptr[i] = str[i]; // старая память только для чтения, поэтому const не мешает
    }
    delete[] str; // освобождаем старую
 
    return ptr; // возвращаем новую
}
 
char * getline()
{
    char c = 1;
    int i = 1;
    char *m = new char[i];
    c = cin.get();
    m[0] = c;
 
    c = cin.get();
 
    while (c != 0 && c != '\n') {
        i++;
        m = resize(m, i - 1, i);
        m[i - 1] = c;
 
        c = cin.get();
    }
 
    m = resize(m, i, i + 1);
    m[i] = '\0';
 
    return m;
 
}

@DrOffset · 16.10.2015, 17:48

Сообщение от JustForStudy

Что из всего этого кушает так много времени ?

Память перевыделяешь на каждой итерации.
Вот для примера:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <cstring>
 
char * resize(char const * p, size_t oldLen, size_t newLen)
{
    char * nBuf = new char[newLen];
    if(p)
    {
        std::memcpy(nBuf, p, std::min(oldLen, newLen));
    }
    delete[] p;
    return nBuf;
}
 
char * getline()
{
    enum { ChunkSize = 20 };
    enum { ChunkLen  = ChunkSize - 1 };
 
    char * buf = resize(0, 0, ChunkSize);
 
    char * cur = buf;
    char const * end = cur + ChunkLen;
 
    size_t len = ChunkLen;
 
    char c = std::getc(stdin);
    while(c != EOF && c != '\n')
    {
        *cur++ = c;
        if(cur == end)
        {
            buf = resize(buf, len, len + ChunkSize);
 
            cur = buf + len;
            end = cur + ChunkLen;
 
            len += ChunkLen;
        }
        c = std::getc(stdin);
    }
    *cur = 0;
    return buf;
}

@JustForStudy · 18.10.2015, 22:37 **[ТС]**

Сообщение от DrOffset

Память перевыделяешь на каждой итерации.

Спасибо за пример и совет. Сделал похоже:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
using namespace std;
 
 
 
int min(int x1, int x2) {
    if (x1 < x2) return x1;
    else return x2;
}
 
char * resize(const char *str, unsigned size, unsigned new_size)
{
    char * ptr = new char[new_size]; // новая память
                                     // копируем старые значения в новую память
                                     // с учетом того, что новая память может занимать меньше, чем старая
    unsigned len = min(size, new_size);
    for (unsigned i = 0; i < len; i++)
    {
        ptr[i] = str[i]; // старая память только для чтения, поэтому const не мешает
    }
    delete[] str; // освобождаем старую
 
    return ptr; // возвращаем новую
}
 
char * getline()
{
    char c = 1;
    int i = 1;
    int j = 1;
 
    char *m = new char[40];
    c = cin.get();
    m[0] = c;
 
    c = cin.get();
 
    while (c != 0 && c != '\n') {
        i++;
        
        if ((i / 40) == 0) {
            j++;
            m = resize(m, (j - 1) * 40, j * 40);
        }
        m[i-1] = c;
 
        c = cin.get();
    }
 
    m = resize(m, j * 40, i + 1);
    m[i] = '\0';
 
    return m;
 
}

Ошибка такая же: Failed test #1. Run time error:
Где-то в другом месте кушается время.

@DrOffset · 18.10.2015, 23:03

JustForStudy, усложнил сильно. Проблема в этом.

Сообщение от JustForStudy

Где-то в другом месте кушается время.

Возьми проанализируй вызов функции resize.
Вставь туда в начало вот такие строки:

C++
1
2
    cout << "new: " << new_size << endl;
    cout << "old: " << size << endl;

Увидишь какие дикие цифры у тебя там получаются.
Подказка: дело в делении.

@hoggy · 18.10.2015, 23:07

Сообщение от JustForStudy

Что из всего этого кушает так много времени ?

выделения/удаления памяти - дорогие операции.

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

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

это позволит быстро (с минимальным количеством реалоков)
накопить достаточный для работы резерв.

вообще так поступают стандартные std::vector/std::string

смотрите в сторону:

C++
1
2
3
4
5
6
// не просто изменяет размер контейнера
// но так же контролирует размер резерва
std::vector::resize    
 
// позволяет явно указать минимальный резерв памяти
std::vector::reserve

для строк...ну.. 1024 резерва на старте должно хватить за глаза я думаю.
что бы можно было вообще забыть про реалоки.

@DrOffset · 18.10.2015, 23:16

JustForStudy,
Вот исправленный твой вариант. Не смотреть, если сам хочешь сделать

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
char * getline()
{
    char *m = new char[40];
 
    char c = cin.get();
 
    int i = 0, j = 1;
    while (c != 0 && c != '\n') {
 
        m[i++] = c;
        if ((i % 40) == 0)
        {
            m = resize(m, j * 40, (j + 1) * 40);
            ++j;
        }
        c = cin.get();
    }
    m[i] = '\0';
 
    return m;
}

@JustForStudy · 18.10.2015, 23:32 **[ТС]**

Сообщение от hoggy

выделения/удаления памяти - дорогие операции.

Спасибо за совет. Запомню.

Сообщение от hoggy

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

Сделал так. Все равно слишком много времени программа занимает.

Сообщение от hoggy

std::vector::resize

Я не знаю пока, что это.

Сообщение от DrOffset

Вот исправленный твой вариант. Не смотреть, если сам хочешь сделать

Хочу, конечно. Это уже целый проект на две страницы форума.

Пока сделал так(все равно работает долго):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
char * getline()
{
    char c = 1;
    int i = 1;
    int j = 1;
 
    char *m = new char[1024];
    c = cin.get();
    m[0] = c;
 
    c = cin.get();
 
    while (c != 0 && c != '\n') {
        i++;
        
        if ((i / 1024) == 0) {
            j *= 2;
            m = resize(m, (j/2) * 1024, j * 1024);
        }
        m[i-1] = c;
 
        c = cin.get();
    }
 
    m = resize(m, j * 1024, i + 1);
    m[i] = '\0';
 
    return m;
 
}

Думаю, что еще можно улучшить для уменьшения времени работы.

@DrOffset · 18.10.2015, 23:39

Сообщение от JustForStudy

Думаю, что еще можно улучшить для уменьшения времени работы.

Ты как-то проигнорировал самое важное: ДЕЛО В ДЕЛЕНИИ.

Добавлено через 42 секунды
JustForStudy, и оставь в покое размер, что 40, что 1024 тут роли не играет. Не гадай - думай!

Добавлено через 5 минут

Сообщение от JustForStudy

C++
1
if ((i / 1024) == 0) {

i деленное нацело на 1024 будет давать ноль всегда, пока оно меньше 1024.
Используй оператор % для нахождения остатка.

ValeryS · 18.10.2015, 23:43

Сообщение от DrOffset

ДЕЛО В ДЕЛЕНИИ.

и не только

Сообщение от JustForStudy

if ((i / 1024) == 0) {

сработает при первой же итерации и сразу пойдет перераспределение

@DrOffset · 18.10.2015, 23:43

Кроме того, у тебя там ошибка в алгоритме, которая нарушает условие задачи:

Сообщение от JustForStudy

Символ переноса строки ('\n') добавлять в строку не нужно

Если сразу нажать ввод, то этот символ таки добавится.

@JustForStudy · 19.10.2015, 06:20 **[ТС]**

Сообщение от DrOffset

Ты как-то проигнорировал самое важное: ДЕЛО В ДЕЛЕНИИ

Исправил.

Сообщение от DrOffset

Если сразу нажать ввод, то этот символ таки добавится.

Исправил.

В итоге получилось:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
char * getline()
{
    char c = 1;
    int i = 0;
    int j = 1;
 
    char *m = new char[1024];
 
    c = cin.get();
 
    while (c != 0 && c != '\n') {
        i++;
        
        if ((i % 1024) == 0) {
            j *= 2;
            m = resize(m, (j/2) * 1024, j * 1024);
        }
        m[i-1] = c;
 
        c = cin.get();
    }
 
    m = resize(m, j * 1024, i + 1);
    m[i] = '\0';
 
    return m;
 
}

Появилась новая ошибка:
Failed test #1. Run time error:
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc

Что это значит ?

@DrOffset · 19.10.2015, 09:59

Сообщение от JustForStudy

Что это значит ?

Слишком много памяти твоя программа затребовала.
Вернись к варианту с 40 байтами.

@JustForStudy · 19.10.2015, 10:01 **[ТС]**

Сообщение от DrOffset

Слишком много памяти твоя программа затребовала.
Вернись к варианту с 40 байтами.

Пробовал. Появляется совсем страшная ошибка:

Кликните здесь для просмотра всего текста

Failed test #1. Run time error:
*** glibc detected *** ./main: double free or corruption (out): 0x0000000001fce760 ***
======= Backtrace: =========
[0x46ffe2]
[0x474bc7]
[0x40094f]
[0x4009ea]
[0x4003db]
[0x457e83]
[0x400759]
======= Memory map: ========
00400000-00521000 r-xp 00000000 ca:00 804455 /home/stepic/instances/master-plugins/arena/codejail-rl1a1cl8/main
00721000-00728000 rw-p 00121000 ca:00 804455 /home/stepic/instances/master-plugins/arena/codejail-rl1a1cl8/main
00728000-0073f000 rw-p 00000000 00:00 0
01fcc000-01fef000 rw-p 00000000 00:00 0 [heap]
7fd8f4258000-7fd8f4259000 rw-p 00000000 00:00 0
7fff13f8f000-7fff13fb0000 rw-p 00000000 00:00 0 [stack]
7fff13fff000-7fff14000000 r-xp 00000000 00:00 0 [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]

@DrOffset · 19.10.2015, 10:12

Сообщение от JustForStudy

Пробовал.

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

@JustForStudy · 19.10.2015, 10:43 **[ТС]**

Сообщение от DrOffset

Правильно, потому что химичишь с размерами, которые подаешь в resize.

Максимально все упростил:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
char * getline()
{
    int i = 0;  int j = 1;
 
    const unsigned char k = 40;
 
    char *m = new char[j * k];
    char c = cin.get();
 
    while (c != 0 && c != '\n') {
        i++;
 
        if ((i % k) == 0) {
            j++;
            m = resize(m, (j - 1) * k, j * k);
        }
 
        m[i - 1] = c;
        c = cin.get();
    }
 
    m[i] = '\0';
 
    return m;
 
}

Все равно пишет, что временной предел исчерпан. Да что же это такое ?

Добавлено через 3 минуты

Сообщение от DrOffset

Вот исправленный твой вариант. Не смотреть, если сам хочешь сделать

Для проверки решил попробовать дать системе ваш код. Система ответила: Failed test #1. Time limit exceeded

@DrOffset · 19.10.2015, 10:46

JustForStudy, JustForStudy, Вставь вывод размеров (старые и новый) в функцию resize. Отлаживайся на маленьких приращениях, например, - 4. Отладь у себя, прежде чем постить код в систему.
Я могу сразу написать решение, но тогда ты ничему не научишься. Итак у тебя туго что-то идет. Главное - не гадай. Старайся понять что происходит.

Добавлено через 2 минуты

Сообщение от JustForStudy

Для проверки решил попробовать дать системе ваш код.

Какой именно? Код отсюда проверку проходит. Я проверял вчера. Основанные на переделке твоего варианта - не проверял.

Новые блоги и статьи Все статьи Все блоги /
FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .
Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .