Dictionary (with silly hash)

Based on this question (but fixed so it can run).

I have kept the code as close to the original as possible.

I have Marked all the changes with Loki (should be easy to spot).

Code here is written in the style of the original author.

Dic.h

#ifndef DIC_H
#define DIC_H

#include 
#include 
using namespace std;

typedef string K;  //key type    //!!!
typedef double V;  //value type  //!!!

/* Loki Added */
namespace HA
{
    int hash(std::string key);  // There are plenty of things already called hash.
                                // This was confusing the compiler so I had
                                // to put it in its own namespace to make sure
                                // I was using the correct one.
}
/* Loki END*/

class Dic{
public:
    Dic( );  //an empty Dic

    //The BIG 3:  operator=, copyconstructor, destructor
    ~Dic();

    Dic( const Dic & src );  //copy con

    Dic & operator=( const Dic & rhs );  //assignment op

    //return null or a pointer at the value in this Dic
    V * find(K key);

    //returns true if it ADDED (false if modified)
    bool addOrMod(K key, V val);

    int size( );

private:
    class DicNode{public: K key; V val; DicNode * nxt; };
    int n;  int SZ;
    DicNode**       table;   // DicNode* [ ]    an array of linked lists of DicNodes

    int dichash(K);            //private hash function
    void deallocate();      //private helper, used by the destructor.
};

#endif

dic.cpp

```
#include "Dic.h"
#include

int Dic::dichash(K key){ //DEPENDS ON K. This one assumes K is string
/Loki Change /
return std::abs(HA::hash(key)) % SZ;
/Loki END/
}

void Dic::deallocate(){ //separate member called by destruc and op=
for(int i=0; inxt;
delete kill;
}
}
delete [] table;
}

V * Dic::find(K key) {
/ Loki Wrote /
int hash = dichash(key);
DicNode* f = table[hash];
while(f != nullptr && f->key != key)
{ f = f->nxt;
}
return f == nullp

Dict.h

Do not do this.

using namespace std;

Especially in a header file. You are polluting the namespace for everybody that uses your header file (and you will break peoples code). Some people say its OK to use this in a source file. I disagree with even that as it causes problems in anything more than a toy program. But to make sure you don't get into bad habits don't even use it in toy programs. Use the explicit prefix std::. It was named std rather than standard explicitly so it would not be a burden to be explicit. See: Why is “using namespace std;” considered bad practice?

When passing object around try and pass them by const reference.

int hash(std::string key);

// Prefer to do this:

int hash(std::string const& key);

This stop a copy of the object being made. Also the function can not modify the original because it was passed by reference.

This is a bit untidy:

Dic( );  //an empty Dic

//The BIG 3:  operator=, copyconstructor, destructor
~Dic();

Dic( const Dic & src );  //copy con

Dic & operator=( const Dic & rhs );  //assignment op

Group constructors together. Put Destructor at the end of the list. Assignment operator after that. The first thing people check when you are doing memory management is to make sure you have the rule of three correctly implemented so put it all together. An addition you should think about is adding move semantics to your class (Move constructor and ove assignment operator).

// Too much vertical space (and useless comments) I would have done:
 Dic();
 Dic(const Dic & src);
 Dic(Dic&& src);
~Dic();
Dic& operator=(Dic const& rhs);
Dic& operator=(Dic&& rhs);

Not a great interface. But it is sufficient.

Remember to pass object parameters by const reference.

V * find(K key);                // Change to:  V*   find(K const& key);
bool addOrMod(K key, V val);    // Change to:  bool addOrMod(K const& key, V val);

When you have methods that don't change the state of your object you should mark them const. This will allow you to retrieve information from a const object. So passing it by const reference will still allow you to query from it:

int size();

// This should have a const on it:

int size() const;

// In addition to the normal find() you specify above.
// It is also worth having a const version that allows your users to read from the object.
V const* find(Key const& key) const;

// Notice that the method is const and the value I return is const.
// So you can read it but not modify the content.

If you are going to declare an all public class you may as well make it a struct (its the same thing).

class DicNode{public: K key; V val; DicNode * nxt; };

I changed the order of your member variable declarations.

In the constructor they are initialized in the same order that you declare them which is important.

int n;  int SZ;
DicNode**       table;   // Note: the * is part of the type.
                         //       So place it with the type.

Not particularly keen on an array of arrays. But you are building a container. But because you have no method to resize it I would have personally used std::array or potentially a std::vector.

To prevent confusion I renamed this function from hash. As it does not actually return a hash but an index into the table (using the hash to calculate the index).

int dichash(K);            //private hash function

Dict.cpp

You have a strange order to your methods.

Personally I always put the Constructors/Destructors first. People need to know how the class is set up before other functions make any sense. So putting the constructors firsts will give people a context on how the other functions will work.

You did not implement this function:

int Dic::dichash(K key){       //DEPENDS ON K. This one assumes K is string
/*Loki Change */
    return std::abs(HA::hash(key)) % SZ;
/*Loki END*/
}

Which is the main reason it did not work.

OK: This code looks like it should work.

void Dic::deallocate(){     //separate member called by destructor and op=
    for(int i=0; inxt;
            delete kill;
        }
    }
    delete []  table;
}

But it looks very untidy. And could have been written much easier with a nested for loop. Other may suggest you use smart pointers here. But I am going to disagree with them. There are two basic types of memory management in C++.

• Smart pointers.

• Containers

There is no point in implementing containers in terms of smart pointers. The container is supposed to do the memory management. A Dictionary (hashed or otherwise) is a container so the memory management is well defined and contained.

Another three functions you did not implement:

V * Dic::find(K key) {
bool Dic::addOrMod(K key, V val){
int Dic::size(){

So we get to the Big 3!!!!

Your main problem is that you did not initialize your members in the constructors. Do not assume they will be zero initialized. You must usually do

StackExchange Code Review Q#67933, answer score: 8