Проблем със задача 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, който се намира в нея? 
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;
}
Идеята на @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, би ви вършил работа, но ви препоръчвам да ползвате някое от горните предложения.
А премливо ли е, след като прочетем първото число и знаем колко реда да очакваме да си създадем (динамично) масив от толкова на брой указатели, всеки от които да сочи към отделен масив (пак динамично заделен). И чрез един loop да си заредим с getline всеки от масивите. Зная ,че това е по-скоро C style подход но със сегашните познания е работещ вариант, поне за мен.
Да, но бих казал, че в случая е ненужно да държиш всичката памет заета до края на програмата - предвид, че само ще сумираш елементи, е достатъчно да четеш по един масив, да го обработваш (сумираш) и след това да освобождаваш паметта. Този масив няма да ти трябва след като го сумираш веднъж, така че няма смисъл да стои в паметта след това. Разбира се, пак трябва всеки един getline ред да го обработиш в тази parseNumbers функция, за да получиш pointer-а, който искаш да запазиш в масива от pointer-и (иначе няма как да знаеш предварително колко точно числа има на този ред и няма как да заделиш предварително за самите числа тази памет - но можеш да я заделиш за редовете, тоест за броя масиви, както ти предлагаш)
Но да, приемливо е, ще реши задачата - в интерес на истината алгоритъма може да се направи без масив изобщо, но идеята на задачата е да упражните заделяне на масив в една функция и използване в друга.
Да, съгласен съм, че за конкретното задание е малко безмислено да се съхранява целия масив. Виж ако трябваше да се сортират елементите би било оправдано.
Не е задължително да пресмятаме дължината на 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;
}
@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++; // Броячът е верен, но при следващото число ще сочи отново към чужда памет
}
Дори и програмата Ви да работи при тестове с по-малки масиви, подходът Ви е фундаментално грешен и няма да мине в по-сериозни програми.
При мен всичко работи много добре. Мога да дам целия код за дебъгване...
Но ето логиката, която следвам:
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++; // Броячът е верен, но при следващото число ще сочи отново към чужда памет. Едновременно брояч за индексите на масива и задаващ новия размер на масива!!
}
Къде се извиква многократно parseNumbers?
В кода, който сте постнали, тази функция се вика само веднъж (от main) и масива също се трие само веднъж (пак в main).
pArr[resultLength] = currentDigit; // Тук пишем в памет, която не принадлежи на pArr. Пишем в индекс 0 на масива, към който сочи пойнтера.
Всъщност, Вашият масив е инициализиран с 0 елемента и няма индекс 0.
resultLength++; // Броячът е верен, но при следващото число ще сочи отново към чужда памет. Едновременно брояч за индексите на масива и задаващ новия размер на масива!!
Къде според Вас в този код става това "ново задаване на размера на масива"?
В извикването чрез новия размер/индекс/присвояване: 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;
}
pArr[resultLength] = currentDigit;
Използването на по-голям индекс за адресиране на елемент, не увеличава размера на масива!
С по-голям индекс просто пишете извън паметта, която сте заделили за pArr при създаването му.
Освен това имате и грешка в логиката при определяне размера на масивите:
Първият го създавате с размер 0, вторият го създавате с размер, равен на числата, въведени за първия масив, третият - според броя на числата, въведени за втория и т.н.
Бих Ви препоръчал да прегледате отново и по-подробно материалите от лекцията за масиви и менажиране на паметта.
Аз пък си мислех, че динамичните масиви са именно такива - чиито размер може да се променя...
Аз ще прегледам, а защо ако Вие сте наясно, програмата работи без грешка? Пробвахте ли я? Как си го обяснявате?
Масиви, дефинирани с new се разполагат в динамичната памет, но това не означава, че са с динамичен размер.
Не съм пробвал програмата Ви, но както писах и по-горе, това че се компилира и не "гърми" при тестове с по-малко елементи, не я прави работеща.
В случая, най-вероятно пишете по клетки от паметта, които не се използват от кода на програмата Ви и затова не сте наблюдавали странични ефекти. С прилична доза увереност бих заявил, че при достатъчно голям брой елементи за първия масив, ще достигнете до адреси в паметта, промяната или достъпа до които ще доведе до проблеми.
Ето къде е проблемът. Аз точно така изтълкувах следното (черният шрифт е от мен):
(из С++ на разбираем език, Брайън Овърленд, София: Алекс Софт, 1999, стр.372)
Динамичния масив е вектор, той си заделя колкото му трябва капацитет и няма нужда да се грижиш за размера му. Когато казваш на компютъра че искаш масив - все едно дали е в диманичнат апамет или в стека ти му казваш "запази няколко поредни клетки в паметта" като той ти връща пойнтер към първата клетка. Масива ти всъщност адреса на този пойнтер - все едно дали е в динамичната памет или в стека.
За да ти запази обаче тази памет компютъра трябва да знае колко бита е. Заради това и при изглаждане на масив се казва какъв тип е масива, съответно компютъра си прави сметки колко е голяма една клетка памет за тази клетка и след това му трябва общия брой за тези клетки. Няма как да ти направи динамичен масив без това знание, защото клетките в масива са поредни и компютъра няма как да ти задели поредни клетки без да е наясно колко са.
Можеш много лесно да определиш какво става като накараш компютъра да ти разпечата реално физическите адреси в паметта. даваш в един цикъл cout<<&елемента на актива и ще ги видиш директно адресите и дали се променят когато увеличаваш масива
При вектора , компютъра просто заделя в началото един брой клетки - мисля че бяха четири. Следи колко са заделени и колко са запълнени и ако се запълнят просто заделя на ново място два пъти повече. Като копира всичко което е имало до сега в масива на новото място и ти връща пойнтер към това ново място.
Напълно невъзможно е без сам да алокираш нова памет и да копираш масива или без да използваш контейнер, който прави това вместо тебе да имаш масив който си променя дължината. Между другото кода ти поне при мен гърми в ран тайм.
@MartinBG е абсолютно прав! С "new" просто си заделяме "парче" памет и си взимаме указател към него. Нищо повече. То (парчето памет) не е "разтегливо" . Ако ти потрява по голямо "парче" - заделяш си НОВО и прехвърляш данните от СТАРОТО в НОВОТО, изтриваш СТАРОТО и пренасочваш указателя ти да сочи към НОВОТО. Това е. Общо взето, според моето лаишко мнение е, че това е по скоро "C" подход.При наличието на толкова по-подходящи контейнери (VECTOR, STACK) в C++ си е безмислено упражнение, освена ако не се пише за някаква embedded система със силно ограничени ресурси или се гони някаква пределна бързина.
Пасажа "броят на необходимите обекти може да бъде определян по време на изпълнение" трябва да се разглежда като обратното на "броя елементи трябва да е известен по време на компилиране" на програмата (т.е. хардкоднат; напр. int arr[10]).
В следващото изречение от пасажа изрично се казва, че трябва да се използва "new за създаване масив с по-големи размери", когато това е нужно. Т.е. ако имаме X елемента и по време на изпълненние на програмата се окаже, че ни трябва по-голям масив, тогава можем да си го създадем с new (и евентуално да копираме съдържанието на текущия плюс новите данни, преди да изтрием стария масив). Разгледайте SmartArray класа, който georgi.stef.georgiev написа на последната лекция - там има методи, които правят точно това.
Алтернативно за "динамични" масиви (т.е. такива, с чиито размер не се занимаваме директно), може да се използва и vector, за който вече няколко пъти стана дума по време на лекциите.
Пробвах го. Точно през 4 байта са.
Ами в случая използвам new, който е добро нововъведение в С++.
Те винаги ще са през четири байта ако иползваш инт. Виж като увеличаваш масива дали ти се променят адресите на първите променливи. Ако не ти се променят адресите, значи компютъра не ти заделя нова памет а записва по-големите масиви върху памет, която не е твоя. И нещо много яко може да гръмне.
Не го разбирам така. Според мен ако ползваме същото име на масив и му зададем по-голям размер, new ще запази всичко, а ще промени само размера. В една от лекциите Жоро каза, че не е гарантирано, дали new винаги ще може да задели исканата памет. Точно така си обяснявам защо този метод е ненадежден и е дал runtime error на @ IvanMitkov.
#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 << " ";
}
пусни да видиш какво става с адресите при вектора.
В "C" това го прави malloc и calloc(който дори ти занулява върнатата памет).
Гърми защото пипа памет там където не му е работа, и очевидно моя компилатор е доста по параноичен от твоя :)
Мдаа... като увеличавам не ги променя; като намалявам ги променя...
мдаа... при вектора след добавянето са различни...