Map doesn't store values in recursion

Question

I do not know why but when recursion tries to add value and then to return it that map after return of function deletes all elements, I do not understand in what a problem.

static int SumNum(string target, string m[], map<string, int> memo = {}){

        if (memo.find(target) != memo.end()) {
            cout << memo.find(target)->second<<"\n";
            return memo.find(target)->second;
        }
        if (target == "") return 1;

        int totalCount = 0;
        
    for(auto i = 0;i < 10; i++)
    {   
        if (target.find(m[i]) == 0){
            
            int numOfWays = SumNum(target.substr(m[i].length()),m,memo);
            totalCount += numOfWays;
            
        }
    }
    memo.emplace(target, totalCount);
    return totalCount;
}
int main(){
    string ar[10] = {"e","ee","eee","eeee","eeeee","eeeeee","f","fdc","d","c"};
    string target = "eeeeeeeeefdc";
    auto answer = SumNum(target,ar);
    cout << answer;
}

Do you know the difference between passing parameters by value versus by reference? — Sam Varshavchik, Oct 24 '21 at 23:29
references are a basic and fundamental concept in C++. You should read a good C++ book [The Definitive C++ Book Guide and List](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) — bolov, Oct 24 '21 at 23:47
@skamer *"but i need solution it now"* -- your emergency is not our emergency. Please see [Under what circumstances may I add "urgent" or other similar phrases to my question, in order to obtain faster answers?](//meta.stackoverflow.com/q/326569) and be aware that the primary purpose of SO is to provide a resource for *future* visitors. It's just a pleasant side-effect when the person asking the question also benefits. — JaMiT, Oct 24 '21 at 23:53
@skamer people already told you how to do it, just pass the map by reference, instead of by value. SO is not a place for people to write the code for you, is for them to help you know the answers to problems you tried alone and wasn't able to. — Gvinfinity, Oct 24 '21 at 23:59
Does this answer your question? [How to set value of a variable in C++ when it's not in global scope and used in custom function?](https://stackoverflow.com/questions/25338167/how-to-set-value-of-a-variable-in-c-when-its-not-in-global-scope-and-used-in) — JaMiT, Oct 25 '21 at 00:04

justANewb stands with Ukraine · Answer 1 · 2021-10-27T06:43:51.483

I think that @Max meant this:

static int SumNum(std::string target, std::string m[], std::map<std::string, int>& memo /* pass by reference */){

        if (memo.find(target) != memo.end()) {
            std::cout << memo.find(target)->second<<"\n";
            return memo.find(target)->second;
        }
        if (target == "") return 1;

        int totalCount = 0;
        
    for(auto i = 0;i < 10; i++)
    {   
        if (target.find(m[i]) == 0){
            
            int numOfWays = SumNum(target.substr(m[i].length()),m,memo);
            totalCount += numOfWays;
            
        }
    }
    memo.emplace(target, totalCount);
    return totalCount;
}
int main(){
    std::map <std::string, int> map;
    std::string ar[10] = {"e","ee","eee","eeee","eeeee","eeeeee","f","fdc","d","c"};
    std::string target = "eeeeeeeeefdc";
    auto answer = SumNum(target, ar, map);
    std::cout << answer;
}

it doesn't work , you need to initialize map,compilator is said it — skamer, Oct 25 '21 at 20:13

score -3 · Answer 2 · edited Oct 25 '21 at 00:21

-3

thanks @Max i did like you say

static int SumNum(string target, string m[], map<string, int> *memo = new map<string, int>()) {
        
        if (memo->find(target) != memo->end()) {
            cout << memo->find(target)->second<<"\n";
            return memo->find(target)->second;
        }
        if (target == "") return 1;

        int totalCount = 0;
        
    for(auto i = 0;i < 10; i++)
    {   
        if (target.find(m[i]) == 0){
            
            int numOfWays = SumNum(target.substr(m[i].length()),m,memo);
            totalCount += numOfWays;
            
        }
    }
    memo->emplace(target, totalCount);
    return totalCount;
}
int main(){
    string ar[10] = {"e","ee","eee","eeee","eeeee","eeeeee","f","fdc","d","c"};
    string target = "eeeeeeeeeeeeefdc";
    auto answer = SumNum(target,ar);
    cout << answer;
}

edited Oct 25 '21 at 00:21

JaMiT

14,422
4
15
31

answered Oct 25 '21 at 00:06

skamer

1
2

4

Your code leaks memory (and does not do what Max suggested). When you use the default parameter, a map is created with `new` but never `delete`d. The suggestion was to use a reference, not to use a pointer. (Using a pointer would be the C way to "pass by reference", but you are using C++. C++ uses references.) – JaMiT Oct 25 '21 at 00:22
@skamer Please run the code with `valgrind` and fix the errors it will point out. (It will give you the exact line numbers and useful memory management hints with a `-g`-compiled binary.) What you have in the answer looks like a memory management disaster. – Andrej Podzimek Oct 25 '21 at 02:30
i see you are from Poland ,can we contact ? – skamer Oct 25 '21 at 20:15
it is disaster but i am only beginning to studying – skamer Oct 25 '21 at 20:20
==8896== LEAK SUMMARY: ==8896== definitely lost: 0 bytes in 0 blocks ==8896== indirectly lost: 0 bytes in 0 blocks ==8896== possibly lost: 0 bytes in 0 blocks ==8896== still reachable: 1,766 bytes in 55 blocks ==8896== suppressed: 0 bytes in 0 blocks ==8896== ==8896== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) – skamer Oct 25 '21 at 23:40
is that ok test? – skamer Oct 25 '21 at 23:41

Map doesn't store values in recursion

2 Answers2