Új hozzászólás Aktív témák

• #2060 mgoogyi senior tag axelf92 #2056

  Új Válasz 2013-05-09 12:21:33 #2060

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  mgoogyi

  senior tag

  válasz axelf92 #2056 üzenetére

  Valami ehhez hasonló kéne legyen az osztályod:

  template < class Key, class Value>
  class HashArray
  {
  
  bool Insert(const Key & index, const Value & value);
  Value operator[] (Key index) { return ...}
  stb..
  }

  A kérdés az, hogy a mögöttes adatstruktúra hogy kéne, hogy kinézzen.
  Két általános módszer van:
  1, Bináris fában vannak a kulcs-érték párok. Ezesetben a kulcsra értelmezhető kell legyen a < operátor.
  2, Vagy úgynevezett bucketokban, kb van egy tömb, aminek minden eleme egy lista. A tömbbéli indexet valamiféle hasheléssel találod ki. Pl. ha a kulcs egy szám és 1024 elemű a belső tömböd, akkor a kulcs % 1024 helyen lévő listába tolod bele az új elemet. Csakhogy itt generikus kulcsról van szó, azt nem annyira triviális hash-elni.

  Itt valszeg az 1-es az ésszerű irány, ami nagyrészt ugyanez, mint az stl mapje:
  pl:
  #include <map>
  #include <string>
  std::map<int, std::string> m;
  m[1] = "kutya";

  A legegyszerűbb az lenne nyilván, ha lenne belül egy std::map-ed memberként. (leszármaztatni nem szabad belőle)
  De valszeg az 1-es irányt akarja az oktatód, szerintem kérdezd meg, hogy arra gondolt e.

Új hozzászólás Aktív témák