Sign in to follow this  
jden

"Automatic" fill

Recommended Posts

jden    100
Hi,
Im testing the fill <algorithm> command.
I want to fill a vector of five elements with numbers 1 - 5.
I think a for loop could do this. But there is a problem:

vector<int> vec(5);
for(int f = 1; f < 5; ++f)
{
fill( vec.begin()+(--f), vec.end(), f );
}

As you can see I want to start at position 0, and with the val 1. Then it should
automatically assign each value every iteration.
Logically I think it would work, but instead it becomes an endless loop.
I know I could do one more value and it would work, but do you see any thinner solution or answer? Thanks!


Share this post


Link to post
Share on other sites
_the_phantom_    11250
Think logically about what the '--f' is doing in that loop and you'll soon realise why it becomes an infinite loop.

I'm pretty sure you have a nice chunk of undefined behaviour there as well with the args to the 'fill' function; if memory serves the order parameters are evaluated aren't fixed, and I'm pretty sure the access/modification to 'f' is undefined as well (lack of sequence points).
(Someone correct me if I'm wrong here).

Share this post


Link to post
Share on other sites
jmastro    114
Quote:
Original post by Chris_F

vector<int> vec(5);
int f = 1;
for(auto it = vec.begin(); it != vec.end(); ++it)
{
*it = f++;
}


You can simplify it even more if you're going to use C++0x, by using initializer lists (assuming compiler support is there currently):


std::vector<int> vec = {1, 2, 3, 4, 5};

Share this post


Link to post
Share on other sites
jden    100
From your answers I think I now know why it doesn't work, the for-loop is
a statement in which a formal parameter always increment it's own scope no matter if you try to use it just for positioning instructions only:

fill(vec.begin() + 0, vec.end(), 1)
->
fill(vec.begin() + 4, vec.end(), 5)
---------------------------------- =
fill(vec.begin() +(--f), vec.end(), f)

Besides your examples, this also works well :
fill(vec.begin()+f, vec.end(), f + 1)

But is it someway possible to make use of "icrementing / decrementing instructions" in iterative loops at all?

Share this post


Link to post
Share on other sites
visitor    643
Basically you are just trying to use an algorithm for something that it is not supposed for. Why use a O(n*n) algorithm for a O(n) operation?

There are many better ways, e.g using a counting_iterator from boost.


#include <vector>
#include <boost/iterator/counting_iterator.hpp>
#include <iostream>
#include <algorithm>
#include <iterator>

int main()
{
std::vector<int> vec(5);
std::copy(boost::make_counting_iterator(1), boost::make_counting_iterator(6), vec.begin());

std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
}

Share this post


Link to post
Share on other sites
alvaro    21246
I didn't understand what the OP problem is, sorry.

I just wanted to point out that this statement is undefined behavior:
fill( vec.begin()+(--f), vec.end(), f );


You are modifying f and using it in another part of the expression, without a sequence point in between.

Share this post


Link to post
Share on other sites
Zahlman    1682
The purpose of std::fill is to assign the same value to many elements of a sequence.

What you are trying to do is assign a different value to each of several elements, following some rule. The natural choice of standard library algorithm for this is std::generate.

The example of std::generate given in this doc even solves your specific problem.

You can also use a "counting iterator" (via third-party tools, or rolling it yourself) as shown in visitor's code. The idea is that we have objects that obey the iterator interface while pretending to "iterate" over a virtual, not-actually-existing "container" of all the integers in order; then we use the standard library algorithm std::copy to copy from this virtual container into a real one in order to get a sequence of real elements.

The infinite loop in your code is caused by the fact that '--f' changes the value of f in addition to simply producing the value used in your calculation. This cancels out the '++f' in the for-loop clause, so each time through the loop, 'f' has the same value, and the loop-exit condition is never met.

EDIT: Except for the part where, as alvaro correctly points out, this actually invokes undefined behaviour, although all practical compilers would produce something that ends up in an infinite loop (it's just that the actual effects on the container might vary).

Share this post


Link to post
Share on other sites
jden    100
Then if it is undefined behavior, the generate command doesn't solve it neither, and I did a test on it also. I haven't got so far to really understand this: "Lack of sequence points" , but probably it will show itself later.

Share this post


Link to post
Share on other sites
SiCrane    11839
The undefined behavior comes from using the decrement operator in your loop on a variable that you access again in the function call. Calling the std::generate() would presumably not suffer from that problem since you would need neither the loop nor the decrement. How exactly did you test it?

Share this post


Link to post
Share on other sites
jden    100
Sorry for the delay.
The generate works good the other way around (functions and iterators). But what I meaned with this specific problem is that it cannot be used like this:

vector<int> vec(5);
for(int f = 1; f < 5; ++f)
{
generate( vec.begin()+(--f), vec.end(), f );
}

Because as you said it access the scoped value multiple times.





Share this post


Link to post
Share on other sites
taz0010    277
std::fill is designed to fill the range with the same value, not different ones. But if you want to force the behaviour for some reason then it is possible.


class Increment{
public:
Increment(){
x = 1;
}
operator int() const{
return x++;
}
mutable int x;

};



int main(){
std::vector<int> v(5);
std::fill(v.begin(),v.end(),Increment());


It's necessary to mark Increment's cast operator as const because std::fill accepts it's value as a const reference. I have no idea if this code is guaranteed to function correctly under the standard or not. The standard mightn't forbid Increment being assigned more times than necessary, in which case the code would break on that implementation.

This is frivulous use of the algorithm functions because all you really need to assign the values 1-5 is:

std::vector<int> v(5);
for(int i=0;i<5;i++)
v[i] = i+1;

Or even:

int vals[] = {1,2,3,4,5};
std::vector<int> v(vals,vals+5);

Share this post


Link to post
Share on other sites
Perost    332
Regarding sequence points, a sequence point is a point in the code where the side-effects of the previous code has been evaluated. C++ does not specify in which order function arguments should be evaluated, so a compiler is free to evaluate a functions arguments in whichever order it wants. When you try to do
fill(vec.begin() + (--f), vec.end(), f);
you therefore have no way of telling what the value of the last f is, since it may or may not have been decremented.

And you still seem to be confused about what algorithms such as fill and generate does. These algorithms work on a range defined by a begin and end iterator. If you were to execute the follow code:

vector<int> vec(5);
for(int f = 1; f <= 5; ++f)
{
fill(vec.begin() + (f - 1), vec.end(), f);
}



this is what will happen:

fill(vec.begin() + 0, vec.end(), 1) => vec = {1, 1, 1, 1, 1}
fill(vec.begin() + 1, vec.end(), 2) => vec = {1, 2, 2, 2, 2}
fill(vec.begin() + 3, vec.end(), 3) => vec = {1, 2, 3, 3, 3}
fill(vec.begin() + 4, vec.end(), 4) => vec = {1, 2, 3, 4, 4}
fill(vec.begin() + 5, vec.end(), 5) => vec = {1, 2, 3, 4, 5}



So if you fix the problems in your code that leads to undefined behaviour it will indeed work. But, you will have used (n^2 + n)/2 = 15 (with n = 5) assignments, instead of just assigning each elements once (you're using a quadratic algorithm instead of a linear one). If you use a vector with 100 elements you will instead have to do 5050 assignments instead of 100. I'm sure that you realize that that's not a good way of solving the problem.

So if you wish to assign each element in a vector some value, use either a for-loop or an algorithm such as generate, but not both.

Share this post


Link to post
Share on other sites
Zahlman    1682
Quote:
Original post by jden
Then if it is undefined behavior, the generate command doesn't solve it neither, and I did a test on it also. I haven't got so far to really understand this: "Lack of sequence points" , but probably it will show itself later.


The entire point of using std::fill, std::generate, and everything else of that sort is to avoid writing your own loop. They replace loops in your code.

I will walk you through it step by step.

We will call std::generate, one time, to put every desired value into the vector. std::generate will call a 'predicate', several times - once for each value in the range - to determine what value to use.

So, first we make a predicate that will return values in ascending order. The neat, reusable way to do this is to use a class which overloads the operator(). This operator lets us treat objects of the class as if they were functions.

We make an class that stores a counter, and implements its operator() by incrementing the counter and returning the value. Since we want the values in the vector to start with 1, we will start the counter at 0. That way, it will increase to 1 the first time it gets called by std::generate().

So, our predicate looks like this:


class counter {
int value;
public:
counter(): value(0) {}
int operator()() { ++value; return value; }
};



Nice and simple, right? And we can probably find other uses for it later, too.

Now we use it with std::generate:


vector<int> vec(5);
// We create a counter, without naming it, and pass it to std::generate.
// std::generate calls it once for each element, each time increasing the value.
std::generate(vec.begin(), vec.end(), counter());



Notice that we did not write 'for' or 'while' or anything like that anywhere. That is because looping is the job of the standard library function.

std::fill is a simpler, but less flexible utility: instead of using a predicate, you just give it a value. That means the same value will be written to the entire range, but you don't have to write a predicate.




As for the 'sequence points' thing, you absolutely must understand this to write proper C++. Please put down everything else you are doing and learn this first. The problem with sequence points has nothing to do with how you call std::fill or std::generate. It has everything to do with how you use the variable 'f'.

You may not write "foo(something + (--f), another_thing, f)", no matter what 'foo', 'something' and 'another_thing' actually are. There is no guarantee of ordering between the parameters. This line of code does not mean "calculate something + --f, then calculate another_thing, then calculate f, then pass it all to foo". It means "calculate these three things that I wrote, in whatever order you like, and pass them to foo (in the order I wrote them)". '--f' changes the value of f. Therefore it absolutely matters whether this is done before or after 'f' is calculated.

What you really meant, instead of '--f', was 'f - 1'. That does not change the value of f. But then there is still no point to using a standard library algorithm, if you are going to write the loop anyway.

Share this post


Link to post
Share on other sites
Zahlman    1682
Quote:
Original post by taz0010
std::fill is designed to fill the range with the same value, not different ones. But if you want to force the behaviour for some reason then it is possible.... I have no idea if this code is guaranteed to function correctly under the standard or not.


Don't say you can do something and then admit that you don't know that it's valid.

And don't abuse implicit casting and 'mutable' to try to make std::fill do what you want, when std::generate does what you want.

Share this post


Link to post
Share on other sites
jden    100
Thanks Zahlman.
Ok, so how to insert a sequence point manually?

Wiki says that sequence points is created with some operators and function calls etc? And forget about the algorithms as they really have no directly connections(?) to undefined behaviors.

This one is the same:
vector<int> vec(5);
for(int f = 1; f < 5; ++f)
{
vec[--f] = f; // Like: vec[0] = 1;.. up to five
}

Share this post


Link to post
Share on other sites
swiftcoder    18432
Quote:
Original post by jden
Ok, so how to insert a sequence point manually?
You don't. Instead you write code that does not present with a lack of sequence points.
Quote:
vector<int> vec(5);
for(int f = 1; f < 5; ++f)
{
vec[--f] = f; // Like: vec[0] = 1;.. up to five
}
The reason this doesn't work has very little to do with sequence points, and very much to do with the *logic* being incorrect.

--f does not mean f-1, as you seem to believe. It means f = f-1.

And since you use ++f to increment once per loop, the decrement is going to cancel that out, so you are going to loop infinitely over the first element in the array.

Share this post


Link to post
Share on other sites
jden    100
I mean, it's not like writing this: f = --f; So I don't see the logic.I only know that everywhere --/++ is used it's going to change the actual value included with that.

Share this post


Link to post
Share on other sites
KulSeran    3267
Maybe you should look at the output of a simpler program and see what those operators are actually doing.

#include <iostream>

int main()
{
int f = 0;
f = 1; std::cout << f << std::endl;
f += 1; std::cout << f << std::endl;
f = f + 1; std::cout << f << std::endl;
// now the tricky stuff
int i = f++;
std::cout << i << " " << f << std::endl;
i = ++f;
std::cout << i << " " << f << std::endl;
//sooooooo f++ increments right?
for( int j = 0; j < 5; ++j )
{
// and j-- decrements.....
--j;
// so j still = 0....
// so this loops forever
}
}





The --/++ operators modify the variable they are used on.
Just write your loop properly by starting at 0 so you don't get confused with it...

vector<int> vec(5);
for(int f = 0; f < 5; ++f)
{
vec[f] = f;
}


Share this post


Link to post
Share on other sites
Zahlman    1682
Quote:
Original post by jden
I only know that everywhere --/++ is used it's going to change the actual value included with that.


Yes; and in your case you do not want that to happen.

Quote:
So I don't see the logic.


So think about it more. Think about every change that happens to 'f' each time through the loop.

Share this post


Link to post
Share on other sites
rip-off    10976
I think there is a good case to be made for never using the increment/decrement operators except as a standalone statement. Saving the extra line it takes to be explicit about whether the value is to be increased or decreased before or after the statement in question isn't really worthwhile IMO.

Share this post


Link to post
Share on other sites
alvaro    21246
Quote:
Original post by rip-off
I think there is a good case to be made for never using the increment/decrement operators except as a standalone statement. Saving the extra line it takes to be explicit about whether the value is to be increased or decreased before or after the statement in question isn't really worthwhile IMO.


I've never made it an explicit rule, but I think I agree.

When I was programming in C and didn't have std::vector<T>::push_back, I used to get similar results on fixed arrays by doing
  moves[n_moves++] = new_move;


But I don't think I've written anything of that sort in many years.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this