std algorithm replacement for this for loop?

Could you invert the mapping, to use std::generate?

You mean call std::generate over the values in a? Won't work in this case because a.size() > b.size(), which I should've specified. a already has data in it, some of which is getting replaced with what is in b, and b_to_a_index says where each item in b goes in a.

How can I write the following loop elegantly using a lambda and an std algorithm? It's just putting b[n] in position b_to_a_index[n] in a.

Having never worked with lambda expressions (or for_each or generate, for that matter), I found your question fun and educational - an opportunity to go familiarise myself with some of stl and modern c++ that I've so far been able to ignore . Too much working on old code around here...

The best I could come up with was the relatively useless and ungainly:


int pos = 0;
std::for_each( b.begin(), b.end(), [&pos,&a,&b_to_a_index](a_b_type x) { a[b_to_a_index[pos++]]=x; } );


but at least I got something out of it ;)

I wonder though - isn't b_to_a_index an intrinsic property of b, since b is (apparently) by definition a subset of a? So couldn't the assignment simply become this:?
std::for_each( b.begin(), b.end(), [&a](a_b_type &bval) { a[bval.a_pos] = bval; } );

And out of interest, - since I've managed to avoid the finer points of stl in the last decade or so - what's the benefit of using stl to traverse that array/vector over this:?

for (size_t i = 0; i < b.size(); ++i)
a[b.a_pos] = b;


[size="1"]also... first post, so be gentle ;)

I wonder though - isn't b_to_a_index an intrinsic property of b, since b is (apparently) by definition a subset of a?

No because b_to_a_index is apparently a different array than b. And in lots of circumstances it must be, like if you wanted to create an alternate ordering of an existing array.

[quote name='latent']
And out of interest, - since I've managed to avoid the finer points of stl in the last decade or so - what's the benefit of using stl to traverse that array/vector over this:?

for (size_t i = 0; i < b.size(); ++i)

[/quote]

There is no real benefit, unless you find that iterators give marginally better performance.

No because b_to_a_index is apparently a different array than b. And in lots of circumstances it must be, like if you wanted to create an alternate ordering of an existing array.

Ah yes, of course.

There is no real benefit, unless you find that iterators give marginally better performance.

Cheers.

The for_each algorithm is hardest to justify, but when you're using some of the more advanced algorithms it becomes much easier. It is a no-brainer to compare a call to std::sort() to writing the sort algorithm by hand.

The main benefit is that the standard algorithms make intent explicit. When you see a loop over a container, you know nothing.

for (size_t i = 0; i < b.size(); ++i)
{
// ...
}

Is this loop guaranteed to iterate over all items in the array? We have no idea, there could be break, return or throw statements (or a dreaded goto) in the body somewhere. Even more confusing, it might modify i in the loop, e.g. reset it to zero or decrement it under certain conditions.

By contrast, you know exactly what std::for_each() is going to do. It will hit each element once and only once. std::find() or std::find_if() will seach linearly until the predicate is passed. Granted, exceptions could still break these guarantee.

Also the std algos. don't make the classic mistake of doing for(size_t i = 0; i < container.size(); ++i) for an algo which doesn't change the size content of the container.

And out of interest, - since I've managed to avoid the finer points of stl in the last decade or so - what's the benefit of using stl to traverse that array/vector over this:?

for (size_t i = 0; i < b.size(); ++i)
a[b.a_pos] = b;


[size="1"]also... first post, so be gentle ;)

An idiomatic iterator-based traversal won't redundantly call size() every loop iteration. Moreover, iterators are general across container types; in this particular situation you need an operator[] with particular semantics, but if you're doing something general, like summing the values in a container, using iterators allows you to swap out container types without rewriting code (assuming you typedef correctly!).

You could define your own for_each that iterates through two containers at the same time (something I've often felt would be nice to have as standard).

[source lang="cpp"]
template

void for_each2(InIt1 begin1, InIt1 end1, InIt2 begin2, Fn fn)
{
for (; begin1 != end1; ++begin1, ++begin2)
{
fn(*begin1, *begin2);
}
}

template
struct indexer
{
explicit indexer(T& out): out(out) {}

void operator()(typename T::value_type value, typename T::value_type index)
{
out[index] = value;
}

private:
T& out;
};

int main(int, char*[])
{
typedef boost::array array_t;

array_t indices = { 0, 2, 1, 3, 4, };
array_t values = { 1, 2, 3, 4, 5, };
array_t new_values;

for_each2(values.begin(), values.end(), indices.begin(), indexer(new_values));

std::copy(new_values.begin(), new_values.end(), std::ostream_iterator(std::cout, " "));
std::cout << std::endl;
}
[/source]

(I'm sure you can replace the indexer with a lambda... I'm still using MSVC 2008).

Biggest problem is that, despite being called lambda, the constructs are anything but.

If trying to design actual lambda, the original code would likely be structured differently.

There is also a lot of ubiquity and undefined behavior. Can b2a contain duplicates? What happens if b2a points out of range of a, if it's different size of b, ....

I wonder though - isn't b_to_a_index an intrinsic property of b, since b is (apparently) by definition a subset of a? So couldn't the assignment simply become this:?[/quote]

Yes, that would be called currying (in lambda calculus).

In this case it doesn't help and unless original data is structured that way merely adds overhead.

For a lambda, one could take b2a and b to produce curried form with positions (result would be function with values "hard-coded"), which would then be applied (maybe mapped) to a. Or similar.

The original code is readily comprehendible. In this case, lamda functions seem like a solution looking for a problem. Unless this is an academic exercise, of course.

Sorry for the non-answer, but I'm not sure there is a better way of doing it.

An idiomatic iterator-based traversal won't redundantly call size() every loop iteration.

Is size() really called every iteration? I remember wondering about that a while ago, but dismissed it as being something that could probably be avoided by the compiler. Not so?

Look at the generated assembly. Using GCC, I see no calls to size() once I pass -O1.

For trivial loops, the size() call can be elided. For loops which do not use constant iterators, modify the contents of the container, etc. it is possible (even likely) that the compiler takes the safest route and re-issues the call every iteration. Of course the best way to know is to look at the assembly, but in general, IMHO it is better to make your code clear first. If you don't intend to call size() every iteration, don't put the call in the per-iteration condition check of a for() loop. Cache it in a temporary instead.

This has the benefit of making your intent clear to later readers of the code, as well as possibly allowing the compiler to make optimizations in certain situations that would have been deemed unsafe otherwise.

Calling size on a vector probably won't cost you anything in real cases. it's typically something like "inline size_t size() const { return size_; }" for a std::vector which will be inlined in almost every case and is therefore pretty much just a memory access. But if you are writing a generic algorithm that calls size a lot and use it on a std::list you are in for a surprise ;). On the other hand the typical "i<container.size()"-loop that uses operator[] won't compile with a std::list anyway.

I usually end up writing for (int i = 0, e = vec.size(); i < e; ++i) { ... } simply to prevent the compiler from giving signed/unsigned comparison warnings.