C# MVC Frameworks - ASP.NET Core - юли 2018
Loading...
AndonAndonov avatar AndonAndonov 1 Точки

Проблем със задача 8 от C++ Programming - февруари 2017

8. Write a function 
int * parseNumbers(const string& str, int& resultLength) which returns a pointer to new-allocated array with the numbers parsed from str (assume you don’t need to handle wrongly-formatted input). str will contain integer numbers separated by spaces. The function writes the length of the allocated array in resultLength. Write a program which lets the user enter a number of lines of integers from the console, and prints their sum. Use the parseNumbers function in your program, but make sure you delete each array once you’re done with it.
Example input (note: first line is the count of lines of numbers, in this case: 2 lines):
2
1 2 3
4 5
Expected output (sum of 1 2 3 and 4 5): 15


Въпросът ми е как едновременно да създам stringstream oт потребителския стринг с данни str във функцията int * parseNumbers(const string& str, int& resultLength) и като викам същата функция да й подам параметър за размера на stringstream, който се намира в нея? blush

int * parseNumbers(const string& str, int& resultLength)
{
    int *userInputNums = new int[resultLength];
    stringstream userInputStream(str);
    
    int size = 0;
    
    while(1)
    {
        int i;
        userInputStream >> i;
        if (!userInputStream)
        {break;}
        ++size;
    }
    
    for (int i = 0; i < resultLength; i++)
    {
        userInputStream >> userInputNums[i];
    }
    return userInputNums;
}

Тагове:
0
C++ Programming 12/03/2017 18:59:12
MartinBG avatar MartinBG 791 Точки
Best Answer

Аз разбирам условието така:

parseNumbers приема като параметър const string& str, който съдържа неизвестен към момента брой числа от тип int.

Във функцията трябва да се определи броя на числата в стринга (аз използвам друга функция за целта, която прави само това), който се запазва (и връща по-късно) чрез int& resultLength. След като е извесетен броя елементи, се създава нов масив (int * pArr = new int[resultLength];) и се попълва с числата от const string& str. Накрая се връща указател към масива (int * parseNumbers(...)), заедно с броя елементи в него (int& resultLength).

Масива трябва да се изтрие по-късно в main():

int* pArr = parseNumbers(str, resultLength);

...

delete [] pArr;

1
12/03/2017 14:02:10
georgi.stef.georgiev avatar georgi.stef.georgiev 916 Точки

Идеята на @MartinBg е вярната (можете да му маркирате отговорa му за верен и да го upvote-нете). Ето малко разяснения от мен.

Стандартния подход за "връщане" на масив от функция (без да се ползват vector или други stl контейнери, за които все още не сме учили) е да върнеш pointer към динамично заделен масив (заделен с new тоест) - но понеже трябва да знаеш и размера на този масив, за да го използваш от викащия код, отделно в една референция записваш колко се получава да е дълъг. Пример за код, който вика тази функция и принтира елементите на масива ред по ред би изглеждал така:

string input;

cin >> input;

int parsedLength; //we expect parseNumbers to set the value of this

int * parsed = parseNumbers(input, parsedLength)

for (int i = 0; i < parsedLength; i++) {

    cout << parsed[i] << endl;

delete[] parsed;

}

Един прост начин да знаете колко памет да заделите в parseNumbers е два пъти подред да направите stringstream по input-а - както правихме в едно от демата за stringstream (това с HTML output-а) - първия път само броите колко числа сте прочели, след това заделяте масив с тази големина, след това минавате пак по input-а със stringstream и тогава вече записвате числата по съответните позиции в масива. Това не е най-ефикасния метод, но е приемлив за тази задача.

