Take a look at iterators in the C++ standard library today.

What is the use of iterators?

As we know, the STL library has six parts: allocator, container, iterator, algorithm, functor, and adapter. Iterators are used to “join” algorithms, replicators and containers. In addition, in design mode, there is a pattern called the iterator pattern, is simply to provide a kind of method, without exposing the internal representation of a container, make it can access each element in the container in order, this kind of design thinking has been widely used in the STL, is the key to STL, through the iterators, Containers and algorithms can be glued together organically, and the same operation can be performed on different containers as long as different iterators are given to the algorithm. (reference: blog.csdn.net/shudou/arti… Find, for example, shows how containers, algorithms, and iterators can work together:

template<typename InputIterator, typename T>
InputIterator find(InputIterator first, InputIterator last, const T &value)
{
    while(first ! = last && *frist ! = value) ++first;return first;
}
Copy the code

The find function above, passing the iterator of the container, can implement the same algorithm for different containers. This is a generic programming idea.

Iterator implementation for different containers

vector

Let’s look at an implementation of iterator in a vector:

 template<typename T,class Alloc = alloc >
    class vector
    { 
 public:
      typedef T    value_type;
      typedefvalue_type* iterator; ......};Copy the code

We can see here that the iterator in the vector is simply defined as a pointer to the type parameter T we passed in.

List

Here’s a simple List iterator implemented by a blogger for you to use: @wengle

#ifndef CPP_PRIMER_MY_LIST_H
#define CPP_PRIMER_MY_LIST_H
#include <iostream>
template<typename T>
class node {
public:
    T value;
    node *next;
    node() : next(nullptr) {}
    node(T val, node *p = nullptr) : value(val), next(p) {}
};

template<typename T>
class my_list {
private:
    node<T> *head;
    node<T> *tail;
    int size;

private:
    class list_iterator {
    private:
        node<T> *ptr; // A pointer to an element in the list

    public:
        list_iterator(node<T> *p = nullptr) : ptr(p) {}
        
        // Override basic operations such as ++, --, *, and ->
        // Return a reference to make it easier to modify the object with *it
        T &operator* ()const {
            return ptr->value;
        }

        node<T> *operator- > ()const {
            return ptr;
        }

        list_iterator &operator++() {
            ptr = ptr->next;
            return *this;
        }

        list_iterator operator+ + (int) {
            node<T> *tmp = ptr;
            // this is a constant pointer to list_iterator, so *this is list_iterator. The prefix ++ has been overridden+ + (*this);
            return list_iterator(tmp);
        }

        bool operator= = (const list_iterator &t) const {
            return t.ptr == this->ptr;
        }

        bool operator! = (const list_iterator &t) const {
            returnt.ptr ! =this->ptr; }};public:
    typedef list_iterator iterator; // Type alias
    my_list() {
        head = nullptr;
        tail = nullptr;
        size = 0;
    }

    // Insert elements from the end of the list
    void push_back(const T &value) {
        if (head == nullptr) {
            head = new node<T>(value);
            tail = head;
        } else {
            tail->next = new node<T>(value);
            tail = tail->next;
        }
        size++;
    }

    // Prints list elements
    void print(std::ostream &os = std::cout) const {
        for(node<T> *ptr = head; ptr ! = tail->next; ptr = ptr->next) os << ptr->value << std::endl; }public:
    // A method to manipulate iterators
    // Return the list header pointer
    iterator begin(a) const {
        return list_iterator(head);
    }

    // Return the list tail pointer
    iterator end(a) const {
        return list_iterator(tail->next);
    }

    Other member functions insert/erase/emplace
};

#endif //CPP_PRIMER_MY_LIST_H
Copy the code

For other container iterator analysis, skip it for now.

Iterator classification

In the STL, iterators are divided into five categories, in addition to native Pointers:Input IteratorAs the name implies, input — this iteratorThe object indicated is not allowed to be modified, that is, read-only. Support ==! =, ++, *, and ->.Output IteratorAllows algorithms to operate on the interval formed by such iteratorsWrite only operation. Operations such as ++ and * are supported.Forward IteratorAllow algorithms in this iteratorThe interval formed for reading and writing operations.But only in one direction, one step at a time. Supports all operations on Input Iterator and Output Iterator.Bidirectional IteratorAllow the algorithmThe interval formed by this iterator can be read and written, and can be moved bidirectionallyYou can only move one step at a time. All operations on the Forward Iterator are supported, plus — operations.Random Access IteratorContains all operations on Pointers,Random access (supported by vector), moving the specified number of steps at will. supportAll operations of the first four iteratorsIn addition, it + N, it-N, IT += N, IT -= N, IT1-IT2, and IT [n] are supported. The classification and connection of the above five iterators can be seen in the following figure:Knowing the types of iterators, we can explain the difference between a vector iterator and a list iterator.It is obvious that the iterator of a vector has all the pointer arithmetic capabilitiesList is a bidirectional linked list, so there are only bidirectional reads and writes but no random access to elements. Vector iterators are Random Access iterators and list iterators are Bidirectional iterators. ** we can use the traits programming trick to extract iterator types based on the iterator types, and then use C++ ‘s overloading mechanism to process iterators differently for different types.To do this, we must define the typepedef STD ::forward_iterator_tag iterator_category for each iterator; In fact, you can inherit the iterator template defined in the STL. The last three parameters of the template have default values. Therefore, you only need to specify the first two parameters during inheritance. As shown below, STL defines five empty types as labels for iterators:

template<class Category.class T.class distance = ptrdiff_t.class Pointer=T*,class Reference=T&>
class iterator{
    typedef Category iterator_category;
    typedef T        value_type;
    typedef Distance difference_type;
    typedef Pointer  pointer;
    typedef Reference reference;
};

struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag:public input_iterator_tag{};
struct bidirectional_iterator_tag:public forward_iterator_tag{};
struct random_access_iterator_tag:public bidirectional_iterator_tag{};
Copy the code

Iterator invalidation?

Using a container’s insert or erase functions to insert, delete, or modify elements (such as a map or set, because the underlying element is a red-black tree) through iterators “may” invalidate the iterator, so to avoid the danger, it is necessary to retrieve the new valid iterator and perform the correct operation. plus

Vector 1. After push_back is inserted, the iterator returned by end is invalidated. If capacity is changed after push_back, then the entire container needs to be reloaded. The iterators returned by first and end are invalid. When erase (pop_back) is performed, iterators pointing to the erase point are invalidated. Iterators to elements after the deletion point are also invalidated.

List 1, insert, and splice do not invalidate the original list iterator. This is not true in a vector, because insertion in a vector might cause a new configuration of memory, invalidating all iterators. Erase only the iterator that refers to the element being deleted is invalid. (List has only found this kind of failure so far)

Associative containers Removing the current iterator from an associative container (map, set,multimap,multiset) simply invalidates the current iterator by incrementing the current iterator as we erase it. This is because the map container, such as using the red-black tree, insert, delete a node will not affect other nodes (although delete an element, the tree will be adjusted, in order to conform to the red-black tree or specification of binary tree, but a single node in memory address did not change, change is the point to the relationship between each node). Erase (iterator ++) : iterator (iterator +) : iterator (iterator +) : iterator (iterator +) : iterator (iterator +) : iterator (iterator +) : iterator (iterator +) : iterator (iterator +) : iterator (iterator +) : iterator (iterator +) : iterator (iterator +) : iterator (iterator +) : iterator (iterator +) We then erase the iterator, so iter was incremented before it expired) **.