1
\$\begingroup\$

It's a simple range function that works like python range and it is only a syntactic sugar for the usual for loop

if we want to operate on numbers in the range from 1 to 10 (1 ... 9) we use this code :

for (int i = 0; i < 10; ++i) { ... }

but c++ 11 came with the for range loops in which this code :

for (auto i : array) {...}

will be expanded to something like this :

for (auto begin = array.begin(), auto end = array.end(); begin != end; ++begin) {auto i = *begin; ... }

the iterators are just wrappers for the pointers

so to make use of this feature and loop in a range of numbers we need to do somethings :

  • make i and end (the pointers) some integral type (int, short, long, ...) instead

  • and we should check if the start value is smaller than the final value because in the new for expression the test is for non equality not for less than or more than . it is this because this syntax is used to operate on the elements of the containers where we want to access the elements that we know they start at begin and end marks that the previous element was the final

so this is my implementation : I implemented two types of range functions

  • one for c++ 11 using iterators like counters

  • the second is for c++ 20 using the new generator and coroutines

both can be called lazy range because we don't get the whole numbers at one time (e.g in a vector) but the first is much faster because the compiler will expand it to a usual for loop and there is nothing to do with synchronize objects like promise, mutexes and condition variables

template <class T>
class range_iterator
{

private:
    T ptr;
    template <typename> friend class range_iterator;
public:
    constexpr range_iterator() : ptr(0) {}

    range_iterator(const range_iterator&) = default;

    explicit range_iterator(T p) : ptr(p) {}

    template <class U>
    constexpr range_iterator(const range_iterator<U>& other) : ptr(other.ptr) {}

    range_iterator& operator=(const range_iterator&) = default;

    template <class U>
    constexpr range_iterator& operator=(const range_iterator<U>& other) { ptr = other.ptr; return *this; }

    constexpr range_iterator& operator++() { ++ptr; return *this; }

    constexpr range_iterator operator++(int) { range_iterator old_iter(ptr); ++ptr; return old_iter; }

    constexpr range_iterator& operator--() { --ptr; return *this; }

    constexpr range_iterator& operator--(int) { range_iterator old_iter(ptr); --ptr; return old_iter; }

    T operator*() const { return ptr; }

    constexpr bool operator==(const range_iterator& other) const { return ptr == other.ptr; }

    constexpr bool operator!=(const range_iterator& other) const { return ptr != other.ptr; }

    template <class U>
    constexpr bool operator==(const range_iterator<U>& other) const { return ptr == other.ptr; }

    template <class U>
    constexpr bool operator!=(const range_iterator<U>& other) const { return ptr != other.ptr; }

    constexpr range_iterator operator+(const range_iterator& other) { return range_iterator(ptr + other.ptr); }

    constexpr range_iterator& operator+=(const range_iterator& other) { ptr += other.ptr; return *this; }

    constexpr range_iterator operator-(const range_iterator& other) { return range_iterator(ptr - other.ptr); }

    constexpr range_iterator& operator-=(const range_iterator& other) { ptr -= other.ptr; return *this; }

    template <class U>
    constexpr range_iterator operator+(const range_iterator<U>& other) { return range_iterator(ptr + other.ptr); }

    template <class U>
    constexpr range_iterator& operator+=(const range_iterator<U>& other) { ptr += other.ptr; return *this; }

    template <class U>
    constexpr range_iterator operator-(const range_iterator<U>& other) { return range_iterator(ptr - other.ptr); }

    template <class U>
    constexpr range_iterator& operator-=(const range_iterator<U>& other) { ptr -= other.ptr; return *this; }

    explicit operator T() const { return ptr; }

    void swap(range_iterator& rhs)
    {
        T temp_ptr = ptr;
        ptr = rhs.ptr;
        rhs.ptr = temp_ptr;
    }

};

template <class T1, class T2>
class range_step_iterator
{
    template <typename, typename> friend class range_step_iterator;

private:
    T1 ptr;
    T2 step;
public:
    constexpr range_step_iterator() : ptr(0), step(1) {}

    range_step_iterator(const range_step_iterator&) = default;

    explicit range_step_iterator(T1 p, T2 s) : ptr(p), step(s) {}

    template <class U1, class U2>
    constexpr range_step_iterator(const range_step_iterator<U1, U2>& other) : ptr(other.ptr), step(other.step) {}

    range_step_iterator& operator=(const range_step_iterator&) = default;

    template <class U1, class U2>
    constexpr range_step_iterator& operator=(const range_step_iterator<U1, U2>& other) { ptr = other.ptr; step = other.step; return *this; }

    constexpr range_step_iterator& operator++() { ptr += step;; return *this; }

    constexpr range_step_iterator operator++(int) { range_step_iterator old_iter(ptr, step); ptr += step; return old_iter; }

