Algorithms for integer ranges?

[red floyd]

I was looking for a way to use standard algorithms with a range of
integers. For example, for the range [1, N), where N can be arbitrarily
large. The problem to me appears to be that library algorithms only
work on iterators. I didn't want to just create a collection containing
the integers, because I was playing with some math which might use large
values (on the order of over a million), and I didn't want to waste the
space.

So for my purposes, I came up with the following.

[BEGIN CODE]
namespace my {
template<typename Integral, typename UnaryFunction>
Integral for_each(Integral first, Integral last, UnaryFunction func)
{
while (first < last)
{
func(first);
++first;
}
return first;
}
template<typename Integral, typename UnaryFunction>
Integral for_each(Integral first, Integral last,
Integral interval, UnaryFunction func)
{
while (first < last)
{
func(first);
first += interval;
}
return first;
}
}
[END CODE]

I don't want to duplicate something already written, is there
something similar in the Standard Library?

-- red floyd

[Sam]

red floyd writes:

> I was looking for a way to use standard algorithms with a range of
> integers. For example, for the range [1, N), where N can be arbitrarily
> large. The problem to me appears to be that library algorithms only
> work on iterators. I didn't want to just create a collection containing
> the integers, because I was playing with some math which might use large
> values (on the order of over a million), and I didn't want to waste the
> space.

It is trivial to whip up an iterator that will iterate over a sequence of a
billion values, that will require zero bytes of memory. The size of the
sequence covered by an iterator has no direct relation to the amount of
memory required for it. There are iterators that iterate over something
that's not represented by a memory range.

People's Exhibit "A": you might be familiar with std::istreambuf_iterator?
It will happily iterate over each byte of a terabyte-sized file, without
needing a terabyte of RAM.

You need to divorce yourself from the notion that just because you have an
iterator that produces a million ints, these million int must be in RAM,
somewhere.

> template<typename Integral, typename UnaryFunction>
> Integral for_each(Integral first, Integral last,
> Integral interval, UnaryFunction func)
> {
> while (first < last)
> {
> func(first);
> first += interval;
> }
> return first;
> }
> }
> [END CODE]
>
> I don't want to duplicate something already written, is there
> something similar in the Standard Library?

Well, you can use std::for_each, with a custom iterator whose operator*
return *this, perhaps.

Or, maybe std::fill or std::generate can be put to good use here, with a few
custom classes.

[Bonita Montero]

