3. STL: Map - freien schluessel finden.

STL: Map - freien schluessel finden.

  • D

    LordJaxom schrieb:

    DEvent schrieb:

    Seit wann ist eine Hashmap oder ein Hashset sortiert???

    Seit wann ist eine STL-Map (ich gehe mal davon aus dass std::map gemeint ist) eine Hashmap?

    😮 hm bin Java gewöhnt, ist den std::map keine Hashmap?

    Edit:
    Okay, die STL ist ja total anderes aufgebaut als die Java API. Gut dann bezieht sich mein Vorschlag nur auf Hashmaps.

    0
  • L

    Îch kann jetzt nicht den Standard zitieren, aber alle Implementierungen die mir bislang über den Weg gelaufen sind waren balanced binary trees.

    0
  • A

    std::map ist definitiv keine Hashmap! Es ist eine einfacher pair-Container. Nicht mehr und nicht weniger. Das einzige besondere ist, das beim einfügen von pairs diese gleich an die richtige sortierte Stelle eingefügt werden.

    Wer Hashmaps braucht, sollte auch die std::tr1::hash_map nutzen. Beim VisualC++ 7.1 ist auch stdext::hash_map dabei.

    0
  • D

    Artchi schrieb:

    std::map ist definitiv keine Hashmap! Es ist eine einfacher pair-Container. Nicht mehr und nicht weniger. Das einzige besondere ist, das beim einfügen von pairs diese gleich an die richtige sortierte Stelle eingefügt werden.

    Wer Hashmaps braucht, sollte auch die std::tr1::hash_map nutzen. Beim VisualC++ 7.1 ist auch stdext::hash_map dabei.

    "Einfach" ein Pair-Container ist das auch nicht. std::map nutzt einen Red-black Tree um die Daten zu halten. Daher auch das sortieren der Pairs.

    grüße

    0
  • B

    Dass es keine Hashmap sein kann sollte einem spätestens auffallen, wenn man versucht eine Hashfunktion vorzugeben und nur die Möglichkeit zur Übergabe eines Ordnungsprädikats vorfindet.

    0
  • M

    Bastel dir doch eine Klasse die eine laufende eindeutige nummer (eine Id) erzeugt. So hast du keine Duplikate und brauchst nicht jedesmal aufwändig zu prüfen ob eine Id bereits existiert.

    Sowas wie:

    class IdServer
{
public:
Idserver():id(0){};
getNextId(){return id++);
protected:
int id;
}
    0
  • T

    dann sollte die klasse singleton werden, sonst ist das ganze konzept von eindeutigkeit gefährdet.

    0
  • B

    thordk schrieb:

    dann sollte die klasse singleton werden, sonst ist das ganze konzept von eindeutigkeit gefährdet.

    Nein, die IDs sollen nur innerhalb der Map eindeutig sein.

    0
  • T

    ich ging davon aus, dass die map von verschiedenen, unabhängigen methoden verwendet wird.

    0
  • S

    Danke erst mal fuer die vielen Antworten. Ich glaube ich hab vergessen ein paar Randbedingungen zu erwaehnen. Die Mapping-Tabelle wird ueber eine sehr lange Zeit verwendet und ich bin sicher, dass es ueber kurz oder lang zu einem Ueberlauf der verwendeten Schluessel kommen wird und ich danach ueber einen "fragmentieren" Bereich nach freien ID's suchen muss. Eine sequentielle Suche ist daher nur beschraenkt moeglich.
    Die map wird hauptsaechlich dazu verwendete gespeicherte Objekte anhand ihrer ID schnellstmoeglich zu finden.
    An und fuer sich tut es ja. Ich war mir nur nicht sicher, ob es doch irgendeine "schoenere" Moeglichkeit gibt, nicht verwendete Schluessel aus der Map zu ziehen.

    Gruss
    snuggl3s

    0
  • F

    Eine extra Klasse statt der map wär vielleicht keine schlechte Idee.

    class object_group
{
public:
  object_group( id_t min_id, id_t max_id );

  void insert_object( object* obj );
  void remove_object( object* obj );

private:
  id_t get_free_id() const;

private:
  typedef std::map<id_t, object*> id_map;
  id_map  objects_;
  typedef <<some_container>>  id_set;
  id_set  free_ids_;
};

object_group::object_group( id_t min_id, id_t max_id )
{
  // fill free_ids_
}

void insert_object( object* obj )
{
  id_t const id = get_free_id();
  obj->set_id(id);
  objects_.insert(id_map::value_type(id, obj));
  free_ids_.erase(id);
}

void remove_object( object* obj )
{
  objects_.erase(obj->get_id());
  free_ids_.insert(obj->get_id());
}

    So als kleine Anregung.

    0
  • V

    snuggl3s schrieb:

    Danke erst mal fuer die vielen Antworten. Ich glaube ich hab vergessen ein paar Randbedingungen zu erwaehnen. Die Mapping-Tabelle wird ueber eine sehr lange Zeit verwendet und ich bin sicher, dass es ueber kurz oder lang zu einem Ueberlauf der verwendeten Schluessel kommen wird und ich danach ueber einen "fragmentieren" Bereich nach freien ID's suchen muss. Eine sequentielle Suche ist daher nur beschraenkt moeglich.

    dann würfle doch einfach. hast 32-bitter als IDs? und sagen wie mal 1000000 datensätze. dann haste beim würfeln ne cahce von 1 zu 4000, daß du nicht beim ersten wurf nen freie platz triffst. ist das nicht gut genug? und 1 zu 16000000, daß du auch beim zweiten mal nicht triffst.

    Die map wird hauptsaechlich dazu verwendete gespeicherte Objekte anhand ihrer ID schnellstmoeglich zu finden.

    dann nimm hash_map statt map.

    An und fuer sich tut es ja. Ich war mir nur nicht sicher, ob es doch irgendeine "schoenere" Moeglichkeit gibt, nicht verwendete Schluessel aus der Map zu ziehen.

    nicht aus der map. bei einer sehr vollen hashtable würde ich noch nen 4k großen stack (oder ringpuffer, falls ich freie IDs möglichst nicht sofort wiederverwenden will) der zuletzt freigegebenen IDs mitschleppen. bei 1 zu 4000 ist aber ein sicher benötigter plattenzugriff auf den stack vor dem vergeben der ID teurer, als einfach zu würfeln. sinds aber so viele zugriffe, daß der stack eh im ram bleibt, ist er schneller. worde hier aber keine überlegungen hinverschwenden, da O(1) in diesem fall nicht deutlich langsamer als O(1) ist und man eh erst duch ausmessen sehen kann, was besser ist und die messerei durchaus spät gemacht werden kann, weil du die ganze geschichte in eine klasse gewrapped hast, die eine hash_map enthält und deren schnittstelle zur verfügung stellt und dasüberhinaus die frage nach einer freien ID erlaubt (bzw ID als rückgabewert von "ID insert(Data d)" in einer überladung zu "void insert(ID i,Data d)" anbietet.)

    0
Anmelden zum Antworten