Hans Aberg <remove.haberg@matematik.su.se> wrote in message
news:remove.haberg-2406012043200001@du129-226.ppp.su-anst.tninet.se...
> In article <B75ADDE7.1706A%sparent@adobe.com>, Sean Parent
> <sparent@adobe.com> wrote:
>
> >The drawbacks are that this could lead developers to blindly code
> >inefficient algorithms not considering the cost of retrieving the
iterator
> >and a small cost in returning a proxy which may be rarely used (cost
depends
> >on compiler and runtime environment).
>
> Could not compilers detect if the return is not used?

Better still, why not permit overloading on a return value?
If a return value is not used, it would match a method with a void return.

Stephen Howe



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

in article MubY6.1921$kx3.167859@bgtnsc06-news.ops.worldnet.att.net, Joe
Gottman at joegottman@worldnet.att.net wrote on 6/21/01 10:30 AM:

> Why do the associative containers return void from the method
> erase(iterator)?

As has already been answered - the reason is efficiency since returning an
iterator to the next item may take significant time.

A good solution to this would be to return a "proxy" iterator - which would
have a private constructor (can only be created by the friend container) and
a cast operator to an iterator. The increment would only happen in the cast
operator - so the penalty is only paid if an iterator is retrieved.

The drawbacks are that this could lead developers to blindly code
inefficient algorithms not considering the cost of retrieving the iterator
and a small cost in returning a proxy which may be rarely used (cost depends
on compiler and runtime environment). The benefit being that code could be
more independent of container types. This change could be made to the
existing library without breaking existing code.

--
Sean Parent
Sr. Engineering Manager
Adobe Workgroup Services
sparent@adobe.com


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <B75ADDE7.1706A%sparent@adobe.com>, Sean Parent
<sparent@adobe.com> wrote:

>The drawbacks are that this could lead developers to blindly code
>inefficient algorithms not considering the cost of retrieving the iterator
>and a small cost in returning a proxy which may be rarely used (cost depends
>on compiler and runtime environment).

Could not compilers detect if the return is not used?

-- I suggested elsewhere in this newsgroup that one might introduce a
concept or keyword "pure", meaning that the compiler is free to treat the
function as if it was pure (rearranging computational order and assume
there are no side effects).

Isn't something like that needed in order to make it possible for the
compiler to detect that if the return is not used, then the involved
function calls can also be removed? -- Because then one will know that
there are (considered to be) no side effects, and any involved function
calls can be removed.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Hans Aberg" <remove.haberg@matematik.su.se> wrote in message
news:remove.haberg-2406012043200001@du129-226.ppp.su-anst.tninet.se...
> In article <B75ADDE7.1706A%sparent@adobe.com>, Sean Parent
> <sparent@adobe.com> wrote:
>
> >The drawbacks are that this could lead developers to blindly code
> >inefficient algorithms not considering the cost of retrieving the
iterator
> >and a small cost in returning a proxy which may be rarely used (cost
depends
> >on compiler and runtime environment).
>
> Could not compilers detect if the return is not used?
>
> -- I suggested elsewhere in this newsgroup that one might introduce a
> concept or keyword "pure", meaning that the compiler is free to treat the
> function as if it was pure (rearranging computational order and assume
> there are no side effects).
>
> Isn't something like that needed in order to make it possible for the
> compiler to detect that if the return is not used, then the involved
> function calls can also be removed? -- Because then one will know that
> there are (considered to be) no side effects, and any involved function
> calls can be removed.
>

    Note that this would NOT be useful in the case of set.erase(iterator),
because this function most definitely does have a side effect.  It erases
the element pointed to by the iterator.

Joe Gottman

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <IKuZ6.8622$3d3.672141@bgtnsc05-news.ops.worldnet.att.net>,
"Joe Gottman" <joegottman@worldnet.att.net> wrote:
>> Isn't something like that needed in order to make it possible for the
>> compiler to detect that if the return is not used, then the involved
>> function calls can also be removed? -- Because then one will know that
>> there are (considered to be) no side effects, and any involved function
>> calls can be removed.
>>
>
>    Note that this would NOT be useful in the case of set.erase(iterator),
>because this function most definitely does have a side effect.  It erases
>the element pointed to by the iterator.

It would not be applied to the function set.erase(iterator) itself, but to
the conversion functions of what it returns. If one knows these functions
are pure, then the compiler knows that they can be removed if their return
values are not used, as they are pure.

Thus, one returns an object with the potential ability to locate the next
iterator, but as all function calls of that object will be pure, it can be
removed altogether by the compiler if it is not in a syntactical position
where it is used. The overhead then becomes zero.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Hans Aberg" <remove.haberg@matematik.su.se> wrote in message
news:remove.haberg->

> It would not be applied to the function set.erase(iterator) itself, but to
> the conversion functions of what it returns. If one knows these functions
> are pure, then the compiler knows that they can be removed if their return
> values are not used, as they are pure.
>
> Thus, one returns an object with the potential ability to locate the next
> iterator, but as all function calls of that object will be pure, it can be
> removed altogether by the compiler if it is not in a syntactical position
> where it is used. The overhead then becomes zero.

    O.K, but something still seems wrong to me.  The function
