c++ - hash_multimap find が正常に機能しない

Question

しばらくの間、hash_multimap を使用しようとしましたが、一致するキーが見つかったことを知っていても、find メソッドはコンテナーの最後に反復子を与え続けます。私が混乱しているのは、以前は別のプロジェクトで同じコードを使用したことがあり、完全に機能していましたが、現在は再生されていることです。私が何かを見つけていることを知っている理由は、ハッシュ関数とハッシュ比較にいくつかの計算を入れたからです。これは、キーが見つかり、hash_multimap::find メソッドに与えたものと一致することを示していますイテレータをくれます。

最初にヘッダーファイル

//
//  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

そしてソースファイル

//
//  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

スペースを節約するために、上記のブロックから多くのメソッドを切り取ったことに注意してください。それらは当面の問題とは関係がないためです。ただし、それらの宣言はヘッダーファイルに残しました。また、私がテンプレートを使ってやっているいくつかのことが醜いことも承知しています。とりあえず対処してください。

ここで、コードで何が起こっているのか、どこに問題があるのかについて詳しく説明します。getlocalobjects メソッドでは、"exists(key)" メソッドが呼び出され、hash_multimap に指定されたキーを持つ要素があるかどうかが判断されます。上記のように、 equal_to 関数に cout を入れて、いつ使用され、その結果が何であるかを教えてくれるので、何かを見つけることができることを知っています。

一貫して、(equal_to デバッグを介して) はいと言っていますが、exist メソッドは依然として false を返します。これにより、hash_multimap::find にバグがある可能性があると考えるようになりました。これは、何かが見つかったとしても、hash_multimap::end へのイテレータが返されることを意味するためです。

私の質問は、マルチマップの使用に関してひどく間違っているのでしょうか? 私の特性構造体には、マルチマップが正しく機能するために必要なものがありませんか?

EDITと、忘れていたhashKeyの実装が含まれています

ヘッダ

#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

とソース

#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

編集 [SOVLED] hash_multimap tp を unordered_multimap に変更したところ、動作するようになったので、最初の疑惑は正しかったです。現時点では、hash_multimap にバグがあり、find メソッドが常に最後に反復子を与えるということです。私はVisual Studio C ++ 2010を使用していることに注意してください。他のプラットフォームや他のコンパイラではバグが発生しない可能性がありますが、私の場合は反抗的にバグが発生しました

c++ - hash_multimap find が正常に機能しない

1 に答える 1

Related

Reference