CODEWITHSUNDEEP
c++stliteratorcontainers
Throckmorton
Throckmorton

Reputation: 582

STL function for determining if distance is within `n`

Let's say I have some container C of elements and two iterators it1 and it2 (it1 <= it2 wlog) . If std::distance(it1, it2) <= n, I want to perform some action f. Furthermore, it1 and it2 are changing (possibly randomly) within a loop and I need to check the distance with every iteration.

If C is very large and not random-access, calling std::distance on every iteration is extremely wasteful, since we only need to determine if the distance is less than some n. It's fairly trivial to write some function which would take two iterators and an integer and return whether or not the distance between the two is within the provided integer, however I'm wondering if there is some way to use the STL to accomplish this task.

Essentially, what I am looking for is an STL version of the function below:

template <class ForwardIt>
bool is_within(ForwardIt it1, ForwardIt it2, int n) {
  int i = 0;
  while (i++ <= n)
    if (it1++ == it2) return true;
  return false
}

Upvotes: 2

Views: 145

Answers (1)

Cruz Jean
Cruz Jean

Reputation: 2819

As far as I'm aware there's nothing in the standard library to do this automatically. However your solution is on the right track to being what you want anyway. You only need a minor change to make it more efficient for random access iterators.

template<typename Iter>
bool is_within(Iter a, Iter b, std::size_t n)
{
    // if we're a random access iterator, use the (faster) std::distance() method
    if constexpr (std::is_same_v<typename std::iterator_traits<Iter>::iterator_category, std::random_access_iterator_tag>)
    {
        return std::distance(a, b) <= n;
    }
    // otherwise go the long way around with short circuiting on n
    else
    {
        for (; n > 0 && a != b; --n, ++a);
        return a == b;
    }
}

Upvotes: 3

Related Questions