hash_multimap find not working the way it should

Question

I've been trying to use a hash_multimap for sometime now, but the find method keeps giving me a iterator to the end of the container even though I know it found a matching key. What has me confused is that I've used the same code before for a different project with it working perfectly but now its playing up. The reason I know its finding something is because I've put a few cout in the hash function and hash compare, which is telling me that a key is found and that it matches what I gave the hash_multimap::find meathod, yet still it gives me an iterator.

first the header file

//
//  HashGrid.h
//  Planetarium
//
//  Created by Taura J Greig on 24/08/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#ifndef _HASHGRID_
#define _HASHGRID_

#include <iostream>
#include <hash_map>
#include <deque>
#include "..//hashKey.h"


struct myTraits
{
    static const size_t bucket_size = 4;
    static const size_t min_buckets = 8;

    myTraits() { };

    myHash hashfunction;
    myEqualTo equal_to;

    size_t operator() (const hashKey& key) const
    {
        size_t hashval = 0;
        hashval = ((key.y * globalGridWidth) + key.x);

        cout << "x : " << key.x << " y : " << key.y << endl;
        cout << "hashVal : " << hashval << endl;

        return hashval;
    }

    bool operator() (const hashKey& key1, const hashKey& key2) const
    {
        bool test = (key1.x == key2.x && key1.y == key2.y);
        cout << "equal_to = " << test << endl;
        return test;
    }
};

using namespace std;
//using namespace stdext;


using namespace stdext;

template <class T>
class HashGrid
{
public:
    typedef deque<T *> localObjects;
    typedef pair<hashKey, T *> addingPair;
    typedef hash_multimap <hashKey, T *, myTraits> hashmMap;
    typedef typename hash_multimap <hashKey, T *, myTraits> :: iterator hashmMapItor;
    typedef pair<hashmMapItor, hashmMapItor> valueRange;

private:

    hashKey keyOffsets[9];

    int gridSize;
    hash_multimap<hashKey, T*, myTraits> theMap;

    inline bool exists(hashKey & theKey);
    inline bool exists(hashKey & theKey, hashmMapItor & it);
public:
    HashGrid();

    void setup(int gridSize);
    void update();
    void draw(); // this is used for viusal debug,

    void resize();

    void addObject(T * object);

    void getLocalObjects(float & x, float & y, int range, localObjects & p1);

};

template <class T>
inline bool HashGrid<T>::exists(hashKey & theKey)
{
    hashmMapItor it;
    it = theMap.find(theKey);
    if (it == theMap.end())
    {
        return false;
    }
    else
    {
        return true;
    }
}

template <class T>
inline bool HashGrid<T>::exists(hashKey & theKey, 
                                      hashmMapItor & it)
{
    it = theMap.find(theKey);
    if (it == theMap.end())
    {
        return false;
    }
    else
    {
        return true;
    }
}

#include "HashGrid.cpp"

#endif

and the source file

//
//  HashGrid.cpp
//  Planetarium
//
//  Created by Taura J Greig on 26/08/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#ifndef _HASHGRID_SOURCE_
#define _HASHGRID_SOURCE_

#include "HashGrid.h"
#include "ofMain.h"


template<class T>
void HashGrid<T>::update()
{
    theMap.clear();
}

template <class T>
void HashGrid<T>::addObject(T *obj)
{
    hashKey tempKey;
    tempKey.x = int(obj -> getPos().x) / gridSize;
    tempKey.y = int(obj -> getPos().y) / gridSize;

    cout << "tempKey.x : " << tempKey.x  << endl;
    cout << "tempKey.y : " << tempKey.y  << endl;

    theMap.insert(addingPair(tempKey, obj));
}

template <class T>
void HashGrid<T>::getLocalObjects(float & x, float & y, int range, localObjects & p1)
{
    cout << "you are gettin local objects" << endl; 

    int gridX = (int(x) / gridSize);
    int gridY = (int(y) / gridSize);

    cout << "player x : " <<  x << endl;
    cout << "player y : " <<  y << endl;
    cout << "girdX " << gridX << endl;
    cout << "girdY " << gridY << endl;


    for (int i = 0; i < 9; i++)
    {
        hashKey tempkey;    

        tempkey.x = gridX;
        tempkey.y = gridY;

        tempkey += keyOffsets[i];

        cout << i << " tempKey : " << tempkey.x << " " << tempkey.y << endl;

        cout << "exists " << exists(tempkey) << " ";

            //this is where the problem lies, the exists function will always return 
            //false even when the key is found
        if (exists(tempkey)) 
        {
            cout << "found" << endl;

            hashmMapItor it;
            valueRange elements;

            elements = theMap.equal_range(tempkey);
            for (it = elements.first; it != elements.second; it++)
            {
                p1.push_back(it->second);

            }
        }
        else
        {
            cout << "not found" << endl;
        }
    }
}

