1 iterator

`作用: 联系 container 和 algorithm`

`用法: 以 find() 为例`

// SGI : find
template <class InputIter, class T>
InputIter 
find(InputIter first,
     InputIter last,
     const T& value) // arg 可为 rvalue
{
    while(first != last && *first != value)
        ++first;
    return first;
}

// vs
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

int main()
{
    const int Size = 3;
    int a[Size] = { 0, 1, 2 };

    // (1) container: 可用 [ptr1, ptr2) 初始化
    std::vector<int> vec(a, a + Size);
    std::list<int> lst(a, a + Size);

    // (2) iterator & algorithm: slgorithm 输入通常是 [iter1, iter2)
    std::vector<int>::iterator iter1 
        = find(vec.begin(), vec.end(), 1);
    if (iter1 == vec.end())
        std::cout << "not fount" << std::endl;
    else
        std::cout << "found:" << *iter1 << std::endl;

    std::list<int>::iterator 
        iter2 = find(lst.begin(), lst.end(), 1);
    if (iter2 == lst.end())
        std::cout << "not fount" << std::endl;
    else
        std::cout << "found:" << *iter2 << std::endl;
}

2 iterator 设计

1. STL 设计思维

对 containers and algorithms: (1) separate + 独立设计 (2) 用 iterator connect

2. container / algorithm 泛型化

container 泛型化: class templates

algorithm 泛型化: function templates

3. iterator 设计

iterator 是一种 smart pointer, 其核心在于 对 解引用 operator*() / 成员访问 operator->() / 移动 operator++/--() 进行重载

3 design a simple container(单向链表) 及其 iterator

参考 STL std::list 设计思路

#include <iostream>
#include <algorithm>

//--- 1. global func: construct/destory/allocate/deallocate
template <class T1, class T2>
void construct(T1* p, const T2& value)
{
    new(p) T1(value); // placement new: call  T1::T1(value)
}

template <class T>
void destory(T* p)
{
    p->~T();         // call dtor 
}

void* allocate(int n)
{
    void* mem = malloc(n);
    return mem;
}

void deallocate(void* p)
{
    free(p);
}

//--- 2. node + iterator + 容器( list )
template <typename T>
struct Node
{
    T data;
    Node<T>* next; // 单链表
};

template <class T>
struct listIter
    : public std::iterator<std::forward_iterator_tag, T>
{
    typedef listIter<T> self;
    typedef Node<T>* link_type;

    // mem data: pnode
    link_type pnode;

    // (1) ctor
    listIter() : pnode(NULL) { }
    listIter(const link_type x) : pnode(x) { }

    // copy ctor
    listIter(const self& x) : pnode(x.pnode) { }

    // operator= default is enough

    // (2) list_iterator 要知道 list 的 node 结构
    T& operator*() const { return (*pnode).data; }
    T* operator->() const { return &(operator*()); }

    // (3) iterator ++ : 实际是 迭代器 internal pointer ++
    self operator++()   // prefix
    {
        pnode = (link_type)(pnode->next);
        return *this;
    }
    self operator++(int) // postfix
    {
        self tmp(pnode);
        ++* this;
        return tmp;
    }

    // (4) == !=
    bool operator==(const self& x) const
    {
        return pnode == x.pnode;
    }
    bool operator!=(const self& x) const
    {
        return pnode != x.pnode;
    }
};

template <typename T>
class list
{
public: 
    typedef Node<T>*    link_type;
    typedef listIter<T> iterator;
protected:
    // mem data: a pointer to head node
    link_type head;

public:
    //(1) ctor: create empty list: 只 头结点（ data 域无效）
    //    => 带头结点的单链表
    list()
    {
        head = (link_type)allocate( sizeof(Node<T>) );
        head->next = NULL;
    }

    // (2) dtor 销毁(析构 + 释放) list
    ~list()
    {
        link_type p = head;
        while (p) // p!= NULL
        {
            link_type tmp = p;
            p = p->next;

            destory(tmp);
            deallocate(tmp);
        }
    }

    // (3) 创建(分配 + 构造) a node， return its pointer
    link_type 
    create_node(const T& x)
    {
        link_type p = (link_type)allocate(sizeof(Node<T>));
        construct(&p->data, x);
        return p;
    }

    // (4) 头插法
    void 
    insert_front(const T& x)
    {
        link_type p = create_node(x);
        p->next = head->next;
        head->next = p;
    }
    // (5) 取 head pointer
    link_type 
    get_head()
    {
        return head;
    }

    // (6) print_list
    void print_list()
    {
        link_type p = head->next;
        std::cout << "list is :" << std::endl;
        while (p)
        {
            std::cout << p->data << std::endl;
            p = p->next;
        }
    }
};

int main()
{
    list<int> lst;
    for (int i = 0; i < 3; i++)
    {
        lst.insert_front(i);
    }
    lst.print_list();

    list<int>::iterator iter(lst.get_head());
    list<int>::iterator end; 

    iter = find(iter, end, 1);
    if (iter == end)
        std::cout << "not fount" << std::endl;
    else
        std::cout << "found:" << *iter << std::endl;
}