在模版和泛型算法中我们实现了一个查找算法：
template <class T, class Iter>
Iter find(Iter start, Iter end, const T& x)
{
Iter p = start;
while( p != end && *p != x) {
p++;
}
return p;
}
可以帮助我们查找任意的线性结构，我们将start和end当作输入迭代器使用。
如果我们想要实现查找某个元素最后一次出现的地方呢？
如果我们仍然使用输入迭代器：
template <class T, class Iter>
Iter find(Iter start, Iter end, const T& x)
{
Iter result = end; // 如果找不到返回end
while (start != end) {
if (*start == x) {
result = start; // 找到最后一个相等的
}
start++;
}
return result;
}
这个算法跟我们现有的find算法差异很大，主要是因为我们需要保存end以便在没有找到的场景下返回这个值。而且，几乎可以肯定的是我们总要遍历完整个序列才行。
如果我们假设Iter是一个双向迭代器呢？这样我们就可以使用operator--进行操作，可以从尾部开始遍历了。
template <class T, class Iter>
Iter find(Iter start, Iter end, const T& x)
{
if (start != end) {
Iter p = end;
do {
if (*(--p) == x) {
return p;
}
} while (p != start);
}
return end;
}
因为end表示指向序列的最后一个元素的下一个位置，所以需要使用do-while的方式操作。这个算法同样跟我们已经实现的find算法差异过大。说明了一个事实：使用迭代器的算法具有不对称性，不对称性的来源就在于end的问题。
因为我们无法说头部指针的前一个位置的值是有效的，c++只保证了最后一个元素的下一个位置有效，但是对于头部没有保证。即：
int a[10];
*(a+10); // 合法
*(a+11); // 非法
*(a-1); // 非法
如果我们修改我们的算法思路：反向查找的时候，如果找不到则返回第一个元素的位置，找到了则返回该元素的下一个元素的迭代器。这样我们看看会发生什么。
template <class T, class Iter>
Iter rnfind(Iter start, Iter end, const T& x)
{
while( start != end && *(end - 1) != x) {
--end;
}
return end;
}
这个算法目前看起来是和find算法在结构上基本一致的了，如果我们创建一个新的类，交换start，end的位置，交换operator++和operator--则这个新的迭代器类就可以应用于我们的find算法了。
自动反向的迭代器
根据我们上面的思路，将一个双向迭代器转换为一个反向迭代器，则这个反向迭代器必须指向原来迭代器的前一个元素。即：在进行解引用操作的时候返回的是当前元素的前一个元素，这样当找不到时，我们也不会出现超出原来迭代器头部的问题。因为当找不到的时候，end == start并且返回了，不存在解引用的操作。
下面我们来实现这个反向迭代器：
template <class Iter, class T>
class Rev{
friend bool operator==(const Rev<Iter, T>& op1, const Rev<Iter, T>& op2);
friend bool operator!=(const Rev<Iter, T>& op1, const Rev<Iter, T>& op2);
public:
Rev() {}
Rev(Iter it) : current(it) {}
Rev(const Rev<Iter, T>&) = default;
operator Iter() { return current; }
Rev<Iter, T>& operator++() { --current; return *this;}
Rev<Iter, T>& operator--() { ++current; return *this; }
Rev<Iter, T> operator++(int) {
Rev<Iter, T> it = *this;
--current;
return it;
}
Rev<Iter, T> operator--(int) {
Rev<Iter, T> it = *this;
++current;
return it;
}
T& operator*() {
Iter it = current;
--it;
return *it; // 返回该位置前一位置的元素的值。
}
private:
Iter current;
};
template <class Iter, class T>
bool operator==(const Rev<Iter, T>& op1, const Rev<Iter, T>& op2)
{
return op1.current == op2.current;
}
template <class Iter, class T>
bool operator!=(const Rev<Iter, T>& op1, const Rev<Iter, T>& op2)
{
return op1.current != op2.current;
}
有了这个反向迭代器，我们就可以继续使用我们前面的查找算法了：
// 我们的查找算法
template <class T, class Iter>
Iter find(Iter start, Iter end, const T& x)
{
Iter p = start;
while( p != end && *p != x) {
p++;
}
return p;
}
int main()
{
int x[100];
int* p = find(x, x+100, 42); // 指针当然可以作为输入迭代器使用
Rev<int, int*> r = find(Rev<int,int*>(x+100), Rev<int, int*>(x), 42);
}
这样我们就实现了使用同一套算法，实现不同的功能的目的。