#endif

Note that I've cut a lot of methods out of the block above to save space because they are unrelated to the problem at hand. However I've left their declarations in the header file. Also I am aware that there a few things that I'm doing with templates that are ugly. Just deal with it for now.

Now I'll go into detail about whats happening in the code and where the problem lies. In the getlocalobjects method, the method "exists(key)" is called to determine if the hash_multimap has an element with the key provided. I know that it does find something because as I mentioned above because I put cout in the equal_to function to tell me when its used an what its result are.

Consistently its telling me yes (via equal_to debug) it found something but the exist method will still return false. This leading me to believe that there may be a bug in hash_multimap::find since it means that even if it finds something its gives me an iterator to hash_multimap::end

So my question is am I doing horribly wrong regarding the use of the multimap? does my traits struct not have something required for the multimap to work correctly

EDIT and the implementation for the hashKey that i forgot it include

header

#ifndef _HASHKEY_
#define _HASHKEY_

#include <iostream>

using namespace std;

static int globalGridSize = 1;

static int globalGridWidth = 1;
static int globalGridHeight = 1;

struct hashKey
{
public:
    int x;
    int y;

    hashKey();
    hashKey(int x, int y);

    void set(int x, int y);
    void set(hashKey & key);

    void printKey()
    {
        cout << x << " " << y <<  endl;
    }

    bool operator < (const hashKey & key1) const;

    bool operator == (const hashKey & key1) const;

    hashKey& operator += (hashKey & key1);
};

#endif

and source

#ifndef _HASHKEY_SOURCE_
#define _HASHKEY_SOURCE_

#include "hashKey.h"

hashKey::hashKey()
{
    x = 0;
    y = 0;
}

hashKey::hashKey(int x, int y)
{
    hashKey::x = x;
    hashKey::y = y;
}

void hashKey::set(int x, int y)
{
    hashKey::x = x;
    hashKey::y = y;
}

void hashKey::set(hashKey &key)
{
    x = key.x;
    y = key.y;
    cout << "set: x = " << x << " y = " << y << endl; 
}

bool hashKey::operator<(const hashKey &key1) const
{
    if ( (this->x < key1.x) && (this->y < key1.y))
    {
        return true;
    }
    return false;
}

bool hashKey::operator == (const hashKey &key1) const
{
    if ((this-> x == key1.x) && (this->y == key1.y))
    {
        return true;
    }
    return false;
}

hashKey& hashKey::operator+=(hashKey &key1)
{
    this->x += key1.x;
    this->y += key1.y;
    return *this;
}

#endif

EDIT [SOVLED] I changed the hash_multimap tp an unordered_multimap and now it works, so initial suspicion was right, that at this time the hash_multimap is bugged an its find method will always give an iterator to the the end. Note that i'm using visual studio c++ 2010, it may not be bugged on other platforms or other compilers, however it defiantly was bugged in my case

Answer 1

The content below is speculation as not all the relevant code is visible.

It seems that you have:

• A hash which is of type size_t (as created from the first operator() of myTraits)
• A key of type hashKey (which is not a hash from the hash_multimap's perspective)

You did not provide the implementation of hashKey, so my immediate question is:

• Did you provide the equality operator for hashKey?
• Or alternatively, did you override equal_to<haskHey>?

The potential problem (and reason for the above questions) that I see is that you defined your hashmMap as hash_multimap <hashKey, T *, myTraits> which overrides the hashing function, but it does not override the key equality (which is of type hashKey). So, I presume that the default comparator of hashKey (and not the one defined in myTraits) might be used. Perhaps hash_multimap <hashKey, T *, myTraits, myTraits> would suffice?

---

Update: I just notice that VS's hash_multimap has a different signature, than the one coming from STL. Compare:

• Visual Studio version
• STL version

The latter has hashing function and key comparator separated. This is just asking for terrible problems once you switch compilers!