rkpalli
asked on
STL HASH_MULTIMAP
To all Experts:
I am novice in using STL classes. I need to have a hash table for storing a unique (which my application generates)
which is string (char array) and a index value (int). I need to lookup to this hash table every often in my application.
So I have decided to go for STL HASHTABLE expecting it to be very efficeint and can handle a big hash table.
Here is my sample code implementation. Since VC++ does not have hash_map class, I am using SGI's
Library classes. I downloaded them from http://www.sgi.com/Technology/STL/ .
#include "stdio.h"
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include <hash_map.h>
#include <hashtable.h>
struct eqstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) == 0;
}
};
typedef hash_multimap<const char*, int, hash<const char*>, eqstr> map_type;
map_type M;
void showup(void);
void lookup(const map_type& Map, const char* str_1)
{
pair<map_type::const_itera tor, map_type::const_iterator> p =
Map.equal_range(str_1);
for (map_type::const_iterator i = p.first; i != p.second; ++i)
cout << "\n"<<(*i).second << "\n";
cout << endl;
}
// Add to the hash table
void addup(char* string1, int index)
{
M.insert(map_type::value_t ype(string 1, index));
// add string to the hash table
}
int main()
{
char str_1[6] ;
for(int i = 1 ; i < 11 ; i++ )
{
_itoa(i, str_1, 10 );
strcat(str_1, "two");
puts(str_1); // string before inserting into HASH
addup(str_1, i);
}
showup() ; // dispay all the values in HASH table
lookup(M, "2two"); // Look for the string "2two"
}
// lists all the hash table values to stdout
void showup()
{
int size_1 = M.size();
map_type::iterator it_1;
it_1 = M.begin();
for(int count = 0 ; count < size_1 ; count++, it_1++ )
printf("%s===%d=\n", (*it_1).first, (*it_1).second );
puts("\n");
}
========================== ========
The output of this looks like this.
10two===5=
10two===9=
10two===9=
10two===9=
10two===9=
10two===9=
10two===9=
10two===9=
10two===9=
10two===9=
where as the output I am expecting should be
1two===1=
2two===2=
3two===3=
3two===4=
5two===5=
6two===6=
7two===7=
8two===8=
9two===9=
10two===10=
My observation is insert function overwriting all previous values. I have spent hours to find out what the problem is
but in vain. Kindly let me know If I am doing any mistake while using STL HASH classes. I am using VC++ 5.0
environemnt under NT4.0
Please get back to me I you need any details.
Thanks
RKPALLI
I am novice in using STL classes. I need to have a hash table for storing a unique (which my application generates)
which is string (char array) and a index value (int). I need to lookup to this hash table every often in my application.
So I have decided to go for STL HASHTABLE expecting it to be very efficeint and can handle a big hash table.
Here is my sample code implementation. Since VC++ does not have hash_map class, I am using SGI's
Library classes. I downloaded them from http://www.sgi.com/Technology/STL/ .
#include "stdio.h"
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include <hash_map.h>
#include <hashtable.h>
struct eqstr
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) == 0;
}
};
typedef hash_multimap<const char*, int, hash<const char*>, eqstr> map_type;
map_type M;
void showup(void);
void lookup(const map_type& Map, const char* str_1)
{
pair<map_type::const_itera
Map.equal_range(str_1);
for (map_type::const_iterator i = p.first; i != p.second; ++i)
cout << "\n"<<(*i).second << "\n";
cout << endl;
}
// Add to the hash table
void addup(char* string1, int index)
{
M.insert(map_type::value_t
// add string to the hash table
}
int main()
{
char str_1[6] ;
for(int i = 1 ; i < 11 ; i++ )
{
_itoa(i, str_1, 10 );
strcat(str_1, "two");
puts(str_1); // string before inserting into HASH
addup(str_1, i);
}
showup() ; // dispay all the values in HASH table
lookup(M, "2two"); // Look for the string "2two"
}
// lists all the hash table values to stdout
void showup()
{
int size_1 = M.size();
map_type::iterator it_1;
it_1 = M.begin();
for(int count = 0 ; count < size_1 ; count++, it_1++ )
printf("%s===%d=\n", (*it_1).first, (*it_1).second );
puts("\n");
}
==========================
The output of this looks like this.
10two===5=
10two===9=
10two===9=
10two===9=
10two===9=
10two===9=
10two===9=
10two===9=
10two===9=
10two===9=
where as the output I am expecting should be
1two===1=
2two===2=
3two===3=
3two===4=
5two===5=
6two===6=
7two===7=
8two===8=
9two===9=
10two===10=
My observation is insert function overwriting all previous values. I have spent hours to find out what the problem is
but in vain. Kindly let me know If I am doing any mistake while using STL HASH classes. I am using VC++ 5.0
environemnt under NT4.0
Please get back to me I you need any details.
Thanks
RKPALLI
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Is this working for you? Do you need more help?
You can use string instead of char* to make the copying automatice:
typedef hash_multimap<string, int, hash<string>, eqstr> map_type;
typedef hash_multimap<string, int, hash<string>, eqstr> map_type;
In fact, you can make that change just about everywhere in your code and your life will be easier!
ASKER
Expert,
Thanks for you answer.
You solution works if I allocate address space with new operator and insert into
hash table. But when I delete from hashtble with M.erase(index), does STL hash
table deletes the memory allocted with new operator at the insert operation. ??
Becz If If try to delete myself it leads to GPF. If STL routine cleans up memory
created with new operator , then It is fine.
One more question, to use string as one of data type do I need to include
any header file or typedef. Becz I get compile error(s) if use string directly.
Thanks
RKPALLI
Thanks for you answer.
You solution works if I allocate address space with new operator and insert into
hash table. But when I delete from hashtble with M.erase(index), does STL hash
table deletes the memory allocted with new operator at the insert operation. ??
Becz If If try to delete myself it leads to GPF. If STL routine cleans up memory
created with new operator , then It is fine.
One more question, to use string as one of data type do I need to include
any header file or typedef. Becz I get compile error(s) if use string directly.
Thanks
RKPALLI
No the hash table does not delete the memory. It does not know that the memory was dynamically allocated (since the string specified may or may not be) sot it does not know if it should be deleted.
The solution is to delete the string yourself, before removing if from the hash table. That should work, so you must have made a mistake. (Post your code?)
The other solution is to use a string class, rather than a C-style char * string. A string class will take care of the memory allocation and deallocation issues for you. I highly recomend this approach not just for this case but throughout your program.
The solution is to delete the string yourself, before removing if from the hash table. That should work, so you must have made a mistake. (Post your code?)
The other solution is to use a string class, rather than a C-style char * string. A string class will take care of the memory allocation and deallocation issues for you. I highly recomend this approach not just for this case but throughout your program.
To use the string class, you shoud include the header <string>. Don't forget that it is in the std namespace.
ASKER
Expert,
Thanks for your quick responce. I tried to include <string> but I get following errors
while I compile. Do I need use any pragma Macro??.
I have also mentioned "using std namespace ; " in main().
C:\Program Files\DevStudio\VC\INCLUDE \xstring(2 9) : error C2143: syntax error : missing ';' before '<'
C:\Program Files\DevStudio\VC\INCLUDE \xstring(3 1) : error C2238: unexpected token(s) preceding ';'
and continues to 85 errors
Kindly reply.
RKPALLI
Thanks for your quick responce. I tried to include <string> but I get following errors
while I compile. Do I need use any pragma Macro??.
I have also mentioned "using std namespace ; " in main().
C:\Program Files\DevStudio\VC\INCLUDE
C:\Program Files\DevStudio\VC\INCLUDE
and continues to 85 errors
Kindly reply.
RKPALLI
Can you post the code around the lines where you included the <string> include file?
Are the arrors related to the line "using std namespace ; "? Because it should be "using namespace std;" .
ASKER
Here is code:. No Even the erros occour even not specifing namespace and specifing
namespace does not reduce errors.
----
#include <string>
using std namespace ;
int main(void)
{
using std namespace;
return ;
}
-----
Thanks
RKPALLI
namespace does not reduce errors.
----
#include <string>
using std namespace ;
int main(void)
{
using std namespace;
return ;
}
-----
Thanks
RKPALLI
I don't use namespaces, but I believe it should be
#include <string>
using namespace std ;
int main(void)
{
return ;
}
From the VC help
using namespace [::] [nested-name-specifier] namespace-name
The using-directive allows the names in a namespace to be used without the namespace-name as an explicit qualifier. In contrast to a using declaration, which allows an individual name to be used without qualification, the using directive allows all the names in a namespace to be used without qualification. See using Declaration for more information.
#include <string>
using namespace std ;
int main(void)
{
return ;
}
From the VC help
using namespace [::] [nested-name-specifier] namespace-name
The using-directive allows the names in a namespace to be used without the namespace-name as an explicit qualifier. In contrast to a using declaration, which allows an individual name to be used without qualification, the using directive allows all the names in a namespace to be used without qualification. See using Declaration for more information.
ASKER
Expert,
I will try your solution. Thanks for your quick responce.
RKPALLI
I will try your solution. Thanks for your quick responce.
RKPALLI
Note, I am only guessing here. But that fits the behavior and is consistent with most container implementations.