创建自定义迭代器时如何获得 std::pair 的第一个和第二个?
How do you get the std::pair's first and second while creating a custom iterator?
我已经创建了一个具有基本实现的简单 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 在评论中也指出了这个问题。按照建议进行更改后,它按预期工作。感谢大家的帮助。
您的 ->
运算符有两个问题:
std::pair<K, V>& operator-> () const
{
assert(itr != nullptr & "Out of bounds");
return std::pair<K, V>(itr->key, itr->value);
}
->
运算符应该 return 一个指针,而不是引用。
- 您 return 对临时对象的引用(与您的
*
运算符相同的问题)。
您当前的迭代器实现生成 个元素而不是指向它们。这在某些情况下是可以接受的,但您将无法实现 ->
运算符,因为它应该 return 指向现有值的指针,而不是临时值。
解决这个问题的最简单方法是在地图的节点中实际存储一个 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;
}
我已经创建了一个具有基本实现的简单 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 在评论中也指出了这个问题。按照建议进行更改后,它按预期工作。感谢大家的帮助。
您的 ->
运算符有两个问题:
std::pair<K, V>& operator-> () const
{
assert(itr != nullptr & "Out of bounds");
return std::pair<K, V>(itr->key, itr->value);
}
->
运算符应该 return 一个指针,而不是引用。- 您 return 对临时对象的引用(与您的
*
运算符相同的问题)。
您当前的迭代器实现生成 个元素而不是指向它们。这在某些情况下是可以接受的,但您将无法实现 ->
运算符,因为它应该 return 指向现有值的指针,而不是临时值。
解决这个问题的最简单方法是在地图的节点中实际存储一个 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;
}