Implement a map of strings

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 functio开发者_如何转开发n getNextPair().

If someone could help me I'd appreciate it.

---

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.

---

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.