CODEWITHSUNDEEP
c++dictionarysetcontainers
elad
elad

Reputation: 369

one class for both a set and a dictionary (map)

I want to implement both Hash-Table and Ballanced-Binary-Tree (AVL, specifically), for both needs of a set and a dictionary (map).

For the first purpose, there is only a Key class, and for the second, there is Key and Data (or Value).

The two versions share a lot of functionality (especially in the tree case), so I really don't want to implement twice :

template<class Key> class AVLTree;
template<class Key, class Val> class AVLTree;

How can I elegantly make one "HashTable" class, and respectively one "AVLTree" class, with one template signature and use them for both purposes (with possibly wrapper/derived classes [[Un]Ordered] "Set" and "Map"?

(No, I don't want to use STL)

Thanks

Upvotes: 0

Views: 42

Answers (1)

m8mble
m8mble

Reputation: 1545

The obvious answer is: Do it as the STL does it.

Introduce the most general form of AVLTree that you need:

template <class K, class V, class KeyOfValue, class Compare>
class AVLTree;

(see _Rb_tree_base as a reference). In this context, an AVLTree only ever stores Values. But for reasons of comparing values, it is capable of retrieving the Key of a Value by means of an KeyOfValue object.

Using this, your dictionary application is obvious. A set can then be modeled by using the same type for Key and Value as well as identity for KeyOfValue. (Probably you don't want to spell this out each time. Just use a wrapper template for that.)

Upvotes: 2

Related Questions