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

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

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

Новые блоги и статьи Все статьи Все блоги /
Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .
Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .	Создание формы заимствованного документа Maks 03.08.2026 Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .	Задача предоставления скидок покупателям Maks 03.08.2026 Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .