Thread: Memory failures in C++ maps

  1. #1
    Registered User FortranLevelC++'s Avatar
    Join Date
    May 2013
    Location
    United States
    Posts
    81

    Memory failures in C++ maps

    I noticed that there is a certain danger when we use the C++ maps to look up a key that was missing. When a missing key is looked up from a map, this actually affects the size() of the map, leading to unexpected secondary bugs when this map is later used again.

    Here is a test code and its output to visualize what is going on:



    Code:
    #include <stdio.h>      
    #include <stdlib.h>  
    #include <iomanip>
    #include <fstream>
    #include <iostream>
     #include <cstring>
    #include <sstream>
    #include <string>
    #include <string.h>
    
    
    #include <vector>
    #include <map>
    
    
    using namespace std;
    
    
    
    
    map<string, int> testMap;
    
    
    int main()
    {    
        
    
    
        testMap["a"]=4;
        testMap["b"]=5;
        testMap["c"]=6;
        testMap["d"]=7;
        testMap["e"]=8;
        testMap["f"]=9;
        testMap["g"]=10;
        testMap["h"]=11;
        testMap["k"]=12;
        testMap["l"]=13;
        
        vector<string> vec_st;
            
        
        vec_st.push_back("a");
        vec_st.push_back("b");
        vec_st.push_back("c");
        vec_st.push_back("d");
        vec_st.push_back("e");
        vec_st.push_back("f");
        vec_st.push_back("g");
        vec_st.push_back("h");
        vec_st.push_back("k");
        vec_st.push_back("l");
    
    
        
            
        int firstSize = testMap.size();
        cout << "Before the search for missing key m, we have testMap.size() = " << firstSize << endl;
        cout << "Values of the map before the attempt to look up missing key: " << endl;
        for(int i=0; i < testMap.size(); i++)
        {
            cout << "testMap[vec_st["<<i<<"] ] = " << testMap[vec_st[i] ] << endl;
        }
        
        string s = "m";
        int j2 = testMap[s] ; // Questionable attempt to find a missing key's value
        cout << "s = " << s << " , but after this questionable lookup of s, we get testMap[s] = " << j2 << endl;
    
    
        int secondSize = testMap.size();
        cout << "Size AFTER the search for missing key m = " << secondSize << endl;
        cout << " After the attempt to look up a missing key we get: " << endl;
    
    
        for(int i=0; i< testMap.size(); i++)
        {
            cout << "testMap[vec_st["<<i<<"] ] = " << testMap[vec_st[i] ]<< endl;
        }
    
    
        // Better safeguard: use the ::count() function to check that the key exists in the first place:
        // Write: if(testMap.count(s) >0) { j2=testMap[s] ; }
        
    
    
    }
    Here is the output that shows that the attempt to look up a missing key results in the alteration of the size of the map, an alteration of the memory:

    Before the search for missing key m, we have testMap.size() = 10
    Values of the map before the attempt to look up missing key:
    testMap[vec_st[0] ] = 4
    testMap[vec_st[1] ] = 5
    testMap[vec_st[2] ] = 6
    testMap[vec_st[3] ] = 7
    testMap[vec_st[4] ] = 8
    testMap[vec_st[5] ] = 9
    testMap[vec_st[6] ] = 10
    testMap[vec_st[7] ] = 11
    testMap[vec_st[8] ] = 12
    testMap[vec_st[9] ] = 13
    s = m , but after this questionable lookup of s, we get testMap[s] = 0
    Size AFTER the search for missing key m = 11
    After the attempt to look up a missing key we get:
    testMap[vec_st[0] ] = 4
    testMap[vec_st[1] ] = 5
    testMap[vec_st[2] ] = 6
    testMap[vec_st[3] ] = 7
    testMap[vec_st[4] ] = 8
    testMap[vec_st[5] ] = 9
    testMap[vec_st[6] ] = 10
    testMap[vec_st[7] ] = 11
    testMap[vec_st[8] ] = 12
    testMap[vec_st[9] ] = 13
    Segmentation fault (core dumped)
    Last edited by FortranLevelC++; 05-23-2013 at 09:23 PM.

  2. #2
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    O_o

    Maybe you should abandon "Fortran Level C++" and just stick with "C++ Level C++"? ^_^;

    This is the intended result of your code.

    If you want to check if a value with an associated key exists in a `std::map<???, ???>' object use `iterator std::map<???, ???>::find(const key_type &)'.

    Soma

    Code:
    testMap.find("m");

  3. #3
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    Code:
    string s = "m";
    int j2 = testMap[s];
    If testMap["m"] does not exist, this will create an entry in the map for that key value thus increasing the size. The value portion of the map for that key gets default initialized, which in the case of an integer means the value of 0. If you don't want to actually create an element, then you do as suggested above.

    You then get the segmentation fault because the size of the map is greater than the size of the vector by 1 element. When you try to loop, you access vec_st[i] for an index i of vec_st that does not exist.

    Code:
    #include <stdio.h>     
    #include <stdlib.h> 
    ...
    #include <string.h>
    The C++ versions of those header files drop the ".h" part and add a "c" to the front meaning they would be:
    Code:
    #include <cstdio>     
    #include <cstdlib> 
    ...
    #include <cstring>
    You've already got a <cstring> in there once. Your program as written does not make use of anything from these headers so they can be safely removed. Also, your current code does not make use of anything that would require the <sstream>, <iomanip>, or <fstream> headers. All you should need based on the observable code are the following:
    Code:
    #include <iostream>
    #include <string>
    #include <vector>
    #include <map>
    Last edited by hk_mp5kpdw; 05-24-2013 at 06:19 AM.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  4. #4
    Registered User FortranLevelC++'s Avatar
    Join Date
    May 2013
    Location
    United States
    Posts
    81
    Quote Originally Posted by hk_mp5kpdw View Post
    Code:
    string s = "m";
    int j2 = testMap[s];
    If testMap["m"] does not exist, this will create an entry in the map for that key value thus increasing the size. The value portion of the map for that key gets default initialized, which in the case of an integer means the value of 0. If you don't want to actually create an element, then you do as suggested above.

    You then get the segmentation fault because the size of the map is greater than the size of the vector by 1 element. When you try to loop, you access vec_st[i] for an index i of vec_st that does not exist.


    [/code]
    Many thanks for the explanation. I now see that even an attempt to access a missing key is causing the map to create an entry for this missing key, but I am still a little bit surprised because I did not make an assignment statement to the second element of the map, I only entered the first (left) element in my code.

    By contrast, when we use a C++ array instead of a map, this time if we try to access an element of the array that is missing, this still does not seem to change the size of the array..

    I wrote the following test code to illustrate this comparison, including the use of the map.find() function that you recommended. The output of the program is also listed after the code:


    Code:
    
    #include <stdio.h>      
    #include <iostream>
    #include <string>
    #include <vector>
    #include <map>
    #include <array>
    
    
    using namespace std;
    
    
    map<string, int> testMap;
    
    
    int main()
    {    
        array<double,5> my_array;
    
    
        for(int i=0; i<5; i++) my_array[i]=i+1; // Initialize
    
    
        testMap["a"]=4;
        testMap["b"]=5;
        testMap["c"]=6;
        testMap["d"]=7;
        testMap["e"]=8;
        testMap["f"]=9;
        testMap["g"]=10;
        testMap["h"]=11;
        testMap["k"]=12;
        testMap["l"]=13;
        
        
        int firstSize = testMap.size();
        cout << "Before the search for missing key m, we have testMap.size() = " << firstSize << endl;
            
        string s1, s2;
        s2 = "m";
        s1 = "a";
    
    
        int j1, j2;
        
        if(testMap.find(s2) == testMap.end() )
        {
            cout << "Key s2 = " << s2 << " is missing, so we don't try to access that element!" << endl;
        }
        else
        {
            j2 = (testMap.find(s2))->second;
            cout << "s2 = " << s2
                << "But after this questionable lookup of s2, we get testMap[2] = " 
                    << j2 << endl;
            cout << "And currently testMap.size()  = " << testMap.size() << endl;
    
    
        }
    
    
        if( testMap.find(s1) != testMap.end() )
        {
            j1 = (testMap.find(s1))->second;
            cout << "s1 = " << s1 
                << " ,and after this acceptable lookup of s1 we get testMap[s1] = " 
                    << j1 << endl;
            cout << "And currently we still have testMap.size()  = " << testMap.size() << endl << endl ;
        }
        
        
        // Other possible safeguard: use the ::count() function to check that the key exists in the fist place:
        // Write: if(testMap.count(s) >0) { j2=testMap[s] ; }
    
    
          cout << "Here is the result of the same code written with the count() function instead of find():" << endl;
        if(testMap.count(s2) < 1)
        {
            cout << "Key s2 = " << s2 << " is missing so we don't try to access that element!" << endl;
        }
        else
        {
            j2 = (testMap.find(s2))->second;
            cout << "s2 = " << s2
                << "But after this questionable lookup of s2, we get testMap[2] = " 
                    << j2 << endl;
            cout << "And currently testMap.size()  = " << testMap.size() << endl;
    
    
        }
    
    
        if( testMap.count(s1) > 0 )
        {
            j1 = (testMap.find(s1))->second;
            cout << "s1 = " << s1 
                << " ,and after this acceptable lookup of s1 we get testMap[s1] = " 
                    << j1 << endl;
            cout << " And currently testMap.size()  = " << testMap.size() << endl<< endl ;
        }
        
        cout << "But finally we note that the size of a map changes if we access a missing key: " << endl;
        j2 = testMap[s2] ; // Questionable attempt to find a missing key's value
        cout <<"After this questionable attempt j2 = testMap[s2], testMap.size() = " 
            << testMap.size() << endl<< endl;
        
        cout << "Now we test what happens to a C++ array size if we try to access an element that doesn't exist:" 
                << endl;
    
    
        double x = my_array[7];
        cout << "Size of my_array despite trying to access a missing element remains: " << my_array.size() << endl;
        cout << "But x= " << x << endl;
            
        cout << "But despite this questionable attempt to access a missing element we still have my_array: "<< endl;
        for( auto it= my_array.begin(); it != my_array.end(); ++it)
        {
            cout << *it << endl;
        }
    
    
    
    
    }
    OUTPUT :

    Before the search for missing key m, we have testMap.size() = 10
    Key s2 = m is missing, so we don't try to access that element!
    s1 = a ,and after this acceptable lookup of s1 we get testMap[s1] = 4
    And currently we still have testMap.size() = 10


    Here is the result of the same code written with the count() function instead of find():
    Key s2 = m is missing so we don't try to access that element!
    s1 = a ,and after this acceptable lookup of s1 we get testMap[s1] = 4
    And currently testMap.size() = 10


    But finally we note that the size of a map changes if we access a missing key:
    After this questionable attempt j2 = testMap[s2], testMap.size() = 11


    Now we test what happens to a C++ array size if we try to access an element that doesn't exist:
    Size of my_array despite trying to access a missing element remains: 5
    But x= 6.90219e-310
    But despite this questionable attempt to access a missing element we still have my_array:
    1
    2
    3
    4
    5

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Yes, the behaviour is intentionally different. You are looking at a feature, not a bug.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User FortranLevelC++'s Avatar
    Join Date
    May 2013
    Location
    United States
    Posts
    81
    Quote Originally Posted by laserlight View Post
    Yes, the behaviour is intentionally different. You are looking at a feature, not a bug.
    Of course, I am not saying that it is a bug, but given that quite often many keys will accidentally be missing from a map, maybe it would be better if the attempt to write "my_map[missing_key]" without an assignment to the second element, like writing: "my_map[missing_key] = newElement", immediately results in an error message, instantly crashing the program instead of altering the size of the map without warning.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by FortranLevelC++
    given that quite often many keys will accidentally be missing from a map, maybe it would be better if the attempt to write "my_map[missing_key]" without an assignment to the second element, like writing: "my_map[missing_key] = newElement", immediately results in an error message
    The thing is, my_map[missing_key] is actually a function call. What you are asking for is for the function to do different things depending on whether certain operations are done on its return value, or otherwise. Generally, this is not possible.

    That said, the C++11 version of the standard library has expanded the std::map interface to provide an at member function that does what you want, except that this at member function throws an exception if the key does not exist, regardless of how the return value would be used. If you are not using a conforming implementation, you could write a function (template) to do this yourself using the find member function.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Don't start making corrections to the standard just because your assumptions are wrong.

    It would not be better. For operator[] also has to be able to work in as a lookup operation. Any reference, literally any reference, will tell you:
    A call to this function is equivalent to:
    (*((this->insert(make_pair(x,mapped_type()))).first)).secon d
    The reason is because when an insert actually fails you still get an iterator to the key & value pair, and the operator returns the value so that you can do whatever you want with it, such as modify it or display the value on the screen.

  9. #9
    Registered User FortranLevelC++'s Avatar
    Join Date
    May 2013
    Location
    United States
    Posts
    81
    whiteflags, laserlight, many thanks for the scholarly comments! From now on I am taking the precautions to deal with missing keys in maps. I originally found my mistake only by visually inspecting nearly a gigabyte of numerical output data. So far this used to be my method of "debugging"!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 08-20-2012, 11:38 PM
  2. Maps
    By dpp in forum C++ Programming
    Replies: 1
    Last Post: 06-27-2009, 11:09 AM
  3. map of maps ??
    By howhy in forum C++ Programming
    Replies: 1
    Last Post: 09-06-2005, 07:00 AM
  4. Reasons & Workarounds For ostream Failures
    By Tronic in forum C++ Programming
    Replies: 1
    Last Post: 04-12-2005, 02:03 PM
  5. assertion failures
    By edwardtisdale in forum C++ Programming
    Replies: 1
    Last Post: 01-17-2002, 04:07 AM