Hash table for Coursera's algorithms course

Question

I implemented a hash table for Coursera's Algorithms and Design class. I am looking for feedback on coding style and other improvements. I want to practice C++ coding but I see myself drifting to C and functional programming a lot. Any advice on switching would be very helpful.

The problem is as follows:

Given a list of 1 million numbers, find all the values of t in [-10000, 10000] such that if you pick 2 distinct numbers from the given list, they sum to t.

Solution (from one of the posts in the discussion forums):

Store all the numbers in a hash table (map of (key, value) where key=int and value=vector). The hash function makes the key by dividing the number by 20000. Then, go to that key in the hash table and do a push_back on the vector for the value of that key.

Here are the 2 files:

#include<iostream>
#include <vector>
#include <fstream>
#include <set>
#include <map>
#include <cmath>
#include <sys/time.h>

using namespace std;

typedef set<long int> inner;
typedef map<int, inner> hashTable_T;





#include "ht2.h"

using namespace std;


void readfile(hashTable_T &H){
    ifstream ipstream;
    ipstream.open("algo1-programming_prob-2sum.txt");
    long int output; int index; hashTable_T::iterator it;
    while (ipstream >> output){
        index = output/(2*t);
        it = H.find(index);
        if (it==H.end()){
            inner innerVec;
            innerVec.insert(output);
            H.insert(make_pair(index,innerVec));
        }
        else{
            (it->second).insert(output);
        }
    }
    ipstream.close();
} 

int findinTable(hashTable_T &H,const  long int &value, const int &binL,const int &binH, set<int> &setofTs){
    hashTable_T :: iterator it, itL, itH;
    inner :: iterator itIn;
    long int sum;

    itL = H.upper_bound(binL);
    if (itL!=H.begin()) itL--;
    itH = H.upper_bound(binH);

    bool done = false;
    while( itL!= H.end()){
        for (itIn = (itL->second).begin() ; itIn != (itL->second).end() ; itIn++){
            sum = *itIn + value;
            if (sum <= t && sum >= -t && *itIn!=value) setofTs.insert(sum) ;
        }
        itL++;
        if (done) break;
        if (itL == itH) done = true;
    }
}

void printHashTable(hashTable_T &H){
    hashTable_T::iterator it;
    inner::iterator vecIt;
    for (it=H.begin(); it!=H.end() ; it++){ 
        cout << it->first << " :";
        for (vecIt = (it->second).begin() ; vecIt != (it->second).end() ; vecIt++){
            cout << *vecIt << " "; 
        }
        cout << endl;
    }
}

int main(){
    int t = 10000;
    hashTable_T HashTable;
    readfile(HashTable);

    set<int> setofTs;
    hashTable_T::iterator it = HashTable.begin();
    inner::iterator it2;
    int binL, binH;
    for (it;it!=HashTable.end();it++){
        for (it2 = (it->second).begin();it2 != (it->second).end(); it2++){
            binL = (-t-(*it2))/(2*t);
            binH = (t- (*it2))/(2*t);
            findinTable(HashTable, *it2, binL, binH, setofTs);
        }
    }
    cout << setofTs.size() << endl;
    return 0;
}

Answer 1

Well, if you're looking to move away from functional programming, making yourself some classes might be a good start.

In your .h file, you declare your class and all that jazz, so it becomes

#include <iostream>
#include <vector>
#include <fstream>
#include <set>
#include <map>
#include <cmath>
#include <sys/time.h>

using namespace std;

class HashTable
{
    typedef set<long int> inner;
    typedef map<int, inner> hashTable_T;
};

Only it doesn't. As has been pretty well established, using namespace std is bad practice. So this is what our header looks like now.

#include <iostream>
#include <vector>
#include <fstream>
#include <set>
#include <map>
#include <cmath>
#include <sys/time.h>

class HashTable
{
    typedef std::set<long int> inner;
    typedef std::map<int, inner> hashTable_T;

    hashTable_T hash;
};

Right, let's start having a look at that .cpp file. Now I see 3 functions that all do an operation on a single hash table. That smells functional to me, so I reckon we're actually going back to editing our .h. And since we're adding in some functions, may as well chuck in a little constructor.

As well as that, we need to think about visibility, as in setting what's public, protected and private, so we'll do that here too. Typically, the members of the class are either private or protected, so we'll make that happen, and whatever functions need to be accessed outside of the class are public, so we'll do that too.

We should give the variable int t, which is being passed to readFile(int) a meaningful name too, but I'm not sure what to call it, so I'll leave that up to you.

#include <iostream>
#include <vector>
#include <fstream>
#include <set>
#include <map>
#include <cmath>
#include <sys/time.h>

class HashTable
{
    typedef std::set<long int> inner;
    typedef std::map<int, inner> hashTable_T;

    private:
        hashTable_T hash;

    public:
        HashTable();
        void readFile(int t, const char* fileName);
        int findinTable(const long int &value, const int &binL,const int &binH, set<int> &setofTs);
        void print();
};

Okay, back to that .cpp. We're killing that using namespace std again. I know all of the c++ tutorials use it, but trust me, you shouldn't.

Given that we've made it a class function, and we might want to read from other files (sorry to those shouting YAGNI, but this is just a little change), why not pass in a string which is the file name? As well as this, I've put in a few formatting changes which I think makes it a bit more readable. This means the readFile function becomes

void HashTable::readfile(int t, const char* fileName){

    ifstream ipstream(fileName);

    long int output;

    while (ipstream >> output){
        int  index = output/(2*t);
        hash[index].insert(output);
    }
} 

After making it a class function, and doing a little bit of formatting, your findinTable is now:

