std::unordered_map fuer Zahlenkombinationen, Wavefront Format

Hi,

Ich schreibe fuer meine Engine derzeit einen .obj model importer.
Ich kriege ab einem gewissen Zeitpunkt folgende Informationen:

f 85/22/28 86/23/28 87/24/28
f 88/23/29 89/22/29 90/24/29
f 85/22/28 92/22/30 93/25/30
...

Ich muss fuer jede einzigartige Kombination, z.B. 85/22/28 (ist in dem Fall nicht einzigartig) GENAU ein eigenes Objekt einer gewissen Struktur erstellen.
Dann verweise Ich meinen Indexbuffer auf dieses erstellte Objekt,
wobei Indexbuffer := std::vector<unsigned int> vIndexBuffer;
Z.B. vIndexBuffer.push_back(0);

Problem: Wie man sieht wiederholt sich die Kombination im 3ten face.
Also muss Ich immer, bevor Ich ein neues Objekt einer gewissen Struktur erstelle prüfen ob diese Kombination nicht schon vorhanden ist, falls ja, dann verweise Ich meinen Indexbuffer auf den Index des bereits erstellten Objekts (wäre also in dem Fall 0).

Mir wurde empfohlen std::unordered_map zu benutzen, jedoch komme Ich damit garnicht klar. Nichtmal ein Ansatz fällt mir ein. Ich muss halt irgendwie die Kombination von unsigned ints reinpacken und dann eine Hashfunktion schreiben um später zu ueberpruefen ob diese Kombination schon vorhanden ist.

Falls sich jemand damit auskennt, bitte um Hilfe!

Danke im Vorraus!
Gruß

volkard

Sind die Zahlen sogar immer so klein, also unter 100?
Dann kannste ganz leicht a*10000+b*100+c statt a/b/c nehmen.
Also 852228 statt "85/22/28".

Hi,
Danke fuer die Antwort.

Leide sind die Zahlen bei größeren Meshes auf deutlich größer.

Gruß

Hier ein Beispiel, wie man unordered_map verwendet:

#include <unordered_map>
#include <vector>
#include <bitset>
#include <string>
#include <utility>

struct Key {
    std::string first;
    std::string second;
};

struct KeyHash {
 std::size_t operator()(const Key& k) const
 {
     return std::hash<std::string>()(k.first) ^
            (std::hash<std::string>()(k.second) << 1);
 }
};

struct KeyEqual {
 bool operator()(const Key& lhs, const Key& rhs) const
 {
    return lhs.first == rhs.first && lhs.second == rhs.second;
 }
};

int main()
{
    // default constructor: empty map
    std::unordered_map<std::string, std::string> m1;

    // list constructor
    std::unordered_map<int, std::string> m2 =
    {
        {1, "foo"},
        {3, "bar"},
        {2, "baz"},
    };

    // copy constructor
    std::unordered_map<int, std::string> m3 = m2;

    // move constructor
    std::unordered_map<int, std::string> m4 = std::move(m2);

    // range constructor
    std::vector<std::pair<std::bitset<8>, int>> v = { {0x12, 1}, {0x01,-1} };
    std::unordered_map<std::bitset<8>, double> m5(v.begin(), v.end());

    // constructor for a custom type
    std::unordered_map<Key, std::string, KeyHash, KeyEqual> m6 = {
            { {"John", "Doe"}, "example"},
            { {"Mary", "Sue"}, "another"}
    };
}

