473,322 Members | 1,494 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

for_each

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
27 2189
"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

"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
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
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
"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
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
"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
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
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
"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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
by: Alex Vinokur | last post by:
Functor-parameters in the for_each() and transform() algorithms are passed by value. Might it make sense to have also algorithms for_each2() and transform2() which pass Functor-parameters by...
3
by: Griff | last post by:
#include <iostream> using namespace std; #include <vector> #include <string> #include <fstream> #include <algorithm> template<class C>void PrintAll(C&v) {
6
by: Michal Wyrebski | last post by:
Hello, I'm new in this group and I don't know if my questions are too silly, but I'm intermediate programmer and don't have enought experience. Please be charitable. I don't know how to write...
1
by: Capstar | last post by:
Hi NG, I have a question on std::for_each. I try to use this in combination with std::bind2nd to call a method of all functions in a container (std::set or std::map) and pass that method the...
12
by: sashan | last post by:
Sometimes I write code using std::for_each. Sometimes I use it on several container classes that are the same size. for_each(v.begin(), v.end(), f1()); for_each(u.begin(), u.end(), f2()); ...
9
by: shaun | last post by:
I am working on code where I am handed a vector of pointers vector<T*> or a map<std::string, T*>, and I have to delete the objects and set the pointers to zero. I have been using a 'for' loop and...
3
by: PolkaHead | last post by:
I was wondering if there's a way to traverse a two-dimensional vector (vector of vectors) with a nested for_each call. The code included traverses the "outer" vector with a for_each, than it...
9
by: Chris Roth | last post by:
I have a vector of vectors: vector< vector<double v; and have initialized it with: v( 5 ); as I know I will have 5 columns of data. At this point, I read text file data into each of the the...
13
by: Sarath | last post by:
What's the advantage of using for_each than the normal iteration using for loop? Is there any 'tweak' to use stream objects as 'Function' parameter of for_each loop. Seems copy function can do...
9
by: nguillot | last post by:
Hello I used to loop on a std::map<k, dto act on the data (d) like that (d being a class with setIntMember method): typedef std::map<k, dtMap; struct setIntMember { setIntMember(int j) :...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.