C++에서 이중 연결 목록에 대한 반복자 구현
Syed Hassan Sabeeh Kazmi
2023년10월12일
이중 연결된 데이터 구조는 일련의 순차적으로 연결된 노드로 구성되므로 시작 및 끝 노드의 이전 및 다음 링크는 연결된 목록의 순회를 용이하게 하기 위해 종료자(일반적으로 센티넬 노드 또는 null)를 가리킵니다. 이 튜토리얼은 C++에서 이중 연결 목록에 대한 반복자를 구현하는 방법을 알려줍니다.
일반적으로 iterator 클래스는 하위 클래스로 연결 목록 클래스에 속하기 때문에 연결 목록 노드에 대한 포인터로 새 요소로 구현됩니다. 네 가지 기본 작업은 다음을 포함하여 반복자 클래스를 사용합니다. 역참조 할당, 비교 및 증분 연산.
클래스를 사용하여 C++에서 이중 연결 목록에 대한 반복자 구현
이중 연결 목록을 작성하기 위해 클래스를 사용하는 것은 반복자와 이중 연결 목록을 최적화할 수 있기 때문에 훌륭한 방법입니다. 이중 연결 목록에 새 요소를 추가하는 측면에서 반복자 클래스는 T 유형 객체를 구축할 수 있습니다.
또한 C++ 컴파일러는 이를 지정하기 위한 수동 도움말 없이 간단한 목록(데이터 구조) 초기화를 사용하여 반복자 초기화를 허용합니다. 또한 value 멤버를 명시적으로 초기화하여 Node 개체를 생성할 때 T의 기본 생성자를 호출할 수 있습니다.
이 메서드와 관련하여 반복자 클래스는 반복자 개체로 iterator<T>와 삽입할 항목으로 constT&를 포함하여 두 개의 인수를 허용/취합니다. 새로 삽입된 노드에 대한 결과로 반복자를 반환합니다.
결과적으로 새 이중 연결 목록 노드가 생성되며 반복자 클래스가 항목을 생성하고 반복자가 삽입하기 전에 연결 목록에 성공적으로 삽입할 수 있기 때문에 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
반복자는 연결된 목록 클래스의 데이터를 조작할 수 있으므로 연결 목록에서 삭제, 업데이트 또는 생성하려는 노드를 가리킵니다. 반복자 클래스의 삽입 및 지우기로 이 문제를 해결할 수 있지만 이 솔루션은 또 다른 문제를 야기합니다.
문제는 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