Cybay
0%

List Iterator

发表于 更新于 分类于 Valine：
设计链表迭代器

链表定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//file : list.h
#ifndef __MYLIST__
#define __MYLIST__
#include<iostream>

template <typename T>
class ListItem
{
public:
    T value() const {return m_val;}
    ListItem* fnext() const {return _next;}
    void setVal(T val) {m_val = val;}
    void setNext(ListItem* next) {_next = next;}
    ListItem() : m_val(0), _next(nullptr) {}
    ListItem(int val) : m_val(val), _next(nullptr) {}
private:
    T m_val;
    ListItem *_next;
};


template <typename T>
class List
{
public:
    void insert_front(T val);
    void insert_end(T val);
    void display(std::ostream &os = std::cout);
    ListItem<T>* front() const {return _front;}

private:
    ListItem<T>* _front;
    ListItem<T>* _end;
    int _size;
public:
    List() : _front(nullptr), _end(nullptr), _size(0) {}
};


template <typename T>
void List<T>::insert_front(T val)
{
    auto newNode = new ListItem<T>(val);
    if(this->_front == nullptr)
        _front = _end = newNode;
    else
    {
        newNode->setNext(this->_front);
        this->_front = newNode;
    }
    ++this->_size;
}

template <typename T>
void List<T>::insert_end(T val)
{
    auto newNode = new ListItem<T>(val);
    if(this->_end == nullptr)
        _front = _end = newNode;
    else
    {
        this->_end->setNext(newNode);
        this->_end = newNode;
    }
    ++this->_size;
}

template <typename T>
void List<T>::display(std::ostream &os)
{
    os<<"size = "<<this->_size<<"; ";
    auto p = this->_front;
    while(p)
    {
        os<<p->value()<<" ";
        p = p->fnext();
    }
    os<<std::endl;
}

template<typename T>
bool operator!=(const ListItem<T>& item, T n)
{return item.value() != n;}

#endif

链表迭代器实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//file : list_iterator.h
#ifndef __ITER__
#define __ITER__

#include "list.h"
template <class Item>
class ListIter: public std::iterator<std::forward_iterator_tag, Item>//继承标准iterator class
{
public:
    Item* ptr;
    ListIter(Item* p = nullptr) : ptr(p) {}

    //copy ctor & operator= = defalut
    ListIter(const ListIter&) = default;
    ListIter& operator=(const ListIter&) = default;

    Item& operator*() const {return *ptr;}
    Item* operator->() const {return ptr;}

    //pre-increment operator
    ListIter& operator++()
        {ptr = ptr->fnext(); return *this;}
    //post-increment operator
    ListIter& operator++(int)
        {auto tmp = *this; ++*this; return tmp;}
    
    bool operator==(const ListIter& l) const
        {return ptr == l.ptr;}
    bool operator!=(const ListIter& l) const
        {return ptr != l.ptr;}
};

//find函数
template <class InputIterator, class T>
InputIterator find(InputIterator first, 
    InputIterator last, const T& val)
{
    while(first != last && *first != val)
        ++first;
    return first;
}

#endif

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//file : main.cpp

#include "list_iterator.h"
int main()
{
    List<int> list;
    for(int i = 0; i < 5; ++i)
    {
        list.insert_front(i);
        list.insert_end(i + 2);
    }
    list.display();

    ListIter<ListItem<int>> begin(list.front());
    ListIter<ListItem<int>> end;
    ListIter<ListItem<int>> iter;

    iter = find(begin, end, 3);
    if(iter == end) printf("Not found\n");
    else printf("found 3\n");

    iter = find(begin, end, 7);
    if(iter == end) printf("Not found\n");
    else printf("found 7\n");

    return 0;
}