STL for newbies. Implementing a container class

Hi Habr, probably everyone who studies C ++ wants to figure out how the container classes from the standard library work and how they are implemented. As for me, in order to better master something similar to containers, then you need to try to implement one of the containers yourself. In this article I want to show you at least about how the container classes are implemented using the example list. I want to say at once that this will not copy all the functionality, but only the concept of the container will be shown, namely, we will implement the list class and the iterator class to work with it.

The article will be interesting only for beginners who are starting to study the standard library, professionals will not find anything new here.

Well, let's start. What is the list from the standard library? This is a sequential container that is optimized for inserting and deleting items. STL uses a bidirectional iterator to work with this container, which we will try to implement. We also implement the insert function at the beginning and at the end of the list, the insertion after the element pointed to by the iterator , the deletion of elements and a few more functions.

And now there will be a lot of code with comments.
file "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 

')
Using the list

 #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; } 

Code analysis

The iterator is implemented as an open nested class. Since the class is open, users can create objects. The class iterator needs to know about some of the private elements of the Double_list class, so we declare the class iterator class-friendly Double_list and also declare the class Double_list in the class iterator .

Now let's take a look at the internal structure of the Double_list :: iterator class. It has a single data item: Double_node * the_node . This is what the iterator should hide. The operations declared in the class iterator allow users to manipulate this node in a particular way.

the end

And that's it. This is how the list class is implemented in the STL library. Of course, our class is a very general example; in STL, everything is more complicated, but the general principle can be understood from this code.