Strategy pattern - design hash table

Question

My programming skill has gotten rusty, so I would like to elicit constructive criticism that can make me write code better. I know the standard design is to use templates, and even obtain the hash function, allocator, etc through it, but I wanted to experiment with patterns, so I'm pretty sure my design here blows. but I'm trying to use the strategy pattern to make a customizable hash table interface, just to reacquaint myself with C++.

How do I design this better (without using all the template parameters, for specifying hash function, etc)? If not the strategy pattern, what pattern would fit better?

//The generic map interface
template <typename K, typename V>
class Map
{
private:

    //Make a reference class so we can enable [] operation
    class reference
    {
        public:
            operator V const () { return map_.Find(key_); }

            reference& operator=(const V& val) { map_.Add(key_, val); return *this; }
            reference& operator=(const reference& ref) { *this = (V&) ref; return *this; }

        private:
            reference (Map& map, const K key) : map_(map), key_(key) {}
            Map& map_;
            K key_;
            friend class Map;
    };

public:
    Map() : hash_(NULL), ds_(NULL), size_(0) { }

    void SetHashStrategy(int hash_type = HashType::SIMPLE_HASH);
    void SetCollisionStrategy(int collision_method = CollisionType::CHAINING);
    void SetDataStructureStrategy(int data_structure_types = DSType::DYNAMIC_MAP);
    virtual ~Map() 
    { 
        Empty(); 
        delete hash_; 
        delete ds_;
    }

    //Interface functions
    void   Add(K key,V value) { ++size_; ds_->Add(key, value); }
    void   Remove(K key)      { --size_; ds_->Remove(key); }
    V&     Find(K key)        { return ds_->Find(key); }
    size_t Size()             { return size_; }
    void   Empty()            { size_ = 0; ds_->Empty(); }

    //Square bracket access
    reference operator[] (const K& key) { return (reference(*this, key)); }

    //printing
    friend std::ostream& operator<< (std::ostream& o, const V& v) { return o << v; }

private:
    HashType* hash_; //is an ADT
    DataStructureType<K,V>* ds_; //this is also an ADT
    size_t size_;
};

And then, choose the hash object like this:

template <class K, class V>
void Map<K,V>::SetHashStrategy(int hash_type)
{
  if(hash_ != NULL)
  {
    delete hash_;
  }

  if(hash_type == HashType::SIMPLE_HASH)
  {
    hash_ = new SimpleHash;
  }
  else if(hash_type == HashType::MD5_HASH)
  {
    hash_ = new MD5Hash;
  }
}

And choose the data structure like this:

template <class K, class V>
void Map<K,V>::SetDataStructureStrategy(int ds_type)
{
  if(ds_ != NULL)
  {
    delete ds_;
  }

  if(ds_type == DSType::DYNAMIC_MAP)
  {
    ds_ = new DynamicMap<K,V>;
  }
  else if(ds_type == DSType::ARRAY_MAP)
  {
    ds_ = new ArrayMap<K,V>;
  }
}

Afraid I can't. However, please do tell me what improvements were possible if I were to, and I will maybe start learning and applying C++11 concepts. — KKP
– KKP, Commented Nov 28, 2014 at 20:57

janos · Accepted Answer · 2014-11-28 07:13:51Z

You're misusing the term strategy pattern. Instead of doing this kind of thing:

template <class K, class V>
void Map<K,V>::SetDataStructureStrategy(int ds_type)
{
  if(ds_ != NULL)
  {
    delete ds_;
  }

  if(ds_type == DSType::DYNAMIC_MAP)
  {
    ds_ = new DynamicMap<K,V>;
  }
  else if(ds_type == DSType::ARRAY_MAP)
  {
    ds_ = new ArrayMap<K,V>;
  }
}

The strategy pattern would look something more like this:

template <class K, class V>
void Map<K,V>::SetDataStructureStrategy(DataStructureStrategy * dsStrategy)
{
  this->dsStrategy = dsStrategy;
}

That is, you would have a DataStructureStrategy abstract parent class, with concrete implementations in subclasses, for example DynamicMapStrategy and ArrayMapStrategy.

And then, the code to initialize the data structure would look like this:

ds_ = dsStrategy->newDataStructure();

where newDataStructure would be implemented in the specialized subclasses like this:

// implementation of DynamicMapStrategy::newDataStructure
return new DynamicMap<K,V>;

// implementation of ArrayMapStrategy::newDataStructure
return new ArrayMap<K,V>;

In other words:

Your hashmap class shouldn't have to know how a strategy is implemented. At no point should the code have conditional statements on DSType. In fact there's no need for DSType.
The same goes for all the other kind of strategies that you implied: hash strategy, collision strategy. Define a common interface for each strategy that the hashmap wants to work with. Move the implementations of strategies outside of the hashmap, into subclasses of the common interfaces.
These strategies should not change during the lifetime of a hashmap. It wouldn't be efficient to switch the strategy of an existing hashmap. So it would be better to make these strategies required at construction time, and remove the setters.

Thank you for the detailed review of the design. Looks like I completely misunderstood what the strategy pattern really meant - my Map should be agnostic to it, you're quite right. And yes, I shouldn't expose the strategy via setters. That makes sense too. — KKP
– KKP, Commented Nov 28, 2014 at 8:24

Yuushi · Accepted Answer · 2014-11-28 06:10:09Z

10

There are a couple of issues with this design. The first is that a default constructed Map object is in a state such that any operations on it will fail. The user instead has to call a bunch of set functions directly after construction. All of this should be moved directly into the constructor itself.

