8
\$\begingroup\$

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 <iostream>
#include <string>
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 <string>

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; i<SZ; i++){
        //get rid of chain i
        DicNode * p = table[i];
        while(p!=0){
            DicNode * kill = p;
            p = p->nxt;
            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 == nullptr
                ? nullptr
                : &f->val;
/* Loki END */
}

bool Dic::addOrMod(K key, V val){

/* Loki Wrote */
    V* current = find(key);
    if (current != nullptr)
    {
        *current = val;
        return false;   // false indicates value was not added just modified.
    }

    int hash = dichash(key);
    table[hash] = new DicNode{key, val, table[hash]};
    return true;        // true indicates new value was added to the table.
/* Loki END */
}

int Dic::size(){

    return n;
}
//-----------------------------------------------------------------

//BIG 3

Dic::Dic()
/*Loki Add
    Must initialize all the members.
    Otherwise your object will have random values in it.
*/
    : n(0)
    , SZ(13)
    , table(new DicNode*[SZ]())
/*Loki END*/
{}

Dic::Dic( const Dic & src )
/*Loki Add
    Must initialize all the members.
    Otherwise your object will have random values in it.
    Having randome valus is not very useful when you call the assignment operator
    which calls the dealloce() method.
*/
    : n(0)
    , SZ(0)
    , table(nullptr)
/*Loki END*/
{
    *this = src;   //Uses operator= defined for Dic
}

Dic & Dic::operator=( const Dic & rhs )
{  //assignment op
    if(this == &rhs){ cout<<"goofy"<<endl; return *this; }

    // clean up any memory allocated by this
    this->deallocate();
    // initialize this n,SZ,table to be like rhs
    this->n=rhs.n; this->SZ = rhs.SZ; this->table=new DicNode*[SZ];
    // duplicate the DicNode chains
    for(int i=0;i<SZ;i++){
        DicNode * q = rhs.table[i];
        if(q==0){
            this->table[i]=0;
        }else{
            this->table[i]=new DicNode;    //note: NOT DicNode()
            DicNode * p = this->table[i];
            while(true){  //loop inv: *p is blank node corresp to *q
                p->key = q->key;  p->val = q->val;
                if(q->nxt==0)break;
                q=q->nxt; p->nxt=new DicNode; p=p->nxt;
            }
            p->nxt=0;
        }
    }
    return *this;
}
namespace HA
{
int hash(string s) {
    int ret=0;
/*Loki Remove
    The SZ member variable is what you want to use.
    This is because you want to take the hash and convert it into an index
    into your table. The string length is the correct value to use as the
    modulus.
    int SZ = s.length();
* Loki END*/
    for (int i=0; i<s.size(); i++) {
        ret+=s[i]-'A';
    }
/*Loki Change
    return ret%SZ;
*Loki End*/

    /* Note returning a hash of the string.
     * It is not modulo anything. So
     * we also need to modify all call points to
     * use modulo if required.
     *    I am not going to comment those changes.
     */
    return ret;
}
}

Dic::~Dic(){this->deallocate();}

Test Code

int main()
{
    Dic     dict;

    dict.addOrMod("Key", 5);
    std::cout << dict.find("Key") << "\n";
    std::cout << *dict.find("Key") << "\n";
}
\$\endgroup\$
8
\$\begingroup\$

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; i<SZ; i++){
        //get rid of chain i
        DicNode * p = table[i];
        while(p!=0){
            DicNode * kill = p;
            p = p->nxt;
            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 this explicitly.

Dic::Dic()

The copy constructor you implement in terms of the assignment operator. Nice idea. But the wrong way around. You should implement the assignment operator in terms of the copy constructor (its called the Copy and Swap Idiom (easy to find on Google or SO)). Also because you did not correctly initialize the object before calling the assignment operator things were going horribly wrong.

Dic::Dic( const Dic & src )

When copying an object. You should do it three distinct phases. This allows you to provide the strong exception guarantee.

Dic & Dic::operator=( const Dic & rhs )
  1. Copy the object into a temporary.
    It is important to put it into a temporary. Because if things go wrong during the copy you still have the original state of the object to fall back on.
  2. Swap the content of the temporary with the state of the current object.
    Swap in C++ is a fundamental property that you should implement as a very simple transfer of safe objects (POD and pointers).
  3. Now that you have swapped the state (and the object is all good) you can destroy the old state.
    Which should now be in the temporary object.

If we look at your copy we can point out the danger spots.

    // clean up any memory allocated by this
    this->deallocate();

At this point your object is not in a very dangerous state. All its data has been deleted but the pointers still point at that memory. If you throw an exception that is caught downstream this object would cause the program to potentially crash (or at least have a high likely hood of undefined behavior).

Back to more general comments. One statement per line please. don't make your code hard to read.

    this->n=rhs.n; this->SZ = rhs.SZ; this->table=new DicNode*[SZ];

Some extra white space around the gibberish would go a long way in making this easier to read.

    for(int i=0;i<SZ;i++){

Personally I would have created another method for copy a list of elements.

        DicNode * q = rhs.table[i];

Hashing

This is a terrible hash function:

int hash(string s) {
    int ret=0;
/*Loki Remove
    The SZ member variable is what you want to use.
    This is because you want to take the hash and convert it into an index
    into your table. The string length is the correct value to use as the
    modulus.
    int SZ = s.length();
* Loki END*/
    for (int i=0; i<s.size(); i++) {
        ret+=s[i]-'A';
    }
/*Loki Change
    return ret%SZ;
*Loki End*/

    /* Note returning a hash of the string.
     * It is not modulo anything. So 
     * we also need to modify all call points to 
     * use modulo if required.
     *    I am not going to comment those changes.
     */
    return ret;
}

To be fair writing your own hash function is really hard; and thus a bad idea. Unless you happen to have a PhD in Maths this is not an easy task. It is better to go onto the internet and lockup existing hashing algorithms. There are some relatively simple ones that give a reasonable distribution for small pet projects like this.

Another thing to note about hash and hash tables. Prime numbers are key. So it is probably a good idea to make your table have a prime number of buckets (that is why I used 13 above). But check your hashing algorithm you eventually pick.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.