Feedback

C++ - Hashtable in C++

Veröffentlicht von am 22.08.2008
(0 Bewertungen)
Diese Hashtable-Klasse ermöglicht es eine generische Liste zu erstellen, die Schlüssel und Werte von beliebigem Typ zulässt.
//**************************************************************************
// CHashtable
//**************************************************************************

template<class TKey, class TValue>
class CHashtable {
  protected:
  template<class TKey, class TValue>
  class CHashvalue {
    public:
    TKey m_hKey;
    TValue m_hValue;
    
    CHashvalue() {}
    CHashvalue(const TKey& hKey, const TValue& hValue) {
      m_hKey = hKey;
      m_hValue = hValue; 
    }
  };
  
  private:
  CList<CHashvalue<TKey, TValue>> m_hObList;
  
  TValue m_hValue_Null;
  
  //-Initialisierung-------------------------------------------------------

  public:
  CHashtable(const TValue& hValue_Null) { m_hValue_Null = hValue_Null; }

  //-Funktionen------------------------------------------------------------

  void Add(const TKey& hKey, const TValue& hValue)  { m_hObList.AddTail(CHashvalue<TKey, TValue>(hKey, hValue)); }
  void Clear()  { m_hObList.RemoveAll(); }
  void Remove(const TKey& hKey);
  BOOL ContainsKey(const TKey& hKey);
  TValue GetValue(const TKey& hKey);
  POSITION GetHeadPosition()  { return m_hObList.GetHeadPosition(); }
  TValue GetNext(POSITION& rPosition)  { return m_hObList.GetNext(rPosition).m_hValue ; }
  TKey GetKey(POSITION& rPosition)  { return m_hObList.GetNext(rPosition).m_hKey ; }
  Int4 GetCount()  { return m_hObList.GetCount(); }
};

//-------------------------------------------------------------------------
// CHashtable::Remove
//-------------------------------------------------------------------------

template<class TKey, class TValue>
AFX_INLINE void CHashtable<TKey, TValue>::Remove(const TKey& hKey) {
  POSITION pos = m_hObList.GetHeadPosition();
  while (pos != NULL) {
    POSITION posOld = pos;
    CHashvalue<TKey, TValue> hHashvalue = m_hObList.GetNext(pos);
    if (hHashvalue.m_hKey == hKey) {
      m_hObList.RemoveAt(posOld);
      
      return;
    }
  }
}

//-------------------------------------------------------------------------
// CHashtable::ContainsKey
//-------------------------------------------------------------------------

template<class TKey, class TValue>
AFX_INLINE BOOL CHashtable<TKey, TValue>::ContainsKey(const TKey& hKey) {
  POSITION pos = m_hObList.GetHeadPosition();
  while (pos != NULL) {
    CHashvalue<TKey, TValue> hHashvalue = m_hObList.GetNext(pos);
    if (hHashvalue.m_hKey == hKey) {
      return TRUE;
    }
  }
  
  return FALSE;
}

//-------------------------------------------------------------------------
// CHashtable::GetValue
//-------------------------------------------------------------------------

template<class TKey, class TValue>
AFX_INLINE TValue CHashtable<TKey, TValue>::GetValue(const TKey& hKey) {
  POSITION pos = m_hObList.GetHeadPosition();
  while (pos != NULL) {
    CHashvalue<TKey, TValue> hHashvalue = m_hObList.GetNext(pos);
    if (hHashvalue.m_hKey == hKey) {
      return hHashvalue.m_hValue;
    }
  }
  
  return m_hValue_Null;
}


Kleine Beispiel:

    CHashtable<CString, CPoint*> ht_Points(NULL);
    ht_Points.Add("Punkt1", new CPoint(10, 20));
    ht_Points.Add("Punkt2", new CPoint(20, 30));
    ht_Points.Add("Punkt3", new CPoint(30, 40));
    
    CPoint* p1 = ht_Points.GetValue("Punkt1");
    CPoint* p2 = ht_Points.GetValue("Punkt2");
    CPoint* p3 = ht_Points.GetValue("Punkt3");
    
    ASSERT(ht_Points.GetValue("Punkt4") == NULL);

    CHashtable<int, CRect> ht_Rect(CRect(-1,-1,-1,-1));
    ht_Rect.Add(1, CRect(p1->x, p1->y, p1->x + 10, p1->y + 10));
    ht_Rect.Add(2, CRect(p2->x, p2->y, p2->x + 10, p2->y + 10));
    
    ASSERT(ht_Rect.GetValue(1).left == p1->x);
    ASSERT(ht_Rect.GetValue(2).right == p2->x + 10);
    ASSERT(
        ht_Rect.GetValue(3).left == -1 && 
        ht_Rect.GetValue(3).top == -1 && 
        ht_Rect.GetValue(3).right == -1 && 
        ht_Rect.GetValue(3).bottom == -1
    );
    
    delete p1;   delete p2;  delete p3;

Kommentare zum Snippet

 

Logge dich ein, um hier zu kommentieren!