For a dense container, the equivalent solution would be to introduce an integer counter and increment it synchronously with the iterator. For sparse containers, there is no alternative, since the index is an inherent part of an element.
An equivalent approach is to create a copy of the iterator and assign it later to the given iterator. Some iterator classes in Polymake Template Library implement reset() more efficiently than the assignment.
An equivalent standard approach is to create a second iterator pointing after the last data item (with Container::end() method) and test it for equality with the given iterator. Many iterator classes in Polymake Template Library implement at_end() more efficiently than the comparing operator.

Polymake Template Library extends the standard Container and Iterator interfaces by a number of methods. The ability of a container (iterator) class to implement some of these methods is called here container (iterator) feature.

First we introduce the features and corresponding methods, then we show how to make an arbitrary container (iterator) to implement them.

end-sensitive bool Iterator::at_end() const;
Check whether the iterator has reached the end of the data sequence it's running along.
An end-sensitive iterator can be created from a pair of standard iterators using the convenience function make_iterator_range(first,last) . For iterating over the entire container use entire() function.
resettable void Iterator::reset();
Rewind an iterator to its initial position it has had immediately after creation.
indexed int Iterator::index() const;
Tell the position of the current element the iterator is pointing to. In a dense container, it's just the ordinal number, starting with 0 at the first element. In a sparse container, it is a coordinate of the element.
reference_relaxed value_type Iterator::operator* () const;
In the general case, a iterator points to data elements physically stored in the container. Each element has an unique address, which is returned by the operator* and operator-> iterator methods. Each persistent container is considered to implement this feature natively.
A lazy container, however, contains no data; its elements are born on the fly as they are visited. Since they are temporary objects, the iterator may not operate on their addresses. Instead, it can either catch the elements, store them in an internal cache, and return the address of this cache from operator* and operator-> or pass on the temporary object.
Per default, a lazy container will create an iterator with internal cache, so that typename iterator::reference is really a reference. With enforced reference_relaxed feature, it will create a more lean and efficient pass-on iterator.
sparse dense pure_sparse sparse_compatible
A sparse container associates with each element a non-negative integer coordinate (index). Indices grow monotonically when iterating from begin() to end(), but may have gaps. The elements with lacking indices are assumed to have a value equivalent to the one created by the default container of the element type. (This incurs that the elements must be default-constructible.)
sparse is an inherent feature of a container, it can't be enforced. But the rest three features can:
pure_sparse is a strengthened variation: it guarantees that all explicitly visible elements differ from the default value. dense is the opposite to sparse: all elements are physically stored in the container independent of their values. sparse_compatible lies on the half way between dense and sparse: the container does not have gaps, but implements the sparse interface described below:
int Container::size() const;
Tell the number of elements physically stored in the container.
int Container::dim() const;
Tell the number of explicit and implicit elements. (For a vector, it would mean its dimension, hence the method name.) Don't mix this up with max_size() which tells how many elements can a container instance ever have.
int get_dim(const Container&);
A convenience function returning dim() for a sparse container and size() for a dense container.
void Container::insert (const typename Container::iterator& position, int index, const typename Container::value_type& value);
Store the element with given index and value before the given position.
void Container::erase (const typename Container::iterator& position);
Remove the element pointed to by position from the container (make it an implicit zero.)
Indeed, a class impementing a sparse container interface may have much more element manipulation methods than these two. It's just the minimum required by the algorithms in Polymake Template Library dealing with sparse containers.

Recognizing features

If you write function templates which have to know what kind of container (iterator) they have got as a parameter, you can easily check it using the following compile-time expressions:

check_iterator_feature<Iterator, Feature>::answer check_container_feature<Container, Feature>::answer
Boolean constants; available for every feature described above.
typename iterator_traits<Iterator>::iterator_category typename container_traits<Container>::category
One of the standard tag types (std::forward_iterator_tag etc.)
Note that the category of a pseudo-container is not necessary the same as the category of its iterator. In fact, it can be more elaborated one, up to the category of the data container it is based upon.

Enforcing additional features

Almost every standard-conforming container can be equipped with additional features. This is accomplished by the helper class

template <typename Container, typename Features> class ensure_features;

where Features is either one of feature names introduced above, or a cons list filled with several feature names (in arbitrary order). The most important types defined therein are:

container
A masquerade class put on the top of the original container. If the given container does implement the required features natively, the resulting type is (up to some technical details) identical to Container.
iterator const_iterator
Iterators over the masqueraded container, having the requested features.

There are convenience functions decorating the containers with additional features:

typename ensure_features<Container, Features>::container& ensure (Container&, (Features*)); const typename ensure_features<Container, Features>::container&; ensure (const Container&, (Features*));

For the most popular features there is a shortcut:

typename Entire<Container>::iterator
is equivalent to
typename ensure_features<Container, end_sensitive>::iterator
and
typename Entire<Container>::const_iterator
is equivalent to
typename ensure_features<Container, cons<end_sensitive, reference_relaxed> >::const_iterator

There are convenience functions for this shortcut too:

typename Entire<Container>::iterator entire(Container&); typename Entire<Container>::const_iterator entire(const Container&);
They allow to write a classical loop visiting all elements in a container more compactly (and, for many data structures also more efficiently:)
for (typename Entire<Container>::const_iterator i=entire(c); !i.at_end(); ++i) { ... }