std::distance(3)

💖 std::distance(3) — C++ Standard Libary, but make it bestie 💖

okay so this is the manual page for std::distance from the C++ Standard Libary manual (yes, that spelling is the manual name, iykyk). Grab a snack, bestie — we're getting into iterator math and it's gonna be cute. 🫶

✨ NAME ✨

std::distance — std::distance. That's the whole NAME section and honestly? It's giving main character energy. 💅

🦋 Synopsis 🦋

Defined in header <iterator>.

template< class InputIt >

typename std::iterator_traits<InputIt>::difference_type  (constexpr
since C++17)

    distance( InputIt first, InputIt last );

Returns the number of hops from first to last. 🎀

If InputIt is not a LegacyRandomAccessIterator, the behavior is undefined if last is not reachable from first.

If InputIt is a LegacyRandomAccessIterator, the behavior is undefined if first and last are neither reachable from each other. No cap, that reachability tea is important.

🎀 Parameters 🎀

• first — iterator pointing to the first element.
• last — iterator pointing to the end of the range.

🧚 Type requirements 🧚

• InputIt must meet the requirements of LegacyInputIterator. The operation is more efficient if InputIt additionally meets the requirements of LegacyRandomAccessIterator.

🌈 Return value 🌈

• The number of increments needed to go from first to last.
• The value may be negative if random-access iterators are used and (since C++11) first is reachable from last.

⭐ Complexity ⭐

• Linear.
• However, if InputIt additionally meets the requirements of LegacyRandomAccessIterator, complexity is constant. Slay.

🛠️ Possible implementation 🛠️

See also the implementations in libstdc++ and libc++.

C++98 implementation via tag dispatch, with constexpr removed

namespace detail
{
    template<class It>
    constexpr // required since C++17
    typename std::iterator_traits<It>::difference_type
        do_distance(It first, It last, std::input_iterator_tag)
    {
        typename std::iterator_traits<It>::difference_type result =
0;
        while (first != last)
        {
            ++first;
            ++result;
        }
        return result;
    }

    template<class It>
    constexpr // required since C++17
    typename std::iterator_traits<It>::difference_type
        do_distance(It first, It last,
std::random_access_iterator_tag)
    {
        return last - first;
    }
} // namespace detail

template<class It>
constexpr // since C++17
typename std::iterator_traits<It>::difference_type
    distance(It first, It last)
{
    return detail::do_distance(first, last,
                               typename
std::iterator_traits<It>::iterator_category());
}

C++17 implementation via if constexpr

template<class It>
constexpr typename std::iterator_traits<It>::difference_type
    distance(It first, It last)
{
    using category = typename
std::iterator_traits<It>::iterator_category;
    static_assert(std::is_base_of_v<std::input_iterator_tag,
category>);

    if constexpr (std::is_base_of_v<std::random_access_iterator_tag,
category>)
        return last - first;
    else
    {
        typename std::iterator_traits<It>::difference_type result =
0;
        while (first != last)
        {
            ++first;
            ++result;
        }
        return result;
    }
}

🍓 Example 🍓

// Run this code

#include <iostream>
#include <iterator>
#include <vector>

int main()
{
    std::vector<int> v{3, 1, 4};
    std::cout << "distance(first, last) = "
              << std::distance(v.begin(), v.end()) << '\n'
              << "distance(last, first) = "
              << std::distance(v.end(), v.begin()) << '\n';
              // the behavior is undefined (until LWG940)

    static constexpr auto il = {3, 1, 4};
    // Since C++17 `distance` can be used in constexpr context.
    static_assert(std::distance(il.begin(), il.end()) == 3);
    static_assert(std::distance(il.end(), il.begin()) == -3);
}

📺 Output 📺

distance(first, last) = 3
distance(last, first) = -3

🩹 Defect reports 🩹

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

• DR: LWG 940 — Applied to: C++98 — Behavior as published: the wording was unclear for the case where first is reachable from last — Correct behavior: made clear.

👀 See also 👀

• advance — advances an iterator by given distance (function template).
• count — returns the number of elements satisfying specific criteria.
• count_if — (function template).
• ranges::distance (C++20) — returns the distance between an iterator and a sentinel, or between the beginning and end of a range (niebloid).

---

💌 Cute little sign-off time: source/version/date tea is http://cppreference.com, 2024.06.10, and the footer tag is std::distance(3) — that's the whole page, bestie. Mwah. 🫶💖🌈