The next issues are to do with language improvements. Instead of using NULL you should instead prefer nullptr. This is much safer as it won't go through the implicit conversions that NULL will. Secondly you should look at using std::unique_ptr instead of raw pointers. Finally you should look at usung an enum class instead of passing enemeration types as raw integers, which is error prone.

One of the largest issues with your API is that it is extremely easy to use incorrectly. For example, if the user starts with one hashing strategy, inserts some elements, and then switches to a new hashing strategy, the inserted elements are (with very high probability) completely unreachable.

answered Nov 28, 2014 at 6:10

Yuushi

11.1k2 gold badges31 silver badges66 bronze badges

\$\begingroup\$ Thank you for taking the time. Very valid points. Would you suggest this to overcome the limitation with the API - if the user changes the strategy, then delete the map and begin over, or just make the function fail if there is already a data structure constructed and in use? They'd have to call Reset() on it or something? \$\endgroup\$

KKP
– KKP

2014-11-28 06:32:51 +00:00
Commented Nov 28, 2014 at 6:32
1

\$\begingroup\$ @KKP The options should be moved into the constructor in my view. You'll still need to be careful with copy construction and copy assingnment, and exactly what semantics these have. \$\endgroup\$

Yuushi
– Yuushi

2014-11-28 07:27:55 +00:00
Commented Nov 28, 2014 at 7:27

Add a comment |

R Sahu · Accepted Answer · 2014-11-29 03:33:10Z

In addition to the points raised by other answers:

void   Add(K key,V value) { ++size_; ds_->Add(key, value); }

What do you expect to happen when a user calls:

Map<int, int> myMap;
// .... setup
myMap.Add(10, 20);
myMap.Add(10, 30);

Do you expect the size the of map to increase by two if there were no prior entries corresponding to 10? It's not clear from your header file what the expected behavior is.

void   Remove(K key)      { --size_; ds_->Remove(key); }

Similar logic here. What happens when the user calls:

myMap.Remove(10);
myMap.Remove(10);

In both of these cases, you have to check whether there is an item corresponding to the key.

In the case of Add, if there is no item corresponding to the key, you will need to increment the size. If there is already an item corresponding to the key, you will need to increment the size only if you are allowed to have multiple values corresponding to a key. Otherwise, don't increment the size if there is already an item corresponding to the key.

In the case of Remove, if there is an item corresponding to the key, you will need to decrement the size. If there is no item corresponding to the key, make sure you don't decrement the size.

V&     Find(K key)        { return ds_->Find(key); }

It's not clear from this implementation what the expected return value is if the map doesn't have an item corresponding to the key. The STL addresses this my returning std::map::end() when there is no item in the map corresponding to the key. You may consider something like:

bool     Find(K key, V& val)        { return ds_->Find(key, val); }

Then, the return value can be true if an item was found, false otherwise.

Oh! You're quite right, it needs to be a true/false value. Also need to do the same with the [] insert I guess. — KKP
– KKP, Commented Nov 30, 2014 at 8:10
@KKP, that's up to you. The std::map inserts an item if it's not there when you use operator[]. In general, I find it very difficult to improve on the interface of the standard library. — R Sahu
– R Sahu, Commented Nov 30, 2014 at 8:13

glampert · Accepted Answer · 2014-11-29 13:46:52Z

A few minor points that weren't mentioned:

A virtual destructor for Map: You didn't specify, but the only reason for Map to have a virtual destructor is if some other class is inheriting from it. If you did it just to make your code "future proof", don't. Follow the YAGNI principle. If you are currently inheriting from Map I would advise against, since you can probably do a better job using composition instead.
Methods that don't mutate member state should be const. Size() is one. It should be declared:
```
size_t Size() const { return size_; }
```
I would also expect Find() to be const. It wouldn't make much sense having a "find" method that change the data structure it operates on.
size_t in C++ is technically a member of the std namespace (it will also be visible globally if you include any C header like stdlib.h, directly or indirectly). Personally, I find it a pain in the neck using it as std::size_t, but if you want to be pedantic...
You'll probably want to provide a second version of operator[] that is const and returns a const reference. Something in the lines of:
```
const reference operator[] (const K& key) const { ... }
```
Method Empty() has a misleading name. It seems to be clearing the map. The name you have chosen is very inadequate in a C++ context because almost all standard C++ containers have an empty() method that tests if the container is empty. So it is very likely that users of your Map would assume the same. Clear() would be the best name, IMHO.
Add(K key, V value): As it is now, using pre-11 C++, you should not pass the parameters by value. Remember that in C++ the default is a copy. Change that function to receive a const reference of the parameters:
```
void Add(const K& key, const V& value);
```
This will prevent an extra copy inside the function. This way there should be a single copy once you place it inside the map and nothing else. A future optimization to this would be adding C++11 move semantics.
I don't like to see the NULL macro being used in C++, though before nullptr we either had to use it or use a plain 0. NULL in C++ is actually just a #define for 0, so I used to go with the 0 back then.

Excellent! Thanks. Good thought about the YAGNI principle - I was setting up my map to be inherited, but I shouldn't until I actually need to. — KKP
– KKP, Commented Nov 30, 2014 at 8:09

Stack Exchange Network

Strategy pattern - design hash table

4 Answers 4

You must log in to answer this question.

Hot Network Questions

Strategy pattern - design hash table

4 Answers 4

You must log in to answer this question.

Related

Hot Network Questions