int HashTable::findinTable(const long int &value, const int &binL, const int &binH, set<int> &setofTs){
    hashTable_T::iterator it, itL, itH;
    inner::iterator itIn;
    long int sum;

    itL = hash.upper_bound(binL);
    if (itL != hash.begin()){
        itL--;
    }

    itH = hash.upper_bound(binH);

    bool done = false;
    while(itL != hash.end()){
        for (itIn = (itL->second).begin(); itIn != (itL->second).end(); itIn++){
            sum = *itIn + value;
            if (sum <= t && sum >= -t && *itIn != value){
                setofTs.insert(sum);
            }
        }
        itL++;
        if (done){
            break;
        }
        if (itL == itH){
            done = true;
        }
    }
}

Getting onto your print function:

void HashTable::print(){
    hashTable_T::iterator it;
    inner::iterator vecIt;

    for (it=hash.begin(); it!=hash.end(); it++){ 
        std::cout << it->first << " :";
        for (vecIt = (it->second).begin(); vecIt != (it->second).end(); vecIt++){
            std::cout << *vecIt << " "; 
        }
        std::cout << std::endl;
    }
}

Okay, looking pretty good so far. Probably not perfect, but a decent start. We wrote that constructor, so I think we should use it. I think it could probably use a bit of modification before it's worth writing though. So the declaration for it was HashTable();, but I think if it's made to be HashTable(const char* sourceFile, int tVal);, it'd be much better.

Then we'd have (as our constructor):

HashTable::HashTable(const char* sourceFile, int tVal){
    readFile(tVal, sourceFile);
}

Finally! Onto main. Now, I'm not entirely convinced about my solution to this but in particular, and I'm pretty sure that there's a more elegant way of doing it that I'm missing, but I'm going to say extract the bit which is doing the work, and put it into a class function. The only alternative (that I can see) is breaking the encapsulation, which is pretty non-OO. So I think that we add a function like this (but with a much better name):

std::set<int> HashTable::makeSet(int t){
    std::set<int> setofTs;
    hashTable_T::iterator it = hash.begin();
    inner::iterator it2;
    int binL, binH;
    for (it; it != hash.end(); it++){
        for (it2 = (it->second).begin(); it2 != (it->second).end(); it2++){
            binL = (-t-(*it2))/(2*t);
            binH = (t- (*it2))/(2*t);
            findinTable(*it2, binL, binH, setofTs);
        }
    }
    return setofTs;
}

So therefore main becomes:

int main(){
    int t = 10000;
    HashTable hTable("algo1-programming_prob-2sum.txt", t);

    std::set<int> setoFTs = hTable.makeSet(t);
    cout << setofTs.size() << endl;
    return 0;
}

And as a round-up, I'll show what states our 2 files are in at this point. I've done a bit of extra cleaning up that I'll explain as I go along in comments

ht2.h

#pragma once //Include guard, always good to have
#include <fstream> //Grouped the includes
#include <iostream>

#include <map>
#include <vector>
#include <set>

#include <cmath>
//Got rid of sys/time, as I couldn't see what it was being used for. If I'm wrong, ignore this.


class HashTable
{
    typedef std::set<long int> inner;
    typedef std::map<int, inner> hashTable_T;

    //Grouped all of the functions by type.
    private:
        hashTable_T hash;

    public:
        HashTable(){};
        HashTable(const char* sourceFile, int tVal);

        int findinTable(const long int &value, const int &binL,const int &binH, set<int> &setofTs);

        void print();
        void readFile(int t, const char* fileName);
};

ht2.cpp

#include "ht2.h"

HashTable::HashTable(const char* sourceFile, int tVal){
        readFile(tVal, sourceFile);
    }

void HashTable::readfile(int t, const char* fileName){

    ifstream ipstream(fileName);

    long int output;

    while (ipstream >> output){
        int index = output/(2*t);
        hash[index].insert(output);
    }
}

int HashTable::findinTable(const long int &value, const int &binL, const int &binH, set<int> &setofTs){
    hashTable_T::iterator it, itL, itH;
    inner::iterator itIn;
    long int sum;

    itL = hash.upper_bound(binL);
    if (itL != hash.begin()){
        itL--;
    }

    itH = hash.upper_bound(binH);

    bool done = false;
    while(itL != hash.end()){
        for (itIn = (itL->second).begin(); itIn != (itL->second).end(); itIn++){
            sum = *itIn + value;
            if (sum <= t && sum >= -t && *itIn != value){
                setofTs.insert(sum);
            }
        }
        itL++;
        if (done){
            break;
        }
        if (itL == itH){
            done = true;
        }
    }
}

std::set<int> HashTable::makeSet(int t){
    std::set<int> setofTs;
    hashTable_T::iterator it = hash.begin();
    inner::iterator it2;
    int binL, binH;
    for (it; it != hash.end(); it++){
        for (it2 = (it->second).begin(); it2 != (it->second).end(); it2++){
            binL = (-t-(*it2))/(2*t);
            binH = (t- (*it2))/(2*t);
            findinTable(*it2, binL, binH, setofTs);
        }
    }
    return setofTs;
}

void HashTable::print(){
    hashTable_T::iterator it;
    inner::iterator vecIt;

    for (it=hash.begin(); it!=hash.end(); it++){ 
        std::cout << it->first << " :";
        for (vecIt = (it->second).begin(); vecIt != (it->second).end(); vecIt++){
            std::cout << *vecIt << " "; 
        }
        std::cout << std::endl;
    }
}

//This *could* be in a file all on it's own, but let's not make it look lonely.
int main(){
    int t = 10000;
    HashTable hTable("algo1-programming_prob-2sum.txt", t);

    std::set<int> setoFTs = hTable.makeSet(t);
    cout << setofTs.size() << endl;
    return 0;
}