Implement a map of strings

Question

I have to implement a class that behaves like a map of strings using binary search tree. This is the class I implemented:

template<class T>
class StringMapper {
private:
    // Pair
    struct Pair {
        std::string el1;
        T el2;
    };

    // Nod
    struct Node {
        Pair* data;
        Node* left;
        Node* right;
        Node()
        {
            data = new Pair;
        }
        ~Node()
        {
            delete data;
        }
        int nod_size()
        {
             // code here
        }
    };
    Node* root;
public:
    StringMapper()
    {
        root = 0;
    }
    ~StringMapper() {}
    void insert(std::string from, const T& to)
    {
        // code here
    }

    bool find(std::string from,const T& to) const
    {
        return find(root, to);
    }

    bool find(Node* node, const T& value) const
    {
        // code here
    }

    bool getFirstPair(std::string& from, T& to)
    {
        if(root != 0)
        {
            from = root->data->el1;
            to = root->data->el2;
            return true;
        }
        return false;
    }
    bool getNextPair(std::string& from, T& to)
    {
        if(root != 0)
        {

        }
        return false;
    }

    int size() const
    {
        return root->nod_size();
    }
};

To be honest I don't know how to implement the function getNextPair().
If someone could help me I'd appreciate it.

Lou Franco · Accepted Answer · 2011-03-06 21:22:57Z

1

Your interface is an internal iterator. You need to keep some kind of pointer to where you are in the iteration, and set it in getFirstPair().

Once you add this, getNextPair() just goes to the next one. It's somewhat difficult to do this, but that's your assignment, so I leave it to you.

The actual std::map uses an external iterator -- that keeps the state of the iteration separate from the data structure. The major advantage is being able to have more than one simultaneous iteration.

answered Mar 6, 2011 at 21:22

Lou Franco

89.4k14 gold badges137 silver badges199 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Shiroko · Accepted Answer · 2011-03-06 21:46:31Z

1

Without just throwing the algorithm for getNextPair, you will need to keep some kind of internal iterator which will point to the "current" pair. Once you got that, in order to figure the algorithm for the next pair draw yourself a tree with some nodes and see how one can find the next node in the tree given any node in the tree.

answered Mar 6, 2011 at 21:46

Shiroko

1,4278 silver badges12 bronze badges

Collectives™ on Stack Overflow

Implement a map of strings

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related