You could use an iterator which wraps a normal iterator and includes
a gap-value. Something like this (don't know if everything is correct):

#include <iterator>

template<typename RandIt>
struct gap_iterator
{
using value_type = typename std::iterator_traits<RandIt>::value_type;
gap_iterator() = default;
gap_iterator( RandIt it, std::size_t gap );
gap_iterator( gap_iterator const &other );
gap_iterator &operator =( gap_iterator const &rhs );
bool operator !=( gap_iterator const &other );
value_type &operator *();
value_type *operator ->();
gap_iterator &operator ++();
gap_iterator &operator +=( std::size_t offset );

private:
RandIt m_it;
size_t m_gap;
};

template<typename RandIt>
inline
gap_iterator<RandIt>::gap_iterator( RandIt it, std::size_t gap )
{
m_it = it;
m_gap = gap;
}

template<typename RandIt>
inline
gap_iterator<RandIt>::gap_iterator( gap_iterator const &other )
{
m_it = other.m_it;
m_gap = other.m_gap;
}

template<typename RandIt>
inline
typename gap_iterator<RandIt>::gap_iterator
&gap_iterator<RandIt>::operator =( gap_iterator const &rhs )
{
m_it = rhs.m_it;
m_gap = rhs.m_gap;
return *this;
}

template<typename RandIt>
inline
bool gap_iterator<RandIt>::operator !=( gap_iterator const &rhs )
{
return m_it != rhs.m_it;
}

template<typename RandIt>
inline
typename gap_iterator<RandIt>::value_type
&gap_iterator<RandIt>::operator *()
{
return *m_it;
}

template<typename RandIt>
inline
typename gap_iterator<RandIt>::value_type
*gap_iterator<RandIt>::operator ->()
{
return &*m_it;
}

template<typename RandIt>
inline
gap_iterator<RandIt> &gap_iterator<RandIt>::operator ++()
{
m_it += m_gap;
return *this;
}

template<typename RandIt>
inline
gap_iterator<RandIt> &gap_iterator<RandIt>::operator +=( std::size_t
offset )
{
m_it += offset * m_gap;
return *this;
}

#include <iostream>
#include <algorithm>
#include <cstdlib>

using namespace std;

int main()
{
int ai[16 * 16];
gap_iterator<int *> giiBegin( ai, 16 ),
giiEnd( giiBegin );
giiEnd += 16;
for_each( giiBegin, giiEnd, []( int &v ) { v = rand(); } );
for_each( giiBegin, giiEnd, []( int v ) { cout << v << " "; } );
}

[Bonita Montero]

Why does this changed version not work ?

#include <iterator>

template<typename RandIt>
struct gap_iterator
{
using value_type = typename std::iterator_traits<RandIt>::value_type;
gap_iterator() = default;
gap_iterator( RandIt it, std::size_t gap );
gap_iterator( gap_iterator const &other );
gap_iterator &operator =( gap_iterator const &rhs );
bool operator !=( gap_iterator const &other );
value_type &operator *();
value_type *operator ->();
gap_iterator &operator ++();
gap_iterator &operator +=( std::size_t offset );

friend gap_iterator operator +( gap_iterator const &gi, std::size_t

gap_iterator<RandIt> operator +( gap_iterator<RandIt> const &gi,
std::size_t offset )
{
gap_iterator<RandIt> ret( gi );
gi.m_it += offset * gi.m_gap;
return ret;

}

#include <iostream>
#include <algorithm>
#include <cstdlib>

using namespace std;

int main()
{
int ai[16 * 16];
gap_iterator<int *> giiBegin( ai, 16 ),

giiEnd( giiBegin + 16 );
//giiEnd += 16;

[Bonita Montero]

>     gi.m_it += offset * gi.m_gap;

ret.m_it += offset * ret.m_gap;

[Bonita Montero]

Am 28.03.2020 um 20:47 schrieb Bonita Montero:
>>      gi.m_it += offset * gi.m_gap;
>      ret.m_it += offset * ret.m_gap;

ret.m_it = ret.m_it + offset * ret.m_gap;
The contained iterator might not know +=.

[Bonita Montero]

Got it:

#include <iterator>

template<typename RandIt>
struct gap_iterator
{
using value_type = typename std::iterator_traits<RandIt>::value_type;
gap_iterator() = default;
gap_iterator( RandIt it, std::size_t gap );
gap_iterator( gap_iterator const &other );
gap_iterator &operator =( gap_iterator const &rhs );
bool operator !=( gap_iterator const &other );
value_type &operator *();
value_type *operator ->();
gap_iterator &operator ++();
gap_iterator &operator +=( std::size_t offset );

template<typename RandIt>
friend gap_iterator<RandIt> operator +( gap_iterator<RandIt> const

ret.m_it = ret.m_it + offset * ret.m_gap;

[Jorgen Grahn]

On Sat, 2020-03-28, red floyd wrote:
>
> I was looking for a way to use standard algorithms with a range of
> integers. For example, for the range [1, N), where N can be arbitrarily
> large. The problem to me appears to be that library algorithms only
> work on iterators.

Seems to me the real problem is you don't have iterators over [1, N).

Isn't there such a thing in Boost or something? If not, I imagine it
would be easy to write something so that:

const Range<int> r{1, 4711};
std::for_each(r.begin(), r.end(), f);

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[red floyd]

On 3/28/20 1:51 PM, Jorgen Grahn wrote:
> On Sat, 2020-03-28, red floyd wrote:
>>
>> I was looking for a way to use standard algorithms with a range of
>> integers. For example, for the range [1, N), where N can be arbitrarily
>> large. The problem to me appears to be that library algorithms only
>> work on iterators.
>
> Seems to me the real problem is you don't have iterators over [1, N).
>
>

TBH, I'm surprised the Committee hasn't addressed this.

[Ned Latham]

red floyd wrote:

> Jorgen Grahn wrote:
> > red floyd wrote:
> > >
> > > I was looking for a way to use standard algorithms with a range of
> > > integers. For example, for the range [1, N), where N can be arbitrarily
> > > large. The problem to me appears to be that library algorithms only
> > > work on iterators.
> >
> > Seems to me the real problem is you don't have iterators over [1, N).
>
> TBH, I'm surprised the Committee hasn't addressed this.

Can you construct a dummy object for the iterator's sake?

[daniel...@gmail.com]

On Saturday, March 28, 2020 at 2:04:11 PM UTC-4, red floyd wrote:
> I was looking for a way to use standard algorithms with a range of
> integers.

Option 1:

#include <iterator>
#include <algorithm>

template <class Iterator,class Enable = void>
class integer_iterator
{
};

template <class T>
class integer_iterator<T,typename std::enable_if<std::is_integral<T>::value
>::type>
{
T value_;
T step_;
public:
using iterator_category = std::random_access_iterator_tag;

using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = typename std::conditional<std::is_const<T>::value,
value_type*,
const value_type*>::type;
using reference = typename std::conditional<std::is_const<T>::value,
value_type&,
const value_type&>::type;

public:
explicit integer_iterator(T n = 0, T step = 1) : value_(n), step_(step)
{
}

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

template <class U,
class=typename std::enable_if<!std::is_same<U,T>::value &&
std::is_convertible<U,T>::value>::type>
integer_iterator(const integer_iterator<U>& other)
: value_(other.value_)
{
}

reference operator*() const
{
return value_;
}

T operator->() const
{
return &value_;
}

integer_iterator& operator++()
{
value_ += step_;
return *this;
}

integer_iterator operator++(int)
{
integer_iterator temp = *this;
++*this;
return temp;
}

integer_iterator& operator--()
{
value_ -= step_;
return *this;
}

integer_iterator operator--(int)
{
integer_iterator temp = *this;
--*this;
return temp;
}

integer_iterator& operator+=(const difference_type offset)
{
value_ += offset;
return *this;
}

integer_iterator operator+(const difference_type offset) const
{
integer_iterator temp = *this;
return temp += offset;
}

integer_iterator& operator-=(const difference_type offset)
{
return *this += -offset;
}

integer_iterator operator-(const difference_type offset) const
{
integer_iterator temp = *this;
return temp -= offset;
}

difference_type operator-(const integer_iterator& rhs) const
{
return value_ - rhs.value_;
}

reference operator[](const difference_type offset) const
{
return *(*this + offset);
}

bool operator==(const integer_iterator& rhs) const
{
return value_ == rhs.value_;
}

bool operator!=(const integer_iterator& rhs) const
{
return !(*this == rhs);
}

bool operator<(const integer_iterator& rhs) const
{
return value_ < rhs.value_;
}

bool operator>(const integer_iterator& rhs) const
{
return rhs < *this;
}

bool operator<=(const integer_iterator& rhs) const
{
return !(rhs < *this);
}

bool operator>=(const integer_iterator& rhs) const
{
return !(*this < rhs);
}

inline
friend integer_iterator<T> operator+(
difference_type offset, integer_iterator<T> next)
{
return next += offset;
}
};

int main(int argc, char** argv)
{
integer_iterator<int> first(1,10);
integer_iterator<int> last(100000001, 10);

int n = 0;
auto f = [&n](int i) {n += i;};
std::for_each(first, last, f);
}

Option 2

int main(int argc, char** argv)
{
int n = 0;
auto f = [&n](int i) {n += i;};
for (int i = 1; i < 100000001; i += 10)
{
f(i);
}
}

Decisions, decisions ...

Daniel

[Alf P. Steinbach]

In C++20 there will be std::something::idiota, or "iota" as the Greeks
tend to shorten it, used like

for( const int i: idiota( n ) ) do { //... use `i` here

With the
under-construction-library-that-I-really-need-to-finish-sometime you can
write similar but much more clear code like

for( const int i: zero_to( n ) ) { //... Use `i` here.

<url:
https://github.com/alf-p-steinbach/cppx-core-language/blob/master/source/cppx-core-language/syntax/collection-util/Sequence_.hpp>.

This is not an `idiota` copy; the library and concept, though not this
particular implementation, predates `idiota` by many years.

There are good reasons for all the shenanigans in that code, so it
illustrates what you're dealing with for defining a general integers
iterator. There may still be bugs. It's not extensively tested.


- Alf

[Chris Vine]

I don't think there is anything in the standard library but I am not
update with everything that C++17/20 has been up to.

However, rather than provide a lazy version of for_each, you would be
better off using an lazy iterator to which you can apply std::for_each,
std::transform and so on. Something like:

class IntIter {
public:
typedef int value_type;
typedef int reference; // read only
typedef void pointer; // read only
typedef int difference_type;
typedef std::random_access_iterator_tag iterator_category;
private:
int val;
public:
explicit IntIter(value_type val_ = 0) noexcept : val(val_) {}
IntIter(const IntIter&) noexcept = default;
IntIter& operator=(const IntIter&) noexcept = default;
IntIter& operator++() noexcept {++val; return *this;}
IntIter operator++(int) noexcept {IntIter tmp = *this; ++val; return tmp;}
IntIter& operator--() noexcept {--val; return *this;}
IntIter operator--(int) noexcept {IntIter tmp = *this; --val; return tmp;}
IntIter& operator+=(difference_type n) noexcept {val += n; return *this;}
IntIter& operator-=(difference_type n) noexcept {val -= n; return *this;}
reference operator[](difference_type n) const noexcept {return val + n;}
reference operator*() const noexcept {return val;}
};

Take your pick with standard comparison operators:

inline bool operator==(IntIter iter1, IntIter iter2) noexcept {
return *iter1 == *iter2;
}
inline bool operator!=(IntIter iter1, IntIter iter2) noexcept {
return !(iter1 == iter2);
}
inline bool operator<(IntIter iter1, IntIter iter2) noexcept {
return *iter1 < *iter2;
}
inline bool operator>(IntIter iter1, IntIter iter2) noexcept {
return iter2 < iter1;
}
inline bool operator<=(IntIter iter1, IntIter iter2) noexcept {
return !(iter1 > iter2);
}
inline bool operator>=(IntIter iter1, IntIter iter2) noexcept {
return !(iter1 < iter2);
}
inline IntIter::difference_type operator-(IntIter iter1, IntIter iter2) noexcept {
return *iter1 - *iter2;
}
inline IntIter operator+(IntIter iter, IntIter::difference_type n) noexcept {
return IntIter{*iter + n};
}
inline IntIter operator-(IntIter iter, IntIter::difference_type n) noexcept {
return IntIter{*iter - n};
}
inline IntIter operator+(IntIter::difference_type n, IntIter iter) noexcept {
return iter + n;
}

[jacobnavia]

In C you woduld write:

1 typedef long long IntType;
2
3 IntType doRange(IntType start,IntType end,
4 IntType increment, IntType(*func)(IntType))
5 {
6 IntType i;
7 for (i=start; i<end; i+= increment)
8 func(i);
9 return i;
10 }

I hope I understood correctly...

[daniel...@gmail.com]

On Sunday, March 29, 2020 at 5:18:29 PM UTC-4, jacobnavia wrote:

>
> In C you would write:
>
> 1 typedef long long IntType;
> 2
> 3 IntType doRange(IntType start,IntType end,
> 4 IntType increment, IntType(*func)(IntType))
> 5 {
> 6 IntType i;
> 7 for (i=start; i<end; i+= increment)
> 8 func(i);
> 9 return i;
> 10 }
>
> I hope I understood correctly...

That's my understanding. Also, note that

for (i=start; i<end; i+= increment)

func(i);

is more robust than the iterator alternative, for example

integer_iterator<int> first(1,10); // starting from 1, increment
// in steps of 10
integer_iterator<int> last(100, 10);

std::for_each(first, last, func);

would result in an infinite loop.

Daniel

[Richard]

[Please do not mail me a copy of your followup]

red floyd <no....@its.invalid> spake the secret code
<r5o3ig$35e$1...@redfloyd.dont-email.me> thusly:

>I was looking for a way to use standard algorithms with a range of

>integers. [...]

Have you looked at the Range support that was added to C++20?
<http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/n4849.pdf>

Look at 24.6.3 Iota view

for (int i : iota_view{1, 10})
cout << i << ' '; // prints 1 2 3 4 5 6 7 8 9 10

--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Terminals Wiki <http://terminals-wiki.org>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>

[Richard]

[Please do not mail me a copy of your followup]

(Richard) legaliz...@mail.xmission.com spake the secret code
<r63hov$t82$1...@news.xmission.com> thusly:

>[Please do not mail me a copy of your followup]
>
>red floyd <no....@its.invalid> spake the secret code
><r5o3ig$35e$1...@redfloyd.dont-email.me> thusly:
>
>>I was looking for a way to use standard algorithms with a range of
>>integers. [...]
>
>Have you looked at the Range support that was added to C++20?
><http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/n4849.pdf>
>
>Look at 24.6.3 Iota view
>
>for (int i : iota_view{1, 10})
> cout << i << ' '; // prints 1 2 3 4 5 6 7 8 9 10

Also, if you don't have C++20 as an option, or don't want to wait, you
can use the Ranges v3 library by Eric Niebler who wrote the spec for
ranges in C++ 20.
<https://github.com/ericniebler/range-v3>

[Melzzzzz]

On 2020-04-02, Richard <legaliz...@mail.xmission.com> wrote:
> [Please do not mail me a copy of your followup]
>
> (Richard) legaliz...@mail.xmission.com spake the secret code
><r63hov$t82$1...@news.xmission.com> thusly:
>
>>[Please do not mail me a copy of your followup]
>>
>>red floyd <no....@its.invalid> spake the secret code
>><r5o3ig$35e$1...@redfloyd.dont-email.me> thusly:
>>
>>>I was looking for a way to use standard algorithms with a range of
>>>integers. [...]
>>
>>Have you looked at the Range support that was added to C++20?
>><http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/n4849.pdf>
>>
>>Look at 24.6.3 Iota view
>>
>>for (int i : iota_view{1, 10})
>> cout << i << ' '; // prints 1 2 3 4 5 6 7 8 9 10
>
> Also, if you don't have C++20 as an option, or don't want to wait, you
> can use the Ranges v3 library by Eric Niebler who wrote the spec for
> ranges in C++ 20.
><https://github.com/ericniebler/range-v3>

I think that this is pointless. Take a look at golang, they recommend
ordinary for loop for this...


--
press any key to continue or any other to quit...
U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec
Svi smo svedoci - oko 3 godine intenzivne propagande je dovoljno da jedan narod poludi -- Zli Zec
Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi
bili naoruzani. -- Mladen Gogala

[Daniel P]

On Wednesday, April 1, 2020 at 11:14:02 PM UTC-4, Melzzzzz wrote:
> On 2020-04-02, Richard <legaliz...@mail.xmission.com> wrote:
> >>
> >>Look at 24.6.3 Iota view
> >>
> >>for (int i : iota_view{1, 10})
> >> cout << i << ' '; // prints 1 2 3 4 5 6 7 8 9 10
> >
> > Also, if you don't have C++20 as an option, or don't want to wait, you
> > can use the Ranges v3 library by Eric Niebler who wrote the spec for
> > ranges in C++ 20.
> ><https://github.com/ericniebler/range-v3>
>
> I think that this is pointless. Take a look at golang, they recommend
> ordinary for loop for this...
>

Agreed.

Daniel

[Jorgen Grahn]

On Thu, 2020-04-02, Melzzzzz wrote:
> On 2020-04-02, Richard <legaliz...@mail.xmission.com> wrote:
>> (Richard) legaliz...@mail.xmission.com spake the secret code
>><r63hov$t82$1...@news.xmission.com> thusly:

>>>red floyd <no....@its.invalid> spake the secret code
>>><r5o3ig$35e$1...@redfloyd.dont-email.me> thusly:

>>>>I was looking for a way to use standard algorithms with a range of
>>>>integers. [...]
>>>
>>>Have you looked at the Range support that was added to C++20?
>>><http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/n4849.pdf>
>>>
>>>Look at 24.6.3 Iota view
>>>
>>>for (int i : iota_view{1, 10})
>>> cout << i << ' '; // prints 1 2 3 4 5 6 7 8 9 10
>>
>> Also, if you don't have C++20 as an option, or don't want to wait, you
>> can use the Ranges v3 library by Eric Niebler who wrote the spec for
>> ranges in C++ 20.
>><https://github.com/ericniebler/range-v3>
>
> I think that this is pointless. Take a look at golang, they recommend
> ordinary for loop for this...

Doesn't mean much without the rationale, unless we all agree that "they"
(who?) are usually right, and that Go advise extends to C++.

I've happily used range() a lot in Python, and seq(1) in the shell
... but neither of those are C++.