for_each

[Fraser Ross]

Is it wrong to describe for_each as a modifying algorithm? It is
described as one here: http://www.josuttis.com/libbook/algolist.pdf.
transform appears to be the algorithm to use for modifying elements in a
range.

Fraser.

Posted Via Usenet.com Premium Usenet Newsgroup Services
----------------------------------------------------------
** SPEED ** RETENTION ** COMPLETION ** ANONYMITY **
----------------------------------------------------------
http://www.usenet.com

[Kai-Uwe Bux]

Daniel T. wrote:

In article <ee**********@m urdoch.acc.Virg inia.EDU>,
Kai-Uwe Bux <jk********@gmx .netwrote:

>Daniel T. wrote:

"Fraser Ross" <fraserATmember s.v21.co.ukwrot e:
"Daniel T."
for_each is a non-modifying algorithm does not explicitly modify the
contents of the container. The functor passed into for_each might,
but the algorithm doesn't.

I think the intention is that although the algorithm doesn't prevent
modification it is expected anyway that the functor does not modify
elements.

The rule of non-modifying vs modifying is amazingly simple. All
modifying sequences algorithms call op= on the elements in at least one
of the sequences it operates on, non-modifying sequence algorithms
don't. As such, for_each is a non-modifying sequence algorithm. The
*algorithm* doesn't modify any of the elements of the sequence (even if
the functor passed in does.)

Do you have any hint for that in the standard? Please consider:

In the code below. std::reverse calls the assignment op of the vectors
contained in the vec_vec. Note:

int main ( void ) {
std::srand( 12 );
log_assignment: :start_logging( );
std::vector< log_assignment a ( 2 );
std::vector< log_assignment b ( 2 );
std::cout << "test whether vector assignments trigger logging:\n";
a = b;
std::cout << "test reverse on vec_vec for assignments of vectors:\n";
std::reverse( a.begin(), a.end() );
}

produces the output:

test whether vector assignments trigger logging:
assignment
assignment
test reverse on vec_vec for assignments of vectors:
assignment
assignment

True. So now, we have an example where reverse calls operator= and one
example where it does not (see below). Whether operator= is called or not
seems to be an implementation detail that even depends on the types passed
to the template function: in some cases reverse() calls operator=, in some
cases, it does not. Also, I do not know of any provision in the standard
that reverse calls operator=. I infer that your proposed "simple rule" is
unreliable at best, misleading at worst, but foremost not based upon
anything in the standard.
Best

Kai-Uwe Bux

PS: I leave the original exmaple for future reference, should this thread
continue:

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

class log_assignment {

unsigned long data;

static
bool & do_log ( void ) {
static bool log = false;
return ( log );
}

public:

log_assignment ( void )
: data ( std::rand() )
{}

bool operator< ( log_assignment other ) const {
return ( data < other.data );
}

log_assignment & operator= ( log_assignment other ) {
data = other.data;
if ( do_log() ) {
std::cout << "assignment \n";
}
return ( *this );
}

static
void start_logging ( void ) {
do_log() = true;
}

};
int main ( void ) {
std::srand( 12 );
std::vector< std::vector< log_assignment vec_vec;
for ( unsigned int i = 0; i < 21; ++i ) {
std::vector< log_assignment dummy ( 25 );
vec_vec.push_ba ck( dummy );
}
log_assignment: :start_logging( );
std::vector< log_assignment a ( 2 );
std::vector< log_assignment b ( 2 );
std::cout << "test whether vector assignments trigger logging:\n";
a = b;
std::cout << "test reverse on vec_vec for assignments of vectors:\n";
std::reverse( vec_vec.begin() , vec_vec.end() );
}
On my machine, this outputs:

test whether vector assignments trigger logging:
assignment
assignment
test reverse on vec_vec for assignments of vectors:

[Kai-Uwe Bux]

Kai-Uwe Bux wrote:

Also, note that there is no guarantee that std::swap uses operator= by
default: as far as I can tell, there could be an implementation like so

// stolen from Boost:
template < typename T >
T * address_of (T & t) {
return (
reinterpret_cas t<T*>(
& const_cast<char &>(
reinterpret_cas t<const volatile char &>( t ) ) ) );
}

template < typename T >
void swap ( T & a, T & b ) {
T dummy ( a );
new ( address_of( a ) ) T ( b );
new ( address_of( b ) ) T ( dummy );
}

Rats, I guess, here I am leaking resources. So an improved version would be:

// stolen from Boost:
template < typename T >
T * address_of (T & t) {
return (
reinterpret_cas t<T*>(
& const_cast<char &>(
reinterpret_cas t<const volatile char &>( t ) ) ) );
}

template < typename T >
void copy_assign ( T & lhs, T & rhs ) {
T * ptr = address_of( lhs );
ptr->~T();
new ( ptr ) T ( rhs );
}

template < typename T >
void swap ( T & a, T & b ) {
T dummy ( a );
copy_assign( a, b );
copy_assign( b, dummy );
}

