Fill an iterator range

[Kaba]

Hi,

Problem: Given is a forward iterator range [begin, end[ that we know is
200 elements long and where iterators dereference to int. Fill the first
100 elements with the value 1, and the next 100 elements with value 2.

Sounds easy, right? Let's start with those 1's:

std::fill_n(begin, 100, 1);

But now, we don't know the starting iterator for the 2's. We need to do:

std::advance(begin, 100);

and only after then:

std::fill_n(begin, 100, 2);

While this works, the std::advance function can spend 100 increments to
move a pure forward iterator, all work that is actually already being
done inside fill_n, but then discarded.

Any idea how to avoid using std::advance?

I think this could be solved by implementing somekind of reference
iterator which would redirect all functionality to a member iterator
which is hold by reference. Maybe Boost has something like this?

 

[Alf P. Steinbach]

* Kaba:

Hi,

Problem: Given is a forward iterator range [begin, end[ that we know is
200 elements long and where iterators dereference to int. Fill the first
100 elements with the value 1, and the next 100 elements with value 2.

Sounds easy, right? Let's start with those 1's:

std::fill_n(begin, 100, 1);

But now, we don't know the starting iterator for the 2's. We need to do:

std::advance(begin, 100);

and only after then:

std::fill_n(begin, 100, 2);

While this works, the std::advance function can spend 100 increments to
move a pure forward iterator, all work that is actually already being
done inside fill_n, but then discarded.

Any idea how to avoid using std::advance?

This sounds like a homework question, but OK.

for( int v = 1; v <= 2; ++v )
{
for( int i = 0; i < 100; ++i )
{
*begin = v;
++begin;
}
}

I think this could be solved by implementing somekind of reference
iterator which would redirect all functionality to a member iterator
which is hold by reference. Maybe Boost has something like this?

Possibly, but it would probably slow down things rather than speed them up.

I think, as general advice, do not be afraid to use ordinary loops; that's what
they're there for.


Cheers & hth.,

- Alf

 

[Kaba]

This sounds like a homework question, but OK.

That means I have succeeded in defining the problem clearly

for( int v = 1; v <= 2; ++v )
{
for( int i = 0; i < 100; ++i )
{
*begin = v;
++begin;
}
}



Possibly, but it would probably slow down things rather than speed them up.

I think, as general advice, do not be afraid to use ordinary loops; that's what
they're there for.

There are optimizations hidden in std::fill_n for certain cases, such as
when the iterator is actually a pointer to a native type. That's why I
wouldn't like to go for loops.

Replace forward iterators with output iterators for an even tougher
problem where std::advance isn't defined.

 

[Alf P. Steinbach]

* Kaba:

That means I have succeeded in defining the problem clearly


There are optimizations hidden in std::fill_n for certain cases, such as
when the iterator is actually a pointer to a native type. That's why I
wouldn't like to go for loops.

Thinking about that sounds to me like a clear case of premature optimization

Replace forward iterators with output iterators for an even tougher
problem where std::advance isn't defined.

And this even more so.

Google up "knuth premature optimization" (or variations thereof).

Measure your app in the form that you'll deliver it.


Cheers & hth.,

- Alf

 

[Kaba]

Thinking about that sounds to me like a clear case of premature optimization

Alf, you have to see beyond the problem I'm posing. The problem I
describe contains the essentials of a general problem one faces in
generic programming. When doing generic programming, optimizations such
as what goes under the hood in std::fill_n become very important, as I
am sure you know.

The bottom line here is this: using C++ standard library, and assuming I
need to fill the values to an output iterator, I actually am not able to
solve the problem using std::fill_n. Assuming forward iterators I am
able to solve the problem using std::advance, but with performance
degradation and loss in genericy.

As you say, creating an iterator which references another iterator to
simulate pass-by-reference for std::fill_n will probably slow down
things because of possible indirection (compiler might optimize).

It seems to me that the only good solution would be to have the
std::fill_n to return an iterator to one-past-last element which was
filled.

What do you think?

 

[Kaba]

It seems to me that the only good solution would be to have the
std::fill_n to return an iterator to one-past-last element which was
filled.

Looking at the current draft for C++0x:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3035.pdf

The std::copy_n which is to be part of C++0x is defined as returning the
one-past-last element which was copied. However, std::fill_n is not
specified to return anything.

 

[Thomas J. Gritzan]

Am 28.02.2010 01:32, schrieb Kaba:

Alf, you have to see beyond the problem I'm posing. The problem I
describe contains the essentials of a general problem one faces in
generic programming. When doing generic programming, optimizations such
as what goes under the hood in std::fill_n become very important, as I
am sure you know.

The bottom line here is this: using C++ standard library, and assuming I
need to fill the values to an output iterator, I actually am not able to
solve the problem using std::fill_n. Assuming forward iterators I am
able to solve the problem using std::advance, but with performance
degradation and loss in genericy.

As you say, creating an iterator which references another iterator to
simulate pass-by-reference for std::fill_n will probably slow down
things because of possible indirection (compiler might optimize).

You can use std::generate and use a generator that generates 100x 1 and
after that 100x 2.

It seems to me that the only good solution would be to have the
std::fill_n to return an iterator to one-past-last element which was
filled.

What do you think?

Think about it: fill_n might, as you say, be optimized for simple types.
It could use memset, some compiler intrinsic or similar. Using memset,
however, you won't get the one-past-last iterator, so this optimization
would be impossible if you specify fill_n to return the one-past-last
iterator. A simple loop would be equal in speed.

 

[Alf P. Steinbach]

* Kaba:

Alf, you have to see beyond the problem I'm posing. The problem I
describe contains the essentials of a general problem one faces in
generic programming. When doing generic programming, optimizations such
as what goes under the hood in std::fill_n become very important, as I
am sure you know.

The bottom line here is this: using C++ standard library, and assuming I
need to fill the values to an output iterator, I actually am not able to
solve the problem using std::fill_n. Assuming forward iterators I am
able to solve the problem using std::advance, but with performance
degradation and loss in genericy.

As you say, creating an iterator which references another iterator to
simulate pass-by-reference for std::fill_n will probably slow down
things because of possible indirection (compiler might optimize).

It seems to me that the only good solution would be to have the
std::fill_n to return an iterator to one-past-last element which was
filled.

What do you think?

Seeing that you understand the issues I recommend posting this suggestion to
[comp.std.c++].

And/or perhaps [comp.lang.c++.moderated], where there is a wider audience.

I think it would be practically very useful change, and it doesn't seem to
affect existing code.


Cheers,

- Alf

 

[Alf P. Steinbach]

* Thomas J. Gritzan:

Am 28.02.2010 01:32, schrieb Kaba:

You can use std::generate and use a generator that generates 100x 1 and
after that 100x 2.

Uh, introducing the slight inefficiency one wants to get rid off.

Think about it: fill_n might, as you say, be optimized for simple types.
It could use memset, some compiler intrinsic or similar. Using memset,
however, you won't get the one-past-last iterator, so this optimization
would be impossible if you specify fill_n to return the one-past-last
iterator. A simple loop would be equal in speed.

*Hark*. When fill_n detects that it can use memset, then it knows that it's
handling raw pointers. And then the end pointer can be computed directly.


Cheers,

- Alf (just assuming that the name is really 'fill_n', I can't recall)

 

[Kaba]

What do you think?

Seeing that you understand the issues I recommend posting this suggestion to
[comp.std.c++].

And/or perhaps [comp.lang.c++.moderated], where there is a wider audience.

I think it would be practically very useful change, and it doesn't seem to
affect existing code.

Thanks Alf, I'm posting the suggestion to comp.std.c++.

 

[Thomas J. Gritzan]

Am 28.02.2010 02:31, schrieb Alf P. Steinbach:

* Thomas J. Gritzan:

*Hark*. When fill_n detects that it can use memset, then it knows that
it's handling raw pointers. And then the end pointer can be computed
directly.

Yeah I got that in the meantime. I think it is a good idea to add that
if it's possible.