c++ hash_set with a custom object

First note that hash_set is not part of the standard STL ... So, it's platform dependent whether you compiler implements it.

Here's how you could create a hash_set of your class :

        hash_set<MyClass> myHashSet;

Note that you have to do quite a few things for this to work though :

#include <iostream>
#include <string>
#include <ext\hash_set>        // <--- in my compiler, the hash_set include was found under ext
 
using namespace std;
using namespace __gnu_cxx;     // <--- in my compiler, the hash_set was in the __gnu_cxx namespace
 
class SomeObject {             // <--- empty class just for testing
};
 
class MyClass{
  private :
    int i, j, k, l, m;
    string a, b, c;
    SomeObject* SO;
  public :
    MyClass(int ii) : i(ii) { }         // <--- just for testing only one member initialized
    ~MyClass() { }
    
    friend ostream& operator<<(ostream &os, const MyClass &mc);
 
    bool operator==(const MyClass &mc) const {      // <--- needs to be provided
      return (i == mc.i);
    }
 
    bool operator<(const MyClass &mc) const {       // <--- provide this also
      return (i < mc.i);
    }
 
    size_t hash() const {                           // <--- this will be the hash function used
      return i;                                     // <--- just a stupid test hash function now
    }
};
 
ostream& operator<<(ostream &os, const MyClass &mc) {    // <--- provided to output a MyClass instance
  os << mc.i;
  return os;
}
 
namespace __gnu_cxx {                      // <--- we need to instantiate a new templatized version of the hash function for MyClass
  template<> struct hash<MyClass> {
    size_t operator()(const MyClass mc) const {
      return mc.hash();                    // <--- it just calls the hash() member of the MyClass class
    }
  };
}
 
int main(void) {
  hash_set<MyClass> myHashSet;   // <--- will use the hash function we defined earlier, and the operator==
 
  MyClass mc1(1);
  MyClass mc2(2);
  MyClass mc3(3);
  MyClass mc4(4);
 
  myHashSet.insert(mc1);
  myHashSet.insert(mc3);
  myHashSet.insert(mc2);
  
  hash_set<MyClass>::const_iterator it = myHashSet.find(mc3);  // <--- this one should be found
  if (it != myHashSet.end()) {
    cout << "found : " << *it << endl;
  }
  else {
    cout << "not found !!" << endl;
  }
 
  it = myHashSet.find(mc4);                                    // <--- this one should not be found
  if (it != myHashSet.end()) {
    cout << "found : " << *it << endl;
  }
  else {
    cout << "not found !!" << endl;
  }
 
  return 0;
}

Select allOpen in new window

Note that hash_set seems to require a different include and a different namespace for your compiler, so you'll need to modify those in the code before compiling.

The code is only for demonstration purposes, as I only ever make use of the i member of the MyClass class ...

Note: I'm using VS2008 C++

I can't get it to compile... the following code gets an error:

      namespace std
      {  
            template<> struct hash<MyClass> {   //<--- Error Here  !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
                  // Define the hash function. We'll just stub it out here.
                  size_t operator()( const MyClass rf ) const { return rf.hash(); }
            };
      }

The Error: error C2143: syntax error : missing ';' before '<'

Here's MSDN on what I'm working with (i think)
http://msdn2.microsoft.com/en-us/library/1t4xas78(VS.80).aspx

Thanks again for your time

I have to go to sleep now, I'll check back in the morning

Here's the rest of the relavent code:

	class MyClass{
	public:
		int x;
 
		bool operator==(const MyClass& rf) const {      
			return true;
		}
 
		bool operator<(const MyClass& mc) const {       
			return true;
		}
 
		size_t hash() const {                           
			return 1;                                     // <--- just a stupid test hash function now
		}
	};

Select allOpen in new window

And for good luck, these are included

#include <hash_set>

using namespace std;
using namespace stdext;

>> I can't get it to compile... the following code gets an error:

It's quite compiler dependent as I said. Try this code for your compiler. Note that I haven't tested it, as I don't have your compiler installed :

#include <iostream>
#include <string>
#include <hash_set>            // <--- another include for your compiler
 
using namespace std;
using namespace stdext;        // <--- another namespace for your compiler
 
class SomeObject {             // <--- empty class just for testing
};
 
class MyClass{
  private :
    int i, j, k, l, m;
    string a, b, c;
    SomeObject* SO;
  public :
    MyClass(int ii) : i(ii) { }         // <--- just for testing only one member initialized
    ~MyClass() { }
    
    friend ostream& operator<<(ostream &os, const MyClass &mc);
 
    bool operator==(const MyClass &mc) const {      // <--- needs to be provided
      return (i == mc.i);
    }
 
    bool operator<(const MyClass &mc) const {       // <--- provide this also
      return (i < mc.i);
    }
 
