hash_multimap

[ct]

How hard is it to roll up our own small hash_multimap ? I am working on a small project, I wouldn't need anything besides the standard STL (hash_multimap under STL would have been so great).
I don't want to use Boost just for hash_multimap, if I don't have any alternative I might use it though. So what are other alternatives ?

BTW, I just need the map for hash_multimap<string, vector<string> >.

[fullmetalcoder]

wouldn't QMultiHash fit???

[ct]

yes, QMultiHash is so nice isn't it . But I wouldn't want to use it just for hashmap,then I would have to rely on the library files... Is there anything else in a single or two header files that could be useful...

How hard is it to roll our own ? I know that if the hash function is not good then the hashmap could perform worse than map. So, guess there is math involved in it....

[fullmetalcoder]

if you are already using STD (string and vector are from STD right?) why not using the hash_multimap from STD? if however you can't afford neither STD nor Qt then you'll have a hard time creating your own... maybe a quick look at Qt sources would help you...

[ct]

if you are already using STD (string and vector are from STD right?) why not using the hash_multimap from STD?

It's STL ( Standard Template Library) and hash_multimap is not a part of STL standard as far as I know.

[fullmetalcoder]

It's STL ( Standard Template Library)

Whoops... yep! sorry, little confusion...

and hash_multimap is not a part of STL standard as far as I know.

right. I'm afraid I misunderstood your first post... I thought hash_multimap was something from STL that you couldn't afford using...

Again I'd suggest having a look at Qt sources... Being a template class it *should* occupy a single file. However the use of implicit sharing makes it much trickier but once you get rid of all these (useless?) portions of code it should fit your purposes...

[ct]

I am confused though if I should go through the trouble of filtering out the hash multimap.
Should I use the multimap that is already there in the STL or go for hash_map.

The array size will be around 100,000 and i might need to find about 10 items in that array...would the lookups be huge for a map ?

[fullmetalcoder]

I am confused though if I should go through the trouble of filtering out the hash multimap.
Should I use the multimap that is already there in the STL or go for hash_map.

The array size will be around 100,000 and i might need to find about 10 items in that array...would the lookups be huge for a map ?

I don't know how well the STL multi_map performs... The thing is that a map orders its elements so it is way slower when inserting items, especially with as much items as you plan to add. As for the lookup, hash-based structures are said to be faster but a map-based, being sorted, uses binary search which can actually turn out to be faster if the number of lookups is relatively small...

[Gopala Krishna]

http://code.google.com/p/google-sparsehash/
Just found the link accidently

[wysota]

You can always use a standard hash and keep there not single items, but lists of items. Something like: std::hash_map<std::list<Item> >

