如果不更改迭代器类型,就没有通用的完整解决方案。
证明:假设迭代器类型只是一个InputIterator,那么
begin
实际上是指(例如)一个流,并且
end
是一个特殊的case标记迭代器,一旦真正的迭代器读取了EOF,它将与“real”迭代器进行比较。
那么任何使用
开始
尝试计算出
结束
要传递到算法,将“消耗”原始值
开始
,因为输入程序就是这样工作的。
你可以做的是编写一个迭代器包装类,这样迭代器就可以计算它被递增了多少次,并且在它被递增了N次之后,与一个“end”迭代器进行比较。N可以是模板参数,也可以是一个或多个迭代器的构造函数参数。
像这样的东西。我已经测试过它的编译并为我工作。仍然要做-我目前只处理两种情况中的一种,“不是随机访问迭代器”。另一个是“距离”。
#include <iterator>
template <typename It>
class FiniteIterator : public std::iterator<
typename std::iterator_traits<It>::iterator_category,
typename std::iterator_traits<It>::value_type> {
typedef typename std::iterator_traits<It>::difference_type diff_type;
typedef typename std::iterator_traits<It>::value_type val_type;
It it;
diff_type count;
public:
FiniteIterator(It it) : it(it), count(0) {}
FiniteIterator(diff_type count, It it = It()) : it(it), count(count) {}
FiniteIterator &operator++() {
++it;
++count;
return *this;
}
FiniteIterator &operator--() {
--it;
--count;
return *this;
}
val_type &operator*() const {
return *it;
}
It operator->() const {
return it;
}
bool operator==(const FiniteIterator &rhs) const {
return count == rhs.count;
}
bool operator!=(const FiniteIterator &rhs) const {
return !(*this == rhs);
}
FiniteIterator operator++(int) {
FiniteIterator cp = *this;
++*this;
return cp;
}
FiniteIterator operator--(int) {
FiniteIterator cp = *this;
--*this;
return cp;
}
};
注意,第二个构造函数只接受一个迭代器,因为底层类型可能不是默认的可构造类型(如果它只是一个InputIterator)。在调用方创建“结束”迭代器的情况下,它不使用它,因为一旦另一个副本递增,它就无效了。
如果底层迭代器类型是RandomAccess,则不需要/不需要此包装器。所以我提供了一个helper模板函数,它以同样的方式进行类型推导
back_inserter
是为了
back_insert_iterator
. 但是,如果其参数类型是随机访问类别的迭代器,则helper不应返回
FiniteIterator<T>
,但是
T
:
template <typename Iterator, typename Category>
struct finite_traits2 {
typedef FiniteIterator<Iterator> ret_type;
static ret_type plus(Iterator it, typename std::iterator_traits<Iterator>::difference_type d) {
return ret_type(d, it);
}
};
template <typename Iterator>
struct finite_traits2<Iterator, std::random_access_iterator_tag> {
typedef Iterator ret_type;
static ret_type plus(Iterator it, typename std::iterator_traits<Iterator>::difference_type d) {
return it + d;
}
};
template <typename Iterator>
struct finite_traits {
typedef typename std::iterator_traits<Iterator>::iterator_category itcat;
typedef typename finite_traits2<Iterator, itcat>::ret_type ret_type;
static ret_type plus(Iterator it, typename std::iterator_traits<Iterator>::difference_type d) {
return finite_traits2<Iterator, itcat>::plus(it, d);
}
};
template <typename Iterator, typename Distance>
typename finite_traits<Iterator>::ret_type finite_iterator(Iterator it, Distance d) {
return finite_traits<Iterator>::plus(it, d);
}
template <typename Iterator>
typename finite_traits<Iterator>::ret_type finite_iterator(Iterator it) {
return finite_traits<Iterator>::plus(it, 0);
}
示例用法(和最小测试):
#include <iostream>
#include <typeinfo>
#include <list>
struct MyIterator : std::iterator<std::bidirectional_iterator_tag, int> {
difference_type count;
};
int main() {
std::cout << typeid(MyIterator::iterator_category).name() << "\n";
std::cout << typeid(FiniteIterator<MyIterator>::iterator_category).name() << "\n";
std::cout << typeid(MyIterator::difference_type).name() << "\n";
std::cout << typeid(FiniteIterator<MyIterator>::difference_type).name() << "\n";
int a[] = {1, 2, 3, 4, 5};
std::copy(finite_iterator(a), finite_iterator(a,4), std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n";
std::list<int> al(finite_iterator(a), finite_iterator(a,4));
std::cout << al.size() << "\n";
std::copy(finite_iterator(al.begin()), finite_iterator(al.begin(),3), std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n";
}
注意:
finite_iterator(x, 1) == finite_iterator(++x, 0)
是
假
,甚至对于前向迭代器更好。有限迭代器只有在从同一个起点创建时才具有可比性。
而且,这还没有完成。例如
std::reverse
不起作用,因为为了访问referrand,
finite_iterator(x, 1)
是“指向”x。
目前,发生了以下情况:
std::list<int>::iterator e = al.begin();
std::advance(e,3);
std::reverse(finite_iterator(al.begin()), finite_iterator(e,3));
所以我不远,但那不是一个好的界面。我需要更多地考虑双向迭代器的情况。