Реализация своей функции 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

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

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

Новые блоги и статьи Все статьи Все блоги /
Очистка реквизитов и табличных частей документа при копировании Maks 26.07.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .	Доктрина интенционального знания - Доктрина для портала "Срез". Hrethgir 25.07.2026 Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .	сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых anaschu 25.07.2026 Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.	сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил anaschu 25.07.2026 две стороны одной монеты
Более приземисто - Эстафету хвоста в .cdl (деревья эстафеты в сад). Hrethgir 24.07.2026 В будущем, после написания блока инверсии обхода дерева (эстафеты хвоста), я планирую вернуться к нашему прошлому разговору о том, обладают ли знания целеполаганием. Тогда я пришел к выводу, что. . .	Вот представьте что вам дали бессмертие. kumehtar 24.07.2026 Вот представьте что вам дали бессмертие, ничего более не меняя. Вообще ничего, только бессмертие в нынешнем виде. Рады были бы? Что бы вы тут делали всё это время? Никакой пенсии. Никакого нового. . .	сукцессия 41 anaschu 24.07.2026 Численная верификация бифуркации в агентной модели лесной сукцессии: от одного параметра к ансамблю Автор: пользователь @Shumilov_AS \| Раздел: Прикладная математика / Численные методы Кратко. . .	сукцессия 40. Ансамблевая кластерная параметризаци, часть 1. anaschu 24.07.2026 Пр# Сопровождение научной статьи ИИ-ассистентом: подготовка публикации и калибровка агентно-ориентированной модели сукцессии микоризных систем Полевые заметки о двухнедельной совместной работе. . .