Wie std :: distance() für benutzerdefinierte Vorlagen Iterator implementieren?

Question

Ich habe einen templated bidirektionalen Iterator. Ich möchte es nicht wahlfrei machen, weil die Operation it += n keine konstante Zeit wäre. Die it2 - it1 Operation ist jedoch konstante Zeit. Ich wollte std::distance() für diesen Iterator spezialisieren, damit Algorithmen, die ihn verwenden (wie std::vector::assign()), die effiziente Differenzoperation verwenden können. Wie kann ich dies tun , wenn der Iterator eine Vorlage ist?

Hier ist ein Spielzeug Beispiel:

#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; 
} 

---

Dies ist ein Follow-up von Is it reasonable to overload std functions such as std::distance?

Wir prinzipiell so etwas tun könnte:

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; 
    } 
} 

aber das würde sei eine Überladung von std::distance(), die fürnicht erlaubt ist 10 Namespace funktioniert nach dem Standard.

Answer 1

Der richtige Weg, dies zu tun, ist Ihre distance Methode im selben Namensraum wie Ihre iter-Vorlage, (in diesem Fall globalen Namensraum) zu definieren.

.... 
    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; 
} 

Und später ADL, wie in diesem Beispiel zu sehen:

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; 
} 

AUSGABE:

my distance called 
5 
using std::distance 
5 

Eine gute Erklärung für dieses Problem der teilweisen Spezialisierung von Vorlagen von Methoden aus std gegeben von Scott Meyers in seinem Buch "Effective C++", dritte Ausgabe, Punkt 25.