hash_map elements deletion

Discussion in 'C++' started by lokki, Mar 7, 2007.

  1. lokki

    lokki Guest

    Hello,

    can anybody tell me what's wrong with following example code?

    char *k, *v;

    k = new char[3];
    strcpy(k, "a2");

    v = new char[10];
    strcpy(v, "987654321");

    mp.insert(std::pair<const char*, const char*>(k, v));

    std::cout << "map size " << mp.size() << std::endl;

    // find
    TStringMapConstIterator i = mp.find("a1");
    if (i != mp.end())
    {
    std::cout << " found: " << i->second << std::endl;
    }
    else
    {
    std::cout << "not found" << std::endl;
    }

    // remove
    for (TStringMapIterator j = mp.begin(); j != mp.end(); j++)
    {
    delete[] (*j).first;
    delete[] (*j).second;
    }
    mp.clear();
    std::cout << "deleted" << std::endl;

    I'm using gnu c++ compiler and there are few typedefs before this code
    to ensure proper comparison and hash computing of const char* in
    hash_map

    namespace __gnu_cxx
    {
    template<> struct hash<std::string>
    {
    size_t operator()(const std::string & __s) const
    { return __stl_hash_string(__s.c_str()); }
    };

    struct tmt_eq_str__
    {
    bool operator() (const char *a, const char *b) const
    {
    return !strcmp(a, b);
    }
    };

    }

    typedef __gnu_cxx::hash_map<const char*, const char*,
    __gnu_cxx::hash<const char *>, __gnu_cxx::tmt_eq_str__> TStringMap;
    typedef __gnu_cxx::hash_map<const char*, const char*,
    __gnu_cxx::hash<const char *>,
    __gnu_cxx::tmt_eq_str__>::const_iterator TStringMapConstIterator;
    typedef __gnu_cxx::hash_map<const char*, const char*,
    __gnu_cxx::hash<const char *>, __gnu_cxx::tmt_eq_str__>::iterator
    TStringMapIterator;

    The problem is removal of the elements. Both key and value pairs were
    created by new operator. That's why I assumed, that they should be
    deleted before callig mp.clear() function.

    Problem is that program hangs in infinite loop when deleting elements.
    There wasn't such problem when compiling similar code under VC++ 8.0

    Thanks in adavance
    lokki, Mar 7, 2007
    #1
    1. Advertising

  2. lokki

    Kai-Uwe Bux Guest

    lokki wrote:

    > Hello,
    >
    > can anybody tell me what's wrong with following example code?
    >
    > char *k, *v;
    >
    > k = new char[3];
    > strcpy(k, "a2");
    >
    > v = new char[10];
    > strcpy(v, "987654321");
    >
    > mp.insert(std::pair<const char*, const char*>(k, v));


    What is mp?

    >
    > std::cout << "map size " << mp.size() << std::endl;
    >
    > // find
    > TStringMapConstIterator i = mp.find("a1");
    > if (i != mp.end())
    > {
    > std::cout << " found: " << i->second << std::endl;
    > }
    > else
    > {
    > std::cout << "not found" << std::endl;
    > }
    >
    > // remove
    > for (TStringMapIterator j = mp.begin(); j != mp.end(); j++)
    > {
    > delete[] (*j).first;
    > delete[] (*j).second;
    > }
    > mp.clear();


    Very likely, you corrupted the integrity of the map by deallocating all the
    pointers. Does the comparision object / hash function for this map /
    unordered_map access the pointees or just the stored pointers? If the
    former is the case, the previous run through the list makes it very likely
    that you enter undefined behavior.

    Suggested fix: don't use char*, use std::string instead.

    > std::cout << "deleted" << std::endl;
    >
    > I'm using gnu c++ compiler and there are few typedefs before this code
    > to ensure proper comparison and hash computing of const char* in
    > hash_map
    >
    > namespace __gnu_cxx
    > {
    > template<> struct hash<std::string>
    > {
    > size_t operator()(const std::string & __s) const
    > { return __stl_hash_string(__s.c_str()); }
    > };
    >
    > struct tmt_eq_str__
    > {
    > bool operator() (const char *a, const char *b) const
    > {
    > return !strcmp(a, b);
    > }
    > };
    >
    > }
    >
    > typedef __gnu_cxx::hash_map<const char*, const char*,
    > __gnu_cxx::hash<const char *>, __gnu_cxx::tmt_eq_str__> TStringMap;
    > typedef __gnu_cxx::hash_map<const char*, const char*,
    > __gnu_cxx::hash<const char *>,
    > __gnu_cxx::tmt_eq_str__>::const_iterator TStringMapConstIterator;
    > typedef __gnu_cxx::hash_map<const char*, const char*,
    > __gnu_cxx::hash<const char *>, __gnu_cxx::tmt_eq_str__>::iterator
    > TStringMapIterator;
    >
    > The problem is removal of the elements. Both key and value pairs were
    > created by new operator. That's why I assumed, that they should be
    > deleted before callig mp.clear() function.
    >
    > Problem is that program hangs in infinite loop when deleting elements.
    > There wasn't such problem when compiling similar code under VC++ 8.0
    >
    > Thanks in adavance
    Kai-Uwe Bux, Mar 7, 2007
    #2
    1. Advertising

  3. lokki

    lokki Guest

    > Very likely, you corrupted the integrity of the map by deallocating all the
    > pointers. Does the comparision object / hash function for this map /
    > unordered_map access the pointees or just the stored pointers? If the
    > former is the case, the previous run through the list makes it very likely
    > that you enter undefined behavior.
    >
    > Suggested fix: don't use char*, use std::string instead.
    >


    I would rather not use std::string because of performance issues in
    target application. I tried to analyse that and came to folowing:

    - The hash_map in target application will have to hold thousands of
    strings.
    - The container holds the copy of every object. In case of const
    char * it holds only pointer, in case of std::string a complex
    object.
    - A lot of constructor/copy constructor calls will be neccesary when
    inserting std::string to hash_map.
    - Data from hash_map will be only read when once inserted. They
    should be const, there is no necessity to change them. A very very
    fast find is required.
    - Almost every external library/ other code in applicaiton is using
    const char * for strings.
    - After usage, it is required to clear map and to load new data.

    I have a previous implementation using std::string and trying to
    rebuild it to const char*.
    Any advice on safer initialisation/deletion of char pointers in
    hash_map?

    Thanks a lot anyway

    -jk
    lokki, Mar 7, 2007
    #3
  4. lokki

    Kai-Uwe Bux Guest

    lokki wrote:

    >> Very likely, you corrupted the integrity of the map by deallocating all
    >> the pointers. Does the comparision object / hash function for this map /
    >> unordered_map access the pointees or just the stored pointers? If the
    >> former is the case, the previous run through the list makes it very
    >> likely that you enter undefined behavior.
    >>
    >> Suggested fix: don't use char*, use std::string instead.
    >>

    >
    > I would rather not use std::string because of performance issues in
    > target application. I tried to analyse that and came to folowing:
    >
    > - The hash_map in target application will have to hold thousands of
    > strings.
    > - The container holds the copy of every object. In case of const
    > char * it holds only pointer, in case of std::string a complex
    > object.
    > - A lot of constructor/copy constructor calls will be neccesary when
    > inserting std::string to hash_map.
    > - Data from hash_map will be only read when once inserted. They
    > should be const, there is no necessity to change them. A very very
    > fast find is required.
    > - Almost every external library/ other code in applicaiton is using
    > const char * for strings.
    > - After usage, it is required to clear map and to load new data.


    Hm, I always found that std::string is just as efficient as char* and
    sometimes more efficient (since it stores a length and). Also, I find that
    if performance becomes an issue, replacing std::string by some other string
    implementation (conforming to the same or similar interface) allows for
    better optimization than moving over to char*.


    > I have a previous implementation using std::string and trying to
    > rebuild it to const char*.
    > Any advice on safer initialisation/deletion of char pointers in
    > hash_map?


    You could try this (untested):

    void clear_char_ptr_map ( whatever_type_mp_was & mp ) {
    TStringMapIterator j = mp.begin();
    while ( j != mp.end() );
    char* dummy_1 = j->first;
    char* dummy_2 = j->second;
    mp.erase( j++ );
    delete [] dummy_1;
    delete [] dummy_2;
    }
    }


    It would probably be best if you designed your own map-class that owns the
    strings and takes care of all memory management for you.


    Best

    Kai-Uwe Bux
    Kai-Uwe Bux, Mar 7, 2007
    #4
  5. lokki

    lokki Guest

    > You could try this (untested):
    >
    > void clear_char_ptr_map ( whatever_type_mp_was & mp ) {
    > TStringMapIterator j = mp.begin();
    > while ( j != mp.end() );
    > char* dummy_1 = j->first;
    > char* dummy_2 = j->second;
    > mp.erase( j++ );
    > delete [] dummy_1;
    > delete [] dummy_2;
    > }
    > }
    >
    >
    > It would probably be best if you designed your own map-class that owns the
    > strings and takes care of all memory management for you.
    >
    >
    > Best
    >
    > Kai-Uwe Bux


    Well, I tried and looks it works.

    Thank you very much

    -jk
    lokki, Mar 7, 2007
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Kristofer Pettijohn

    2d hash_map iteration ?

    Kristofer Pettijohn, Jun 26, 2003, in forum: C++
    Replies:
    1
    Views:
    992
    Rob Williscroft
    Jun 26, 2003
  2. Jacek Generowicz

    Pre-standardizing hash_map & friends.

    Jacek Generowicz, Aug 26, 2003, in forum: C++
    Replies:
    0
    Views:
    360
    Jacek Generowicz
    Aug 26, 2003
  3. Charles Herman

    hash_map iterator

    Charles Herman, Nov 3, 2003, in forum: C++
    Replies:
    5
    Views:
    5,975
    Ron Natalie
    Nov 4, 2003
  4. Florian Liefers

    C2143, hash_map

    Florian Liefers, Nov 12, 2003, in forum: C++
    Replies:
    11
    Views:
    1,308
    Dan Cernat
    Nov 12, 2003
  5. Jon Cosby

    hash_map

    Jon Cosby, Nov 30, 2003, in forum: C++
    Replies:
    10
    Views:
    8,634
    David Fisher
    Dec 2, 2003
Loading...

Share This Page