wie verwenden von boost::unordered_map
für meine Anwendung brauche ich die Verwendung einer hash map, damit ich geschrieben habe ein test-Programm, in dem ich speichern einige Instanzen einer baseclass in einer boost::unordered_map. ich möchte aber erreichen die Instanzen durch Aufruf von speziellen Funktionen, die Rückkehr einer abgeleiteten Klasse von der Basis und ich verwenden Sie die Funktionen " Parameter für die hash-Schlüssel unordered_map. wenn keine Klasse gefunden wird, wobei bestimmte Parameter, dann wird eine Klasse generiert und gespeichert in der Karte. der Zweck des Programms kann nicht klar sein, aber hier ist der code.
#include <boost/unordered_map.hpp>
#include <iostream>
using namespace std;
using namespace boost;
typedef unsigned char BYT;
typedef unsigned long long ULL;
class BaseClass
{
public:
int sign;
size_t HASHCODE;
BaseClass(){}
};
class ClassA : public BaseClass
{
public:
int AParam1;
int AParam2;
ClassA(int s1, int s2) : AParam1(s1), AParam2(s2)
{
sign = AParam1;
}
};
struct HashKey
{
ULL * hasharray;
size_t hashNum;
size_t HASHCODE;
HashKey(ULL * ULLarray, size_t Hashnum) : hasharray(ULLarray), hashNum(Hashnum), HASHCODE(0)
{ }
bool operator == (const HashKey & hk ) const
{
bool deg = (hashNum == hk.hashNum);
if (deg)
{
for (int i = 0; i< hashNum;i++)
if(hasharray[i] != hk.hasharray[i]) return false;
}
return deg;
}
};
struct ihash : std::unary_function<HashKey, std::size_t>
{
std::size_t operator()(HashKey const & x) const
{
std::size_t seed = 0;
if (x.hashNum == 1)
seed = x.hasharray[0];
else
{
int amount = x.hashNum * 8;
const std::size_t fnv_prime = 16777619u;
BYT * byt = (BYT*)x.hasharray;
for (int i = 0; i< amount;i++)
{
seed ^= byt[0];
seed *= fnv_prime;
}
}
return seed;
}
};
typedef std::pair<HashKey,BaseClass*> HashPair;
unordered_map<HashKey,BaseClass*,ihash> UMAP;
typedef unordered_map<HashKey,BaseClass*,ihash>::iterator iter;
BaseClass * & FindClass(ULL* byt, int Num, size_t & HCode)
{
HashKey hk(byt,Num);
HashPair hp(hk,0);
std::pair<iter,bool> xx = UMAP.insert(hp);
// if (xx.second) UMAP.rehash((UMAP.size() + 1) /UMAP.max_load_factor() + 1);
if (!xx.first->second) HCode = UMAP.hash_function()(hk);
return xx.first->second;
}
template <typename T, class A,class B>
T* GetClass(size_t& hashcode ,A a, B b)
{
ULL byt[3] = {a,b,hashcode};
BaseClass *& cls = FindClass(byt, 3, hashcode);
if(! cls){ cls = new T(a,b); cls->HASHCODE = hashcode;}
return static_cast<T*>(cls);
}
ClassA * findA(int Period1, int Period2)
{
size_t classID = 100;
return GetClass<ClassA>(classID,Period1,Period2);
}
int main(int argc, char* argv[])
{
int limit = 1000;
int modnum = 40;
int result = 0;
for(int i = 0 ; i < limit; i++ )
{
result += findA( rand() % modnum ,4)->sign ;
}
cout << UMAP.size() << "," << UMAP.bucket_count() << "," << result << endl;
int x = 0;
for(iter it = UMAP.begin(); it != UMAP.end(); it++)
{
cout << ++x << "," << it->second->HASHCODE << "," << it->second->sign << endl ;
delete it->second;
}
return 0;
}
das problem ist, erwarte ich, dass die Größe der UMAP gleich modnum es ist jedoch immer größer als modnum was bedeutet, es gibt mehr als eine Instanz, die die gleichen Parameter und HASHCODE.
was ist die Lösung zu meinem problem? bitte helfen Sie.
Dank
ist das jetzt ok?
Nein, Sie include <windows.h>, machen system("PAUSE") verwenden Sie LARGE_INTEGER und QueryPerformanceCounter (was auch immer diese sind).
Versuchen Sie, das Programm viel kürzer ist, und erklären, was es tun soll
mate, dieser code ist nicht von meinem eigentlichen Anwendung, ist nur ein test Programm und alle Strukturen und Methoden innerhalb des Codes. das ist also der kürzeste.
InformationsquelleAutor ali_bahoo | 2010-10-21
Du musst angemeldet sein, um einen Kommentar abzugeben.
Hier sind ein paar design-Probleme:
Key type speichert einen Zeiger auf einigen array. Aber dieser Zeiger wird initialisiert mit der Adresse von einem lokalen Objekt:
Dies macht die map store eine HashKey-Objekt mit einem baumelnden Zeiger. Auch Sie sind der Rückgabe einer Referenz auf ein Mitglied einer Funktion ein lokales Objekt namens xx in FindClass. Die Nutzung dieser Verweis ruft Undefiniertes Verhalten.
Betrachten Umbenennung der Karte die Schlüssel geben. Der hash-code sollte man sich nicht ein key. Und als operator== für HashKey schon sagt, wollen Sie nicht den eigentlichen Schlüssel, um den hash-code, sondern die Folge von ganzen zahlen mit variabler Länge. Bedenken Sie auch, speichern die Reihenfolge innerhalb des Schlüssels Typ statt ein Zeiger, zum Beispiel als ein Vektor. Darüber hinaus vermeiden Rückkehr Verweise auf Funktion lokale Objekte.
InformationsquelleAutor sellibitze
Mit unordered_map nicht garantieren, dass Sie nicht bekommen hat, Kollisionen, das ist, was Sie hier beschreiben.
Können Sie tune Ihre hashing-Algorithmus zu minimieren, aber in der (unvermeidlichen) Kollision Fall ist, wird der hash-container erweitert die Liste der Objekte im Eimer entspricht, die als hashcode. Der Geschlechter-Vergleich wird dann verwendet, um die Kollision zu einem bestimmten passenden Objekt. Dies kann, wo dein problem liegt - vielleicht ist Ihr
operator==
nicht richtig eindeutig machen ähnliche, aber nicht identische Objekte.Kann man nicht erwarten, ein Objekt pro Eimer oder container wachsen würde unbounded im großen Sammlung Größe Fällen.
btw, wenn Sie eine neuere compiler, den Sie vielleicht finden, es unterstützt
std::unordered_map
, so dass Sie können verwenden, dass (die offizielle STL-version) anstelle der Boost-version.InformationsquelleAutor Steve Townsend