Shulou(Shulou.com)06/02 Report--

How to analyze C++ 's STL iterator principle and implementation, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain in detail for you, people with this need can come to learn, I hope you can get something.

1. Brief introduction of iterator

In order to improve the efficiency of C++ programming, many containers are provided in STL (Standard Template Library), including vector, list, map, set and so on. However, some containers (vector) can access the data in the container by subscript index, but most containers (list, map, set) cannot access the elements in the container in this way. In order to unify the access method when accessing different containers, STL designs an embedded iterator class for each container. Different containers have their own iterators (the exclusive iterator is responsible for implementing the specific details of the corresponding container access elements), and use iterators to access the data in the container. In addition, you can combine containers with general algorithms through iterators, and as long as you give different iterators to the algorithm, you can perform the same operation on different containers, such as find lookup functions (because iterators provide uniform access, which is the benefit of using iterators). The iterator overloads some basic operations such as *,->, +, =,!, and =, giving it the ability to traverse complex data structures, depending on the container being traversed, and the use of all iterators is very similar to the use of pointers. Get the header and tail iterators of the container through the begin,end function. The end iterator is not included in the container. When the iterators returned by begin and end are the same, the container is empty.

STL is mainly composed of container, iterator, algorithm, function object, and memory allocator.

two。 Implementation principle of iterator

First, take a look at the implementation of iterators in STL:

As you can see from the figure above, STL achieves external unification through type aliases; the real iterator types of type aliases are different in different containers, and the real iterator types are different for basic operations such as +,--, *,->, and so on. (PS: the iterator is a good illustration of the separation of interface and implementation.)

Now that we know how to implement an iterator, how do we design a simple iterator for a list container?

The 1.list class requires methods to manipulate iterators

1.begin/end

2.insert/erase/emplace

The 2.list class has an inner class list_iterator

1. There is a member variable ptr that points to an element in the list container

2.iterator is responsible for overloading + +,--, *,-> and other basic operations.

The 3.list class defines the type alias of the inner class list_iterator

These are the details you need to consider to implement a simple iterator for a list container.

3. Simple implementation of iterator

My_list.h (important parts are annotated)

/ Created by wengle on 2020-03-14 public / # ifndef CPP_PRIMER_MY_LIST_H#define CPP_PRIMER_MY_LIST_H# include templateclass node {public: T value; node * next; node (): next (nullptr) {} node (T val, node * p = nullptr): value (val), next (p) {}; templateclass my_list {private: node * head; node * tail; int size Private: class list_iterator {private: node * ptr / / pointer to an element in the list container public: list_iterator (node * p = nullptr): ptr (p) {} / / overload + +,--, *,-> and other basic operations / / return references. It is convenient to modify the object T & operator* () const {return ptr- > value through * it. } node * operator- > () const {return ptr;} list_iterator & operator++ () {ptr = ptr- > next; return * this;} list_iterator operator++ (int) {node * tmp = ptr / / this is a constant pointer to list_iterator, so * this is the list_iterator object, and the front + + has been overloaded + (* this); return list_iterator (tmp);} bool operator== (const list_iterator & t) const {return t.ptr = = this- > ptr } bool operators = (const list_iterator & t) const {return t.ptr! = this- > ptr;}}; public: typedef list_iterator iterator; / / type alias my_list () {head = nullptr; tail = nullptr; size = 0 Insert elements void push_back (const T & value) {if (head = = nullptr) {head = new node (value); tail = head;} else {tail- > next = new node (value) from the end of the linked list; tail = tail- > next;} size++ } / / print linked list element void print (std::ostream & os = std::cout) const {for (node * ptr = head; ptr! = tail- > next; ptr = ptr- > next) os value next);} / / other member functions insert/erase/emplace}; # endif / / CPP_PRIMER_MY_LIST_H

Test.cpp

/ Created by wengle on 2020-03-14.//#include # include "my_list.h" struct student {std::string name; int age; student (std::string n, int a): name (n), age (a) {} / / overload the output operator friend std::ostream & operator

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.