problems with stl maps

[Christian Christmann]

Hi,

I've a class htable.cpp with a private member: map<string, void*>
stringhash;

and a function:
"void HashTable::Insert(char* ky,void* entr) {
strhash.insert(pair<string, void*>(ky, entr));
}"

When adding some values in the driver program with: "
HashTable testIntHT;

char* eins = "eins";
char* zwei = "zwei";
char* drei = "drei";
char* vier = "vier";

testIntHT.Insert(1, eins);
testIntHT.Insert(2, zwei);
testIntHT.Insert(3, drei);
testIntHT.Insert(4, vier);
"

and printing the values with the function: "void
HashTable:rintStringHT()
{
std::map<string, void*>::const_iterator iter; cout << endl;
for (iter = strhash.begin(); iter != strhash.end(); ++iter) {
cout << iter->first << 't' << iter->second << 'n';
}
}"

I get an output:
drei 0x3
eins 0x1
vier 0x4
zwei 0x2

-----------------

Now, I want to replace this class by a template class in order to add
arbitrary values to the hashtable. The new template class htableT.cpp:
"template <class KEYTYPE> class HashTableT {
std::map<KEYTYPE, void*> hash;
[snip] "

with the insert function:
"template <class KEYTYPE>
void HashTableT<KEYTYPE>::Insert(KEYTYPE ky,void* entr) {
hash.insert(pair<KEYTYPE, void*>(ky, entr));
}
"

After inserting the values with:
"
HashTableT<int> testIntHT;
char* eins = "eins";
char* zwei = "zwei";
char* drei = "drei";
char* vier = "vier";

testIntHT.Insert(1, eins);
testIntHT.Insert(2, zwei);
testIntHT.Insert(3, drei);
testIntHT.Insert(4, vier);
"
and printing the values with the function: template <class KEYTYPE>
void HashTableT<KEYTYPE>:rintHashTable() {
typename std::map<KEYTYPE, void*>::const_iterator iter = hash.begin();
cout << endl;
for (iter = hash.begin(); iter != hash.end(); ++iter) {
cout << iter->first << 't' << iter->second << 'n';
}
}

I get:

eins 0x1
zwei 0x2
drei 0x3
vier 0x4


As you can see there is a difference in the outputs. The first map is
sorting the values alphabetically while the second is keeping the order
the values have been inserted.

How can I get the same behaviour with my template insert function ie. what
do I have to do to have the STL map sort the values automatically after
they have been inserted? Thanks

Chris

 

[Christian Christmann]

Hi,

I've a class htable.cpp with a private member: map<string, void*>
stringhash;

and a function:
"void HashTable::Insert(char* ky,void* entr) {
strhash.insert(pair<string, void*>(ky, entr));
}"

When adding some values in the driver program with: " HashTable testIntHT;

char* eins = "eins";
char* zwei = "zwei";
char* drei = "drei";
char* vier = "vier";

testIntHT.Insert(1, eins);
testIntHT.Insert(2, zwei);
testIntHT.Insert(3, drei);
testIntHT.Insert(4, vier);
"

and printing the values with the function: "void
HashTable:rintStringHT()
{
std::map<string, void*>::const_iterator iter; cout << endl; for (iter =
strhash.begin(); iter != strhash.end(); ++iter) {
cout << iter->first << 't' << iter->second << 'n';
}
}"

I get an output:
drei 0x3
eins 0x1
vier 0x4
zwei 0x2

-----------------

Now, I want to replace this class by a template class in order to add
arbitrary values to the hashtable. The new template class htableT.cpp:
"template <class KEYTYPE> class HashTableT {
std::map<KEYTYPE, void*> hash;
[snip] "

with the insert function:
"template <class KEYTYPE>
void HashTableT<KEYTYPE>::Insert(KEYTYPE ky,void* entr) {
hash.insert(pair<KEYTYPE, void*>(ky, entr));
}
"

After inserting the values with:
"
HashTableT<int> testIntHT;
char* eins = "eins";
char* zwei = "zwei";
char* drei = "drei";
char* vier = "vier";

testIntHT.Insert(1, eins);
testIntHT.Insert(2, zwei);
testIntHT.Insert(3, drei);
testIntHT.Insert(4, vier);
"
and printing the values with the function: template <class KEYTYPE> void
HashTableT<KEYTYPE>:rintHashTable() {
typename std::map<KEYTYPE, void*>::const_iterator iter = hash.begin();
cout << endl;
for (iter = hash.begin(); iter != hash.end(); ++iter) {
cout << iter->first << 't' << iter->second << 'n';
}
}
}
I get:

eins 0x1
zwei 0x2
drei 0x3
vier 0x4


As you can see there is a difference in the outputs. The first map is
sorting the values alphabetically while the second is keeping the order
the values have been inserted.

How can I get the same behaviour with my template insert function ie. what
do I have to do to have the STL map sort the values automatically after
they have been inserted? Thanks

Chris

Sorry, I posted the wrong code:
Here is the correct one but the problem remains:

The working insert function:

void LargeHashTable::Insert(char* ky,void* entr)
{
strhash.insert(pair<string, void*>(ky, entr));
}

And the inserted values:
"
HashTable testCharHT;
testCharHT.Insert("eins", (void*)1);
testCharHT.Insert("zwei", (void*)2);
testCharHT.Insert("drei", (void*)3);
testCharHT.Insert("vier", (void*)4);
"

The output:
drei 0x3
eins 0x1
vier 0x4
zwei 0x2


The not working new function:
template <class KEYTYPE>
void HashTableT<KEYTYPE>::Insert(KEYTYPE ky,void* entr)
{
hash.insert(pair<KEYTYPE, void*>(ky, entr));
}

