链表迭代器实现C ++ [英] Linked List Iterator Implementation C++
问题描述
我已经用C ++创建了一个链表，并希望为其实现一个迭代器，以便可以进行范围循环:for (const int& i : list)其中Linked_List<int> list;.
I've created a Linked List in C++ and want to implement an iterator for it so that I can do range loops: for (const int& i : list) where Linked_List<int> list;.
我的想法是创建Iterator作为Linked_List类的一部分，如下所示:
My idea is to create the Iterator as part of the Linked_List class like this:
这是我到目前为止得到的:
This is what I got so far:
template <typename T>
class Linked_List
{
public:
struct Iterator;
struct Node;
public:
Linked_List();
~Linked_List() noexcept(false);
Linked_List(const Linked_List&) = delete;
Linked_List(Linked_List&&) = delete;
Linked_List& operator=(const Linked_List&) = delete;
Linked_List& operator=(Linked_List&&) = delete;
void push_back(T);
void push_front(T);
void pop_back();
void pop_front();
bool empty() const;
T back() const;
T front() const;
//void swap(T, T);
//void insert(Iterator, T);
//void erase(Iterator);
//Iterator begin() const;
//Iterator end() const;
private:
Node* head;
Node* tail;
};
template<typename T>
struct Linked_List<T>::Node
{
Node() : prev(nullptr), next(nullptr) {}
Node(T t) : value(t), prev(nullptr), next(nullptr) {}
Node* prev;
Node* next;
T value;
};
- 这是一个好方法吗?
- 在增加列表以检查
current->next == tail时是否应该进行错误检查?如果是这样，我该怎么做?因为我的迭代器没有带尾的列表对象.
- Is this a good approach?
- Should I do error checking when incrementing the list to check if
current->next == tail? If so, how do I do that? Because my Iterator doesn't have a list object with a tail.
修改:
我不确定如何实现struct Iterator;，在弄清楚如何将其与列表连接时会卡住，以便可以检查从迭代器返回的当前节点是否等于Linked_List <中列表的尾部Iterator end() const方法.
Edit:
I'm not sure how to implement the struct Iterator;, I get stuck when figuring out how to connect it with the list so that I can check if the current node returned from the iterator equals the tail in the list, in the Linked_List Iterator end() const method.
比方说，我已经为迭代器实现了所有必要的运算符，如下所示:
Let's say I've implemented all the necessary operators for an iterator like this:
struct Iterator
{
T& operator*() const { return current->value; }
bool operator!=(const Iterator& rhs) { return (*_current != rhs._current); }
Iterator& operator++()
{
current = current->next;
return *this;
}
};
我现在将如何实施Iterator Linked_List<T>::begin() const;和end()?
我想象一个虚构的用户制作一个迭代器对象，如下所示:
Linked_List<int>::Iterator it;
I imagine an imaginary user making an iterator object like this:
Linked_List<int>::Iterator it;
一个想法是有一个没有参数的公共构造函数和一个以节点为参数的私有构造函数，该节点将被设置为_current，并把Linked_List类作为朋友.
An idea is to have a public constructor with no parameters and a private constructor that takes a node as a parameter which _current will be set to, and have the Linked_List class as a friend.
推荐答案
一些注意事项.
有两个选项可以声明Node和Iterator.列表类内部为List<T>::Node或外部为Node<T>.这在某种程度上是一个品味问题.但是从工程的角度来看，嵌套类的符号名称更长，因此您的debuginfo更大.另外，如果嵌套类也是模板，则在必要时/很难对其进行专业化处理(因为首先需要完全对封闭模板进行专门化处理)，但这不是这种情况.
There are two options where to declare Node and Iterator. Inside the list class as List<T>::Node or outside as Node<T>. It is, in part, a matter of taste. From engineering perspective though, the symbol names are longer for nested classes, so your debuginfo is bigger. Also, when nested classes are also templates it is harder to specialize them if/when necessary (because that requires fully specializing the enclosing template first), but this is not the case here.
当一个列表节点用作列表头和尾时，它会导致代码更优美.空列表是其next和prev指向其自身的节点. push_front附加到list.next，后者指向第一个节点或自身. push_back将一个节点附加到list.prev，该节点指向最后一个节点或自身.插入/删除节点时，无需对第一个节点和最后一个节点进行特殊处理.例如. :
It leads to more elegant code when one list node is used as list head and tail. Empty list is a node whose next and prev point to itself. push_front appends to list.next which points to the first node or itself. push_back appends a node to list.prev which points to the last node or itself. When inserting/removing nodes there is no need to have special handling of the first and last nodes. E.g. :
struct Node {
Node *next_, *prev_;
Node()
: next_(this), prev_(this)
{}
~Node() {
unlink();
}
void push_back(Node* n) {
n->next_ = this;
n->prev_ = prev_;
prev_->next_ = n;
prev_ = n;
}
void unlink() {
Node *next = next_, *prev = prev_;
next->prev_ = prev;
prev->next_ = next;
next_ = this;
prev_ = this;
}
};
在上面，Node仅需要两项操作即可维护列表.不仅如此，Node本身就是一个极简列表，可用于侵入式列表(在析构函数中具有自动取消链接).请注意，使用this如何使对nullptr的检查变得不必要-Node始终是有效列表.
In the above, Node only needs two operations to be able to maintain a list. More than that, Node is itself a minimalist list that can be used for intrusive lists (with auto-unlink in the destructor). Note how using this makes checks for nullptr unnecessary - Node is always a valid list.
错误检查应仅在调试模式下(例如，使用assert).否则，这些检查会通过不必要的运行时检查来惩罚正确的应用程序.
Error checking should be in debug mode only (use assert, for example). Otherwise, those checks penalise correct applications with unnecessary run-time checks.
这是一个基于您的想法的最小工作示例:
Here is a minimal working example based on the ideas for you:
template<class T>
class List;
class Iterator;
class Node {
friend class Iterator;
template<class T> friend class List;
protected:
Node *next_, *prev_;
void push_back(Node* n) {
n->next_ = this;
n->prev_ = prev_;
prev_->next_ = n;
prev_ = n;
}
void unlink() {
Node *next = next_, *prev = prev_;
next->prev_ = prev;
prev->next_ = next;
next_ = this;
prev_ = this;
}
public:
Node()
: next_(this), prev_(this)
{}
~Node() { unlink(); }
};
class Iterator {
protected:
Node* node_;
Iterator(Node* node)
: node_(node)
{}
public:
Iterator& operator++() {
node_ = node_->next_;
return *this;
}
bool operator==(Iterator b) const { return node_ == b.node_; }
bool operator!=(Iterator b) const { return node_ != b.node_; }
// Implement the rest of iterator interface.
};
template<class T>
class List {
class NodeT : public Node {
friend class List<T>;
T value_;
NodeT(T t) : value_(t) {}
};
template<class U>
class IteratorT : public Iterator {
friend class List<T>;
NodeT* node() const { return static_cast<NodeT*>(node_); }
public:
U& operator*() const { return node()->value_; }
U* operator->() const { return &node()->value_; }
operator IteratorT<U const>() const { return node_; } // iterator to const_iterator conversion
IteratorT(Node* node) : Iterator{node} {}
};
Node list_;
public:
using iterator = IteratorT<T>;
using const_iterator = IteratorT<T const>;
~List() { clear(); }
bool empty() const { return list_.next_ == &list_; }
iterator begin() { return list_.next_; }
iterator end() { return &list_; }
void push_back(T t) { list_.push_back(new NodeT(t)); }
void erase(const_iterator i) { delete i.node(); }
void clear() {
while(!empty())
erase(begin());
}
// Implement the rest of the functionality.
};
int main() {
List<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3);
for(auto elem : l)
std::cout << elem << ' ';
std::cout << '\n';
}
这篇关于链表迭代器实现C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