    size_t hash() const {                           // <--- this will be the hash function used
      return i;                                     // <--- just a stupid test hash function now
    }
};
 
ostream& operator<<(ostream &os, const MyClass &mc) {    // <--- provided to output a MyClass instance
  os << mc.i;
  return os;
}
 
namespace stdext {                      // <--- another namespace for your compiler
  template<> class hash_compare<MyClass> {    // <--- hash_compare instead of hash for your compiler
    size_t operator()(const MyClass &mc) const {
      return mc.hash();                 // <--- it just calls the hash() member of the MyClass class
    }
  };
}
 
int main(void) {
  hash_set<MyClass> myHashSet;   // <--- will use the hash function we defined earlier, and the operator==
 
  MyClass mc1(1);
  MyClass mc2(2);
  MyClass mc3(3);
  MyClass mc4(4);
 
  myHashSet.insert(mc1);
  myHashSet.insert(mc3);
  myHashSet.insert(mc2);
  
  hash_set<MyClass>::const_iterator it = myHashSet.find(mc3);  // <--- this one should be found
  if (it != myHashSet.end()) {
    cout << "found : " << *it << endl;
  }
  else {
    cout << "not found !!" << endl;
  }
 
  it = myHashSet.find(mc4);                                    // <--- this one should not be found
  if (it != myHashSet.end()) {
    cout << "found : " << *it << endl;
  }
  else {
    cout << "not found !!" << endl;
  }
 
  return 0;
}

Select allOpen in new window

I'm just wondering why specifically you want to use a hash set and whether just using the standard std::set implementation (which is part of the C++ standard) would be sufficient?
http://www.cplusplus.com/reference/stl/set/

Now, everything defining the hash_set compiles just fine, however, when I try to declare a hash_set, I get the following error:

hash_set<MyClass> h;

error C2039: 'bucket_size' : is not a member of 'stdext::hash_compare<MyClass>'
         : see declaration of 'stdext::hash_compare<MyClass>'
         : see reference to class template instantiation 'stdext::_Hash<_Traits>' being compiled
        with
        [
            _Traits=stdext::_Hset_traits<MyClass,stdext::hash_compare<MyClass>,std::allocator<MyClass>,false>
        ]
        c:\documents and settings\brian\desktop\raptor\raptor_ui.cpp(36) : see reference to class template instantiation 'stdext::hash_set<_Kty>' being compiled
        with
        [
            _Kty=MyClass
        ]
 : error C2065: 'bucket_size' : undeclared identifier
 : error C2039: 'min_buckets' : is not a member of 'stdext::hash_compare<MyClass>'
 : see declaration of 'stdext::hash_compare<MyClass>'
 : error C2065: 'min_buckets' : undeclared identifier


Any thoughts on what may be causing this?

That's the problem with non-standard template classes heh. Different compilers have their own ways of implementing them.

