hash_map elements deletion

[lokki]

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
TStringMapConst Iterator i = mp.find("a1");
if (i != mp.end())
{
std::cout << " found: " << i->second << std::endl;
}
else
{
std::cout << "not found" << std::endl;
}

// remove
for (TStringMapIter ator 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::strin g>
{
size_t operator()(cons t std::string & __s) const
{ return __stl_hash_stri ng(__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__TString Map;
typedef __gnu_cxx::hash _map<const char*, const char*,
__gnu_cxx::hash <const char *>,
__gnu_cxx::tmt_ eq_str__>::cons t_iterator TStringMapConst Iterator;
typedef __gnu_cxx::hash _map<const char*, const char*,
__gnu_cxx::hash <const char *>, __gnu_cxx::tmt_ eq_str__>::iter ator
TStringMapItera tor;

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]

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
TStringMapConst Iterator i = mp.find("a1");
if (i != mp.end())
{
std::cout << " found: " << i->second << std::endl;
}
else
{
std::cout << "not found" << std::endl;
}

// remove
for (TStringMapIter ator 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::strin g>
{
size_t operator()(cons t std::string & __s) const
{ return __stl_hash_stri ng(__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__TString Map;
typedef __gnu_cxx::hash _map<const char*, const char*,
__gnu_cxx::hash <const char *>,
__gnu_cxx::tmt_ eq_str__>::cons t_iterator TStringMapConst Iterator;
typedef __gnu_cxx::hash _map<const char*, const char*,
__gnu_cxx::hash <const char *>, __gnu_cxx::tmt_ eq_str__>::iter ator
TStringMapItera tor;

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]

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

[Kai-Uwe Bux]

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_ma p 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_m p_was & mp ) {
TStringMapItera tor 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

[lokki]

You could try this (untested):

>
void clear_char_ptr_ map ( whatever_type_m p_was & mp ) {
TStringMapItera tor 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