Click here to Skip to main content
15,918,808 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
I am trying to implement map on C++.

Can please take a look why I my end() function is not working correctly?

What I am doing wrong? Even I can't print my whole table.

What I have tried:

Here is my whole code:
C++
<pre>#include <iostream>
#include <utility>
#include <string>
#include <list>
#include <vector>

using namespace std;

class HComp {
public :
    int operator() (const int& i) const
    {
        return i;
    }
 };

template <typename K, typename V, typename H>
class HashMap {

public:
    typedef pair<const K, V> Entry;
    class Iterator;

public:
    HashMap(int capacity = 100) : n(0), B(capacity) { }

    int size() const
    {
        return n;
    }

    bool empty() const
    {
        return size() == 0;
    }

    Iterator find(const K& k);

    Iterator put(const K& k, const V& v);

    void erase(const Iterator& p) { eraser(p); }

    void erase(const K& k);

    Iterator begin();

    Iterator end();

    void print();

protected:
    typedef list<Entry> Bucket;
    typedef vector<Bucket> BktArray;
    typedef typename Bucket::iterator EItor;
    typedef typename BktArray::iterator BItor;

    Iterator finder(const K& k);
    Iterator inserter(const Iterator& p, const Entry& e);

    void eraser(const Iterator& p);

    void nextEntry(Iterator& p)
    {
        ++p.ent;
    };

    bool endOfBkt(const Iterator& p)
    {
        return p.ent == p.bkt->end();
    }

private:
    int n;
    H hash;
    BktArray B;

public:

class Iterator {
     private:
        EItor ent;
        BItor bkt;
        const BktArray* ba;

     public:
        Iterator(const BktArray& a, const BItor& b, const EItor& q = EItor())
        : ent(q), bkt(b), ba(&a) { }

        Entry& operator*() const;

        bool operator==(const Iterator& p) const;

        Iterator& operator++();

        friend class HashMap;
     };
};

template <typename K, typename V, typename H>
typename HashMap<K, V, H>::Entry& HashMap<K,V,H>::Iterator::operator*() const
{
    return *ent;
}

template <typename K, typename V, typename H>
bool HashMap<K,V,H>::Iterator::operator==(const Iterator& p) const
{
    if (ba != p.ba || bkt != p.bkt) {
        return false;
    } else if (bkt == ba->end()) {
        return true;
    } else {
        return (ent == p.ent);
    }
}

template <typename K, typename V, typename H>
typename HashMap<K, V, H>::Iterator& HashMap<K,V,H>::Iterator::operator++() {
    ++ent;

    if (HashMap().endOfBkt(*this)) {
        ++bkt;

        while (bkt != ba->end() && bkt->empty()) {
            ++bkt;
        }

        if (bkt == ba->end()) {
            return *this;
        }

        ent = bkt->begin();
    }

    return *this;
}

template <typename K, typename V, typename H>
typename HashMap<K, V, H>::Iterator HashMap<K,V,H>::find(const K& k) {
    Iterator p = finder(k);

    if (HashMap().endOfBkt(p)) {
        return end();
    } else {
        return p;
    }
}

template <typename K, typename V, typename H>
typename HashMap<K, V, H>::Iterator HashMap<K,V,H>::finder(const K& k) {
    int i = hash(k) % B.size();
    BItor bkt  = B.begin() + i;
    Iterator p(B, bkt, bkt->begin());
    while (!HashMap().endOfBkt(p) && (*p).first != k) {
        nextEntry(p);
    }

    return p;
}

template <typename K, typename V, typename H>
typename HashMap<K, V, H>::Iterator HashMap<K,V,H>::put(const K& k, const V& v) {
    Iterator p = finder(k);

    if (HashMap().endOfBkt(p)) {
        return inserter(p, Entry(k, v));
    } else {
        p.ent->second = v;
        return p;
    }
}

template <typename K, typename V, typename H>
typename HashMap<K, V, H>::Iterator HashMap<K,V,H>::inserter(const Iterator& p, const Entry& e) {
    EItor ins = p.bkt->insert(p.ent, e);
    n++;
    return Iterator(B, p.bkt, ins);
}

template <typename K, typename V, typename H>
void HashMap<K,V,H>::erase(const K& k) {
   Iterator p = finder(k);
   if (HashMap().endOfBkt(p)) {
        cout << "Erasing nonexistent";
        return;
   }

   eraser(p);
}

template <typename K, typename V, typename H>
void HashMap<K,V,H>::eraser(const Iterator& p) {
   p.bkt->erase(p.ent);
   n--;
}

template <typename K, typename V, typename H>
typename HashMap<K,V,H>::Iterator HashMap<K,V,H>::end() {
    return Iterator(B, B.end());
}

template <typename K, typename V, typename H>
typename HashMap<K,V,H>::Iterator HashMap<K,V,H>::begin() {
    if (empty()) {
        return end();
    }

    BItor bkt = B.begin();

    while (bkt->empty()) {
        ++bkt;
    }

    return Iterator(B, bkt, bkt->begin());
}

int main()
{
    HashMap<int, int, HComp> hm;

    hm.put(1, 10);
    hm.put(2, 1);
    hm.put(3, 33);
    //hm.put(3, 1);

    HashMap<int, int, HComp>::Iterator start = hm.begin();
    HashMap<int, int, HComp>::Iterator endP = hm.end();
    //HashMap<int, int, HComp>::Iterator i = start;
    HashMap<int, int, HComp>::Iterator kk = hm.find(5);

//    for (auto i = start; i != endP; ++i) {
//        cout << "Key: " << (*i).first
//            << "Value: " << (*i).second
//        << endl;
//    }

    cout << "The size is: " << hm.size() << endl;
    return 0;
}
Posted
Updated 20-Jan-21 1:20am

1 solution

You should overload the != operator of your Iterator class, or, alternatively use std::rel_ops (see rel_ops - C++ Reference[^]).
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900