为链表中的链接重载运算符 ++ (c++)
Overloading operator ++ for links in a linked list (c++)
考虑 LinkedList 在 c++ 中的 class Link 的标准实现。
我想知道在这个 class 中重载运算符 ++ 是否是个好主意（我注意到在处理 linked 列表时我重复了行 link = link->next; 很多，所以我我认为如果我重载这个运算符会更容易）。这是我的实现：
#ifndef LINK_H
#define LINK_H
#include <iostream>
#include "typeinfo.h"
#include "LinkedList.h"
template <class T> class LinkedList; //|Forward declaration of the generic LinkedList.
template <class T>
class Link
{
public:
//|-------------------- Constructors --------------------
Link(T data): m_data(data), next(NULL){}
//|-------------------- Methods --------------------
T getData(){
return m_data;
}
T& getNext(){
return next;
}
void setNext(Link* newLink){
next = newLink;
}
void setData(T data){
m_data = data;
}
//|-------------------- Operator overload --------------------
bool operator==(Link& other){
if(this->m_data == other.m_data)
return true;
return false;
}
void operator++(){ //Is this okay?
this = this->next;
}
//|-------------------- Friend functions --------------------
friend std::ostream& operator<<(std::ostream& out,const Link<T>& link){
out<<link.m_data;
return out;
}
//|-------------------- Destructor --------------------
virtual ~Link(){}
protected:
public:
//|-------------------- Private fields --------------------
T m_data;
Link<T>* next;
friend class LinkedList<T>;
};
#endif // LINK_H
我想我尝试做的方式并不好（它确实像我预期的那样工作）。我尝试使用 this 因为我希望它在指向某个 link.
的指针上工作
那么，这是个好主意吗？如果是，正确的实施方式是什么？
谢谢。
也许你应该重构你的设计和代码。
link，或者更好的说法是节点，通常作为自己的 class 实现。 this class 嵌入到 LinkedList class 中。并且那个节点class应该是完全封装的，不对外展示
class 的用户将只处理数据值。应该隐藏所有指针内容。
并且为了能够迭代您的 class，这类似于 std::forward_list，您可以添加超简单的迭代器功能。大多数功能都可以使用一个衬里来实现。
下面我将向您展示一个非常简单的实现示例。这可以根据您的需要轻松扩展。
您可能会从中吸取一些想法来改进您的设计。
通过添加的迭代器功能，您可以使用基于范围的 for 循环和 std:: 算法等。
请大家看一下，有什么不明白的地方再问。
#include <iostream>
#include <iterator>
#include <initializer_list>
#include <algorithm>
// Very simple implementation of a forward list
template <class T>
class SinglyLinkedList {
// The node
struct Node {
T data{}; // Data. Would normally be a templated argument
Node* next{}; // And the pointer to the next node
Node(const T& i, Node* n = nullptr) : data(i), next(n) {}; // Simple constructor to set a value and next pointer
};
Node* head{}; // This is the start of the list
// It would be advisable to have a tail pointer. We use the more inefficient approach here
Node* getLast() const { Node* n{ head }; while (n and n->next) n = n->next; return n; }
public:
// Constructor / Destructor --------------------------------------------------------------------------------------------------------
~SinglyLinkedList() { clear(); }
// Default constuctor
SinglyLinkedList() {} // Default
// From an initialization list
SinglyLinkedList(const std::initializer_list<T>& il) { clear(); for (const T& i : il) push_back(i); } // From initializer list
// Copy constructor
SinglyLinkedList(const SinglyLinkedList& other) { clear(); for (const T &i : other) push_back(i); }
// Move constructor. Will steal the elements from the other
SinglyLinkedList(SinglyLinkedList&& other) noexcept { head = other.head; other.head = nullptr; }
// Assignment operator
SinglyLinkedList& operator = (const SinglyLinkedList& other) { clear(); for (const T &i : other) push_back(i); }
// Move assignment operator
SinglyLinkedList& operator = (SinglyLinkedList&& other) { head = other.head; other.head = nullptr; }
// Housekeeping --------------------------------------------------------------------------------------------------------------
void clear() { Node* tmp{ head }; while (tmp) { Node* toDelete{ tmp }; tmp = tmp->next; delete toDelete; } head = nullptr; }
int empty() const { return head == nullptr; }
int size() const { int k{}; Node* n{ head }; while (n) { ++k; n = n->next; } return k; }
// Modify content --------------------------------------------------------------------------------------------------------------
void push_front(const T& i) { Node* n = new Node(i); n->next = head; head = n; };
void push_back(const T& i) { Node* n = new Node(i); Node* l = getLast(); if (l) l->next = n; else head = n; }
void pop_front() { if (head) { Node* tmp = head->next; delete head; head = tmp; } }
void pop_back() { // This is a little bit more difficult in a singly linked list
if (head) {
Node* n{ head }, * previous{};
while (n and n->next) {
previous = n;
n = n->next;
}
delete n;
if (previous)
previous->next = nullptr;
else
head->next = nullptr;
}
}
// Access elements --------------------------------------------------------------------------------
T front() const { return head ? head->data : 0; };
T back() const { Node* n = getLast(); return n ? n->data : 0; }
// Add iterator properties to class ---------------------------------------------------------------
struct iterator { // Local class for iterator
Node* iter{}; // Iterator is basically a pointer to the node
// Define alias names necessary for the iterator functionality
using iterator_category = std::forward_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = T;
using pointer = T*;
using reference = T&;
// Constructor
iterator() {}
iterator(Node* n) : iter(n) {}
// Dereferencing
reference operator *() const { return iter->data; }
pointer operator ->() const { return &iter->data; }
// Aithmetic operations
iterator& operator ++() { if (iter) iter = iter->next; return *this; }
iterator operator ++(int) { iterator temp{ *this }; ++* this; return temp; }
iterator operator +(const difference_type& n) const { iterator temp{ *this }; difference_type k{ n }; while (k--)++temp; return temp; }
iterator& operator +=(const difference_type& n) { difference_type k{ n }; while (k--)++* this; return *this; };
// Comparison
bool operator != (const iterator& other) const { return iter != other.iter; }
bool operator == (const iterator& other) const { return iter == other.iter; }
bool operator < (const iterator& other) const { return iter < other.iter; }
bool operator > (const iterator& other) const { return iter > other.iter; }
bool operator <= (const iterator& other) const { return iter <= other.iter; }
bool operator >= (const iterator& other) const { return iter >= other.iter; }
// Difference. Also complicated, because no random access
difference_type operator-(const iterator& other) const {
difference_type result{};
Node* n{ iter };
while (n and n != other.iter) {
++result;
n = n->next;
}
return result;
}
};
// Begin and end function to initialize an iterator
iterator begin() const { return iterator(head); }
iterator end() const { return iterator(); }
// Functions typcical for forward lists ----------------------------------------------------------------------
// Easy, becuase we can operate form the current iterator and do not need the "previous" element
iterator insertAfter(iterator& pos, const T& i) {
iterator result{};
if (pos.iter and pos.iter->next) {
Node* n = new Node(i, pos.iter->next);
pos.iter->next = n;
result = n;
}
return result;
}
iterator eraseAfter(iterator& pos) {
iterator result{};
if (pos.iter and pos.iter->next) {
Node* tmp = pos.iter->next->next;
delete pos.iter->next;
pos.iter->next = tmp;
result = pos.iter->next;
}
return result;
}
};
// Test/Driver Code
int main() {
// Example for initilizer list
SinglyLinkedList<int> sllbase{ 5,6,7,8,9,10,11,12,13,14,15 };
// Show move constructor
SinglyLinkedList<int> sll(std::move(sllbase));
// Add some values in the front
sll.push_front(4);
sll.push_front(3);
sll.push_front(2);
sll.push_front(1);
// Delete 1st element (Number 1)
sll.pop_front();
// Delete last element
sll.pop_back();
// Use a std::algorithm on our custom linked list. Works because we have an interator
SinglyLinkedList<int>::iterator iter = std::find(sll.begin(), sll.end(), 8);
// Now add an element after 8
iter = sll.insertAfter(iter, 88);
// End delete the 9
iter = sll.eraseAfter(iter);
// Use range based for loop. Works because, we have iterators
for (int i : sll)
std::cout << i << ' ';
}
考虑 LinkedList 在 c++ 中的 class Link 的标准实现。
我想知道在这个 class 中重载运算符 ++ 是否是个好主意（我注意到在处理 linked 列表时我重复了行 link = link->next; 很多，所以我我认为如果我重载这个运算符会更容易）。这是我的实现：
#ifndef LINK_H
#define LINK_H
#include <iostream>
#include "typeinfo.h"
#include "LinkedList.h"
template <class T> class LinkedList; //|Forward declaration of the generic LinkedList.
template <class T>
class Link
{
public:
//|-------------------- Constructors --------------------
Link(T data): m_data(data), next(NULL){}
//|-------------------- Methods --------------------
T getData(){
return m_data;
}
T& getNext(){
return next;
}
void setNext(Link* newLink){
next = newLink;
}
void setData(T data){
m_data = data;
}
//|-------------------- Operator overload --------------------
bool operator==(Link& other){
if(this->m_data == other.m_data)
return true;
return false;
}
void operator++(){ //Is this okay?
this = this->next;
}
//|-------------------- Friend functions --------------------
friend std::ostream& operator<<(std::ostream& out,const Link<T>& link){
out<<link.m_data;
return out;
}
//|-------------------- Destructor --------------------
virtual ~Link(){}
protected:
public:
//|-------------------- Private fields --------------------
T m_data;
Link<T>* next;
friend class LinkedList<T>;
};
#endif // LINK_H
我想我尝试做的方式并不好（它确实像我预期的那样工作）。我尝试使用 this 因为我希望它在指向某个 link.
那么，这是个好主意吗？如果是，正确的实施方式是什么？
谢谢。
也许你应该重构你的设计和代码。
link，或者更好的说法是节点，通常作为自己的 class 实现。 this class 嵌入到 LinkedList class 中。并且那个节点class应该是完全封装的，不对外展示
class 的用户将只处理数据值。应该隐藏所有指针内容。
并且为了能够迭代您的 class，这类似于 std::forward_list，您可以添加超简单的迭代器功能。大多数功能都可以使用一个衬里来实现。
下面我将向您展示一个非常简单的实现示例。这可以根据您的需要轻松扩展。
您可能会从中吸取一些想法来改进您的设计。
通过添加的迭代器功能，您可以使用基于范围的 for 循环和 std:: 算法等。
请大家看一下，有什么不明白的地方再问。
#include <iostream>
#include <iterator>
#include <initializer_list>
#include <algorithm>
// Very simple implementation of a forward list
template <class T>
class SinglyLinkedList {
// The node
struct Node {
T data{}; // Data. Would normally be a templated argument
Node* next{}; // And the pointer to the next node
Node(const T& i, Node* n = nullptr) : data(i), next(n) {}; // Simple constructor to set a value and next pointer
};
Node* head{}; // This is the start of the list
// It would be advisable to have a tail pointer. We use the more inefficient approach here
Node* getLast() const { Node* n{ head }; while (n and n->next) n = n->next; return n; }
public:
// Constructor / Destructor --------------------------------------------------------------------------------------------------------
~SinglyLinkedList() { clear(); }
// Default constuctor
SinglyLinkedList() {} // Default
// From an initialization list
SinglyLinkedList(const std::initializer_list<T>& il) { clear(); for (const T& i : il) push_back(i); } // From initializer list
// Copy constructor
SinglyLinkedList(const SinglyLinkedList& other) { clear(); for (const T &i : other) push_back(i); }
// Move constructor. Will steal the elements from the other
SinglyLinkedList(SinglyLinkedList&& other) noexcept { head = other.head; other.head = nullptr; }
// Assignment operator
SinglyLinkedList& operator = (const SinglyLinkedList& other) { clear(); for (const T &i : other) push_back(i); }
// Move assignment operator
SinglyLinkedList& operator = (SinglyLinkedList&& other) { head = other.head; other.head = nullptr; }
// Housekeeping --------------------------------------------------------------------------------------------------------------
void clear() { Node* tmp{ head }; while (tmp) { Node* toDelete{ tmp }; tmp = tmp->next; delete toDelete; } head = nullptr; }
int empty() const { return head == nullptr; }
int size() const { int k{}; Node* n{ head }; while (n) { ++k; n = n->next; } return k; }
// Modify content --------------------------------------------------------------------------------------------------------------
void push_front(const T& i) { Node* n = new Node(i); n->next = head; head = n; };
void push_back(const T& i) { Node* n = new Node(i); Node* l = getLast(); if (l) l->next = n; else head = n; }
void pop_front() { if (head) { Node* tmp = head->next; delete head; head = tmp; } }
void pop_back() { // This is a little bit more difficult in a singly linked list
if (head) {
Node* n{ head }, * previous{};
while (n and n->next) {
previous = n;
n = n->next;
}
delete n;
if (previous)
previous->next = nullptr;
else
head->next = nullptr;
}
}
// Access elements --------------------------------------------------------------------------------
T front() const { return head ? head->data : 0; };
T back() const { Node* n = getLast(); return n ? n->data : 0; }
// Add iterator properties to class ---------------------------------------------------------------
struct iterator { // Local class for iterator
Node* iter{}; // Iterator is basically a pointer to the node
// Define alias names necessary for the iterator functionality
using iterator_category = std::forward_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = T;
using pointer = T*;
using reference = T&;
// Constructor
iterator() {}
iterator(Node* n) : iter(n) {}
// Dereferencing
reference operator *() const { return iter->data; }
pointer operator ->() const { return &iter->data; }
// Aithmetic operations
iterator& operator ++() { if (iter) iter = iter->next; return *this; }
iterator operator ++(int) { iterator temp{ *this }; ++* this; return temp; }
iterator operator +(const difference_type& n) const { iterator temp{ *this }; difference_type k{ n }; while (k--)++temp; return temp; }
iterator& operator +=(const difference_type& n) { difference_type k{ n }; while (k--)++* this; return *this; };
// Comparison
bool operator != (const iterator& other) const { return iter != other.iter; }
bool operator == (const iterator& other) const { return iter == other.iter; }
bool operator < (const iterator& other) const { return iter < other.iter; }
bool operator > (const iterator& other) const { return iter > other.iter; }
bool operator <= (const iterator& other) const { return iter <= other.iter; }
bool operator >= (const iterator& other) const { return iter >= other.iter; }
// Difference. Also complicated, because no random access
difference_type operator-(const iterator& other) const {
difference_type result{};
Node* n{ iter };
while (n and n != other.iter) {
++result;
n = n->next;
}
return result;
}
};
// Begin and end function to initialize an iterator
iterator begin() const { return iterator(head); }
iterator end() const { return iterator(); }
// Functions typcical for forward lists ----------------------------------------------------------------------
// Easy, becuase we can operate form the current iterator and do not need the "previous" element
iterator insertAfter(iterator& pos, const T& i) {
iterator result{};
if (pos.iter and pos.iter->next) {
Node* n = new Node(i, pos.iter->next);
pos.iter->next = n;
result = n;
}
return result;
}
iterator eraseAfter(iterator& pos) {
iterator result{};
if (pos.iter and pos.iter->next) {
Node* tmp = pos.iter->next->next;
delete pos.iter->next;
pos.iter->next = tmp;
result = pos.iter->next;
}
return result;
}
};
// Test/Driver Code
int main() {
// Example for initilizer list
SinglyLinkedList<int> sllbase{ 5,6,7,8,9,10,11,12,13,14,15 };
// Show move constructor
SinglyLinkedList<int> sll(std::move(sllbase));
// Add some values in the front
sll.push_front(4);
sll.push_front(3);
sll.push_front(2);
sll.push_front(1);
// Delete 1st element (Number 1)
sll.pop_front();
// Delete last element
sll.pop_back();
// Use a std::algorithm on our custom linked list. Works because we have an interator
SinglyLinkedList<int>::iterator iter = std::find(sll.begin(), sll.end(), 8);
// Now add an element after 8
iter = sll.insertAfter(iter, 88);
// End delete the 9
iter = sll.eraseAfter(iter);
// Use range based for loop. Works because, we have iterators
for (int i : sll)
std::cout << i << ' ';
}