    constexpr range_step_iterator& operator--() { ptr -= step; return *this; }

    constexpr range_step_iterator& operator--(int) { range_step_iterator old_iter(ptr, step); ptr -= step; return old_iter; }

    T1 operator*() const { return ptr; }

    constexpr bool operator==(const range_step_iterator& other) const { return ptr == other.ptr; }

    constexpr bool operator!=(const range_step_iterator& other) const { return ptr != other.ptr; }

    template <class U1, class U2>
    constexpr bool operator==(const range_step_iterator<U1, U2>& other) const { return ptr == other.ptr; }

    template <class U1, class U2>
    constexpr bool operator!=(const range_step_iterator<U1, U2>& other) const { return ptr != other.ptr; }

    constexpr bool operator==(T1 other) const { return ptr == other; }

    constexpr bool operator!=(T1 other) const { return ptr != other; }

    constexpr range_step_iterator operator+(const range_step_iterator& other) const { return range_step_iterator(ptr + other.ptr, step); }

    constexpr range_step_iterator& operator+=(const range_step_iterator& other) { ptr += other.ptr; return *this; }

    constexpr range_step_iterator operator-(const range_step_iterator& other) const { return range_step_iterator(ptr - other.ptr, step); }

    constexpr range_step_iterator& operator-=(const range_step_iterator& other) { ptr -= other.ptr; return *this; }

    template <class U1, class U2>
    constexpr range_step_iterator operator+(const range_step_iterator<U1, U2>& other) const { return range_step_iterator(ptr + other.ptr); }

    template <class U1, class U2>
    constexpr range_step_iterator& operator+=(const range_step_iterator<U1, U2>& other) { ptr += other.ptr; return *this; }

    template <class U1, class U2>
    constexpr range_step_iterator operator-(const range_step_iterator<U1, U2>& other) const { return range_step_iterator(ptr - other.ptr); }

    template <class U1, class U2>
    constexpr range_step_iterator& operator-=(const range_step_iterator<U1, U2>& other) { ptr -= other.ptr; return *this; }

    explicit operator T1() const { return ptr; }

    void swap(range_step_iterator& rhs)
    {
        T1 temp_ptr = ptr;
        T2 temp_step = step;
        ptr = rhs.ptr;
        step = rhs.step;
        rhs.ptr = temp_ptr;
        rhs.step = temp_step;
    }

    template <class U1, class U2>
    void swap(range_step_iterator<U1, U2>& rhs)
    {
        T1 temp_ptr = ptr;
        T2 temp_step = step;
        ptr = rhs.ptr;
        step = rhs.step;
        rhs.ptr = temp_ptr;
        rhs.step = temp_step;
    }

};


namespace std
{
    template <class T>
    void swap(range_iterator<T>& lhs, range_iterator<T>& rhs)
    {
        lhs.swap(rhs);
    }

    template <class T1, class T2, class U1, class U2>
    void swap(range_step_iterator<T1, T2>& lhs, range_step_iterator<U1, U2>& rhs)
    {
        lhs.swap(rhs);
    }

    template <class T>
    void swap(reverse_range_iterator<T>& lhs, reverse_range_iterator<T>& rhs)
    {
        lhs.swap(rhs);
    }

};


template <class T1, class T2>
class range_1_step
{
    static_assert(std::is_integral_v<T1> && std::is_integral_v<T2>, "T1 and T2 must be an integral type");
private:
    range_iterator<T1> from_iter;
    range_iterator<T2> to_iter;
public:
    constexpr range_1_step(T1 from, T2 to) : from_iter(from), to_iter(to) { if (from >= to) from_iter = to_iter; }

    constexpr range_iterator<T1> begin() const { return range_iterator<T1>(from_iter); }

    constexpr range_iterator<T2> end() const { return range_iterator<T2>(to_iter); }

    constexpr bool empty() const { return from_iter == to_iter; }

    constexpr T1 size() const { return T1(to_iter - from_iter); }

};

template <class T1, class T2, class T3>
class range_step
{
    static_assert(std::is_integral_v<T1> && std::is_integral_v<T2> && std::is_integral_v<T3>, "T1 and T2 and T3 must be an integral type");
    using iterator = typename range_step_iterator<T1, T3>;
    iterator from_iter;
    iterator to_iter;

public:
    constexpr range_step(T1 from, T2 to, T3 step) : from_iter(from, step), to_iter(to, step) 
    {
        if (!step)
            throw std::runtime_error("step can't be zero");
        if ((from > to && step > 0) || (from < to && step < 0)) from_iter = to_iter; 
    }

    constexpr iterator begin() const { return from_iter; }

    constexpr iterator end() const { return to_iter; }

    constexpr bool empty() const { return from_iter == to_iter; }

