STL 源码剖析 3.2 节中的 iterator 例子

Posted on | Comments:

在看《STL 源码剖析》这本书第 3.2 节 iterator 的时候，想要尝试实现一下书中的 list 例子。遇到了一点小问题。

我用的编译器是 clang 7.0, 没有完全按照书中的写法，用了一些 C++11 的语法。但是在 编译时遇到了错误，源码如下：

mylist.h: 

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
#include <iostream>
#include <iterator>

template <typename T>
class ListItem;

template <typename T>
class List {
public:
    List() : _front(nullptr), _end(nullptr), _size(0) {}
    void insert_front(T value) {
	auto new_front = new ListItem<T>(value);
	new_front->_next = _front;
	_front = new_front;
	if (!_end)
	    _end = new_front;
	++_size;
    }
    void insert_end(T value) {
	auto new_end = new ListItem<T>(value);
	if (_end) {
	    _end->_next = new_end;
	    _end = new_end;
	}
	else
	    _end = new_end;
	if (!_front)
	    _front = new_end;
	++_size;
    }
    ListItem<T>* front() { return _front; }
    void display(std::ostream& os = std::cout) const {
	os << _size << " : {";
	auto i = _front;
	for (; i != _end; i = i->next())
	    os << ' ' << i->value();
	os << ' ' << i->value() << " }\n";
    }

private:
    ListItem<T>* _front;
    ListItem<T>* _end;
    long         _size;
};

template <typename T>
class ListItem {
public:
    ListItem(T value) : _value(value) {}
    T value() const { return _value; }
    ListItem* next() const { return _next; }

private:
    T _value;
    ListItem* _next;

    friend class List<T>;
};

template <class Item>
struct ListIter {
    // typedef std::forward_iterator_tag iterator_category;
    Item* ptr;

    ListIter(Item* p = nullptr) : ptr(p) {}

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

    ListIter& operator++() { ptr = ptr->next(); return *this;}
    ListIter  operator++(int) { auto tmp = *this; ++*this; return tmp; }

    bool operator==(const ListIter& i) const { return ptr == i.ptr; }
    bool operator!=(const ListIter& i) const { return ptr != i.ptr; }
};

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

mylist-test.cc: 

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
#include "mylist.h"
#include <algorithm>

int main(int argc, char *argv[])
{
    List<int> mylist;
    for (int i = 0; i < 5; ++i) {
	mylist.insert_front(i);
	mylist.insert_end(i+2);
    }
    mylist.display();

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

    iter = std::find(begin, end, 3);
    if (iter == end)
	std::cout << "not found\n";
    else
	std::cout << "found " << iter->value() << '\n';

    iter = std::find(begin, end, 7);
    if (iter == end)
	std::cout << "not found\n";
    else
	std::cout << "found " << iter->value() << '\n';

    return 0;
}

编译用的命令为： 

1
clang++ mylist-test.cc -std=c++11

得到了如下的错误提示： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
In file included from mylist-test.cc:2:
In file included from /usr/lib/gcc/x86_64-linux-gnu/8.0.1/../../../../include/c++/8.0.1/algorithm:62:
/usr/lib/gcc/x86_64-linux-gnu/8.0.1/../../../../include/c++/8.0.1/bits/stl_algo.h:162:10: error: no
      matching function for call to '__iterator_category'
		       std::__iterator_category(__first));
		       ^~~~~~~~~~~~~~~~~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/8.0.1/../../../../include/c++/8.0.1/bits/stl_algo.h:3905:19: note: in
      instantiation of function template specialization 'std::__find_if<ListIter<ListItem<int> >,
      __gnu_cxx::__ops::_Iter_equals_val<const int> >' requested here
      return std::__find_if(__first, __last,
		  ^
mylist-test.cc:17:17: note: in instantiation of function template specialization
      'std::find<ListIter<ListItem<int> >, int>' requested here
    iter = std::find(begin, end, 3);
		^
/usr/lib/gcc/x86_64-linux-gnu/8.0.1/../../../../include/c++/8.0.1/bits/stl_iterator_base_types.h:205:5: note: 
      candidate template ignored: substitution failure [with _Iter = ListIter<ListItem<int> >]: no type
      named 'iterator_category' in 'std::iterator_traits<ListIter<ListItem<int> > >'
    __iterator_category(const _Iter&)
    ^
1 error generated.

开始我以为是这个实现没有遵循 C++ 标准中 iterator 的规范，少了一些 typedef 之类的 定义，于是我在 ListIter 加了一行： 

1
typedef std::forward_iterator_tag iterator_category;

重新编译时发现错误提示并没有什么变化，我以为定义了这个类型就会提示其他错误，想之 后再根据提示修改的。但是错误提示没有变化说明可能不是这个错误原因。然后换了 g++ 重新编译还是同样的错误信息。

最后突然想到 clang 默认是使用 libstdc++ 的，g++ 也是，换成 libc++ 不知道会不会给 出更显示的错误提示，于是改为链接 libc++： 

1
clang++ mylist-test.cc -std=c++11 -stdlib=libc++

结果直接编译成功了。其中的原因还不清楚。

2018-08-27:

g++ 编译不通过的原因应该是 ListIter 没有定义五种相应的类型，即1

Member type Definition
iterator_category Category
value_type T
difference_type Distance
pointer Pointer
reference Reference

书中 3.5 节给出了正确的方法，即从 std::iterator 继承： 

1
2
3
4
5
6
template <class Item>
struct ListIter :
    public std::iterator<std::forward_iterator_tag, Item>
{
    //...
}

我自己尝试在类中手工定义一下这几个类型，也可以使 g++ 通过编译。

clang++ 在不定义这几个类型时也能编译通过的原因还是不清楚。。。

Last Updated 2018-09-04 Tue 00:08.
Render by hexo-renderer-org with Emacs 25.2.2 (Org mode 9.1.13)
0%