この記事は、標準ライブラリの学習を開始する初心者にのみ興味深いものであり、専門家はここで新しいものを見つけることはできません。
さあ、始めましょう。 標準ライブラリのリストとは何ですか？ これは、要素の挿入と削除に最適化された順次コンテナです。 このコンテナを操作するために、 STLは双方向イテレータを使用します。これを実装しようとします。 また、リストの最初と最後にinsert関数を実装し、 iteratorが指す要素の後に挿入し、要素といくつかの関数を削除します。
そして今、コメント付きのコードがたくさんあります。
ファイル「dlist.h」
#ifndef DLIST_H_ #define DLIST_H_ #include <iostream> template <typename T> class Double_list { public: class iterator; friend class iterator; // Double_list private: class Double_node; friend class Double_node; class Double_node // { public: friend class Double_list<T>; friend class iterator; // T Double_node(T node_val): val(node_val) {} Double_node() {} ~Double_node() {} void print_val() {std::cout << val << " "; } Double_node *next; // Double_node *prev; // . T val; //. }; public: class iterator { friend class Double_list<T>; public: // iterator() :the_node(0) {} // Double_node iterator(Double_node *dn): the_node(dn) {} // iterator(const iterator &it): the_node(it.the_node) {} iterator& operator=(const iterator &it) { the_node = it.the_node; return *this; } // == , // bool operator == (const iterator &it) const { return (the_node == it.the_node); } bool operator!=(const iterator &it) const { return !(it == *this); } // . iterator& operator++() { if (the_node == 0) throw "incremented an empty iterator"; if (the_node->next == 0) throw "tried to increment too far past the end"; the_node = the_node->next; return *this; } // і . iterator & operator--() { if (the_node == 0) throw "decremented an empty iterator"; if (the_node->prev == 0) throw "tried to decrement past the beginning"; the_node = the_node->prev; return *this; } // . T& operator*() const { if (the_node == 0) throw "tried to dereference an empty iterator"; return the_node->val; } private: Double_node *the_node; }; private: Double_node *head; // . Double_node *tail; // , iterator head_iterator; //, iterator tail_iterator; //, , . public: Double_list() { head = tail = new Double_node; tail->next = nullptr; tail->prev = nullptr; // head_iterator = iterator(head); tail_iterator = iterator(tail); } // , . Double_list(T node_val) { head = tail = new Double_node; tail->next = nullptr; tail->prev = 0; head_iterator = iterator(head); tail_iterator = iterator(tail); add_front(node_val); } ~Double_list() { Double_node *node_to_delete = head; for (Double_node *sn = head; sn != tail;) { sn = sn->next; delete node_to_delete; node_to_delete = sn; } delete node_to_delete; } bool is_empty() {return head == tail;} iterator front() {return head_iterator;} iterator rear() {return tail_iterator;} // void add_front(T node_val) { Double_node *node_to_add = new Double_node (node_val); node_to_add->next = head; node_to_add->prev = nullptr; head->prev = node_to_add; head = node_to_add; // head , head_iterator head_iterator= iterator(head); } // void add_rear(T node_val) { if (is_empty()) add_front(node_val); else { Double_node *node_to_add = new Double_node(node_val); node_to_add->next = tail; node_to_add->prev = tail->prev; tail->prev->next = node_to_add; tail->prev = node_to_add; // tail_iterator tail_iterator = iterator(tail); } } // node_val key_i bool insert_after(T node_val, const iterator &key_i) { for (Double_node *dn = head; dn != tail; dn = dn->next) { // if (dn == key_i.the_node) { Double_node *node_to_add = new Double_node(node_val); node_to_add->prev = dn; node_to_add->next = dn->next; dn->next->prev = node_to_add; dn->next = node_to_add; return true; } } return false; } // . T remove_front() { if (is_empty()) throw "tried to remove from an empty list"; Double_node *node_to_remove = head; T return_val = node_to_remove->val; head = node_to_remove->next; head->prev = 0; head_iterator = iterator(head); delete node_to_remove; return return_val; } T remove_rear() { if (is_empty()) throw "tried to remove from an empty list"; Double_node *node_to_remove = tail->prev; if(node_to_remove->prev == 0) { return remove_front(); } else { T return_val = node_to_remove->val; node_to_remove->prev->next = tail; tail->prev = node_to_remove->prev; delete node_to_remove; return return_val; } } bool remove_it(iterator &key_i) { for (Double_node *dn = head; dn != tail; dn = dn-next) { // if (dn == key+i.the_node) { dn->prev->next = dn->next; dn->next->prev = dn->prev; delete dn; key_i.the_node =0; return true; } } return false; } // , node_val iterator find(T node_val) const { for (double_node *dn = head; dn != tail; dn = dn->next) { if (dn->val == node_val) return iterator(dn); } // node_val tail_iterator return tail_iterator; } // , n- iterator get_nth(const int element_num) const { if (element_num < 1) return tail_iterator; int count = 1; for(Double_node *dn = head; dn != tail; dn = dn->next) { if (count++ == element_num) return iterator(dn); } return tail_iterator; } // . int size() const { int count = 0; for (Double_node *dn = head; dn != tail; dn = dn->next) ++count; return count; } void print() const { for (Double_node *dn = head; dn!= tail; dn = dn->next) { dn->print_val(); } std::cout << std::endl; } }; #endif
リストの使用
#include "dlist.h" int main() { Double_list<int> the_list; Double_list<int>::iterator list_iter; for (int i=0; i<5; ++i) { the_list.add_front(i); } the_list.print(); the_list.remove_front(); for (list_iter = the_list.front(); list_iter != the_list.rear(); ++ list_iter) { std::cout << *list_iter << " "; } std::cout << std:: endl; // for (list_iter = the_list.rear(); list_iter != the_list.front();) { --list_iter; std::cout << *list_iter << " "; } std::cout << std::endl; system("PAUSE"); return 0; }
コード分析
イテレーターは、ネストされたオープンクラスとして実装されます。 クラスが開いているため、ユーザーはオブジェクトを作成できます。 イテレータクラスはDouble_listクラスのプライベート要素のいくつかを知る必要があるため、 Double_listクラスに適したイテレータクラスを宣言し、 イテレータクラスで別のDouble_listクラスを宣言します 。
次に、 Double_list :: iteratorクラスの内部デバイスを見てみましょう。 単一のデータ項目Double_node * the_nodeがあります。 これは、イテレータが非表示にする必要があるものです。 反復子クラスで宣言された操作により、ユーザーはこのノードを特定の方法で操作できます。
終わり
そしてそれだけです。 これが、STLライブラリのリストクラスの実装方法です。 もちろん、私たちのクラスは非常に一般的な例であり、STLではすべてがより複雑ですが、一般的な原則はこのコードから理解できます。