Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » C / C++ (ANSI-Standard) » dumme frage: Hashing mittels STL hash_map ?

Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: > 1 < [ 2 ]
000
11.10.2006, 22:44 Uhr
~grimmel
Gast


Hallo,
ich habe nur eine kurze Frage - der stl container hash map - ist das die gängige art hash maps zu implementieren? Oder gibts da was anderes üblicheres?
Danke
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
001
11.10.2006, 22:52 Uhr
~grimmel
Gast


hat die stl überhaupt einen container hash table? gibts sowas wie hash_map ?
der "normale" map container ist beim find glaube ich langsamer als O(n) oder?
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
002
12.10.2006, 05:49 Uhr
Spacelord
Hoffnungsloser Fall


hash map ist (noch) kein Standard Container.Viele Implementierungen bieten aber trotzdem einen an.
Für den "normalen" map Container garantiert der Standard ,für eine Suche nach einem bestimmten Schlüssel,logarithmische Laufzeit. Wenn du nach nem bestimmten Wert suchen willst ,musst du dir das selber basteln und wirst mit linearer Laufzeit vorlieb nehmen müssen.

Gruß Spacelord
--
.....Ich mach jetzt nämlich mein Jodeldiplom.Dann hab ich endlich was Eigenes.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
003
12.10.2006, 16:17 Uhr
0xdeadbeef
Gott
(Operator)


hash_map ist eine sgi-Erweiterung. Die verhalten sich zum Standard ähnlich wie boost, d.h. sie sind auf dem Papier kein Standard-C++, aber jede bessere Implementierung der STL kann sie.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
004
12.10.2006, 20:38 Uhr
~grimmel
Gast


Danke,

ich bin etwas durcheinander ...ist denn eine std::map<int, ***> nicht eine art hash?
Jeder schlüssel ist doch nur einmal vorhanden und der zugriff erfolgt schnell wie spacelord schon sagt in logarithmischer laufzeit...

danke für aufklärung
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
005
12.10.2006, 20:57 Uhr
0xdeadbeef
Gott
(Operator)


std::map baut intern in aller Regel einen RB-Baum (Der Standard garantiert ein entsprechendes Laufzeitverhalten, d.h. so ziemlich alles läuft in O(log(n))). Eine Hashtabelle dagegen errechnet aus einem Objekt den Hashwert in konstanter Zeit und adressiert damit das Objekt - die Idee ist so eine Art in sich gefaltetes Array. Solange keine Kollisionen vorkommen, geschieht die Adressierung dementsprechend in konstanter Zeit - deswegen besteht die Auswahl eines geeigneten Hashverfahrens auch daraus, die Kollisionsgeschwindigkeit (dass mehrere Objekte den gleichen Hashwert erzeugen) zu minimieren.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
006
12.10.2006, 20:57 Uhr
Blubber2063



Das ist Implementationssache, Hashverfahren haben eigentlich im Mittel eine Laufzeit von O(1), bei logarithmischer Laufzeit ist die Wahrscheinlichkeit eines balancierten Baumes recht wahrscheinlich.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
007
12.10.2006, 21:35 Uhr
~grimmel
Gast


ah jetzt verstehe ich - danke.

ich habe folgende implementierung eines hashs versucht:


Code:

#include <iostream>
#include <ext/hash_map>

Class::Class()
{    
    //std::hash_map<int, double> map(10);
    stdext::hash_map< double, int,size_t(*)(double), eqdouble >  map(10,hash_d);
    //hash_map< double, int,size_t(*)(double), eqdouble >  map(10,hash_d);

    map[3.14] = 3;
    map[2.7] = 2;
    map[2.8] = 15;

    std::cout << "2.7 -> " << map[2.7] << std::endl;
}


struct eqdouble
{
    bool operator()(double d1, double d2) const
    {
        return  d1 == d2;
    }
};


struct eqstr
{
    bool operator()(const char* s1, const char* s2) const
    {
        return strcmp(s1, s2) == 0;
    }
};


size_t Caching::hash_d( double d )
{
    return  (size_t)(fabs( d ));




Mein error lautet:

bei allen drei varianten:
hasp_map not found (first use this function)
stdext undeclared( firlst use this function)

ich habe in meinen bibliotheken geschaut und auch unter /ext/ die betreffenden hash_map files bzw. stl_hash_map gefunden...
aber irgendwie bringe ich das nicht zum laufen....
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
008
12.10.2006, 21:58 Uhr
~grimmel
Gast


liegt am compiler:
habs so hinbekommen:


C++:

namespace __gnu_cxx
{
    template<> struct hash< std::string >
    {
        size_t operator()( const std::string& x ) const
        {
            return hash< const char* >()( x.c_str() );
        }
    };
}


Class::Class()
{    
    __gnu_cxx::hash_map<int, int> hash;
}



hier der Link der das verdeutlicht:
http://gcc.gnu.org/ml/libstdc++/2002-04/msg00107.html
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
009
12.10.2006, 22:01 Uhr
Blubber2063



Also entweder ist die Klasse nicht in dem Header deklariert, oder er findet die Datei nicht. Nebenbei Gleitpunktzahlen als Index sind gar nicht gut, der Wert den du dort angibst ist meistens nicht korrekt. Meint Gleitpunktzahlen sind selbst bei double recht ungenau, da können Dopplungen auftreten oder du die falsche Zahl suchst.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: > 1 < [ 2 ]     [ C / C++ (ANSI-Standard) ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: