By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
428,530 Members | 880 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 428,530 IT Pros & Developers. It's quick & easy.

for_each

P: n/a
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
Sep 17 '06 #1
Share this Question
Share on Google+
27 Replies


P: n/a
"Fraser Ross" <fraserATmembers.v21.co.ukwrote:
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.
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. Specifically, there is no assignment operation
inside the algorithm.

--
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.
Sep 17 '06 #2

P: n/a

"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.

Fraser.

Posted Via Usenet.com Premium Usenet Newsgroup Services
----------------------------------------------------------
** SPEED ** RETENTION ** COMPLETION ** ANONYMITY **
----------------------------------------------------------
http://www.usenet.com
Sep 17 '06 #3

P: n/a
In article <11**************@sp6iad.superfeed.net>, "Fraser Ross"
<fraserATmembers.v21.co.uksays...
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.
The C++ standard places the description of for_each in the "Non-
modifying Sequence Operations." OTOH, there's nothing in its description
that precludes it from modifying the items in the sequence either.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Sep 17 '06 #4

P: n/a
In article <11**************@sp6iad.superfeed.net>, "Fraser Ross"
<fraserATmembers.v21.co.uksays...
>
"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.
I doubt it. Other algorithms (e.g. transform) state specific
requirements about lack of side-effects in the operations they invoke. I
think if that was intended, it would be stated in the dsecription of
for_each as well.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Sep 17 '06 #5

P: n/a
"Fraser Ross" <fraserATmembers.v21.co.ukwrote:
>
"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.
That intention is not stated in the standard. The description of for_each is
very clear:

template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f);

Effects: Applies f to the result of dereferencing every iterator in the
range [first, last), starting from first and proceeding to last - 1.
Returns: f.
Complexity: Applies f exactly last - first times.

It follows that if you pass a const_iterator, you will not be able to
modify. If you pass a (non-const) iterator, you will be able to modify
because the result of dereferencing the iterator is not const.
Best

Kai-Uwe Bux
Sep 17 '06 #6

P: n/a
The book "STL Tutorial And Reference Guide" says "It is assumed f does
not apply any nonconstant function through the dereferenced iterator."

The help files with BCB6 says "Since this a non-mutating algorithm, the
function f cannot make any modifications to the sequence, but it can
achieve results through side effects (such as copying or printing). "

They seem to expecting the range to not be modified.

Posted Via Usenet.com Premium Usenet Newsgroup Services
----------------------------------------------------------
** SPEED ** RETENTION ** COMPLETION ** ANONYMITY **
----------------------------------------------------------
http://www.usenet.com
Sep 17 '06 #7

P: n/a
"Fraser Ross" <fraserATmembers.v21.co.ukwrote:
The book "STL Tutorial And Reference Guide" says "It is assumed f does
not apply any nonconstant function through the dereferenced iterator."

The help files with BCB6 says "Since this a non-mutating algorithm, the
function f cannot make any modifications to the sequence, but it can
achieve results through side effects (such as copying or printing). "

They seem to expecting the range to not be modified.
As I already pointed out, those opinions have, to the best of my knowledge,
no basis in the language of the standard. Maybe you should ask the authors
of your sources, where in the standard they find the provisions in support
for their theory.
Best

Kai-Uwe Bux

Sep 17 '06 #8

P: n/a
Fraser Ross wrote:
The book "STL Tutorial And Reference Guide" says "It is assumed f does
not apply any nonconstant function through the dereferenced iterator."

The help files with BCB6 says "Since this a non-mutating algorithm, the
function f cannot make any modifications to the sequence, but it can
achieve results through side effects (such as copying or printing). "

They seem to expecting the range to not be modified.
On the other hand, if you look at the page cited in the original
message, it lists for_each as both a non-modifying algorithm and a
modifying algorithm.

Much of this confusion comes from failing to distinguish between two
different modifications: modifying the order of the elements in the
passed sequence (e.g. sort) and modifying elements in the sequence (e.g.
transform).

In fact, the classification in the standard distinguishes between
modifying sequence operations and non-modifying sequence operations. The
choice of words is deliberate: it emphasizes that what's being operated
on is the sequence, and not the elements themselves. So for_each is a
non-modifying sequence operation, because it does not modify the order
the elements in the sequence.

There's a newly added note that says that if you pass a mutable iterator
to for_each, the function can modify the elements.

--

-- Pete

Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." For more information about this book, see
www.petebecker.com/tr1book.
Sep 17 '06 #9

P: n/a
In article <11**************@sp6iad.superfeed.net>,
"Fraser Ross" <fraserATmembers.v21.co.ukwrote:
The book "STL Tutorial And Reference Guide" says "It is assumed f does
not apply any nonconstant function through the dereferenced iterator."

The help files with BCB6 says "Since this a non-mutating algorithm, the
function f cannot make any modifications to the sequence, but it can
achieve results through side effects (such as copying or printing). "

They seem to expecting the range to not be modified.
From Stroustrup:

The for_each() algorithm is classified as nonmodifying because it
doesn't explicitly modify a sequence. However, if applied to a
non-const sequence for_each()'s operation (its third argument) may
change the elements of the sequence.

--
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.
Sep 17 '06 #10

P: n/a
"Fraser Ross" <fraserATmembers.v21.co.ukwrote:
>"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.)

--
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.
Sep 17 '06 #11

P: n/a
Daniel T. wrote:
"Fraser Ross" <fraserATmembers.v21.co.ukwrote:
>"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.)
sort also doesn't modify any elements, but it's a modifying sequence
operation. That's because it changes the order of the elements in the
passed sequence. That's the distinction between non-modifying sequence
operations and modifying sequence operations.

--

-- Pete

Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." For more information about this book, see
www.petebecker.com/tr1book.
Sep 17 '06 #12

P: n/a
Pete Becker <pe********@acm.orgwrote:
Daniel T. wrote:
>"Fraser Ross" <fraserATmembers.v21.co.ukwrote:
>>"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.)

sort also doesn't modify any elements, but it's a modifying sequence
operation.
'sort' does modify the elements in the sequence. Here is my proof, the
below won't compile because sort needs to be able to modify the
elements, and objects of type Object can't be modified.

class Object
{
Object& operator=( const Object& o ); // I can't be modified.
public:
int v;
Object(): v( rand() ) { }
};

bool operator<( const Object& lhs, const Object& rhs )
{
return lhs.v < rhs.v;
}

int main()
{
vector< Object vec( 25 );
sort( vec.begin(), vec.end() );
}

--
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.
Sep 17 '06 #13

P: n/a
In article <da****************************@news.west.earthlin k.net>,
da******@earthlink.net says...

[ ... ]
'sort' does modify the elements in the sequence. Here is my proof, the
below won't compile because sort needs to be able to modify the
elements, and objects of type Object can't be modified.

class Object
{
Object& operator=( const Object& o ); // I can't be modified.
public:
int v;
Object(): v( rand() ) { }
};
All your code proves is that you're apparently unaware of the
requirement in section 23.1/3 that anything you store in a vector be
assignable.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Sep 17 '06 #14

P: n/a
Jerry Coffin <jc*****@taeus.comwrote:
da******@earthlink.net says...

[ ... ]
'sort' does modify the elements in the sequence. Here is my proof, the
below won't compile because sort needs to be able to modify the
elements, and objects of type Object can't be modified.

class Object
{
Object& operator=( const Object& o ); // I can't be modified.
public:
int v;
Object(): v( rand() ) { }
};

All your code proves is that you're apparently unaware of the
requirement 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.

--
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.
Sep 17 '06 #15

P: n/a
Daniel T. wrote:
"Fraser Ross" <fraserATmembers.v21.co.ukwrote:
>>"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:
#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_back( 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:

Best

Kai-Uwe Bux
Sep 18 '06 #16

P: n/a
In article <da****************************@news.west.earthlin k.net>,
da******@earthlink.net says...

[ ... ]
All your code proves is that you're apparently unaware of the
requirement 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.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Sep 18 '06 #17

P: n/a
In article <ee**********@murdoch.acc.Virginia.EDU>,
Kai-Uwe Bux <jk********@gmx.netwrote:
Daniel T. wrote:
"Fraser Ross" <fraserATmembers.v21.co.ukwrote:
>"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
>

#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_back( 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:
--
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.
Sep 18 '06 #18

P: n/a
Jerry Coffin <jc*****@taeus.comwrote:
da******@earthlink.net says...
>>All your code proves is that you're apparently unaware of the
requirement 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.

--
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.
Sep 18 '06 #19

P: n/a
Daniel T. wrote:
>>>
sort also doesn't modify any elements, but it's a modifying sequence
operation.

'sort' does modify the elements in the sequence. Here is my proof, the
below won't compile because sort needs to be able to modify the
elements, and objects of type Object can't be modified.
You're looking at objects, not elements. Remember, STL is value-based.
If the sequence has the same values when an algorithm is finished as it
had at the start, then its elements have not been changed.
Note, also, that if modifying sequence operations get their name because
they modify individual objects, then std::sort is a modifying sequence
operation and std::list::sort is a non-modifying sequence operation.
That elevates implementation details over abstraction, and is not at all
what the STL is about.

--

-- Pete

Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." For more information about this book, see
www.petebecker.com/tr1book.
Sep 18 '06 #20

P: n/a
Daniel T. wrote:
In article <ee**********@murdoch.acc.Virginia.EDU>,
Kai-Uwe Bux <jk********@gmx.netwrote:
>Daniel T. wrote:
"Fraser Ross" <fraserATmembers.v21.co.ukwrote:
"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_back( 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:

Sep 18 '06 #21

P: n/a
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_cast<T*>(
& const_cast<char&>(
reinterpret_cast<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_cast<T*>(
& const_cast<char&>(
reinterpret_cast<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
Sep 18 '06 #22

P: n/a
Daniel T. wrote:
Jerry Coffin <jc*****@taeus.comwrote:
>da******@earthlink.net says...
>>>All your code proves is that you're apparently unaware of the
requirement 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 BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator 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_cast<T*>(
& const_cast<char&>(
reinterpret_cast<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
Sep 18 '06 #23

P: n/a
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.
Sep 18 '06 #24

P: n/a
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_cast<T*>(
& const_cast<char&>(
reinterpret_cast<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_cast<T*>(
& const_cast<char&>(
reinterpret_cast<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.
Sep 18 '06 #25

P: n/a
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
Sep 18 '06 #26

P: n/a
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<8byte;

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_cast<T*>(
& const_cast<char&>(
reinterpret_cast<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<8byte;

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
Sep 18 '06 #27

P: n/a
In article <da****************************@news.west.earthlin k.net>,
da******@earthlink.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. Misunderstanding 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.
Sep 18 '06 #28

This discussion thread is closed

Replies have been disabled for this discussion.