Looks wicked -- criticism welcome.
Best

Kai-Uwe Bux

[Kai-Uwe Bux]

Daniel T. wrote:

Jerry Coffin <jc*****@taeus. comwrote:

>da******@earthl ink.net says...

>>>All your code proves is that you're apparently unaware of the
requiremen t in section 23.1/3 that anything you store in a vector
be assignable.

What it proves is that sort assigns to items contained in the
vector, thus literally modifying the elements in the container.
Exactly what Pete claimed it didn't do. Well, it does do it, just
like every other modifying algorithm, and unlike any of the
non-modifying algorithms.

Wrong. The moment you put something into the container that isn't
assignable, all you have is undefined behavior. Period. The end. You
don't have any proof of anything about any algorithm you might
choose to attempt to apply to the container. Undefined behavior is
undefined behavior, NOT a proof.

Jerry (and Pete) are asserting that I am wrong? Are you asserting that
(a) there is a non-modifying algorithm that assigns to elements of a
container and/or (b) there is a modifying algorithm that doesn't?

If you are, then state which algorithm it is otherwise accept it.

std::reverse() is not required to use operator= and there can be compliant
implementations of the standard library where it never does.

From the standard [25.2.9]:

Reverse [lib.alg.reverse]

template<class BidirectionalIt erator>
void reverse(Bidirec tionalIterator first, BidirectionalIt erator last);

Effects: For each non-negative integer i <= (last - first)/2, applies
iter_swap to all pairs of iterators first + i, (last - i) - 1.

Complexity: Exactly (last - first)/2 swaps.

Thus, std::reverse() will not call operator= for any class that has a
specialized swap method that happens to be not defined in terms of its
operator=.

Also, note that there is no guarantee that std::swap uses operator= by
default: as far as I can tell, there could be an implementation like so

// stolen from Boost:
template < typename T >
T * address_of (T & t) {
return (
reinterpret_cas t<T*>(
& const_cast<char &>(
reinterpret_cas t<const volatile char &>( t ) ) ) );
}

template < typename T >
void swap ( T & a, T & b ) {
T dummy ( a );
new ( address_of( a ) ) T ( b );
new ( address_of( b ) ) T ( dummy );
}

Similarly, if your library chooses to implement std::sort entirely in terms
of comparisons and swaps, there will be no calls to operator= if swap is
implemented based upon copy construction.

Come to think of it: most likely the copy-constructor trick could be used in
a standard library throughout so that operator= will never be called unless
explicitly required by the standard.
Best

Kai-Uwe Bux

[Daniel T.]

Kai-Uwe Bux <jk********@gmx .netwrote:

True. So now, we have an example where reverse calls operator= and
one example where it does not (see below).

No we don't. We have my example that calls op= of the things that the
vector contains, and your example that also calls op= of the things that
the vector contains.

I infer that your proposed "simple rule" is unreliable at best,
misleading at worst, but foremost not based upon anything in the
standard.

Your example is misleading at best, and dishonest at worst.

--
There are two things that simply cannot be doubted. Logic and our
ability to sense the world around us. Doubt those, and you no longer
have anyone to discuss it with, nor any ability to discuss it.

[Daniel T.]

Kai-Uwe Bux <jk********@gmx .netwrote:

Kai-Uwe Bux wrote:

>Also, note that there is no guarantee that std::swap uses operator=
by default: as far as I can tell, there could be an implementation
like so

// stolen from Boost:
template < typename T >
T * address_of (T & t) {
return (
reinterpret_cas t<T*>(
& const_cast<char &>(
reinterpret_cas t<const volatile char &>( t ) ) ) );
}

template < typename T >
void swap ( T & a, T & b ) {
T dummy ( a );
new ( address_of( a ) ) T ( b );
new ( address_of( b ) ) T ( dummy );
}

Rats, I guess, here I am leaking resources. So an improved version
would be:

// stolen from Boost:
template < typename T >
T * address_of (T & t) {
return (
reinterpret_cas t<T*>(
& const_cast<char &>(
reinterpret_cas t<const volatile char &>( t ) ) ) );
}

template < typename T >
void copy_assign ( T & lhs, T & rhs ) {
T * ptr = address_of( lhs );
ptr->~T();
new ( ptr ) T ( rhs );
}

template < typename T >
void swap ( T & a, T & b ) {
T dummy ( a );
copy_assign( a, b );
copy_assign( b, dummy );
}

Looks wicked -- criticism welcome.

Yes, it looks wicked. The lengths you are going through to modify the
elements of the container without calling op= are incredible. Do you
really think that because you are implementing op= outside of the object
contained that this makes a difference?

But I will resend my statement. How about this instead:

All non-modifying algorithms can be called with const iterators passed
in, modifying algorithms cannot.

--
There are two things that simply cannot be doubted. Logic and our
ability to sense the world around us. Doubt those, and you no longer
have anyone to discuss it with, nor any ability to discuss it.

