C++ で双方向リンク リストの反復子を実装する
Syed Hassan Sabeeh Kazmi
2023年10月12日
二重にリンクされたデータ構造は、連続してリンクされたノードのセットで構成されるため、その開始ノードと終了ノードの前と次のリンクはターミネータ (通常はセンチネル ノードまたは null) を指し、リンクされたリストのトラバーサルを容易にします。 このチュートリアルでは、二重リンク リスト の反復子を C++ で実装する方法を説明します。
一般に、反復子クラスは、リンク リスト クラスにそのサブクラスとして属しているため、リンク リスト ノードへのポインタとして新しい要素として実装されます。 次の 4つの主要な操作では、反復子クラスが使用されます。 逆参照割り当て、比較、およびインクリメント操作。
クラスを使用して C++ で双方向リンク リストの反復子を実装する
クラスを使用して双方向連結リストを作成することは、反復子と双方向連結リストを最適化できるため、優れた方法です。 二重連結リストに新しい要素を追加するという点では、反復子クラスは T-type オブジェクトを構築できます。
さらに、C++ コンパイラでは、単純なリスト (データ構造として) の初期化を使用して反復子を初期化できます。手動で指定する必要はありません。 さらに、明示的に value メンバーを初期化することにより、Node オブジェクトを作成するときに、T の デフォルト コンストラクター を呼び出すことができます。
このメソッドに関して、イテレータ クラスは、イテレータ オブジェクトとしての iterator<T> と、挿入されるアイテムとしての constT& を含む 2つの引数を受け入れます。 結果として、新しく挿入されたノードに反復子を返します。
その結果、要素として constT& アイテムを含む新しい双方向リンク リスト ノードが作成されます。これは、反復子クラスがそれを生成し、反復子による挿入の前にリンク リストに正常に挿入できるためです。
#include <iostream>
// optional: using namespace std;
// template with the `T` typename to manipulate and initialize the variables
template <typename T>
// the `linkedlist_node` class has access to the linked list
class linkedlist_node {
public:
T list_data;
linkedlist_node<T>* node_next;
linkedlist_node() : node_next(nullptr) {}
linkedlist_node(const T& con_listitem,
linkedlist_node<T>* activelist_ptr = nullptr)
: list_data(con_listitem), node_next(activelist_ptr) {}
};
// the `linkedlist_main` is the primary/main linked list class
template <typename T>
class linkedlist_main {
public:
linkedlist_main() {
// creating dummy head and tail nodes
node_head = node_tail = new linkedlist_node<T>();
}
linkedlist_main(const linkedlist_main<T>& other) = delete;
linkedlist_main(linkedlist_main<T>&& other) = delete;
~linkedlist_main() {
while (node_head->node_next != nullptr) {
// build the `node_head` head node from the `listdata_temp`
linkedlist_node<T>* listdata_temp = node_head;
node_head = node_head->node_next;
delete listdata_temp; // delete the temp afterward
}
// empty the `node_head` by removing its content
delete node_head;
}
// delete the `linkedlist_main` contents after a successful insertion or
// creation
linkedlist_main<T>& operator=(const linkedlist_main<T>& other) = delete;
linkedlist_main<T>& operator=(linkedlist_main<T>&& other) = delete;
// the `mainCon_iterator` is an inner class inherited from the
// `linkedlist_main` class it creates an iterator implemented on a
// doubly-linked list
class mainCon_iterator {
friend class linkedlist_main; // inherited from
private: // private elements (restricted access)
linkedlist_node<T>* listnode_ptr; // it's a private node that can only be
// accessed by authorized personnel
// only an authorized person can create instances of iterators because the
// constructor is private
mainCon_iterator(linkedlist_node<T>* newlist_ptrnode)
: listnode_ptr(newlist_ptrnode) {}
public: // public elements (general access)
mainCon_iterator() : listnode_ptr(nullptr) {}
// Overload: comparison operator !=
// create an object from the `mainCon_iterator` and perform the comparison
// operator
bool operator!=(const mainCon_iterator& obj_itr) const {
return listnode_ptr != obj_itr.listnode_ptr; // comparison
}
// Overload: dereference operator *
// pass the node via `operator` object `const`
T& operator*() const {
// access to the `list_node` node
return listnode_ptr->node_next->list_data;
}
// Overload: post-increment operator ++
mainCon_iterator operator++(int) {
mainCon_iterator iterator_temp = *this;
listnode_ptr = listnode_ptr->node_next;
return iterator_temp;
}
}; // end of the `mainCon_iterator` inner class
mainCon_iterator begin() const { return mainCon_iterator(node_head); }
mainCon_iterator end() const { return mainCon_iterator(node_tail); }
mainCon_iterator insert(mainCon_iterator iterator_pos,
const T& itrPos_value) {
linkedlist_node<T>* new_listnode = new linkedlist_node<T>(
itrPos_value, iterator_pos.listnode_ptr->node_next);
if (iterator_pos.listnode_ptr == node_tail) node_tail = new_listnode;
iterator_pos.listnode_ptr->node_next = new_listnode;
return iterator_pos;
}
mainCon_iterator erase(mainCon_iterator iterator_pos) {
linkedlist_node<T>* itrposition_delete =
iterator_pos.listnode_ptr->node_next;
iterator_pos.listnode_ptr->node_next =
iterator_pos.listnode_ptr->node_next->node_next;
if (itrposition_delete == node_tail) node_tail = iterator_pos.listnode_ptr;
delete itrposition_delete;
return iterator_pos;
}
private:
linkedlist_node<T>* node_head;
linkedlist_node<T>* node_tail;
};
int main(int argc, const char* argv[]) {
std::cout
<< "Iterator for the doubly-linked list is successfully implemented!"
<< std::endl;
linkedlist_main<int> list_var;
list_var.insert(list_var.end(), 4);
list_var.insert(list_var.end(), 7);
list_var.insert(list_var.end(), 9);
auto iterator = list_var.begin();
iterator = list_var.insert(iterator, 3);
iterator++;
list_var.insert(iterator++, 6);
iterator++;
list_var.insert(iterator, 2);
iterator = list_var.begin();
iterator++;
list_var.erase(iterator);
for (auto iterator = list_var.begin(); iterator != list_var.end(); iterator++)
std::cout << *iterator << std::endl;
return 0;
}
出力：
Iterator for the doubly-linked list is successfully implemented!
3
4
7
2
9
イテレータは連結リスト クラスのデータを操作できるため、消去、更新、または作成する連結リスト内のノードを指します。 iterator クラスの insert と erase はこの問題を解決できますが、この解決策は別の問題を引き起こします。
問題は、リンクされたリストの開始点を指す反復子を返すことを想定している begin() メソッドを処理することです。 この問題を処理するには、リストの実際の開始ノードの前に、次のようなダミーのヘッド ノードを使用します。
iterator begin() const {return iterator(head);} // to handle begin()
プリインクリメント ++itr 演算子とポストインクリメント itr++ 演算子は反復子によってサポートされており、C++ コードの同じステートメントで他の演算子と一緒に使用すると、それらの違いがより明確になります。
ノードを使用して C++ で双方向リンク リストの反復子を実装する
これには、C++ テンプレートとしてかなり標準的な双方向リンク リストへの反復子を実装することが含まれます。 サンプル コードで条件付きコンパイル ディレクティブを使用しており、メンバーを変更する場合に機能を追加できるような重大な欠陥やその他の欠陥は含まれていません。
C++ はインクリメント演算子 (プリインクリメント ++itr とポストインクリメント itr++) をサポートし、反復子クラスでそれらをオーバーロードすることによって、それらの固有の性質を定義または明確にするために独特の規則が必要でした。 iterator& operator++() または iterator operator++(int) をプリインクリメントまたはポストインクリメントにそれぞれ使用し、return *this; を使用できます。 複合 C++ 式でインクリメントを実行する関数。
#include <ctime>
#include <iostream>
#include <random>
template <typename T>
class linkedlist_main {
private:
struct list_node {
list_node* right_node;
list_node* left_node;
T list_value;
list_node(list_node* listnode_left, const T& listnode_value,
list_node* listnode_right)
: left_node(listnode_left),
list_value(listnode_value),
right_node(listnode_right) {}
list_node(list_node* listnode_left, list_node* listnode_right)
: left_node(listnode_left), right_node(listnode_right) {}
};
public:
class iterator_mainClass;
class con_itr_main : public std::iterator<std::bidirectional_iterator_tag,
list_node, int, list_node*, T> {
friend class linkedlist_main;
friend class iterator_mainClass;
private:
typename con_itr_main::pointer pointer_main;
con_itr_main(typename con_itr_main::pointer pointer_first)
: pointer_main(pointer_first) {}
public:
con_itr_main& operator++() {
pointer_main = pointer_main->right_node;
return *this;
}
con_itr_main& operator--() {
pointer_main = pointer_main->left_node;
return *this;
}
con_itr_main operator++(int) {
typename con_itr_main::pointer type_temp = pointer_main;
pointer_main = pointer_main->right_node;
return type_temp;
}
con_itr_main operator--(int) {
typename con_itr_main::pointer type_temp = pointer_main;
pointer_main = pointer_main->left_node;
return type_temp;
}
typename con_itr_main::reference operator*() {
return pointer_main->list_value;
}
friend bool operator==(const con_itr_main& list_first,
const con_itr_main& list_second) {
return list_first.pointer_main == list_second.pointer_main;
}
friend bool operator!=(const con_itr_main& list_first,
const con_itr_main& list_second) {
return !(list_first == list_second);
}
friend bool operator==(const con_itr_main& pri_iterator,
const iterator_mainClass& itr_ele);
friend bool operator!=(const con_itr_main& pri_iterator,
const iterator_mainClass& itr_ele);
};
class iterator_mainClass
: public std::iterator<std::bidirectional_iterator_tag, const list_node,
int, const list_node*, const T> {
friend class linkedlist_main;
private:
typename iterator_mainClass::pointer pointer_main;
iterator_mainClass(typename iterator_mainClass::pointer pointer_first)
: pointer_main(pointer_first) {}
public:
iterator_mainClass(const con_itr_main& pri_iter)
: pointer_main(pri_iter.pointer_main) {}
iterator_mainClass& operator++() {
pointer_main = pointer_main->right_node;
return *this;
}
iterator_mainClass& operator--() {
pointer_main = pointer_main->left_node;
return *this;
}
iterator_mainClass operator++(int) {
typename iterator_mainClass::pointer death = pointer_main;
pointer_main = pointer_main->right_node;
return death;
}
iterator_mainClass operator--(int) {
typename iterator_mainClass::pointer ordinary = pointer_main;
pointer_main = pointer_main->left_node;
return ordinary;
}
typename iterator_mainClass::reference operator*() {
return pointer_main->list_value;
}
friend bool operator==(const iterator_mainClass& temp_iterator,
const iterator_mainClass& temp_iteratorSec) {
return temp_iterator.pointer_main == temp_iteratorSec.pointer_main;
}
friend bool operator!=(const iterator_mainClass& temp_iterator,
const iterator_mainClass& temp_iteratorSec) {
return !(temp_iterator == temp_iteratorSec);
}
friend bool operator==(const con_itr_main& primary_itr,
const iterator_mainClass& primary_itrrator_alt);
friend bool operator!=(const con_itr_main& primary_itr,
const iterator_mainClass& primary_itrrator_alt);
};
friend bool operator==(const con_itr_main& primary_itr,
const iterator_mainClass& primary_itrrator_alt) {
return primary_itr.pointer_main == primary_itrrator_alt.pointer_main;
}
friend bool operator!=(const con_itr_main& primary_itr,
const iterator_mainClass& primary_itrrator_alt) {
return !(primary_itr == primary_itrrator_alt);
}
linkedlist_main() = default;
template <typename... Types>
linkedlist_main(const T& value, Types&&... values)
: linkedlist_main(values...) {
add_valuetotop(value);
}
linkedlist_main(const linkedlist_main& QEL) { *this = QEL; }
linkedlist_main(iterator_mainClass position_start,
const iterator_mainClass position_end) {
for (; position_start != position_end; position_start++)
this->add_valuetoend(*position_start);
}
linkedlist_main(T&& value) { push_front(value); }
~linkedlist_main() {
this->clear();
delete valueto_end;
}
void delete_lastnode() // deletes the last node
{
list_node* delete_lasttemp = valueto_end;
valueto_end = valueto_end->left_node;
valueto_end->right_node = nullptr;
delete delete_lasttemp;
linkedlist_size--;
}
void delete_firstnode() // deletes the first node
{
list_node* delete_firsttemp = listnode_head;
listnode_head = listnode_head->right_node;
listnode_head->left_node = nullptr;
delete delete_firsttemp;
linkedlist_size--;
}
void add_valuetoend(
const T& linkedlist_addvalue) // adds the value to the end of the list
{
valueto_end = new list_node(valueto_end, nullptr);
valueto_end->left_node->list_value = linkedlist_addvalue;
if (linkedlist_size > 0)
valueto_end->left_node->left_node->right_node = valueto_end->left_node;
valueto_end->left_node->right_node = valueto_end;
linkedlist_size++;
}
void add_valuetotop(const T& linkedlist_addvalue_top) // adds the value to
// the top of the list
{
listnode_head =
new list_node(nullptr, linkedlist_addvalue_top, listnode_head);
listnode_head->right_node->left_node = listnode_head;
linkedlist_size++;
}
void clear() {
list_node* clear_buffer;
// a loop to clear all the linked lists temp obj
for (int temp = 0; temp < linkedlist_size; temp++) {
clear_buffer = listnode_head;
listnode_head = listnode_head->right_node;
delete clear_buffer;
}
listnode_head = valueto_end;
linkedlist_size = 0;
}
void erase(iterator_mainClass
node_current_pos) // deletes the node that the iterator points
// to (the iterator itself becomes hung)
{
if (node_current_pos.pointer_main != listnode_head &&
node_current_pos.pointer_main != valueto_end->left_node) {
node_current_pos.pointer_main->left_node->right_node =
node_current_pos.pointer_main->right_node;
node_current_pos.pointer_main->right_node->left_node =
node_current_pos.pointer_main->left_node;
delete node_current_pos.pointer_main;
linkedlist_size--;
} else if (node_current_pos.pointer_main == listnode_head) {
this->delete_firstnode();
} else {
this->delete_lastnode();
}
}
void erase(iterator_mainClass node_startposition,
const iterator_mainClass
node_endposition) // deletes everything from begin_pos to
// end_pos (end_pos itself is not deleted)
{
while (node_startposition != node_endposition) {
this->erase(node_startposition++);
}
}
// the start of the primary iterator
con_itr_main begin() { return con_itr_main(listnode_head); }
iterator_mainClass con_itr_begin() const {
return iterator_mainClass(listnode_head);
}
// the end-point of the primary iterator
con_itr_main end() { return con_itr_main(valueto_end); }
iterator_mainClass con_itr_end() const {
return iterator_mainClass(valueto_end);
}
T& operator[](unsigned const int& oprIndex_con) const {
if (oprIndex_con > (linkedlist_size - 1) / 2) {
return scroll_node(-(linkedlist_size - 1 - oprIndex_con),
valueto_end->left_node)
->list_value;
} else {
return scroll_node(oprIndex_con, listnode_head)->list_value;
}
}
void operator=(const linkedlist_main& oprQel_var) {
this->clear();
auto iter = oprQel_var.con_itr_begin();
for (; iter != oprQel_var.con_itr_end(); iter++) {
this->add_valuetoend(*iter);
}
}
size_t size() const { return linkedlist_size; }
private:
size_t linkedlist_size = 0;
list_node* valueto_end = new list_node(nullptr, nullptr);
list_node* listnode_head = valueto_end;
list_node* scroll_node(int numIndex_pri, list_node* node_ptr) const {
if (numIndex_pri > 0)
for (int i = 0; i < numIndex_pri; i++) {
node_ptr = node_ptr->right_node;
}
else {
numIndex_pri = abs(numIndex_pri);
for (int i = 0; i < numIndex_pri; i++) {
node_ptr = node_ptr->left_node;
}
}
return node_ptr;
}
};
template <typename S>
linkedlist_main<S> template_sort(const linkedlist_main<S>& new_linkedlist) {
srand(time(NULL));
// in case the linked list exists and isn't null
if (new_linkedlist.size() <= 1) {
return new_linkedlist;
}
linkedlist_main<S> size_minimum;
linkedlist_main<S> size_maximum;
linkedlist_main<S> list_elements;
S list_element = new_linkedlist[rand() % new_linkedlist.size()];
auto opr_iterator = new_linkedlist.con_itr_begin();
for (; opr_iterator != new_linkedlist.con_itr_end(); opr_iterator++) {
if (*opr_iterator > list_element) {
size_maximum.add_valuetoend(*opr_iterator);
} else if (*opr_iterator < list_element) {
size_minimum.add_valuetoend(*opr_iterator);
} else {
list_elements.add_valuetoend(list_element);
}
}
size_minimum = template_sort(size_minimum);
opr_iterator = list_elements.con_itr_begin();
for (; opr_iterator != list_elements.con_itr_end(); opr_iterator++) {
size_minimum.add_valuetoend(*opr_iterator);
}
size_maximum = template_sort(size_maximum);
opr_iterator = size_maximum.con_itr_begin();
for (; opr_iterator != size_maximum.con_itr_end(); opr_iterator++) {
size_minimum.add_valuetoend(*opr_iterator);
}
return size_minimum;
}
template <typename S>
linkedlist_main<S> tempSort_selection(linkedlist_main<S> selection_linkedlist) {
linkedlist_main<int> linkedlist_second;
while (selection_linkedlist.size() > 0) {
auto int_maximum = selection_linkedlist.begin();
auto iterator_main = int_maximum;
for (; iterator_main != selection_linkedlist.end(); iterator_main++)
if (*iterator_main > *int_maximum) int_maximum = iterator_main;
linkedlist_second.add_valuetotop(*int_maximum);
selection_linkedlist.erase(int_maximum);
}
return linkedlist_second;
}
int main() {
linkedlist_main<int> linkedlist_orig(0, 1, 9, 26, 8, 3, 7, 4, 6, 5, 11, 47,
2);
linkedlist_main<int> linkedlist_rev = template_sort(linkedlist_orig);
std::cout << "The original list | Size: " << linkedlist_orig.size()
<< std::endl;
std::cout << "Revised version of the original list: " << linkedlist_rev.size()
<< std::endl;
for (int i = 0; i < linkedlist_rev.size(); i++)
std::cout << linkedlist_rev[i] << std::endl;
linkedlist_main<int> linkedlist_sec(tempSort_selection(
linkedlist_main<int>(5, 67, 4, 7, 3, 8, 2, 9, 1, 22, 54, 6)));
std::cout << "The sorted list: " << linkedlist_sec.size() << std::endl;
for (int info = 0; info < linkedlist_sec.size(); info++)
std::cout << linkedlist_rev[info] << std::endl;
std::cout << clock() / static_cast<double>(CLOCKS_PER_SEC) << std::endl;
return 0;
}
出力：
The original list | Size: 13
Revised version of the original list: 13
0
1
2
3
4
5
6
7
8
9
11
26
47
The sorted list: 12
0
1
2
3
4
5
6
7
8
9
11
26
0
結論として、双方向リンク リストには、ポインターを格納して検索を効率化するための余分なスペースとメモリが必要です。 メモリの制限が問題にならない場合は、反復子を実装することも非常に効率的です。
Hassan is a Software Engineer with a well-developed set of programming skills. He uses his knowledge and writing capabilities to produce interesting-to-read technical articles.
GitHub