0

我一直在尝试使用 hash_multimap 一段时间，但是即使我知道它找到了匹配的键，find 方法仍然给我一个指向容器末尾的迭代器。让我感到困惑的是，我之前在不同的项目中使用过相同的代码，它运行良好，但现在它正在发挥作用。我知道它找到东西的原因是因为我在散列函数和散列比较中放了一些 cout，这告诉我找到了一个键并且它与我给 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 是否有一个元素提供了key。我知道它确实找到了一些东西，因为正如我上面提到的，因为我将 cout 放在 equal_to 函数中以告诉我它何时使用以及它的结果是什么。

它始终告诉我是的（通过 equal_to 调试）它找到了一些东西，但存在的方法仍然会返回 false。这让我相信 hash_multimap::find 中可能存在一个错误，因为这意味着即使它找到了一些东西，它也会给我一个 hash_multimap::end 的迭代器

所以我的问题是我在使用多重地图方面做错了吗？我的特征结构是否没有多图正常工作所需的东西

编辑和我忘记的 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，它可能不会在其他平台或其他编译器上被窃听，但在我的情况下它无疑是被窃听的

4

1 回答 1

0

下面的内容是推测，因为并非所有相关代码都是可见的。

看来你有：

  • 类型size_t为的哈希（从第一个operator()创建myTraits）
  • 类型的键hashKey（从 hash_multimap 的角度来看不是散列）

您没有提供 的实现hashKey，所以我的直接问题是：

  • 您是否为 提供了相等运算符hashKey？
  • 或者，您是否覆盖equal_to<haskHey>？

我看到的潜在问题（以及上述问题的原因）是您将您定义hashmMap为hash_multimap <hashKey, T *, myTraits>覆盖散列函数的 as，但它没有覆盖键相等（类型为hashKey）。因此，我认为可能会使用默认比较器hashKey（而不是 中定义的比较器myTraits）。也许hash_multimap <hashKey, T *, myTraits, myTraits>就足够了？

更新：我只是注意到 VS 的hash_multimap签名与来自 STL 的签名不同。相比：

后者具有分离的散列函数和密钥比较器。这只是在切换编译器后提出可怕的问题！

于 2013-05-30T07:06:08.043 回答