Най-добрия вариант е да преброите числата на базата на space-овете пред тях (обърнете внимание, че в задачата изрично пише, че числата са разделени със space, тоест всеки два поредни символа, първия от които е space, а за втория isdigit връща true, e число (не забравяйте да преброите и първото число). Не е достатъчно да преброите само space-овете, защото задачата не гарантира, че числата са разделени само с по един space (тоест това е валиден вход: 1 3    7 13).

Има и трети, "по-напреднал" вариант, който ако се замислите добре можете да го постигнете със знанията дотук, ако на някой му се занимава - проучете как горе-долу работи vector в C++, или List в C#, или ArrayList в Java (един и същ принцип стои зад тях).

Поздрави,

Жоро

 

Edit: демо 19 от лекцията (за което нямахме време на самата лекция) ползва същата концепция - само че то връща string* към динамично заделен масив. И там заделянето на памет нарочно е направено с лош performance, за да е ясно как може да се заделят и освобождават в една функция много масиви (има коментар с подробности там) - подобен на този код, само че за int, би ви вършил работа, но ви препоръчвам да ползвате някое от горните предложения.

0
12/03/2017 15:22:58
Dimitar_Petkov_Petkov avatar Dimitar_Petkov_Petkov 156 Точки

А премливо ли е, след като прочетем първото число и знаем колко реда да очакваме да си създадем (динамично) масив от толкова на брой указатели, всеки от които да сочи към отделен масив (пак динамично заделен). И чрез един loop да си заредим с getline всеки от масивите. Зная ,че това е по-скоро C style подход но със сегашните познания е работещ вариант, поне за мен.

0
georgi.stef.georgiev avatar georgi.stef.georgiev 916 Точки

Да, но бих казал, че в случая е ненужно да държиш всичката памет заета до края на програмата - предвид, че само ще сумираш елементи, е достатъчно да четеш по един масив, да го обработваш (сумираш) и след това да освобождаваш паметта. Този масив няма да ти трябва след като го сумираш веднъж, така че няма смисъл да стои в паметта след това. Разбира се, пак трябва всеки един getline ред да го обработиш в тази parseNumbers функция, за да получиш pointer-а, който искаш да запазиш в масива от pointer-и (иначе няма как да знаеш предварително колко точно числа има на този ред и няма как да заделиш предварително за самите числа тази памет - но можеш да я заделиш за редовете, тоест за броя масиви, както ти предлагаш)

Но да, приемливо е, ще реши задачата - в интерес на истината алгоритъма може да се направи без масив изобщо, но идеята на задачата е да упражните заделяне на масив в една функция и използване в друга.

0
Dimitar_Petkov_Petkov avatar Dimitar_Petkov_Petkov 156 Точки

Да, съгласен съм, че за конкретното задание е малко безмислено да се съхранява целия масив. Виж ако трябваше да се сортират елементите би било оправдано.

0
zzerro avatar zzerro 11 Точки

Не е задължително да пресмятаме дължината на new масива преди да го създадем. Можем да го инициализираме с нулев размер в началото и после динамично да го променяме с извикване+присвояване в самото му обхождане. Мисля, че това е проблемът в някои домашни. Затова не им работи 9-та задача, защото се опитват да пресметнат и зададат предварително размера, а не го актулизират динамично. Ето какво имам предвид:

...

int main()

{

int resultLenght = 0;

...

int* mainParr = parseNumbers(str, resultLength);

...

delete [] mainParr;

}
int * parseNumbers(const string& str, int& resultLength)
{
    int* pArr = new int[resultLength];

    istringstream digitsStr (str);
    int currentDigit = 0;
    resultLength = 0;
    while (digitsStr >> currentDigit)
        {
            pArr[resultLength] = currentDigit;
            resultLength++;
        }

    return pArr;
}

0
24/03/2017 09:16:37
MartinBG avatar MartinBG 791 Точки

@zzerro 

На пръв поглед забелязвам следните проблеми в предложения код:

 

int resultLenght = 0; // Задаване на размера на масива - 0 - ОК

...

int* mainParr = parseNumbers(str, resultLength); // Подаване на нулев размер - ОК 

...

int * parseNumbers(const string& str, int& resultLength)
{

int* pArr = new int[resultLength];  // Създаване на пойнтър към масив с 0 int елемента

...

resultLength = 0; // Отново сетваме размера на масива на 0 - излишно, защото размера е подаден от main() и грешно, ако очакваме да не е подаден от main() - в този случай трябва да го инициализираме във функцията, преди да го използваме за първи път (т.е. преди да създадем pArr);

...

    while (digitsStr >> currentDigit)
        {
            pArr[resultLength] = currentDigit;
// Тук пишем в памет, която не принадлежи на pArr
            resultLength++; // Броячът е верен, но при следващото число ще сочи отново към чужда памет
        }

 

Дори и  програмата Ви да работи при тестове с по-малки масиви, подходът Ви е фундаментално грешен и няма да мине в по-сериозни програми.

 

 

 

0
24/03/2017 10:02:53
zzerro avatar zzerro 11 Точки

При мен всичко работи много добре. Мога да дам целия код за дебъгване...

Но ето логиката, която следвам:

int resultLenght = 0; // Задаване на размера на масива - 0 - ОК. Това е само за първото извикване.

...

int* mainParr = parseNumbers(str, resultLength); // Подаване на нулев размер - ОК 

...

int * parseNumbers(const string& str, int& resultLength)
{

int* pArr = new int[resultLength];  // Създаване на пойнтър към масив с 0 int елемента

...

resultLength = 0; // Отново сетваме размера на масива на 0 - излишно, защото размера е подаден от main() и грешно, ако очакваме да не е подаден от main() - в този случай трябва да го инициализираме във функцията, преди да го използваме за първи път (т.е. преди да създадем pArr); Необходимо е, защото ще следват многократни извиквания и след последното  изтриване трябва да се инициализира наново.

...

    while (digitsStr >> currentDigit)
        {
            pArr[resultLength] = currentDigit;
 // Тук пишем в памет, която не принадлежи на pArr. Пишем в индекс 0 на масива, към който сочи пойнтера.
            resultLength++; // Броячът е верен, но при следващото число ще сочи отново към чужда памет. Едновременно брояч за индексите на масива и задаващ новия размер на масива!!
        }

0
24/03/2017 10:49:49
MartinBG avatar MartinBG 791 Точки

Къде се извиква многократно parseNumbers?

В кода, който сте постнали, тази функция се вика само веднъж (от main) и масива също се трие само веднъж (пак в main).

             pArr[resultLength] = currentDigit; // Тук пишем в памет, която не принадлежи на pArr. Пишем в индекс 0 на масива, към който сочи пойнтера.

Всъщност, Вашият масив е инициализиран с 0 елемента и няма индекс 0.


            resultLength++; // Броячът е верен, но при следващото число ще сочи отново към чужда памет. Едновременно брояч за индексите на масива и задаващ новия размер на масива!!

Къде според Вас в този код става това "ново задаване на размера на масива"?

0
zzerro avatar zzerro 11 Точки

В извикването чрез новия размер/индекс/присвояване: pArr[resultLength] = currentDigit;

Но ето го целия код, за да не изпадаме в излишни обяснения:

#include<iostream>
#include<sstream>
#include<stdio.h>
using namespace std;

int * parseNumbers(const string& str, int& resultLength);

int main()
{
    int numInputLines, resultLength = 0, sum = 0;
    string str;

    cout << "How many lines you want to sum: ";
    cin >> numInputLines;
    getchar(); // To clean the '\n' char from input buffer for getline().

    for (int i = 1; i <= numInputLines; i++)
        {
            switch (i)
                {
                    case 1: cout << "Enter integers for the 1st line (separated by space): "; break;
                    case 2: cout << "Enter integers for the 2nd line: "; break;
                    default: cout << "Enter integers for the "<< i << "th line: ";
                }
            cout << endl;
            getline (cin, str);

            int* mainParr = parseNumbers(str, resultLength);

            for (int i = 0; i < resultLength; i++)
                {
                    sum = sum + mainParr[i];
                }

            delete [] mainParr; // Delete pointer for the next line input loop.
        }

    cout << endl << "The sum is: " << sum << endl;

    return 0;
}

int * parseNumbers(const string& str, int& resultLength)
{
    int* pArr = new int[resultLength];

    istringstream digitsStr (str);
    int currentDigit = 0;
    resultLength = 0;
    while (digitsStr >> currentDigit)
        {
            pArr[resultLength] = currentDigit;
            resultLength++;
        }

    return pArr;
}

0
24/03/2017 13:55:15
MartinBG avatar MartinBG 791 Точки

pArr[resultLength] = currentDigit;

Използването на по-голям индекс за адресиране на елемент, не увеличава размера на масива!

С по-голям индекс просто пишете извън паметта, която сте заделили за pArr при създаването му.

Освен това имате и грешка в логиката при определяне размера на масивите:

Първият го създавате с размер 0, вторият го създавате с размер, равен на числата, въведени за първия масив, третият - според броя на числата, въведени за втория и т.н.

Бих Ви препоръчал да прегледате отново и по-подробно материалите от лекцията за масиви и менажиране на паметта.

 

 

0
24/03/2017 14:10:07
zzerro avatar zzerro 11 Точки

Използването на по-голям индекс за адресиране на елемент, не увеличава размера на масива!

Аз пък си мислех, че динамичните масиви са именно такива - чиито размер може да се променя...

Бих Ви препоръчал да прегледате отново и по-подробно материалите от лекцията за масиви и менажиране на паметта.

Аз ще прегледам, а защо ако Вие сте наясно, програмата работи без грешка? Пробвахте ли я? Как си го обяснявате?

0
MartinBG avatar MartinBG 791 Точки

Масиви, дефинирани с new се разполагат в динамичната памет, но това не означава, че са с динамичен размер.

Не съм пробвал програмата Ви, но както писах и по-горе, това че се компилира и не "гърми" при тестове с по-малко елементи, не я прави работеща.

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

0
zzerro avatar zzerro 11 Точки

 ...в динамичната памет, но това не означава, че са с динамичен размер....

Ето къде е проблемът. Аз точно така изтълкувах следното (черният шрифт е от мен):

Операторът new създава динамично един или повече обекти и връща указател към този обект(или първия обект, ако създавате масив). В този контекст "динамично" означава, че броят на необходимите обекти може да бъде определян по време на изпълнение. Например, ако започнете да увеличавате размера на масив, можете да използвате new за създаване масив с по-големи размери.

(из С++ на разбираем език, Брайън Овърленд, София: Алекс Софт, 1999, стр.372)

0
24/03/2017 15:20:57
IvanMitkov avatar IvanMitkov 19 Точки

Динамичния масив е вектор, той си заделя колкото му трябва капацитет и няма нужда да се грижиш за размера му. Когато казваш на компютъра че искаш масив - все едно дали е в диманичнат апамет или в стека ти му казваш "запази няколко поредни клетки в паметта" като той ти връща пойнтер към първата клетка. Масива ти всъщност адреса на този пойнтер - все едно дали е в динамичната памет или в стека.

За да ти запази обаче тази памет компютъра трябва да знае колко бита е. Заради това и при изглаждане на масив се казва какъв тип е масива, съответно компютъра си прави сметки колко е голяма една клетка памет за тази клетка и след това му трябва общия брой за тези клетки. Няма как да ти направи динамичен масив без това знание, защото клетките в масива са поредни и компютъра няма как да ти задели поредни клетки без да е наясно колко са.

Можеш много лесно да определиш какво става като накараш компютъра да ти разпечата реално физическите  адреси в паметта. даваш в един цикъл cout<<&елемента на актива и ще ги видиш директно адресите и дали се променят когато увеличаваш масива

При вектора , компютъра просто заделя в началото един брой клетки - мисля че бяха четири. Следи колко са заделени и колко са запълнени и ако се запълнят просто заделя на ново място два пъти повече. Като копира всичко което е имало до сега в масива на новото място и ти връща пойнтер към това ново място.

Напълно невъзможно е без сам да алокираш нова памет и да копираш масива или без да използваш контейнер, който прави това вместо тебе да имаш масив който си променя дължината. Между другото кода ти поне при мен гърми в ран тайм.

 

0
Dimitar_Petkov_Petkov avatar Dimitar_Petkov_Petkov 156 Точки

@MartinBG е абсолютно прав! С "new" просто си заделяме "парче" памет и си взимаме указател към него. Нищо повече. То (парчето памет) не е "разтегливо" . Ако ти потрява по голямо "парче" - заделяш си НОВО и прехвърляш данните от СТАРОТО в НОВОТО,  изтриваш СТАРОТО и пренасочваш указателя ти да сочи към НОВОТО. Това е. Общо взето, според моето лаишко мнение е, че това е по скоро "C" подход.При  наличието на толкова по-подходящи контейнери (VECTOR, STACK)  в C++ си е безмислено упражнение, освена ако не се пише за някаква embedded система със силно ограничени ресурси или се гони някаква пределна бързина.

0
MartinBG avatar MartinBG 791 Точки

Пасажа "броят на необходимите обекти може да бъде определян по време на изпълнение" трябва да се разглежда като обратното на "броя елементи трябва да е известен по време на компилиране" на програмата (т.е. хардкоднат; напр. int arr[10]).

В следващото изречение от пасажа изрично се казва, че трябва да се използва "new за създаване масив с по-големи размери", когато това е нужно. Т.е. ако имаме X елемента и по време на изпълненние на програмата се окаже, че ни трябва по-голям масив, тогава можем да си го създадем с new (и евентуално да копираме съдържанието на текущия плюс новите данни, преди да изтрием стария масив). Разгледайте SmartArray класа, който georgi.stef.georgiev написа на последната лекция - там има методи, които правят точно това.

Алтернативно за "динамични" масиви (т.е. такива, с чиито размер не се занимаваме директно), може да се използва и vector, за който вече няколко пъти стана дума по време на лекциите.

0
zzerro avatar zzerro 11 Точки

Можеш много лесно да определиш какво става като накараш компютъра да ти разпечата реално физическите  адреси в паметта. даваш в един цикъл cout<<&елемента на актива и ще ги видиш директно адресите и дали се променят когато увеличаваш масива

Пробвах го. Точно през 4 байта са.

0
zzerro avatar zzerro 11 Точки

...То (парчето памет) не е "разтегливо" . Ако ти потрява по голямо "парче" - заделяш си НОВО и прехвърляш данните от СТАРОТО в НОВОТО,  изтриваш СТАРОТО и пренасочваш указателя ти да сочи към НОВОТО...това е по скоро "C" подход.При  наличието на толкова по-подходящи контейнери (VECTOR, STACK)  в C++ си е безмислено ...

Ами в случая използвам new, който е добро нововъведение в С++.

0
24/03/2017 15:45:58
IvanMitkov avatar IvanMitkov 19 Точки

Те винаги ще са през четири байта ако иползваш инт. Виж като увеличаваш масива дали ти се променят адресите на първите променливи. Ако не ти се променят адресите, значи компютъра не ти заделя нова памет а записва по-големите масиви върху памет, която не е твоя. И нещо много яко може да гръмне.

0
zzerro avatar zzerro 11 Точки

... Т.е. ако имаме X елемента и по време на изпълненние на програмата се окаже, че ни трябва по-голям масив, тогава можем да си го създадем с new (и евентуално да копираме съдържанието на текущия плюс новите данни, преди да изтрием стария масив)...

Не го разбирам така. Според мен ако ползваме същото име на масив и му зададем по-голям размер, new ще запази всичко, а ще промени само размера. В една от лекциите Жоро каза, че не е гарантирано, дали new винаги ще може да задели исканата памет. Точно така си обяснявам защо този метод е ненадежден и е дал runtime error на @ IvanMitkov.

0
24/03/2017 15:51:58
IvanMitkov avatar IvanMitkov 19 Точки

#include<iostream>
#include<vector>
using namespace std;

 

int main()
{
    vector<int>vec = { 1,2,3 };
    for (auto a : vec)cout << &a << " ";
    vec.push_back(5);
    vec.push_back(5);
    cout << endl;
    for (auto a : vec)cout << &a << " ";
}

пусни да видиш какво става с адресите при вектора.

0
Dimitar_Petkov_Petkov avatar Dimitar_Petkov_Petkov 156 Точки

В "C" това го прави malloc и calloc(който дори ти занулява върнатата памет).

0
IvanMitkov avatar IvanMitkov 19 Точки

Гърми защото пипа памет там където не му е работа, и очевидно моя компилатор е доста по параноичен от твоя :)

0
zzerro avatar zzerro 11 Точки

...Виж като увеличаваш масива дали ти се променят адресите на първите променливи. Ако не ти се променят адресите, значи компютъра не ти заделя нова памет а записва по-големите масиви върху памет, която не е твоя...

Мдаа... като увеличавам не ги променя; като намалявам ги променя...

0
24/03/2017 16:03:53
zzerro avatar zzerro 11 Точки

мдаа... при вектора след добавянето са различни...

0
24/03/2017 16:15:17