On 3 Mar 1999 16:52:14 GMT, Christopher Eltschka

>for_each(select(v.begin(), foo, bar), select(v.end()), do_sth());

Fine, but the selection_iterator<...> returned by "select(v.end())"
still has excess baggage, although the user doesn't see it directly.
Indeed, this appears to be the case with the object
"ostream_iterator<int>()".  It has a pointer to an istream, but this
pointer is set to null.  It also has a delimeter field, which is
set to the empty string.


>> But it still seems simpler to change the template args of
>> std::for_each and a few other functions.  And best of all, the
>> change wouldn't affect anyone!  Well, it would make compile
>> times about 0.01% slower.
>
>It wouldn't affect correct code. It would detect a few less
>errors for incorrect code. I don't know if those errors are
>common enough.

Good point.


>BTW, while client code generally should not work with
>the containers themselves, handing out iterators (or
>ranges) can make sense. Think about a composite graphical
>object, where you might want to iterate through the
>objects it contains.

In this case, we could give the composite graphical class a
templated for_each function.  Eg,
   class composite_graphical_object {
      ...
      template <class Action> Action for_each(Action);
      //void for_each(Action*); // class Action is a polymorphic base class
      ...
   };

Or we could return an iterator range.  Eg,
   class composite_graphical_object {
      ...
      Range get(); // Range contains begin/end iterators
      ...
   };

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <slrn7dr916.2a1.sbnaran@bardeen.ceg.uiuc.edu>,
  sbnaran@KILL.uiuc.edu wrote:
> On 3 Mar 1999 16:52:14 GMT, Christopher Eltschka
>
> >for_each(select(v.begin(), foo, bar), select(v.end()), do_sth());
>
> Fine, but the selection_iterator<...> returned by "select(v.end())"
> still has excess baggage, although the user doesn't see it directly.
> Indeed, this appears to be the case with the object
> "ostream_iterator<int>()".  It has a pointer to an istream, but this
> pointer is set to null.  It also has a delimeter field, which is
> set to the empty string.

You take this too far. We have template functions which take a pair of
iterators and operate on the data between them. The fact that one of
those iterators is often set to the past-the-end value is irrelevant.

Do you suggest that long int has "excess baggage" because it's
high-order bits are often all zero?

Let's put this in simpler, business terms. We have a class called
customer. A junior programmer discovers that fully 92% of our
customers have no data in the address2[] field. That's 42 wasted
bytes per customer. The junior programmer suggests that we change
customer into customerNormal, which has no address2. Then we could
create a derived class, customerLongAddress, which does have an
address2. With virtual functions we would still be able to handle
the 8% of customers that have long addresses, while saving 42 bytes
per customer in the normal case. Do you give the junior programmer
the go-ahead?

I hope not. For one thing, the proposal probably fails to meet it's
own goal, namely saving RAM. We save 42 bytes per customer, but we
take up several thousand bytes of additional code complexity (both in
the new virtual functions and in the compiler overhead to dispatch to
such functions). The program becomes more error prone, harder to
write and maintain, and (at least trivially) slower to execute. This
would be a bad idea. The term "overkill" would be kind.

Data types that can be used in generic ways must have data to support
all reasonable operations. Often we can predict that one or more
elements will have known fixed values. This does not automatically
make those elements worthless in the grand scheme.

P.S. Is a delimeter a device for measuring delicatessans? I'd like to
clock the corn beef sandwhiches... :)

----
AllanW@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 04 Mar 99 18:28:54 GMT, AllanW@my-dejanews.com

>I hope not. For one thing, the proposal probably fails to meet it's
>own goal, namely saving RAM. We save 42 bytes per customer, but we
>take up several thousand bytes of additional code complexity (both in
>the new virtual functions and in the compiler overhead to dispatch to
>such functions). The program becomes more error prone, harder to
>write and maintain, and (at least trivially) slower to execute. This
>would be a bad idea. The term "overkill" would be kind.

Now I think you take the idea too far.  You're talking about the
cost of designing specialized classes and specialized algorithms
to handle special cases.  It's a maintainance nightmare, I know,
and hardly worth it.

