如何在创建自定义迭代器时获得std：：结对的第一个和第二个？
如何在创建自定义迭代器时获得std：：结对的第一个和第二个？
提问于 2018-10-21 08:14:48
我使用基本实现创建了一个简单的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在评论中也指出了这一点。在按建议进行更改后，它将按预期的方式工作。谢谢大家的帮助。
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-10-21 08:45:25
您的->操作符有两个问题：
std::pair<K, V>& operator-> () const
{
assert(itr != nullptr & "Out of bounds");
return std::pair<K, V>(itr->key, itr->value);
}->运算符应该返回指针，而不是引用。- 返回对临时对象的引用(与
*操作符的问题相同)。
当前的迭代器实现生成元素，而不是指向它们。在某些情况下，这是可以接受的，但是您将无法实现->操作符，因为它应该返回指向现有值的指针，而不是临时值。
解决这一问题的最简单方法是在地图的节点中实际存储一个pair：
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;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52913329
复制相关文章
相似问题
腾讯云开发者