( http://en.cppreference.com/w/cpp/container/unordered_map/unordered_map )

Hi,
Ich kann die codebeispiele von den ganzen Seiten.
Aber wie kriegt man das mit 3 int Werten hin?
In den Beispielen wird immer nur gezeigt wie man ein Paar in die hashmap schmeist,
Ich muss jedoch 3 Werte reinschmeissen!
Gruß

Skym0sh0

Ich weis nicht genau, ob dir klar ist, was Hashing bedeutet oder was es ist.

Daher hier eine kurze Erklärung:
Aus einem Dateum (also ein paar Daten, nicht das zeitliche Datum ist gemeint) soll mithilfe einer (math.) Funktion der Index von eben diesen Daten für eine Datenstruktur deterministisch erzeugt werden.

Auf deutsch:
Stell dir ein Array vor. Dort hast du eine Reihe Indizes (von 0 bis n-1) und Daten die du an die entsprechende Adresse schreibst. Z.B.:

arr[0] = "Abc";
arr[1] = "Bcd";
...

Du hast also quasi eine Zuordnung von Ints zu Strings:

N -> Str*

Wir wollen aber jetzt, dass die Ints durch einen beliebigen Typen (in deinem Fall 3 Ints) ersetzt werden können. Die Werte (hier in dem Beispiel oben die Strings) sollen auch parametrisiert werden, aber das ist ja kein Problem.

Was wir also brauchen ist eine FUnktion, die aus Strings (oder halt 3 Ints, oder oder oder) eine natürliche Zahl macht. Und zwar eindeutig. Das bedeutet, wenn das gleiche mehrmals reinkommt, soll auch immer dasselbe rauskommen. Man kann auch sagen, die Ausgabe ist nur von der Eingabe abhängig.

In der Uni waren die ersten einfachen Beispiele immer die Modulo-Funktion:

h(x) = x % 13 (z.B.)

Ein Nachteil dabei ist, es gibt merhere Eingaben, die die gleiche Ausgabe erzeugen

-> x + i*13 mit i = natürliche Zahl

Die Kunst es ist, sich eine Funktion auszudenken/zu schreiben, die möglichst kollisionsfrei ist, schnell zu berechnen ist und für die gleiche Eingabe immer die gleiche Ausgabe erzeugt.

Die genauen Spezifikationen vom C++ Standard kenne ich nicht. Aber eine einfache (und schlechte) Funktion wäre die Addition der 3 Werte.

Hier ein Beispiel:

#include <unordered_map>
#include <vector>
#include <bitset>
#include <string>
#include <utility>

 struct IntTriple
 {
	int a, b, c;

	IntTriple(int a = 0, int b = 0, int c = 0)
		: a(a), b(b), c(c)
	{ }

	bool operator==(IntTriple const& oth) const
	{
		return this->a == oth.a && this->b == oth.b && this->c == oth.c;
	}
 };

struct IntTripleHash {
	std::size_t operator()(const IntTriple& k) const
	{
		return k.a + k.b + k.c;
		//return k.a + 100*k.b + 10000*k.c
		// hier bessere Funktionen bauen
	}
};

int main()
{
    std::unordered_map<IntTriple, std::string, IntTripleHash> l1;

	l1[IntTriple(1, 2, 3)] = "abc";
	l1[IntTriple(1, 2, 5)] = "cbde";
}

Ideone

Das Prinzip des Hashen ist recht einfach, aber eine gute Hashfunktion zu schreiben ist es nicht. Nicht einmal die GCC-Standardlibrary macht das gut. Hier mein Vorschlag:

Skym0sh0 schrieb:

struct IntTripleHash {
	std::size_t operator()(const IntTriple& k) const
	{
		unsigned a=k.a, b=k.b, c=k.c; // cast to unsigned
		return ((17 + a)*31 + b<<10 + b>>20)*31 + c<<20 + c>>10;
	}
};

Kellerautomat

boost::hash_combine

Nice! Danke euch beiden fuer die Antworten!
Ka ob man jetzt wirklich ne Hashfunktion braucht:

hashmap map;

	map[IntTriple(1, 2, 3)] = 0;
	map[IntTriple(1, 2, 5)] = 1;

	hashmap::const_iterator find = map.find(IntTriple(1, 2, 5)); // find call, braucht man die Hashfunktion dafuer?

	if( find == map.end() )
	{
		std::cout << "Not found!";
	}
	else
	{
		std::cout << "Found!\n";
		std::cout << find->first.a << find->first.b << find->first.c;
	}

Hab zwar jetzt die Hashfunktion

struct IntTripleHash 
{ 
	std::size_t operator()(const IntTriple& k) const 
	{ 
		unsigned a=k.a, b=k.b, c=k.c; // cast to unsigned 
		return ((17 + a)*31 + b<<10 + b>>20)*31 + c<<20 + c>>10;
	} 
};

hinzugefügt bin mir aber nicht sicher ob das unbedingt notwendig war, da Ich find benutze. Wofuer ist dann diese Hashfunktion? Fuer find?

Ethon

Kellerautomat schrieb:

boost::hash_combine

Warum zur Hölle gibt's soetwas nicht in der Standardbibliothek?
Ne Hashmap ohne Möglichkeit Hashes zu kombinieren anzubieten ist ähnlich sinnvoll wie Autos ohne Sitze zu verkaufen ... man kann damit fahren wenn man nen Stuhl reinstellt aber es ist scheiße.

Skym0sh0

JohnnyYolo schrieb:

Nice! Danke euch beiden fuer die Antworten!
Ka ob man jetzt wirklich ne Hashfunktion braucht:
// ...
hinzugefügt bin mir aber nicht sicher ob das unbedingt notwendig war, da Ich find benutze. Wofuer ist dann diese Hashfunktion? Fuer find?

Ja, dafür braucht man die.

Du willst halt quasi die Position im Array zu wissen kriegen. Und die wird mit der Hashfunktion errechnet.

Zumal du die Hashfunktion (bzw. in den Beispielen hier ist ja ein Funktionsobjekt aka Funktor) eh als Templateparameter angeben musst und die Map halt sich diese wann immer sie braucht. Wenn das irgendwo nicht geht, dann kompilierts nicht.