BTW. Are you sure hash_multimap is not available (I know it's not part of the standard, but for instance my system supports it)?
http://www.sgi.com/tech/stl/hash_multimap.html

[ct]

BTW. Are you sure hash_multimap is not available (I know it's not part of the standard, but for instance my system supports it)?

yes I think both g++ and VC++ has support for multimap but the usage varies. I needed something that would compile for both the compilers.
However, map and multimap should suffice my needs at the moment with O(logn) time complexity. I had mistakenly taken the time complexity of STL's map as O(n)..I was so wrong.. O (log n) is still fast..

[wysota]

STL on Linux is different than STL on Windows - these are completely different implementations, so you'll have differences in all other classes as well (probably including std::vector). The API should be the same on both platforms.

[ct]

Wow, you are right. The API of both g++ and vc++ is same; just have to insert the required headers. I have the same program working for both g++ and vc++ 2005 right now.
Here is the code:

//VC++
#include<iostream>
#include<cstdio>
#include<hash_map>
using namespace std;
using namespace stdext;
int main(int argc,char** argv)
{   
    hash_map<int,int> mapping;
    hash_map<int,int>::const_iterator miter;
 
    mapping.insert(pair<int,int>(1,100));
    mapping.insert(pair<int,int>(2,200));
    miter = mapping.find(1);
 
    if(miter == mapping.end())
        cout << "Not found";
    else
       cout << miter->first << " = " << miter->second;
 
 
    getchar();
    return 0;
}

//VC++
#include<iostream>
#include<cstdio>
#include<hash_map>
using namespace std;
using namespace stdext;
int main(int argc,char** argv)
{   
    hash_map<int,int> mapping;
    hash_map<int,int>::const_iterator miter;
    
    mapping.insert(pair<int,int>(1,100));
    mapping.insert(pair<int,int>(2,200));
    miter = mapping.find(1);
    
    if(miter == mapping.end())
        cout << "Not found";
    else
       cout << miter->first << " = " << miter->second;
   
    
    getchar();
    return 0;
}

To copy to clipboard, switch view to plain text mode 

//g++
#include<iostream>
#include<cstdio>
#include<ext/hash_map>
using namespace std;
using namespace __gnu_cxx;
int main(int argc,char** argv)
{   
    hash_map<int,int> mapping;
    hash_map<int,int>::const_iterator miter;
 
    mapping.insert(pair<int,int>(1,100));
    mapping.insert(pair<int,int>(2,200));
    miter = mapping.find(1);
 
    if(miter == mapping.end())
        cout << "Not found";
    else
       cout << miter->first << " = " << miter->second;
 
 
    getchar();
    return 0;
}

//g++
#include<iostream>
#include<cstdio>
#include<ext/hash_map>
using namespace std;
using namespace __gnu_cxx;
int main(int argc,char** argv)
{   
    hash_map<int,int> mapping;
    hash_map<int,int>::const_iterator miter;
    
    mapping.insert(pair<int,int>(1,100));
    mapping.insert(pair<int,int>(2,200));
    miter = mapping.find(1);
    
    if(miter == mapping.end())
        cout << "Not found";
    else
       cout << miter->first << " = " << miter->second;
   
    
    getchar();
    return 0;
}

To copy to clipboard, switch view to plain text mode 

However I am running into some problem with hash_map<string,string> for both the compilers. I am sure there is some compare function that needs to be defined for strings or is there something already available ?

[ct]

BTW, how can I combine both these files into one so that both the compilers can compile it. Is there some flag that needs to be checked to find out if the compiler is VC++ or g++ ?

[spud]

#ifdef Q_CC_MSVC
#include<hash_map>
using namespace stdext;
#endif
 
#ifdef Q_CC_GNU
#include<ext/hash_map>
using namespace __gnu_cxx;
#endif

#ifdef Q_CC_MSVC
#include<hash_map>
using namespace stdext;
#endif

#ifdef Q_CC_GNU
#include<ext/hash_map>
using namespace __gnu_cxx;
#endif

To copy to clipboard, switch view to plain text mode 

[ct]

#ifdef Q_CC_MSVC
#include<hash_map>
using namespace stdext;
#endif
 
#ifdef Q_CC_GNU
#include<ext/hash_map>
using namespace __gnu_cxx;
#endif

#ifdef Q_CC_MSVC
#include<hash_map>
using namespace stdext;
#endif

#ifdef Q_CC_GNU
#include<ext/hash_map>
using namespace __gnu_cxx;
#endif

To copy to clipboard, switch view to plain text mode 

That certainly didn't work. Is that some QT preprocessor that does the same thing? I opened up the glut.h file and saw how they have done it so I got upto here.

#include<iostream>
#include<cstdio>
 
#if defined(__MINGW32__)
#include<ext/hash_map>
using namespace __gnu_cxx;
#endif
 
#if defined(_MSC_VER)
#include<hash_map>
using namespace stdext;
#endif
 
#include<iostream>
#include<cstdio>
 
using namespace std;
 
int main(int argc,char** argv)
{   
    hash_map<int,int> mapping;
    hash_map<int,int>::const_iterator miter;
 
    mapping.insert(pair<int,int>(1,100));
    mapping.insert(pair<int,int>(2,200));
    miter = mapping.find(1);
 
    if(miter == mapping.end())
        cout << "Not found";
    else
       cout << miter->first << " = " << miter->second;
 
 
    getchar();
    return 0;
}

#include<iostream>
#include<cstdio>

#if defined(__MINGW32__)
#include<ext/hash_map>
using namespace __gnu_cxx;
#endif

#if defined(_MSC_VER)
#include<hash_map>
using namespace stdext;
#endif

#include<iostream>
#include<cstdio>

using namespace std;

int main(int argc,char** argv)
{   
    hash_map<int,int> mapping;
    hash_map<int,int>::const_iterator miter;
    
    mapping.insert(pair<int,int>(1,100));
    mapping.insert(pair<int,int>(2,200));
    miter = mapping.find(1);
    
    if(miter == mapping.end())
        cout << "Not found";
    else
       cout << miter->first << " = " << miter->second;
   
    
    getchar();
    return 0;
}

To copy to clipboard, switch view to plain text mode 

The preprocessors have always confused me a bit. Is there a list of all the preprocessors that can be used (at least the more common ones ). Can anyone point to some good resource about types of general preprocessors or may be list some common ones out here ?