书上已经讲得很清楚了,这里给出一个编译通过的例子。
3mylist.h
// file: 3mylist.h
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
template <typename T>
class ListItem
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
public:
ListItem(T value, ListItem<T>* next)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
_value = value;
_next = next;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
T value() const
{ return _value; }
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
void value(T value)
{ _value = value; }
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
ListItem* next() const
{ return _next; }
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
void next(ListItem* next)
{ _next = next; }
//![](http://www.cppblog.com/Images/dot.gif)
private:
T _value;
ListItem* _next; // †ÎÏò´®ÁУ¨single linked list£©
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
template <typename T>
class List
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
public:
~List()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(_front == _end) return;
ListItem<T>* item = _front;
while(item != _end)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
ListItem<T>* iter = item;
item = item->next();
delete iter;
}
}
void insert_front(T value)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
_front = new ListItem<T>(value, _front);
}
void insert_end(T value)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(_front == _end)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
_front = new ListItem<T>(value, _front);
}
ListItem<T>* item = _front;
while(item->next() != _end)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
item = item->next();
}
item->next(new ListItem<T>(value, _end));
}
void display(std::ostream &os = std::cout) const
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
ListItem<T>* item = _front;
while(item != _end)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
os<<item->value()<<" ";
item = item->next();
}
os<<endl;
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
ListItem<T>* front()
{ return _front;}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
ListItem<T>* end()
{ return _end;}
// ![](http://www.cppblog.com/Images/dot.gif)
private:
ListItem<T>* _end;
ListItem<T>* _front;
long _size;
};![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
3mylist-iter.h
// file : 3mylist-iter.h
#include "3mylist.h"
template <class Item> // Item可以是单向列表节点或双向列表节点。
struct ListIter // 此处这个迭代器特定只为列表服务,因为其
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{ // 独特的 operator++之故。
Item* ptr; // 保持与容器之间的一个联系
ListIter(Item* p = 0) // default ctor
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
: ptr(p)
{ }
// 不必实作 copy ctor,因为编译器提供的预设行为已足够。
// 不必实作 operator=,因为编译器提供的预设行为已足够。
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
Item& operator*() const
{ return *ptr; }
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
Item* operator->() const
{ return ptr; }
// 以下两个operator++遵循标准作法,参见[Meyers96]条款6
// (1) pre-increment operator
ListIter& operator++()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{ ptr = ptr->next(); return *this; }
// (2) post-increment operator
ListIter operator++(int)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{ ListIter tmp = *this; ++*this; return tmp; }
bool operator==(const ListIter& i) const
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{ return ptr == i.ptr; }
bool operator!=(const ListIter& i) const
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{ return ptr != i.ptr; }
};
3mylist-iter.cpp
// file : 3mylist-iter.cpp
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include "stdafx.h"
#include "3mylist-iter.h"
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
// 摘自 SGI <stl_algo.h>
template <class InputIterator, class T>
InputIterator find(InputIterator first,
InputIterator last,
const T& value)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
while (first != last && (*first).value() != value)
++first;
return first;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
// 3mylist-iter-test.cpp
void main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
List<int> mylist;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=0; i<5; ++i)
{
mylist.insert_front(i);
mylist.insert_end(i+2);
}
mylist.display(); // 10 ( 4 3 2 1 0 2 3 4 5 6 )
ListIter<ListItem<int> > begin(mylist.front());
ListIter<ListItem<int> > end(mylist.end()); // default 0, null
ListIter<ListItem<int> > iter; // default 0, null
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
// 执行结果:found. 3
iter = find(begin, end, 3);
if (iter == end)
cout << "not found" << endl;
else
cout << "found. " << iter->value() << endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
// 执行结果:not found
iter = find(begin, end, 7);
if (iter == end)
cout << "not found" << endl;
else
cout << "found. " << iter->value() << endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return;
}![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)