Try this (again not tested as I don't have your compiler) :

#include <iostream>
#include <string>
#include <hash_set>            // <--- another include for your compiler
 
using namespace std;
using namespace stdext;        // <--- another namespace for your compiler
 
class SomeObject {             // <--- empty class just for testing
};
 
class MyClass{
  private :
    int i, j, k, l, m;
    string a, b, c;
    SomeObject* SO;
  public :
    MyClass(int ii) : i(ii) { }         // <--- just for testing only one member initialized
    ~MyClass() { }
    
    friend ostream& operator<<(ostream &os, const MyClass &mc);
 
    bool operator==(const MyClass &mc) const {      // <--- needs to be provided
      return (i == mc.i);
    }
 
    bool operator<(const MyClass &mc) const {       // <--- provide this also
      return (i < mc.i);
    }
 
    size_t hash() const {                           // <--- this will be the hash function used
      return i;                                     // <--- just a stupid test hash function now
    }
};
 
ostream& operator<<(ostream &os, const MyClass &mc) {    // <--- provided to output a MyClass instance
  os << mc.i;
  return os;
}
 
namespace stdext {                      // <--- another namespace for your compiler
  template<> class hash_compare<MyClass> {    // <--- hash_compare instead of hash for your compiler
    public :
      const size_t bucket_size = 4;
      const size_t min_buckets = 8;
      hash_compare() { }
 
      size_t operator()(const MyClass &mc) const {
        return mc.hash();                 // <--- it just calls the hash() member of the MyClass class
      }
 
      bool operator()(const MyClass &mc1, const MyClass &mc2) const {
        return (mc1 < mc2);
      }
  };
}
 
int main(void) {
  hash_set<MyClass> myHashSet;   // <--- will use the hash function we defined earlier, and the operator==
 
  MyClass mc1(1);
  MyClass mc2(2);
  MyClass mc3(3);
  MyClass mc4(4);
 
  myHashSet.insert(mc1);
  myHashSet.insert(mc3);
  myHashSet.insert(mc2);
  
  hash_set<MyClass>::const_iterator it = myHashSet.find(mc3);  // <--- this one should be found
  if (it != myHashSet.end()) {
    cout << "found : " << *it << endl;
  }
  else {
    cout << "not found !!" << endl;
  }
 
  it = myHashSet.find(mc4);                                    // <--- this one should not be found
  if (it != myHashSet.end()) {
    cout << "found : " << *it << endl;
  }
  else {
    cout << "not found !!" << endl;
  }
 
  return 0;
}

Select allOpen in new window

>> bucket_size and min_buckets have to be declared as static

Not according to :

         http://msdn2.microsoft.com/en-us/library/1s1byw77.aspx

>>Not according to :
    >>     http://msdn2.microsoft.com/en-us/library/1s1byw77.aspx

According to my compiler (VS 2008) it has to be declared static.
The sample code provided by you compiles, as soon as these both constants are declared static.

>> The sample code provided by you compiles, as soon as these both constants are declared static.
I tend to agree with this assertion as I experience the same with VS2005.

1>------ Build started: Project: testr, Configuration: Debug Win32 ------
1>Compiling...
1>main.cpp
1>c:\temp\testr\testr\main.cpp(43) : error C2864: 'stdext::hash_compare<MyClass>::bucket_size' : only static const integral data members can be initialized within a class
1>c:\temp\testr\testr\main.cpp(44) : error C2864: 'stdext::hash_compare<MyClass>::min_buckets' : only static const integral data members can be initialized within a class
1>c:\temp\testr\testr\main.cpp(45) : error C2758: 'stdext::hash_compare<MyClass>::bucket_size' : must be initialized in constructor base/member initializer list
1>        c:\temp\testr\testr\main.cpp(43) : see declaration of 'stdext::hash_compare<MyClass>::bucket_size'
1>c:\temp\testr\testr\main.cpp(45) : error C2758: 'stdext::hash_compare<MyClass>::min_buckets' : must be initialized in constructor base/member initializer list
1>        c:\temp\testr\testr\main.cpp(44) : see declaration of 'stdext::hash_compare<MyClass>::min_buckets'
1>c:\program files\microsoft visual studio 8\vc\include\xhash(127) : error C2597: illegal reference to non-static member 'stdext::hash_compare<MyClass>::bucket_size'
1>        c:\program files\microsoft visual studio 8\vc\include\hash_set(69) : see reference to class template instantiation 'stdext::_Hash<_Traits>' being compiled
1>        with
1>        [
1>            _Traits=stdext::_Hset_traits<MyClass,stdext::hash_compare<MyClass>,std::allocator<MyClass>,false>
1>        ]
1>        c:\temp\testr\testr\main.cpp(58) : see reference to class template instantiation 'stdext::hash_set<_Kty>' being compiled
1>        with
1>        [
1>            _Kty=MyClass
1>        ]
1>c:\program files\microsoft visual studio 8\vc\include\xhash(128) : error C2597: illegal reference to non-static member 'stdext::hash_compare<MyClass>::min_buckets'
1>Build log was saved at "file://c:\temp\testr\testr\Debug\BuildLog.htm"
1>testr - 6 error(s), 0 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

Select allOpen in new window

Ok. Nice :)

I think I'm excused since I wrote the code without the possibility to test it lol.

>> I think I'm excused since I wrote the code without the possibility to test it lol.
Of course. :)

Thanks for all the effort on the question! As I think we can all agree, the documentation is very poor on this!

Like I said before, you might be better off using std::Set unless you specifically need to use a hash_Set.

I have moved over to use std:set -- though I am not thrilled about the slower lookup speeds

Thanks evil

I think it is ridiculous that they took hash_set out of the standard, I use them a lot in other languages

>> I think it is ridiculous that they took hash_set out of the standard,

They didn't take it out - they just didn't put it in. The reason was that they were not yet proposed at the moment the standard was published. They might be added in later versions of the standard.

Ok, in that case - I think it's ridiculous that it isn't in in the first place - In my view of things, hash_set provides an important part of any language.

Then again, I learned to program with VB -- so my view of reality differs wildly from the old farts that decide things on these languages =)

Well, look at it this way : you can always find things to add to the standard. At one point you have to decide to stop adding stuff, and publish the standard. Otherwise it's never-ending.

Btw, you can use the standardized STL containers to create hash-based data structures without a problem.

So, basically there's another way to simulate a hash_set using other structures?

Sure. You could for example use something like this :

        multimap< hash<string>, string >

or :

        map< hash<string>, vector<string> >

or even differently.

Thanks for the great info Infinity, it is much appreciated!