I want to print the most visited sites/urls in the browser

Question

Below is the code that I have written in C++ and it is printing the wrong result for the 2nd and 3rd output line. I am not able to figure it out why it is happening.

Below is the code which I have written and it is a completely functional code on visual studio. This code expects the one input file named urlMgr.txt whose content should be URLs. Below is the sample URLs which I am using it.

  web.whatsapp.com 
  web.whatsapp.com 
  cplusplus.com/reference/algorithm/find_if 
  stackoverflow.com/questions/760221/breaking-in-stdfor-each-loop 
  mail.google.com/mail/u/0/#inbox 
  http://stackoverflow.com/questions/18085331/recursive-lambda-functions-in-c14
  mail.google.com/mail/u/0/#inbox 
  en.cppreference.com/w/cpp/language/lambda 
  https://www.google.co.in/?ion=1&espv=2#q=invariant%20meaning
  mail.google.com/mail/u/0/#inbox
  http://stackoverflow.com/questions/11699083/where-can-i-find-all-the-exception-guarantees-for-the-standard-containers-and-al
  https://www.google.co.in/?ion=1&espv=2#q=array+of+references:quora&start=10
  mail.google.com/mail/u/0/#inbox 
  web.whatsapp.com 
  quora.com/Whats-the-purpose-of-load-factor-in-hash-tables 
  https://www.quora.com/Whats-the-difference-between-the-rehash-and-reserve- methods-of-the-C++-unordered_map      cplusplus.com/reference/unordered_map/unordered_map/load_factor
  cplusplus.com/max_load_factor 
  cplusplus.com/max_load_factor 
  cplusplus.com/max_load_factor 
  cplusplus.com/max_load_factor
  cplusplus.com/max_load_factor 
  cplusplus.com/max_load_factor 
  cplusplus.com/max_load_factor 
  cplusplus.com/max_load_factor 

Code is also pasted below.

#include <iostream>
#include <string>
#include <unordered_set>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <functional>
#include <unordered_map>
#include <queue>
using namespace std;

class urlInfo
{
public:
    urlInfo(string &url):urlName(url),hitCount(1)
    {
    }

    int getHitCount() const
    {
        return hitCount;
    }

    string getURL()
    {
        return urlName;
    }

    string getURL() const
    {
        return urlName;
    }

    void updateHitCount()
    {
        hitCount++;
    }

    void setHitCount(int count)
    {
        hitCount = count;
    }

private:
    string urlName;
    int hitCount;
};

class urlInfoMaxHeap
{
public:
    bool operator() (urlInfo *url1, urlInfo *url2) const
    {
        if(url2->getHitCount() > url1->getHitCount())
            return true;
        else
            return false;
    }
};


bool operator==(const urlInfo &ui1,const urlInfo& ui2)
{
    //return (ui1.getURL().compare(ui2.getURL()) == 0) ? 1:0;

    return (ui1.getURL() == ui2.getURL());
}

namespace std
{
    template <> struct hash<urlInfo>
    {
        size_t operator()(urlInfo const & ui)
        {
            return hash<string>()(ui.getURL());
        }
    };
}

class urlMgr
{
public:
    urlMgr(string &fileName)
    {
        ifstream rdStr;
        string str;
        rdStr.open(fileName.c_str(),ios::in);
        if(rdStr.is_open())
        {
            int len;
            rdStr.seekg(0,ios::end);
            len = rdStr.tellg();
            rdStr.seekg(0,ios::beg);
            str.reserve(len+1);
            char *buff = new char[len +1];
            memset(buff,0,len+1);
            rdStr.read(buff,len);
            rdStr.close();
            str.assign(buff);
            delete [] buff;
        }
        stringstream ss(str);
        string token;

        while(getline(ss,token,'\n'))
        {
            //cout<<endl<<token;
            addUrl(token);
        }

    }


    void addUrl(string &url)
    {
        unordered_map<string,urlInfo*>::iterator itr;
        itr = urls.find(url);
        if(itr == urls.end())
        {
            urlInfo *u = new urlInfo(url);
            urls[url] = u;
            maxHeap.push_back(u);
        }
        else
        {
            itr->second->updateHitCount();
            urlInfo* u = itr->second;
            vector<urlInfo*>::iterator vItr;
            vItr = find(maxHeap.begin(),maxHeap.end(),u);
            if(vItr!=maxHeap.end())
            {
                maxHeap.erase(vItr);
                maxHeap.push_back(u);
            }
        }

        make_heap(maxHeap.begin(),maxHeap.end(),urlInfoMaxHeap());
    }

    void releaseResources()
    {
        for_each(urls.begin(),urls.end(),[](pair<string,urlInfo*> p){
            urlInfo* u = p.second;
            delete u;
        });
    }

    void printHeap()
    {
        for_each(maxHeap.begin(),maxHeap.end(),[](urlInfo* u){
            cout<<endl<<u->getHitCount()<<"  "<<u->getURL();
        });
    }
private:
    unordered_map<string,urlInfo*> urls;
    vector<urlInfo*> maxHeap;
};


int main()
{
    string fileName("urlMgr.txt");
    urlMgr um(fileName);
    um.printHeap();
    um.releaseResources();
    cout<<endl<<"Successfully inserted the data"<<endl;
}

The output i am getting is

   8 cplusplus.com/max_load_factor
   3 web.whatsapp.com
   4 mail.google.com/mail/u/0/#inbox
   1 en.cppreference.com/w/cpp/language/lambda
   1 other url's and so on. //all other url's show count as 1.

What i expect is

   8 cplusplus.com/max_load_factor   
   4 mail.google.com/mail/u/0/#inbox
   3 web.whatsapp.com
   1 en.cppreference.com/w/cpp/language/lambda
   1 other url's and so on. //all other url's show count as 1.

Answer 1

Finally after some debugging i have found the problem.The problem is in the way you are interpreting how max_heap() works.

Consider this.

url1 occurs 8 times
url2 occurs 4 times
url3 occurs 3 times

After a call to max_heap() what you will get is

maxHeap[0]=8                     8
maxHeap[1]=4                   4   3
maxHeap[2]=3

Or you can also get

maxHeap[0]=8                     8
maxHeap[1]=3                  3     4
maxHeap[2]=4

Both of the above are maxHeaps but you are considering that only the first heap can occur and so in the below code you are just printing maxHeap content without realizing that you may be printing second heap.

  void printHeap()
{
    for_each(maxHeap.begin(),maxHeap.end(),[](urlInfo* u){
        cout<<endl<<u->getHitCount()<<"  "<<u->getURL();
    });
}

To resolve this.One way is to after picking up maxHeap[0] .You delete first element and again call max_heap before picking up maxHeap[0] again.Or you can also have something like below.

 while(maxHeap.size()>0){
    cout<<(*maxHeap.begin())->getHitCount()<<" "<<(*maxHeap.begin())->getURL()<<endl;
    std::pop_heap(maxHeap.begin(),maxHeap.end(),urlInfoMaxHeap());maxHeap.pop_back();}

In the above code pop_heap() will move the topmost element(which has the highest priority according to your implementation of compare function which you pass to make_heap()) to the end and heapify again. You can then delete the last element then.

Also i did not find the use of the below in your code

 vector<urlInfo*>::iterator vItr;
        vItr = find(maxHeap.begin(),maxHeap.end(),u);
        if(vItr!=maxHeap.end())
        {
            maxHeap.erase(vItr);
            maxHeap.push_back(u);
        }