    constexpr T1 size() const { return T1(to_iter - from_iter); }

};

template <class T1, class T2, class T3>
auto range(T1 from, T2 to, T3 step)
{
    return range_step(from, to, step);
}

template <class T1, class T2>
auto range(T1 from, T2 to)
{
    return range_1_step(from, to);
}

template <class T>
auto range(T to)
{
    return range_1_step((T)0, to);
}

template <class T1, class T2 = T1, class T3 = T1>
std::experimental::generator<T1> lazy_range(T1 from, T2 to, T3 step)
{
    for (; from < to; from += step)
        co_yield from;
}

template <class T1, class T2 = T1>
std::experimental::generator<T1> lazy_range(T1 from, T2 to)
{
    for (; from < to; ++from)
        co_yield from;
}

template <class T>
std::experimental::generator<T> lazy_range(T to)
{
    for (T i = 0; i < to; ++i)
        co_yield i;
}

usage example :

int main()
{
    auto print_duration = [](long long nano_dur)
    {
        std::cout << "[*] it took " << nano_dur << " nano => " << nano_dur / 1000 << " micro => "
            << nano_dur / 1000000 << " milli => " << nano_dur / 1000000000 << " sec" << endl;
    };

    const unsigned long long iterations = 100000;
    unsigned long long sub = 0;
    std::chrono::time_point t1 = std::chrono::high_resolution_clock::now();
    for (auto i : range(iterations))
        sub += i;
    std::chrono::time_point t2 = std::chrono::high_resolution_clock::now();
    auto dur = t2 - t1;
    print_duration(dur.count());

    t1 = std::chrono::high_resolution_clock::now();
    for (auto i : lazy_range(iterations))
        sub += i;
    t2 = std::chrono::high_resolution_clock::now();
    auto dur2 = t2 - t1;
    print_duration(dur2.count());

    if (dur2 > dur)
        cout << "coroutine is slower " << endl;
    else
        cout << "coroutine is faster" << endl;
}

from this sample the range function is much much faster than lazy range function but the gap goes some small if I use the variable sub because in the above code the compiler may have optimized the whole loop in the first case but it couldn't in the second , but the difference is still much big

some missing points :

  • the result type in the iteration is only the first type given to the function , so one should take care of the type he is using

  • I couldn't reverse the the range with the same behavior of other containers because range(0, 10) gives : (0 ... 9) but reverse_range(0, 10) gives (10 ... 1) using the reverse iterators that I'm working on

this is because the compiler converts :

for (int i = 0; i != 10; ++i) {}

to :

for (int i = 10; i != 0; --i) {}

so the second is not the reverse of the first but I think it isn't very bad anyway

\$\endgroup\$
4
  • \$\begingroup\$ It is more likely that the compiler converts it to for (int i = 11; --i; ) since most computers have a decrement and test instruction. \$\endgroup\$
    – pacmaninbw
    Sep 8, 2019 at 18:10
  • \$\begingroup\$ What kind of review are you asking for specifically? \$\endgroup\$
    – pacmaninbw
    Sep 8, 2019 at 18:11
  • \$\begingroup\$ I am not sure . I wrote the code and wanted to share it so someone code benefit from it or build something upon it \$\endgroup\$
    – dev65
    Sep 8, 2019 at 18:55
  • \$\begingroup\$ @dev65 your question is accumulating close votes because it is unclear what you are asking: if you could add a paragraph to the answer discussing the context in which you would use these, and explaining whether you want a comparative review or a general review of both methods then that should help. (Note: be sure to put such information in the answer rather than in comments: comments have a habit of disappearing and not everyone will read them) \$\endgroup\$ Sep 11, 2019 at 10:34

1 Answer 1

2
\$\begingroup\$

This is undefined behavior:

namespace std
{
    template <class T>
    void swap(range_iterator<T>& lhs, range_iterator<T>& rhs)
    {
        lhs.swap(rhs);
    }

    template <class T1, class T2, class U1, class U2>
    void swap(range_step_iterator<T1, T2>& lhs, range_step_iterator<U1, U2>& rhs)
    {
        lhs.swap(rhs);
    }

    template <class T>
    void swap(reverse_range_iterator<T>& lhs, reverse_range_iterator<T>& rhs)
    {
        lhs.swap(rhs);
    }

};

You should never overload swap in the std namespace. Instead, the swap should be overloaded in the same namespace as the type to be swapped. This allows correct usage of swap to find the version with ADL.

This is wrong:

void swap(range_iterator& rhs)
{
    T temp_ptr = ptr;
    ptr = rhs.ptr;
    rhs.ptr = temp_ptr;
}

it should be

using std::swap;
swap(ptr, rhs.ptr);

instead. Same for the other swap functions.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.