c++ - 创建自定义迭代器时如何获取 std::pair 的第一个和第二个？

Question

我已经创建了一个带有基本实现的简单 HashMap (unordered_map)。现在，我想创建一个派生自 std::iterator 的简单自定义前向迭代器。但是，我无法弄清楚迭代器的第一个和第二个成员的实现，例如 unordered_map 的迭代器。有人能帮助我吗 ？为简单起见，假设我的 HashMap 有固定的 10 个桶，并且假设元素是整数类型，只使用简单的模数来获取索引。下面是我的 HashMap 和迭代器的实现。

#include <iostream>
#include <iterator>
#include <utility>
#include <cassert>

template<typename K, typename V>
class Node
{
public:
    K key;
    V val;
    Node *next;

    Node(K k, V v)
    {
        key = k; val = v; next = nullptr;
    }
};

template<typename K, typename V>
class Element
{
public:
    int count;
    Node<K, V> *head;
    Node<K, V> *tail;
    Element *next;

    Element()
    {
        count = 0;
        head = tail = nullptr;
        next = nullptr;
    }
};

template<typename K, typename V>
class ForwardIterator : public std::iterator<std::forward_iterator_tag, std::pair<K, V>>
{
    Node<K, V> *itr;
    Element<K, V> *el;

public:
    explicit ForwardIterator(Node<K, V> *i, Element<K, V> *e) : itr(i), el(e) {}
    ForwardIterator() : itr(nullptr), el(nullptr) {}

    void swap(ForwardIterator& other)
    {
        std::swap(itr, other.itr);
        std::swap(el, other.el);
    }

    ForwardIterator& operator++()
    {
        assert(itr != nullptr && "Out of bounds");
        if(itr->next == nullptr) // last node in the current index
        {
            while(el->next != nullptr)
            {
                el = el->next;
                if(el->head != nullptr) // if there is atleast one node at the current index
                {
                    itr = el->head;
                    break;
                }
                else
                    itr = nullptr;
            }
        }
        else
            itr = itr->next;

        return *this;
    }

    ForwardIterator operator++(int)
    {
        assert(itr != nullptr && "Out of bounds");
        ForwardIterator tmp(*this);
        if(itr->next == nullptr) // last node in the current index
        {
            while(el->next != nullptr)
            {
                el = el->next;
                if(el->head != nullptr) // if there is atleast one node at the current index
                {
                    itr = el->head;
                    break;
                }
                else
                    itr = nullptr;
            }
        }
        else
            itr = itr->next;

        return tmp;
    }

    template<typename key, typename value>
    bool operator==(const ForwardIterator<key, value>& rhs) const
    {
        return itr == rhs.itr && el == rhs.el;
    }

    template<typename key, typename value>
    bool operator!=(const ForwardIterator<key, value>& rhs) const
    {
        return itr != rhs.itr || el != rhs.el;
    }

    std::pair<K, V>& operator* () const
    {
        assert(itr != nullptr && "Out of bounds");
        return std::pair<K, V>(itr->key, itr->val);
    }

    std::pair<K, V>& operator-> () const
    {
        assert(itr != nullptr && "Out of bounds");
        return std::pair<K, V>(itr->key, itr->val);
    }
};

template<typename K, typename V>
class MyHashMap
{
private:
    Element<K, V>* arr[10];
    int size;

public:
    typedef ForwardIterator<K, V> myIt;
    typedef ForwardIterator<const K, const V> cMyIt;

    MyHashMap()
    {
        size = 0;
        arr[0] = new Element<K, V>();
        for(int i=1; i<10; ++i)
        {
            arr[i] = new Element<K, V>();
            arr[i-1]->next = arr[i];
        }
    }

    myIt begin()
    {
        if(size == 0)
        {
            myIt m(nullptr, nullptr);
            return m;
        }
        else
        {
            Element<K, V> *temp = arr[0];
            while(temp->head == nullptr)
                temp = temp->next;

            myIt m(temp->head, temp);
            return m;
        }
    }

    myIt end()
    {
        myIt m(nullptr, nullptr);
        return m;
    }

    std::pair<myIt, bool> insert(std::pair<K, V>& p)
    {
        int index = p.first%10;
        if(arr[index]->head == nullptr)
        {
            arr[index]->head = new Node<K, V>(p.first, p.second);
            arr[index]->tail = arr[index]->head;
            ++(arr[index]->count);
        }
        else
        {
            Node<K, V> *temp = new Node<K, V>(p.first, p.second);
            arr[index]->tail->next = temp;
            arr[index]->tail = temp;
            ++(arr[index]->count);
        }

        ++size;
        myIt m(arr[index]->tail, arr[index]);
        return std::pair<myIt, bool>(m, true);
    }

    myIt find(K k)
    {
        int index = k%10;
        Node<K, V> *temp = arr[index]->head;
        while(temp != nullptr)
        {
            if(temp->key == k)
            {
                myIt m(temp, arr[index]);
                return m;
            }
            else
                temp = temp->next;
        }

        return end();
    }

    int remove(K k)
    {
        int index = k%10;
        Node<K, V> *temp = arr[index]->head;
        Node<K, V> *t2 = temp;
        while(temp != nullptr)
        {
            if(temp->key == k)
            {
                if(arr[index]->count == 1)
                {
                    delete temp;
                    arr[index]->head = arr[index]->tail = nullptr;
                }
                else if(arr[index]->head == temp)
                {
                    arr[index]->head = arr[index]->head->next;
                    delete temp;
                }
                else if(arr[index]->tail == temp)
                {
                    delete temp;
                    t2->next = nullptr;
                    arr[index]->tail = t2;
                }
                else
                {
                    t2->next = temp->next;
                    delete temp;
                }
                --(arr[index]->count);
                --size;
                return 1;
            }   
            else
            {
                t2 = temp;
                temp = temp->next;
            }
        }

        return 0;
    }

    V &operator[](K k)
    {
        int index = k%10;
        Node<K, V> *temp = arr[index]->head;
        while(temp != nullptr)
        {
            if(temp->key == k)
                return temp->value;
            else
                temp = temp->next;
        }

        exit(0);
    }   
};    

现在，下面是我的主要部分。

int main()
{
    MyHashMap<int, int> mhm;
    mhm.insert(std::pair<int, int>(1,1));
    mhm.insert(std::pair<int, int>(2,2));

    MyHashMap<int, int>::myIt it = mhm.begin();
    //std::cout << it->first << " " << it->second << std::endl ->this line doesn't compile  

}

编辑:上面提到的代码片段恢复到有问题的原始状态。 @"r3mus n0x"的回答非常清楚地总结了这个问题，@Evg 在评论中也指出了这个问题。按照建议进行更改后，它按预期工作。感谢大家的帮助。

Answer 1

-> 运算符有两个问题:

std::pair<K, V>& operator-> () const
{
    assert(itr != nullptr & "Out of bounds");
    return std::pair<K, V>(itr->key, itr->value);
}

1. -> 运算符应该返回一个指针，而不是一个引用。
2. 您返回对临时对象的引用(与您的 * 运算符相同的问题)。

您当前的迭代器实现生成 元素而不是指向它们。这在某些情况下是可以接受的，但您将无法实现 -> 运算符，因为它应该返回一个指向现有值的指针，而不是临时值。

解决这个问题的最简单方法是在 map 节点中实际存储一个对:

template<typename K, typename V>
class Node
{
public:
    std::pair<K, V> value;
}

然后像这样实现您的 -> 运算符:

std::pair<K, V>* operator-> () const
{
    assert(itr != nullptr & "Out of bounds");
    return &itr->value;
}