I have a templated bidirectional iterator. I do not want to make it random access because the it += n
operation would not be constant time. However, the it2 - it1
operation is constant time. I wanted to specialize std::distance()
for this iterator so that algorithms that use it (such as std::vector::assign()
) can make use of the efficient difference operation. How can I do this if the iterator is a template?
Here's a toy example:
#include <iterator>
#include <iostream>
// template bidirectional iterator
template<typename T>
class iter : public std::iterator<std::bidirectional_iterator_tag, T> {
T *ptr;
public:
iter(T *ptr) : ptr(ptr) { }
iter() = default;
iter(const iter &) = default;
iter &operator = (const iter &) = default;
T *operator * () { return ptr; }
bool operator == (const iter &it) { return ptr == it.ptr; }
bool operator != (const iter &it) { return ptr != it.ptr; }
iter &operator ++ () { ++ptr; return *this; }
iter operator ++ (int) { iter tmp(*this); operator++(); return tmp; }
iter &operator -- () { --ptr; return *this; }
iter operator -- (int) { iter tmp(*this); operator--(); return tmp; }
// Would not be used for a bidirectional iterator.
// Implemented only so we can use it in std::distance() below.
ptrdiff_t operator - (const iter &it) { return ptr - it.ptr; }
};
namespace std {
// We could specialize std::distance() for iter<int> like this:
template<>
iter<int>::difference_type distance(iter<int> first, iter<int> last) {
std::cout << "my distance called\n";
return last - first;
}
// QUESTION: Can we do it in general, for iter<T> ?
}
// Just to test that everything works as intended.
int main() {
int arr[5];
iter<int> it1(&arr[0]);
iter<int> it2(&arr[5]);
std::cout << std::distance(it1, it2) << std::endl;
return 0;
}
This is a follow-up of Is it reasonable to overload std functions such as std::distance?
We could in principle do something like this:
namespace std {
template<class T>
typename iter<T>::difference_type distance(iter<T> first, iter<T> last) {
std::cout << "my distance called\n";
return last - first;
}
}
But that would be an overload of std::distance()
, which is not allowed for std
namespace functions according to the standard.
The distance() function in C++ helps find the distance between two iterators. In other words, we can use this function to calculate the number of elements present between the two iterators. This function is available in the <iterator> header file.
The iterator is implemented as a pointer to a node, and contains operator overloads for the four usual iterator operations of dereference, increment, comparison, and assignment. in the list class that can be used to insert new data items at arbitrary locations in the list.
std::distanceReturns the number of elements between first and last . The behavior is undefined if last is not reachable from first by (possibly repeatedly) incrementing first .
The correct way to do it is to define your distance
method in the same namespace as your iter
-template, (in this case global namespace).
....
typename iter::difference_type operator -(const iter &it)
{
return ptr - it.ptr;
}
}; // close template<typename T> class iter
template<typename T>
typename iter<T>::difference_type distance( iter<T> first, iter<T> last)
{
std::cout << "my distance called\n";
return last - first;
}
And later using ADL as seen in this example:
int main()
{
int arr[5];
iter<int> it1(&arr[0]);
iter<int> it2(&arr[5]);
using std::distance;
using std::begin;
using std::end;
std::cout << distance(it1, it2) << '\n';
std::cout << "using std::distance\n";
std::cout << distance(begin(arr), end(arr)) << '\n';
return 0;
}
will output:
my distance called
5
using std::distance
5
A good explanation of this problem of partial specialization of templates of methods from std is given by Scott Meyers in his book "Effective C++", third edition, item 25.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With