The the inserted values:
"
HashTableT<char*> testCharHT;
testCharHT.Insert("eins", (void*)1);
testCharHT.Insert("zwei", (void*)2);
testCharHT.Insert("drei", (void*)3);
testCharHT.Insert("vier", (void*)4);
"

The new output:
eins 0x1
zwei 0x2
drei 0x3
vier 0x4





Chris

 

[Victor Bazarov]

I've a class htable.cpp with a private member: map<string, void*>
stringhash;

and a function:
"void HashTable::Insert(char* ky,void* entr) {
strhash.insert(pair<string, void*>(ky, entr));
}"

When adding some values in the driver program with: "
HashTable testIntHT;

char* eins = "eins";
char* zwei = "zwei";
char* drei = "drei";
char* vier = "vier";

BAD IDEA(tm). Do not initialise char* with a literal.

testIntHT.Insert(1, eins);
testIntHT.Insert(2, zwei);
testIntHT.Insert(3, drei);
testIntHT.Insert(4, vier);
"

That shouldn't work. Your 'Insert' function expects a char*, and you
are passing a number. Are you sure you're talking about working code?

and printing the values with the function: "void
HashTable:rintStringHT()
{
std::map<string, void*>::const_iterator iter; cout << endl;
for (iter = strhash.begin(); iter != strhash.end(); ++iter) {
cout << iter->first << 't' << iter->second << 'n';
}
}"

I get an output:
drei 0x3
eins 0x1
vier 0x4
zwei 0x2

REALLY? I somehow doubt that. What compiler allowed you to convert
integer numbers into char*?

-----------------

Now, I want to replace this class by a template class in order to add
arbitrary values to the hashtable. The new template class htableT.cpp:
"template <class KEYTYPE> class HashTableT {
std::map<KEYTYPE, void*> hash;
[snip] "

with the insert function:
"template <class KEYTYPE>
void HashTableT<KEYTYPE>::Insert(KEYTYPE ky,void* entr) {
hash.insert(pair<KEYTYPE, void*>(ky, entr));
}
"

After inserting the values with:
"
HashTableT<int> testIntHT;
char* eins = "eins";
char* zwei = "zwei";
char* drei = "drei";
char* vier = "vier";

You should definitely avoid initialising pointers to non-const char with
string literals. While it's allowed for compatibility with C, it is
a BAD IDEA(tm).

testIntHT.Insert(1, eins);
testIntHT.Insert(2, zwei);
testIntHT.Insert(3, drei);
testIntHT.Insert(4, vier);
"
and printing the values with the function: template <class KEYTYPE>
void HashTableT<KEYTYPE>:rintHashTable() {
typename std::map<KEYTYPE, void*>::const_iterator iter = hash.begin();
cout << endl;
for (iter = hash.begin(); iter != hash.end(); ++iter) {
cout << iter->first << 't' << iter->second << 'n';
}
}

I get:

eins 0x1
zwei 0x2
drei 0x3
vier 0x4

REALLY? Do you mean to say that when you print out 'iter->first', which
should be an int, you get strings "eins", etc., and when you print out
't' you get some whitespace? Whom are you trying to fool here? Post
real code.

As you can see there is a difference in the outputs.

Difference? As in "it doesn't correspond to the code"?

The first map is
sorting the values alphabetically while the second is keeping the order
the values have been inserted.

If you need to keep the insertion order, use std::list instead of
std::map.

How can I get the same behaviour with my template insert function ie. what
do I have to do to have the STL map sort the values automatically after
they have been inserted? Thanks

It _does_ sort them automatically. It sorts them based on the 'key' you
provide. And you provided *integers* from 1 to 4 as keys. You do get
your values sorted. The order just *happens* to be the same as insertion
order.

All screw-up aside, you need to make the key of the second (the template)
variation a 'string', not an integer.

V

 

[Victor Bazarov]

stringhash or strhash? Why don't you actually post _real_ code?

and a function:
"void HashTable::Insert(char* ky,void* entr) {
strhash.insert(pair<string, void*>(ky, entr));
}"
[...]

Sorry, I posted the wrong code:

No joke?

Here is the correct one but the problem remains:

The working insert function:

void LargeHashTable::Insert(char* ky,void* entr)
{
strhash.insert(pair<string, void*>(ky, entr));
}

And the inserted values:
"
HashTable testCharHT;
testCharHT.Insert("eins", (void*)1);
testCharHT.Insert("zwei", (void*)2);
testCharHT.Insert("drei", (void*)3);
testCharHT.Insert("vier", (void*)4);
"

The output:
drei 0x3
eins 0x1
vier 0x4
zwei 0x2


The not working new function:
template <class KEYTYPE>
void HashTableT<KEYTYPE>::Insert(KEYTYPE ky,void* entr)
{
hash.insert(pair<KEYTYPE, void*>(ky, entr));
}

The the inserted values:
"
HashTableT<char*> testCharHT;
testCharHT.Insert("eins", (void*)1);
testCharHT.Insert("zwei", (void*)2);
testCharHT.Insert("drei", (void*)3);
testCharHT.Insert("vier", (void*)4);
"

The new output:
eins 0x1
zwei 0x2
drei 0x3
vier 0x4

While keys that are 'string' have 'std::less' comparator that actually
compares the _contents_ of the strings, if you define your map to have
the Key a 'char*', the comparison of those does NOT go into the _contents_
of the memory, it only compares the _values_ of the pointers.

You could supply your own comparator to your map (see any decent book on
the Standard library containers to learn how to do it), or you could just
keep the map based on 'string' and not use bare pointers.

V