But changing the template arg of std::for_each won't incur any
additional complexity, and any additional maintainance hassle.
One potential problem is that certain errors would go unnoticed,
as Christopher said.  But it's not like we're redesigning the
world or something :).

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Siemel Naran wrote:
>
> On 1 Mar 1999 16:14:19 GMT, Howard Hinnant
>
> >>    template <class IterBegin, class IterEnd, class Action>
> >>    Action find_if(IterBegin begin, const IterEnd end, Action action)
>
> >>    std::for_each(select(v.begin()),v.end(),DoSomething());
>
> >Very interesting idea.  Could your idea work like:
> >
> >   std::for_each(select(v.begin()),select(v.end()),DoSomething());
>
> Of course, this works, and is what I'm currently doing.
> But it is inefficient and inelegant.
>
> Recall the definition of class selection_iterator.
> It has three private variables -- the normal iterator, the end
> iterator, and a search predicate.
> The begin iterator "select(v.begin())" needs these three variables,
> as we will be doing ++begin.
> The end iterator "select(v.end())" does not need all three variables.
> But sizeof(select(v.end()))>sizeof(v.end()), which is efficient.

The compiler will inline the for_each call anyway; and a good
optimizer might then see that you only use one field of
select(v.end()), and optimize away the rest of them.
Since it doesn't change the behaviour, it is allowed under
the as-if rule.

>
> How to define operator==(selection_iterator,selection_iterator).
> The conventional definition is to compare all three private data fields.
> But we need compare only one data field -- namely the normal iterator.
> But an operator== that does not compare every field is inelegant.

What about using the istream_iterator aproach: The end iterator is
taken just by default constructor. The begin iterator would then
have to store the v.end() as well.

Your call would then look like this:

for_each(select(v.begin(), v.end()), select(), DoSomething());

>
> Also, the expression "select(v.end())" generates an object that
> contains more information than is needed.
> Extra information is bad for maintainance.
> And it is also inelegant.

IMHO the concept of designating a range by begin iterator and
end iterator is inelegant per se. Instead, there should have
been a range type, which has all the functionality of a
begin-end pair. This would also be less error prone (no way
to take an invalid end iterator, unless you construct a range
manually from begin and end iterator).
With this approach, one would need to explicitly create a
range from two pointers, if pointers are used as source,
but IMHO this is no problem. You already have different syntax
for pointers, since you cannot do just array.begin() and
array.end().
The istream_iterator shows the problem of the iterator pair
abstraction. An end iterator to user input is semanticlly
nonsense - you don't know ahead when input ends. The end
iterator by default constructor is just a trick to get
input pressed into the iterator-pair abstraction.
A range object would not suffer from this, since you don't
need to know ahead where the range ends (this would be a
special feature of fixed ranges, which would be the
equivalent to forward iterators). An input range would
just be a possibly unbounded range.
Of course, begin iterators must be obtained from ranges,
but end iterator needn't - just ask the range, if the
iterator is at its end. Most ranges would compare to
their internally stored end iterator, but some ranges
would do somethin different - an istream_range would
test the iterator's stream for eof/error, and a
selector_range (the equivalent to your select iterator)
would test the "real" iterator with the "real" range.

A for_each method would then look like this:

template<class InputRange, class Action>
 Action for_each(InputRange range, Action action)
{
  for(InputRange::iterator i=range.begin(); !range.at_end(i); ++i)
    action();
  return action;
}

To apply this to a container with range interface, one would write

for_each(container.range(), do_something());

To apply this to an array, one could do:

int a[20];

void increment(int&);

for_each(range(a), increment);

int* p=new int[100];

for_each(range(p, 100), increment);
// or
for_each(range(p, p+100), increment);

Where range is defined as

template<typename Iterator>
 inline IteratorRange<Iterator> range(Iterator begin, Iterator end)
{
  return IteratorRange<Iterator>(begin, end);
}