[Kai-Uwe Bux]

Daniel T. wrote:

Kai-Uwe Bux <jk********@gmx .netwrote:

>True. So now, we have an example where reverse calls operator= and
one example where it does not (see below).

No we don't. We have my example that calls op= of the things that the
vector contains, and your example that also calls op= of the things that
the vector contains.

You are missing the point: it does not call operator= for what the vector
contains that is passed to reverse(). It calls

swap< std::vector< log_assignment

(as required by the standard, see my remarks elsethread), which does *not*
invoke std::vector< log_assignment >::operator=.

>

> I infer that your proposed "simple rule" is unreliable at best,
misleading at worst, but foremost not based upon anything in the
standard.

Your example is misleading at best, and dishonest at worst.

Nope.
Best

Kai-Uwe Bux

[Kai-Uwe Bux]

Daniel T. wrote:

Kai-Uwe Bux <jk********@gmx .netwrote:

>Kai-Uwe Bux wrote:

[snip]

>template < typename T >
void swap ( T & a, T & b ) {
T dummy ( a );
copy_assign( a, b );
copy_assign( b, dummy );
}

Looks wicked -- criticism welcome.

Yes, it looks wicked. The lengths you are going through to modify the
elements of the container without calling op= are incredible.

True. But it's fun.

Do you really think that because you are implementing op= outside of the
object contained that this makes a difference?

I thought about this. Actually, it is somewhat disturbing that the above
could be a standard compliant implementation of swap. For instance, for
proxy classes it makes a difference (although you just get a different
bug):

a) here is the bug that the obvious implementation of std::swap has:

#include <bitset>
#include <iostream>
#include <string>

typedef std::bitset<8by te;

int main ( void ) {
byte x ( std::string( "00010" ) );
byte::reference a = x[0];
byte::reference b = x[1];
std::cout << a << b << '\n';
std::swap( a, b );
std::cout << x << '\n';
}

Output on my machine:

01
00000011

So the bits were not swapped but one overwrites the other (a bug).
b) The alternative implementation of swap produces a different bug:
#include <bitset>
#include <iostream>
#include <string>

// stolen from Boost:
template < typename T >
T * address_of (T & t) {
return (
reinterpret_cas t<T*>(
& const_cast<char &>(
reinterpret_cas t<const volatile char &>( t ) ) ) );
}

template < typename T >
void copy_assign ( T & lhs, T & rhs ) {
T * ptr = address_of( lhs );
ptr->~T();
new ( ptr ) T ( rhs );
}

template < typename T >
void swap ( T & a, T & b ) {
T dummy ( a );
copy_assign( a, b );
copy_assign( b, dummy );
}

typedef std::bitset<8by te;

int main ( void ) {
byte x ( std::string( "00010" ) );
byte::reference a = x[0];
byte::reference b = x[1];
std::cout << a << b << '\n';
::swap( a, b );
std::cout << a << b << '\n';
std::cout << x << '\n';
a = false;
std::cout << x << '\n';
}

Output:

01
10
00000010
00000000
Here the fake references get reseated (also a bug).

But I will resend my statement. How about this instead:

All non-modifying algorithms can be called with const iterators passed
in, modifying algorithms cannot.

Much better. Of course, now for_each with a modifying function is a
modifying algorithm, which makes sense!

I tend to read those section headings as non-descriptive: the standard does
not really give a definition of modifying vs. non-modifying.
Best

Kai-Uwe Bux

[Jerry Coffin]

In article <da************ *************** *@news.west.ear thlink.net>,
da******@earthl ink.net says...

[ ... ]

Jerry (and Pete) are asserting that I am wrong?

I'm asserting that your claim of a proof is simply pure nonsense. Code
that has undefined behavior doesn't prove anything. The compiler you're
using may reject it, but the standard explicitly waives all requirements
under those circumstances -- there's no requirement about accepting or
rejecting it, nor even a requirement about issuing a diagnostic.

The minute you include undefined behavior, there is nothing meaningful
to be gleaned from the code at all. Even your assertion that the
compiler will reject the code is basically false -- your compiler might
reject it, but there's no requirement that all compilers do so.

Are you asserting that
(a) there is a non-modifying algorithm that assigns to elements of a
container and/or (b) there is a modifying algorithm that doesn't?

I'm asserting that your claim of a "proof" was nothing of the sort.

If you are, then state which algorithm it is otherwise accept it.

You're the one who needs to accept something: specifically, that code
that includes undefined behavior doesn't prove anything. Beyond that,
you have a simple situation: the standard doesn't contain any
"official" definition of what "modifying" or "non-modifying" really
means.

IMO, any use of the phrase is probably ill-advised -- meaningful
communication requires that the sender and the receiver agree on the
meanings of the terms. Misunderstandin g is always a possibility, but in
this case, it's nearly a certainty -- making it a lousy way to
communicate.

--
Later,
Jerry.

The universe is a figment of its own imagination.