set.erase(iterator) invalidates the iterator passed to it.  Therefore, the
decision on whether to increment the iterator must be made before this
function returns.  Doesn't this decision count as a side-effect?

    It might be simpler if C++ could implement something like the Perl
wantarray() function.  If set.erase(iterator) could tell if its return value
is being used, then it could return the incremented iterator if necessary,
and nothing at all otherwise.

Joe Gottman

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <6FPZ6.9292$kx3.723008@bgtnsc06-news.ops.worldnet.att.net>,
"Joe Gottman" <joegottman@worldnet.att.net> wrote:
>> Thus, one returns an object with the potential ability to locate the next
>> iterator, but as all function calls of that object will be pure, it can be
>> removed altogether by the compiler if it is not in a syntactical position
>> where it is used. The overhead then becomes zero.
>
>    O.K, but something still seems wrong to me.  The function
>set.erase(iterator) invalidates the iterator passed to it.  Therefore, the
>decision on whether to increment the iterator must be made before this
>function returns.  Doesn't this decision count as a side-effect?
>
>    It might be simpler if C++ could implement something like the Perl
>wantarray() function.  If set.erase(iterator) could tell if its return value
>is being used, then it could return the incremented iterator if necessary,
>and nothing at all otherwise.

I have no ideas about this specific case what would be exactly needed.

But evidently compilers are already making a lot of dependency analysis on
basic data types to figure which variables can be eliminated, put into
registers, etc.

My hunch is that it would be better to try augment C++ with a more general
mechanism, so that the same kind of compiler optimizations can be applied
to class defined types.

As for the "pure" suggestion, it is just an input: I think that one
essential component in such optimizations is knowing that the involved
function calls are pure, because it means that one does not have to worry
about any state being manipulated. But I do not know exactly what is need
in those optimizations -- that would a task for an expert on writing C++
compilers to specify.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Why do the associative containers return void from the method
erase(iterator)?  This makes it unnecessarily difficult to write template
code that uses erase. For instance, suppose I wanted to write a function

template <class Container, class Predicate>
void erase_if(Container &c, const Predicate &f)
{
    for (Container::iterator it = c.begin(); it != c.end(); /*No
increment*/) {
         if (f(*it)) {
               it = c.erase(it); // Erase it, get next iterator
         } else {
               ++it;
        }
}

This function would work fine for vectors, deques, and lists, but it would
fail for associative containers because their erase methods do not return
iterators.  Note that the line c.erase(it++) would fail for vectors and
deques because erasing invalidates iterators.

Joe Gottman

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Joe Gottman" <joegottman@worldnet.att.net> wrote in message
news:MubY6.1921$kx3.167859@bgtnsc06-news.ops.worldnet.att.net...

> Why do the associative containers return void from the method
> erase(iterator)?

The answer is -- for efficiency! To meet the complexity requirements and the
semantics of the operations allowed on the associative containers, the
implementation has to choose some kind of balanced binary tree as the
underlying representation for the associative containers. In the original
STL code from Hewlett-Packard the associative containers were implemented
using a red-black tree, and all the contemporary STL implementations that I
have seen stick to that tradition (mostly because no one has yet come up
with something superior).

Given that the associative containers allow you to iterate through their
elements in the non-descending order of the keys of the controlled elements,
the complexity of the operation of incrementing/decrementing an associative
container's iterator is actually substantially bigger compared to the cost
of incrementing/decrementing any sequence's iterator. In fact incrementing
an associative container's iterator may involve walking any number of levels
up the tree (not more than the length of the longest tree path, which cannot
exceed floor(log2(n))+1 for a red-black tree with n elements).

As one of the major design goals for the development of STL was efficiency,
having 'erase(iterator)' for an associative container return '++iterator'
would be prohibitively expensive for cases when the return value is not
needed.


> This makes it unnecessarily difficult to write template
> code that uses erase.

Not really, as you can build on the fact that an 'erase(iterator)' for an
associative container invalidates only the iterators, pointers and
references to the element to be erased. So no one prevents you from getting
the next iterator by way of
'erase(iterator++)'.


> For instance, suppose I wanted to write a function
>
> template <class Container, class Predicate>
> void erase_if(Container &c, const Predicate &f)
> {
>     for (Container::iterator it = c.begin(); it != c.end(); /*No
> increment*/) {
>          if (f(*it)) {
>                it = c.erase(it); // Erase it, get next iterator
>          } else {
>                ++it;
>         }
> }
>
> This function would work fine for vectors, deques, and lists, but it would
> fail for associative containers because their erase methods do not return
> iterators.  Note that the line c.erase(it++) would fail for vectors and
> deques because erasing invalidates iterators.

Not always, if you are erasing at the beginning of a deque, the construct
'c.erase(it++)' will not invalidate anything but the iterators, pointers and
references to the element to be erased. But on the whole you are right, it's
usually really too difficult to write container independent code.


Regards,

Andrei Iltchenko.



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]