template<typename Iterator>
 inline IteratorRange<Iterator> range(Iterator begin, size_t length)
{
  return IteratorRange<Iterator>(begin, advance(begin, length);
}

template<class T, int n>
 inline IteratorRange<T*> range(T (&arr)[n])
{
  return IteratorRange<T*>(arr, arr+n);
}

Where IteratorRange is a special range which consists of a begin
and an end iterator.

However, the STL interface is fixed, and will be so forever
(at least I cannot imagine that such a fundamental change
could be made to the interface, no matter if in the second,
the tenth or the hundreth version of the standard).
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Christopher Eltschka wrote in message
<36DBB7FE.5B2266A1@physik.tu-muenchen.de>...
[range discussion snipped]
>However, the STL interface is fixed, and will be so forever
>(at least I cannot imagine that such a fundamental change
>could be made to the interface, no matter if in the second,
>the tenth or the hundreth version of the standard).


Yes, but who stops you from making your range class and function and
from overloading for_each (and other algorithms)? They can coexist
with STL.

Adding a range class to my collection of five-liners (in almost the
exact form you presented) is also my plan for when I'll have time :o).
Happy to see when other people think the same.

Andrei




[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 02 Mar 99 11:40:48 GMT, Christopher Eltschka

>> >   std::for_each(select(v.begin()),select(v.end()),DoSomething());

BTW, as the constructor of selection_iterator must initialize three
data fields -- the normal iterator, the const end iterator, and the
function predicate -- the above should really be:

       std::for_each
          (select(v.begin(),v.end(),Pred(3)),
           select(v.end  (),v.end(),Pred(0)),
           DoSomething());

My apologies for not being clear the first time around.



>The compiler will inline the for_each call anyway; and a good
>optimizer might then see that you only use one field of
>select(v.end()), and optimize away the rest of them.
>Since it doesn't change the behaviour, it is allowed under
>the as-if rule.

This is beside the point.  What if I'm calling a big function that
can't be inlined?

The most serious objection I have to the above code is that there's
too much information in it.  The code "select(v.end(),...)" strikes
me as aesthetically unpleasing, although it probably won't be a
serious performance bottleneck.  And in general, code that has
excess baggage is always harder and more expensive to maintain.



>What about using the istream_iterator aproach: The end iterator is
>taken just by default constructor. The begin iterator would then
>have to store the v.end() as well.
>
>Your call would then look like this:
>
>for_each(select(v.begin(), v.end()), select(), DoSomething());

Thanks.  I've never used istream_iterator and ostream_iterator, so
I didn't know this trick.  It is slightly more elegant.

But it still seems simpler to change the template args of
std::for_each and a few other functions.  And best of all, the
change wouldn't affect anyone!  Well, it would make compile
times about 0.01% slower.


>template<class InputRange, class Action>
>Action for_each(InputRange range, Action action)
>{
>  for(InputRange::iterator i=range.begin(); !range.at_end(i); ++i)
>    action();
>  return action;
>}

This is definitely safer.  But is it worth it?  Ideally, client code
should not work with bare containers and algorithms, but instead
should use the public members of a useful class.

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Siemel Naran wrote:
>
> On 02 Mar 99 11:40:48 GMT, Christopher Eltschka
>
> >> >   std::for_each(select(v.begin()),select(v.end()),DoSomething());
>
> BTW, as the constructor of selection_iterator must initialize three
> data fields -- the normal iterator, the const end iterator, and the
> function predicate -- the above should really be:
>
>        std::for_each
>           (select(v.begin(),v.end(),Pred(3)),
>            select(v.end  (),v.end(),Pred(0)),
>            DoSomething());
>
> My apologies for not being clear the first time around.
>
> >The compiler will inline the for_each call anyway; and a good
> >optimizer might then see that you only use one field of
> >select(v.end()), and optimize away the rest of them.
> >Since it doesn't change the behaviour, it is allowed under
> >the as-if rule.
>
> This is beside the point.  What if I'm calling a big function that
> can't be inlined?
>
> The most serious objection I have to the above code is that there's
> too much information in it.  The code "select(v.end(),...)" strikes
> me as aesthetically unpleasing, although it probably won't be a
> serious performance bottleneck.  And in general, code that has
> excess baggage is always harder and more expensive to maintain.

You can overload the select function (or the select constructor,
if select is the class itself) to take only one parameter. This
one-parameter form would only be used for the end iterator:

for_each(select(v.begin(), foo, bar), select(v.end()), do_sth());


> >What about using the istream_iterator aproach: The end iterator is
> >taken just by default constructor. The begin iterator would then
> >have to store the v.end() as well.
> >
> >Your call would then look like this:
> >
> >for_each(select(v.begin(), v.end()), select(), DoSomething());
>
> Thanks.  I've never used istream_iterator and ostream_iterator, so
> I didn't know this trick.  It is slightly more elegant.
>
> But it still seems simpler to change the template args of
> std::for_each and a few other functions.  And best of all, the
> change wouldn't affect anyone!  Well, it would make compile
> times about 0.01% slower.

It wouldn't affect correct code. It would detect a few less
errors for incorrect code. I don't know if those errors are
common enough.

> >template<class InputRange, class Action>
> >Action for_each(InputRange range, Action action)
> >{
> >  for(InputRange::iterator i=range.begin(); !range.at_end(i); ++i)
> >    action();
> >  return action;
> >}
>
> This is definitely safer.  But is it worth it?  Ideally, client code
> should not work with bare containers and algorithms, but instead
> should use the public members of a useful class.

It is also better suited to problems which are not best
described as iterator pair. Your select iterator is such
an example, as is istream_iterator.
The range abstraction supports the begin/end abstraction well.
But the begin/end abstraction does not support the range
abstraction too well (you _can_ do it, but the result is
s.th. line istream_iterators).

BTW, while client code generally should not work with
the containers themselves, handing out iterators (or
ranges) can make sense. Think about a composite graphical
object, where you might want to iterate through the
objects it contains.


[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

I find that std::for_each is designed like this:

   template <class Iter, class Action>
   Action find_if(Iter begin, const Iter end, Action action)
   {
      while (begin!=end) action(*begin++);
      return action;
   }

But I think it should be like this:

   template <class IterBegin, class IterEnd, class Action>
   Action find_if(IterBegin begin, const IterEnd end, Action action)
   {
      while (begin!=end) action(*begin++);
      return action;
   }


1. Say we write a selection iterator.
2. selection_iterator::operator++() advances not to the next element in
   the container, but to the next element in the container that matches
   a certain predicate.
3. So the selection iterator contains as private data a normal iterator,
   a predicate object, and the end iterator (a normal iterator).


template <class Iter, class Predicate>
class selection_iterator
{
   private:
      const Predicate pred;
      const Iter end;
      Iter iter;

   public:
      typedef typename Iter::reference reference;

      selection_iterator(Iter begin, Iter end_, Predicate pred_)
         : pred(pred_), end(end_), iter(std::find(begin,end,pred))
      {
      }

      reference operator*() const { return *iter; }

      selection_iterator& operator++()
      {
         iter=std::find_if(++iter,end,pred);
         return *this;
      }

      bool operator==(Iter that) const { return this->iter==that); }
      bool operator!=(Iter that) const { return this->iter!=that); }
};


The one calls
   std::for_each(select(v.begin()),v.end(),DoSomething());
where the function select(...) returns a selection_iterator<...>.


--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------
---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <slrn7dk3m2.7r2.sbnaran@fermi.ceg.uiuc.edu>,
sbnaran@KILL.uiuc.edu wrote:

> But I think it should be like this:
>
>    template <class IterBegin, class IterEnd, class Action>
>    Action find_if(IterBegin begin, const IterEnd end, Action action)
>    {
>       while (begin!=end) action(*begin++);
>       return action;
>    }
>
> The one calls
>    std::for_each(select(v.begin()),v.end(),DoSomething());
> where the function select(...) returns a selection_iterator<...>.

Very interesting idea.  Could your idea work like:

   std::for_each(select(v.begin()),select(v.end()),DoSomething());

?

-Howard


[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 1 Mar 1999 16:14:19 GMT, Howard Hinnant

>>    template <class IterBegin, class IterEnd, class Action>
>>    Action find_if(IterBegin begin, const IterEnd end, Action action)

>>    std::for_each(select(v.begin()),v.end(),DoSomething());

>Very interesting idea.  Could your idea work like:
>
>   std::for_each(select(v.begin()),select(v.end()),DoSomething());

Of course, this works, and is what I'm currently doing.
But it is inefficient and inelegant.

Recall the definition of class selection_iterator.
It has three private variables -- the normal iterator, the end
iterator, and a search predicate.
The begin iterator "select(v.begin())" needs these three variables,
as we will be doing ++begin.
The end iterator "select(v.end())" does not need all three variables.
But sizeof(select(v.end()))>sizeof(v.end()), which is efficient.

How to define operator==(selection_iterator,selection_iterator).
The conventional definition is to compare all three private data fields.
But we need compare only one data field -- namely the normal iterator.
But an operator== that does not compare every field is inelegant.

Also, the expression "select(v.end())" generates an object that
contains more information than is needed.
Extra information is bad for maintainance.
And it is also inelegant.

--
----------------------------------
Siemel B. Naran (sbnaran@uiuc.edu)
----------------------------------


[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]