Реализовать карту строк

Question

Я должен реализовать класс, который ведет себя как карта строк, используя двоичное дерево поиска.Это класс, который я реализовал:

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();
    }
};

Если честно, я не знаю, как реализовать функцию getNextPair().
Если бы кто-то мог мне помочь, я был бы признателен.

Answer 1

Не бросая алгоритм getNextPair, вам нужно будет сохранить какой-то внутренний итератор, который будет указывать на «текущую» пару.Как только вы это получите, чтобы понять алгоритм следующей пары, нарисуйте себе дерево с некоторыми узлами и посмотрите, как можно найти следующий узел в дереве по любому узлу дерева.

Answer 2

Ваш интерфейс является внутренним итератором. Вам нужно сохранить какой-то указатель на то, где вы находитесь в итерации, и установить его в getFirstPair ().

Как только вы добавите это, getNextPair () просто перейдет к следующему. Это довольно сложно сделать, но это твое задание, поэтому я оставляю это тебе.

Фактический std::map использует внешний итератор - который сохраняет состояние итерации отдельно от структуры данных. Основным преимуществом является возможность иметь более одной одновременной итерации.