пользовательская реализация std :: distance

Question

Я сделал шаблонную функцию «расстояние» для расчета расстояния между двумя итераторами. В функции я делю случаи, один для итератора произвольного доступа, а другой. Он хорошо определяет тип итератора с iterator_traits, но я не могу использовать эту функцию с двунаправленным итератором.

Вот моя функция расстояния

template <typename Iter>
ptrdiff_t distance(Iter first, Iter last)
{
    typedef typename std::iterator_traits<Iter>::iterator_category type;
    ptrdiff_t dist = 0;
    if (typeid(type) == typeid(std::random_access_iterator_tag)) {
        return last - first;
    }
    for (; first != last; ++first)
        dist++;
    return (dist);
}

Вот основной код, который я пытаюсь проверить

int main(void)
{
    std::list<int> li;
    li.push_back(100);
    std::cout << ft::distance(li.begin(), li.end()) << std::endl;   
    return (0);
}

Это сообщение об ошибке

./iterator.hpp:149:16: error: invalid operands to
      binary expression ('std::_List_iterator<int>' and
      'std::_List_iterator<int>')
                return (last - first);

Я пытался сделать функцию расстояния без "last - first" что-то вроде ниже

template <typename Iter>
static ptrdiff_t subtract(Iter first, Iter last)
{
    return (last - first);
};

template <typename Iter>
ptrdiff_t distance(Iter first, Iter last)
{
    typedef typename std::iterator_traits<Iter>::iterator_category type;
    ptrdiff_t dist = 0;
    if (typeid(type) == typeid(std::random_access_iterator_tag)) {
        return subtract(first, last);
    }
    for (; first != last; ++first)
        dist++;
    return (dist);
}

Но все равно выдает ту же ошибку. Как я могу решить эту проблему?

Answer 1

Ваша проблема в том, что if (typeid(type) == typeid(std::random_access_iterator_tag)) должно быть if constexpr, чтобы вы не пытались скомпилировать last - first для итераторов без произвольного доступа, но if constexpr (typeid(type) == typeid(std::random_access_iterator_tag)) не компилируется.

Тем не менее, есть пример в cppreference («вторая версия»), который показывает другой способ сделать это, например так:

if constexpr (std::is_base_of_v<std::random_access_iterator_tag, type>)
    return last - first;
else { ...

Это все относится к C ++ 17 и потом. Если вы ищете решение для C ++ 14 или более ранней версии, то приведенная выше ссылка также показывает, как это можно сделать с помощью диспетчеризации тегов («первая версия»).

Answer 2

Обычный подход в реализациях стандартной библиотеки заключается в использовании тега итератора для отправки в конкретную специализацию:

template <class Iter, class Tag>
std::ptrdiff_t distance_impl(Iter first, Iter last, Tag) {
    std::ptrdiff_t dist = 0;
    while (first != last) {
        ++dist;
        ++first;
    }
    return dist;
}

template <class Iter>
std::ptrdiff_t distance_impl(Iter first, Iter last, std::random_access_iterator_tag) {
    return last - first;
}

template <class Iter>
std::ptrdiff_t my_distance(Iter first, Iter last) {
    typedef typename std::iterator_traits<Iter>::iterator_category type;
    return distance_impl(first, last, type());
}

Это намного чище, чем написание функции, которая содержит несколько путей кода, которые могут или не могут быть частью скомпилированной версии. (Да, constexpr if, я смотрю на тебя ...)