Pete Becker <petebecker@acm.org> wrote:

>Thus demonstrating that analyzing humor destroys it, which is hardly
>surprising.

But it is defined behaviour. :-)

--
Mike
Please followup to the group
X-Replace-Address
X-No-Reject-Notice

---
[ 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 <celtschk@physik.tu-muenchen.de> wrote:
>Pete Becker wrote:

>> is doing more than one thing. So here's the challenge: what is the name
>> of this algorithm? In particular, it cannot be "unique", because calling
>> it with the predicate not_equal produces a sequence of identical
>> elements.
>
>adjacent_remove

I agree, with the addition of adjacent_remove_if that takes a pred.

--
Mike
Please followup to the group
X-Replace-Address
X-No-Reject-Notice

---
[ 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              ]

Andrew Koenig wrote:
>
> In article <38886F09.C3F08154@acm.org>,
> Pete Becker  <petebecker@acm.org> wrote:
> >Andrew Koenig wrote:
>
> >> Suppose I describe unique() to you this way:
>
> >>         It makes a sequential pass through the input and selects
> >>         the first element and every subsequent element for which
> >>         the predicate is false when applied to the most recently
> >>         selected element and the candidate.
>
> >>         The result is therefore the maximal sequence of elements
> >>         from the original sequence, without changing the relative
> >>         order of elements, and with the property that the predicate
> >>         is false when applied to every adjacent pair of elements
> >>         within the sequence.
>
> >As a library vendor, how do I implement this so that it works when
> >someone passes a predicate that randomly chooses between true and false?
> >I know how to satisfy the first paragraph, but not the second.
>
> I suspect that there are a lot of algorithms whose descriptions
> render them impossible to implement if the user-supplied predicates
> are not functions in the mathematical sense -- that is, if you call
> them twice with the same argument, you're not guaranteed to get the
> same result.

Thus coming back to what I said originally: that some algorithms imply
constraints on their predicates.

>
> Nevertheless, I think it would be possible to deal with your objection
> in this case by changing the second paragraph so that instead of predicting
> what would happen if you were to apply the predicate to those arguments
> in the future, it made a statement about what had happened when applying
> the predicate to those values in the past.

Perhaps. But that doesn't address the underlying problem. This proposed
wording contains two independent definitions of "unique", one
operational and one conceptual, and they are inconsistent. I understand
the desire to include a conceptual definition, since that's the way the
other algorithms are defined. So far nobody has produced one that works,
either here or on the standards reflector. I suspect that this version
of "unique" is, indeed, unique, in that it can be described best
operationally. There is no concept behind it.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <387DEEA4.C74298DA@wizard.net>,
  James Kuyper <kuyper@wizard.net> wrote:
> From the description of the algorithm, I gather that it applies the
> predicate in order to consecutive pairs of elements in the iterator
> range provided, with the earlier element in the list always provided
> as the second argument to the predicate. The second element is
> removed if the predicate is not equal to false. From these facts I
> can't derive a single meaningful restriction on the predicate other
> than that it's return type must be convertible to bool.
>
> Now, if I take the word "equal" as constraining the predicate, rather
> than being simply verbal shorthand for it, then I can derive the
> requirements that std::equal_to<> must be instantiatiable for the
> given type, and that the predicate must return false iff
> std::equal_to<> would return false.
>
> How do you derive contraints that fall somewhere in between these two
> extremes?

One way to derive constraints is to try to recreate the original
intent. If unique is supposed to remove "duplicate" items, why do
we allow the predicate to be overridden at all? The only sensible
reason for this would be to allow the user to determine which
items are "duplicate." For instance, if we wish to remove duplicate
customers from a vector sorted by account number, we must use a
different predicate than the same vector sorted by last and first
names.

An important attribute of the STL algorithms is that it recognizes
that equivalent does not always mean 100% identical. For instance,
our duplicate customers may have different addresses, telephone
numbers, and "last update" dates. Therefore we must know which copy
of the customer will be retained by unique(). The description of the
algorithm answers this question.

If you agree with everything I've said so far, you'll agree that
the user has great control over the way that two elements are
compared, and that the standard explicitly describes WHICH elements
are compared. Therefore, if the input values and the predicate are
both known, the output values should be deterministic and easy to
predict.

In the original post, Stefan did exactly that -- he used predicate
greater<int> with values (1, 3, 7, 1, 2). Comparing adjacent values,
we find that pred(1,3) is false, pred(3,7) is false, pred(7,1) is
true, and pred(1,2) is false. Therefore we expect output values to
be 1,3,7,2.

What happens instead? We find that pred(1,3) is false, pred(3,7) is
false, pred(7,1) is true, and *pred(7,2) is true*. The last
comparison isn't what we expected! Because of the return values, we
end up omitting the final 2 from the result set.

If you don't agree with me, then please consider this program,
quite similar to Stefan's original program:

   #include <algorithm>
   #include <functional>
   #include <iostream>
   using namespace std;
   struct myInt {
       int i;
       ostream&show(ostream&o) const
           { return o<<" ("<<i<<" at "<<this<<')'; }
       myInt(int x) : i(x) { show(cout<<"Construct")<<endl; }
       myInt(const myInt&x) : i(x.i)
           { x.show(show(cout<<"Copy")<<" from")<<endl; }
       ~myInt() { show(cout<<"Destroy ")<<endl; }
       myInt&operator=(const myInt&x)
           { x.show(show(cout<<"Assign")<<" from")<<endl;
             i=x.i;
             return *this; }
       bool operator==(const myInt&x) const
           { return i-7<x.i && i+7>x.i; }
       //bool operator==(const myInt&x) const { return i>x.i; }
   };
   ostream&operator<<(ostream&o,const myInt&x) { return o<<x.i; }

   struct ApproxEqual {
      bool operator()(const myInt&left, const myInt&right) {
         right.show(left.show(cout<<"Comparing")<<" to")
              << ((left==right) ? ": Equal" : ": Different")
              << endl;
         return left==right;
      }
   };

   int main() {
       myInt f[] = { 10, 20, 24, 28, 40 };
       //myInt f[] = { 1, 3, 7, 1, 2 };
       myInt* z = unique(f, f+5, ApproxEqual());
       copy(f, z, ostream_iterator<myInt>(cout, " "));
       cout << endl;
       return 0;
   }

Notice some of the changes I've used.
 1. I used a class myInt instead of integers. This allows me to use
    debugging statements to see what happens.
 2. My predicate could be called "approximately equal." It returns
    true if the values are within 7 of each other.
 3. I've changed the values in f[] to emphasize my points.

Now you know the input data and the predicate, so go ahead and
predict the output values. Go on, do it right now. I'll wait.

Okay, did you write down your prediction? Personally, I expected
to see this:
   Construct 10 at addr0 // First construct the array: f[0]
   Construct 20 at addr1 // f[1]
   Construct 24 at addr2 // f2
   Construct 28 at addr3 // f3
   Construct 32 at addr4 // f4
   // Now start comparing until we find an equal pair
   Comparing (10 at addr0) to (20 at addr1): Different // f0 vs f1
   Comparing (20 at addr1) to (24 at addr2): Equal     // f1 vs f2
   // So f[2] can be overwritten by the next one that's different
   Comparing (24 at addr2) to (28 at addr3): Equal     // f2 vs f3
   Comparing (28 at addr3) to (40 at addr4): Different // f3 vs f4
   // Found one that's different, do the overwrite: f2=f4
   Assign (24 at addr2) from (40 at addr4)             // f2=f4
   10 20 40
   // Destroy array on exit
   Destroy 40 at addr4 // Stale values: f4
   Destroy 28 at addr3 // f3
   Destroy 40 at addr2 // Retained values: f2
   Destroy 20 at addr1 // f1
   Destroy 10 at addr0 // f0

Here's what I got instead, when I ran it in MSVC6:
   Construct (10 at 0012FF60) // Construct the array: f[0]
   Construct (20 at 0012FF64) // f1
   Construct (24 at 0012FF68) // f2
   Construct (28 at 0012FF6C) // f3
   Construct (40 at 0012FF70) // f4
   // Start comparing until we find an equal pair
   Comparing (10 at 0012FF60) to (20 at 0012FF64): Different // f0,f1
   Comparing (20 at 0012FF64) to (24 at 0012FF68): Equal     // f1,f2
   // A redundant assign and compare?!?
   Assign (20 at 0012FF64) from (20 at 0012FF64)             // f1=f1
   Comparing (20 at 0012FF64) to (24 at 0012FF68): Equal     // f1,f2
   // ***********************************************
   // *** NEXT: we compare f1,f3 instead of f2,f3 ***  <<== PROBLEM!
   // ***********************************************
   Comparing (20 at 0012FF64) to (28 at 0012FF6C): Different // f1,f3
   Assign (24 at 0012FF68) from (28 at 0012FF6C)             // f2=f3
   // Finish by comparing f2,f4
   Comparing (28 at 0012FF6C) to (40 at 0012FF70): Different // f2,f4
   Assign (28 at 0012FF6C) from (40 at 0012FF70)             // f2=f4
   10 20 28 40
   // Destroy array on exit
   Destroy  (40 at 0012FF70) // Stale value in f[4]
   Destroy  (40 at 0012FF6C) // Retained value in f[3]
   Destroy  (28 at 0012FF68) // f2
   Destroy  (20 at 0012FF64) // f1
   Destroy  (10 at 0012FF60) // f0

See the problem? Once we decided to keep the value 20, we used that
to compare to 28 instead of comparint 24 to 28.

To see the same problem at work in Stefan's original complaint,
simply change the definition of operator== and array f[] to use
the commented-out versions.

--
Allan_W@my-deja.com is a "Spam Magnet," never read.
Please reply in newsgroups only, sorry.


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ 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 <38825C48.53A99E91@acm.org>,
  Pete Becker <petebecker@acm.org> wrote:
>
> James Kuyper wrote:
> >
> > Pete Becker wrote:
> > ....
> > > Possibly, but my concern is clarity. Consider what happens to
> > > an average programmer who sees unique being called with a
> > > predicate that returns true when its two arguments are unequal.
> >
> > I may have lost track of your point. Are you suggesting that
> > it's wrong to use such a predicate? Why use the form of
> > unique<> that requires a predicate if the non-predicate form
> > would do the same thing?
> >
>
> What I suggested is that unique with UNequal is very confusing.

  struct CensusPerson {
     string Name;
     unsigned long HouseHoldID;
     // much more...
  };
  struct SameHousehold {
     bool operator()(const CensusPerson&a,const CensusPerson&b)
        { return a.HouseHoldID==b.HouseHoldID; }
  };
  struct DifferentHousehold {
     bool operator()(const CensusPerson&a,const CensusPerson&b)
        { return a.HouseHoldID!=b.HouseHoldID; }
  };

  // Find out how many homes have two or more people in them
  // Prerequisite: list of CensusPerson is sorted by HouseHoldID
  size_t MultiPersonHomes(const CensusPerson*x, int count)
  {
      // Special case
      if (count<2) return count;

      // Make a copy that we can destroy
      CensusPerson *list = new CensusPerson[count];
      for (int i=0; i<count; ++i) list[i]=x[i];

      // First household stays on list even if it's single-person
      // So initialize to -1 in this case to compensate
      int rval = 0;
      if (DifferentHousehold()(list[0],list[1]))
          --rval;

      // Remove homes with only one person
      // We're sorted by HouseHoldID, so this removes the first
      // person for each ID. Anything remaining by definition
      // must have two or more people.
      CensusPerson *end = unique(list, list+count,
          DifferentHousehold());

      // Don't count the remaining households more than once!
      end = unique(list, end, SameHousehold());

      // Adjust return value
      rval += (end-list);

      // Clean up and get out
      delete[] list;
      return rval;
  }

--
Allan_W@my-deja.com is a "Spam Magnet," never read.
Please reply in newsgroups only, sorry.


Sent via Deja.com http://www.deja.com/
Before you buy.


[ 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              ]

AllanW wrote:
....
> One way to derive constraints is to try to recreate the original
> intent. If unique is supposed to remove "duplicate" items, why do
> we allow the predicate to be overridden at all? The only sensible
> reason for this would be to allow the user to determine which
> items are "duplicate." For instance, if we wish to remove duplicate
> customers from a vector sorted by account number, we must use a
> different predicate than the same vector sorted by last and first
> names.
>
> An important attribute of the STL algorithms is that it recognizes
> that equivalent does not always mean 100% identical. For instance,

One of the points in this debate has been the fact that the standard
says "equal", rather than "equivalent". The word "equal" can't be
intended to constrain to the operation of pred(). If it did constrain
pred(), the constraint it necessarily imposes would be "pred(a,b)!=false
iff std::equal_to(a,b)!=false". I'd feel differently about the matter if
it instead had said "equivalent". Then it would have been plausible that
it was intended to constrain pred() to defining an equivalence relation.

> our duplicate customers may have different addresses, telephone
> numbers, and "last update" dates. Therefore we must know which copy
> of the customer will be retained by unique(). The description of the
> algorithm answers this question.
>
> If you agree with everything I've said so far, you'll agree that
> the user has great control over the way that two elements are
> compared, and that the standard explicitly describes WHICH elements
> are compared. Therefore, if the input values and the predicate are
> both known, the output values should be deterministic and easy to
> predict.

Only if you make an assumption about when the removals occur. The
standard does not seem to specify this. In the following paragraph you
seem to assume that removal of an element occurs only after all
comparisons that the removed element could have been involved in have
been resolved.

> In the original post, Stefan did exactly that -- he used predicate
> greater<int> with values (1, 3, 7, 1, 2). Comparing adjacent values,
> we find that pred(1,3) is false, pred(3,7) is false, pred(7,1) is
> true, and pred(1,2) is false. Therefore we expect output values to
> be 1,3,7,2.

The standard specifies the behavior of unique<> in terms of pred(*i,
*(i-1)). Therefore, I wouldn't expect any of the pairs of arguments
you've listed to be relevant, unless we're going to assume that
pred(a,b) is required to equal pred(b,a). But if you were using that
assumption, then you wouldn't have even suggested using greater<int> as
the predicate. Therefore, the result I'd expect is {1,1} (since the
first element in the series happens to be the smallest one, you get the
same results no matter when the removals occur).

This is, however, contrary to current practice. The existing
implementation that I examined applies the predicate in the opposite
order from that specified by the standard, for no particularly good
reason that I can discern. Others contributing to this thread have said
the same about the implementations they've looked at.

> What happens instead? We find that pred(1,3) is false, pred(3,7) is
> false, pred(7,1) is true, and *pred(7,2) is true*. The last
> comparison isn't what we expected! Because of the return values, we
> end up omitting the final 2 from the result set.

The discrepancy arises, of course, from assuming in this case that
removing each element is done immediately, which is effectively what the
implementation I've examined does (what it actually does is to compare
items at gaps larger than 1, skipping the removed elements; this allows
it to copy only the surviving elements, and to copy them only to their
final location, and to only copy them when that final location is
different from the initial one).

> If you don't agree with me, then please consider this program,
> quite similar to Stefan's original program:
>
>    #include <algorithm>
>    #include <functional>
>    #include <iostream>
>    using namespace std;
>    struct myInt {
>        int i;
>        ostream&show(ostream&o) const
>            { return o<<" ("<<i<<" at "<<this<<')'; }
>        myInt(int x) : i(x) { show(cout<<"Construct")<<endl; }
>        myInt(const myInt&x) : i(x.i)
>            { x.show(show(cout<<"Copy")<<" from")<<endl; }
>        ~myInt() { show(cout<<"Destroy ")<<endl; }
>        myInt&operator=(const myInt&x)
>            { x.show(show(cout<<"Assign")<<" from")<<endl;
>              i=x.i;
>              return *this; }
>        bool operator==(const myInt&x) const
>            { return i-7<x.i && i+7>x.i; }
>        //bool operator==(const myInt&x) const { return i>x.i; }
>    };
>    ostream&operator<<(ostream&o,const myInt&x) { return o<<x.i; }
>
>    struct ApproxEqual {
>       bool operator()(const myInt&left, const myInt&right) {
>          right.show(left.show(cout<<"Comparing")<<" to")
>               << ((left==right) ? ": Equal" : ": Different")
>               << endl;
>          return left==right;
>       }
>    };
>
>    int main() {
>        myInt f[] = { 10, 20, 24, 28, 40 };
>        //myInt f[] = { 1, 3, 7, 1, 2 };
>        myInt* z = unique(f, f+5, ApproxEqual());
>        copy(f, z, ostream_iterator<myInt>(cout, " "));
>        cout << endl;
>        return 0;
>    }
>
> Notice some of the changes I've used.
>  1. I used a class myInt instead of integers. This allows me to use
>     debugging statements to see what happens.
>  2. My predicate could be called "approximately equal." It returns
>     true if the values are within 7 of each other.
>  3. I've changed the values in f[] to emphasize my points.
>
> Now you know the input data and the predicate, so go ahead and
> predict the output values. Go on, do it right now. I'll wait.

My predictions for a standard-conforming implementation, using your
notation:
   Construct 10 at addr0
   Construct 20 at addr1
   Construct 24 at addr2
   Construct 28 at addr3
   Construct 32 at addr4
   Construct 40 at addr5
   Comparing (20 at addr1) to (10 at addr0): Different
   Comparing (24 at addr2) to (20 at addr1): Equal

Pete Becker wrote:
>
> Christopher Eltschka wrote:
> >
> > adjacent_remove
> >
>
> That's pretty good, with one reservation: adjacent_find returns the
> first iterator for which the predicate returns true for the value and
> its successor. By analogy, then, adjacent_remove would remove the second
> matching element. So it's a slight extension of the analogy for
> adjacent_remove to remove all but the first element in the matching
> range, and a much more drastic extension to remove elements from all
> such ranges.

find returns the first iterator pointing to an element comparing
  equal to the given object.
remove removes each element comparing eaqual to the given object.

find_if returns the first iterator pointing to an element for which
  the predicate is true.
remove_if removes each element for which the predicate is true.

In both cases, the remove algorithm could be written as

template<class Iter, class T>
 Iter remove_algo(Iter (*find_algo)(Iter, Iter, T),
                  Iter first, Iter last, T extra_arg)
{
  while ((first = find_algo(first, last, extra_arg)) != last)
  {
    Iter next = first;
    ++next;
    copy(next, last, first);
    --last;
  }
  return last;
}

template<class Iter, class T>
 Iter remove(Iter first, Iter last, T const& value)
{
  return remove_algo<Iter, T const&>(find, first, last, value);
}

template<class Iter, class Pred>
 Iter remove_if(Iter first, Iter last, Pred predicate)
{
  return remove_algo<Iter, Pred>(find_if, first, last, predicate);
}

So it's a slight extension of the analogy to remove all but the
first element of each range (the algorithm above, with find_algo being
adjacent_find, would remove all but the last element of each range),
but it would be a huge extension to remove all but the first element
only for the first element.

---
[ 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 <38886F09.C3F08154@acm.org>,
Pete Becker  <petebecker@acm.org> wrote:
>Andrew Koenig wrote:

>> Suppose I describe unique() to you this way:

>>         It makes a sequential pass through the input and selects
>>         the first element and every subsequent element for which
>>         the predicate is false when applied to the most recently
>>         selected element and the candidate.

>>         The result is therefore the maximal sequence of elements
>>         from the original sequence, without changing the relative
>>         order of elements, and with the property that the predicate
>>         is false when applied to every adjacent pair of elements
>>         within the sequence.

>As a library vendor, how do I implement this so that it works when
>someone passes a predicate that randomly chooses between true and false?
>I know how to satisfy the first paragraph, but not the second.

I suspect that there are a lot of algorithms whose descriptions
render them impossible to implement if the user-supplied predicates
are not functions in the mathematical sense -- that is, if you call
them twice with the same argument, you're not guaranteed to get the
same result.

Nevertheless, I think it would be possible to deal with your objection
in this case by changing the second paragraph so that instead of predicting
what would happen if you were to apply the predicate to those arguments
in the future, it made a statement about what had happened when applying
the predicate to those values in the past.
--
Andrew Koenig, ark@research.att.com, http://www.research.att.com/info/ark



[ 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 <5E27226F.4A77BB45@artquest.net>,
Pierre Baillargeon  <pb@artquest.net> wrote:

>So on a pure mathematical scale, option A seems better. But since it
>would appear that most implementations currently are supporting only
>equivalence relations, the result would be:

Why do you think that most implementations currently are supporting
only equivalence relations?
--
Andrew Koenig, ark@research.att.com, http://www.research.att.com/info/ark




[ 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              ]

Andrew Koenig wrote:
>
> Why do you think that most implementations currently are supporting
> only equivalence relations?

Well, studies have shown...

I have to admit that was solely my impression from the posts in this
thread. Since a lot of people kept refererring to the original
implementation doing the comparison with the first element of a range of
identical elements, I assumed that most implementation were still doing
that.

My meta-point remains valid though: depending where one puts value, the
conclusion can differ. I was also trying to treat each side of the
question fairly. Oh well, foiled again.


[ 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              ]

Andrew Koenig wrote:
>
> Suppose I describe unique() to you this way:
>
>         It makes a sequential pass through the input and selects
>         the first element and every subsequent element for which
>         the predicate is false when applied to the most recently
>         selected element and the candidate.
>
>         The result is therefore the maximal sequence of elements
>         from the original sequence, without changing the relative
>         order of elements, and with the property that the predicate
>         is false when applied to every adjacent pair of elements
>         within the sequence.
>

One of the lessons that programmers are supposed to have learned over
the years is that program entities need descriptive names. A somewhat
more advanced lesson is that if you cannot come up with a good name for
some program entity then it probably needs to be redesigned because it
is doing more than one thing. So here's the challenge: what is the name
of this algorithm? In particular, it cannot be "unique", because calling
it with the predicate not_equal produces a sequence of identical
elements.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Andrew Koenig wrote:
>
> Suppose I describe unique() to you this way:
>
>         It makes a sequential pass through the input and selects
>         the first element and every subsequent element for which
>         the predicate is false when applied to the most recently
>         selected element and the candidate.
>
>         The result is therefore the maximal sequence of elements
>         from the original sequence, without changing the relative
>         order of elements, and with the property that the predicate
>         is false when applied to every adjacent pair of elements
>         within the sequence.
>

As a library vendor, how do I implement this so that it works when
someone passes a predicate that randomly chooses between true and false?
I know how to satisfy the first paragraph, but not the second.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <200120001422244755%lisa_lippincott@bigfix.com>, Lisa
Lippincott <lisa_lippincott@bigfix.com> writes
>In general, the traditional unique always produces a sequence in
>which pred( *i, *i-1 ) is false for all i.  And it is thus idempotent --
>applying it a second time will have no effect.

Excellent point.  Whatever our other expectations most of us would not
expect two successive applications of unique to provide something
different from a single one.


Francis Glassborow      Journal Editor, Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation

---
[ 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 20 Jan 2000 17:51:26 GMT, Francis Glassborow
<francis@robinton.demon.co.uk> wrote:

: Well I wouldn't be.  It took me sometime to work out how you arrived at
: the other answers.

I understand that the 2 3 3 answer does not make sense other than the
"common" sense that changing the pred from equal_to to not_equal_to
just might select the items which were originally removed.  Common
sense is almost always wrong when it comes to algorithms.

: For example I would expect 1 2 3 1 2 1 to generate 1
: 1 1 if I used not_equal as the predicate.  In general I would expect a
: list of exactly those elements that compared equal to the first one.

I don't understand why you expect that although the standard states
that pred(*i, *(i-1)) is used an implementation would really use
pred(*o, *i).

I can understand how an implementation could assume that the pred was
an equivalence relation and use code which would only be correct when
it was.  I can also understand how the designer of something as
complex as STL could write a specification for the code which assumed
an equivalence relation but failed to state the assumption.  I can also
understand how this specification could go through the standardization
process without notice.

John

---
[ 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              ]

Darin Adler wrote:
>
>
>    A) Leave the standard alone. Agree that Pete Becker is right, the
> standard is already clear. Don't expect defined behavior if you provide
> a predicate that is not really "equality".

I didn't say that it's clear, just that with some work it's possible to
come up with a resonable interpretation. That doesn't mean that I oppose
fixing it.

>
>    B) Clarify the wording in the standard to make it clear that the
> behavior of unique, unique_copy, and adjacent_find algorithms is
> undefined (or unspecified?) if you provide a predicate that doesn't
> describe an equivalence relation. I'm not sure how to word this, but I'm
> trying to capture Pete's notion of "good" and "bad" predicates.
>
>    C) Correct the standard's description of the algorithm for unique,
> unique_copy, and adjacent_find to match the "traditional
> implementation". Perhaps clarify the wording to make it clear that you
> can pass any predicate you like, and the algorithm presented in the
> standard defines what result you'd get, even if it doesn't match
> someone's intuitive sense of what "union" means.

Or even if it does. <g> (that's obviously a programmer's typo)

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pete Becker wrote:
>
> Andrew Koenig wrote:
> >
> > Suppose I describe unique() to you this way:
> >
> >         It makes a sequential pass through the input and selects
> >         the first element and every subsequent element for which
> >         the predicate is false when applied to the most recently
> >         selected element and the candidate.
> >
> >         The result is therefore the maximal sequence of elements
> >         from the original sequence, without changing the relative
> >         order of elements, and with the property that the predicate
> >         is false when applied to every adjacent pair of elements
> >         within the sequence.
> >
>
> As a library vendor, how do I implement this so that it works when
> someone passes a predicate that randomly chooses between true and false?
> I know how to satisfy the first paragraph, but not the second.

If the second paragraph were made part of the requirements, then it
would have to be accompanied by a requirement that pred(a,b) produces a
result that depends only upon the values of a and b, and not on the
order or number of previous calls to pred().


[ 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              ]

Pete Becker wrote:
>
> John Potter wrote:
> >
> > Common sense is almost always wrong when it comes to algorithms.
> >
>
> It better not be, at least, not when trying to figure out what an
> algorithm is intended to do. If it produces results that surprise most
> users then it is not useful.

By that standard C++ itself is not useful. Which has been of course
already been claimed, for precisely that reason, among others.


[ 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:
>
> adjacent_remove
>

That's pretty good, with one reservation: adjacent_find returns the
first iterator for which the predicate returns true for the value and
its successor. By analogy, then, adjacent_remove would remove the second
matching element. So it's a slight extension of the analogy for
adjacent_remove to remove all but the first element in the matching
range, and a much more drastic extension to remove elements from all
such ranges.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 21 Jan 2000 17:19:20 GMT, James Kuyper <kuyper@wizard.net> wrote:

: I'd have no objection to B or C; but I'd prefer B. I don't like the idea
: of the standard defining the algorithm. It should define the
: requirements and the effects, but not how they're achieved.

That's an interesting point.  In this case, the effects of the algorithm
are determined by the implementation.  I would prefer an algorithm which
was usable because it was well defined to an algorithm which was
unusable except in special cases.  After all, it is an algorithm.

John


[ 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 20 Jan 2000 19:35:13 GMT, Darin Adler <darin@bentspoon.com> wrote:

: I said that I had noticed that there is a traditional implementation
: that compares each element to the first in a range. I mentioned that I
: assumed that all extant implementations of unique, unique_copy, and
: adjacent_find used this traditional implementation, and not what is
: described in the standard.

Could you explain how adjacent_find fits into this discussion?  I can
not find any difference between the standard and the SGI implementation.

John

---
[ 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              ]

James Kuyper wrote:
>
> Pete Becker wrote:
> >
> > John Potter wrote:
> > >
> > > Common sense is almost always wrong when it comes to algorithms.
> > >
> >
> > It better not be, at least, not when trying to figure out what an
> > algorithm is intended to do. If it produces results that surprise most
> > users then it is not useful.
>
> By that standard C++ itself is not useful.
>

Thus demonstrating that C++ is not an algorithm, which is hardly
surprising.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Francis Glassborow wrote:
>
> In article <200120001422244755%lisa_lippincott@bigfix.com>, Lisa
> Lippincott <lisa_lippincott@bigfix.com> writes
> >In general, the traditional unique always produces a sequence in
> >which pred( *i, *i-1 ) is false for all i.  And it is thus idempotent --
> >applying it a second time will have no effect.
>
> Excellent point.  Whatever our other expectations most of us would not
> expect two successive applications of unique to provide something
> different from a single one.
>

Which implies a constraint on the predicates that can be used with
unique. I prefer the one that already has a definition in the standard:
the predicate should be an equivalence relation. I'll leave it to those
who want more flexibility to figure out how to word a constraint that
rules out, for instance, a predicate that returns random values. (There
are less obviously perverse forms of predicates that result in violating
this property, but I think this makes the problem clear)

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Francis Glassborow wrote:
>
> I think option A is a non-starter.  Despite Pete's arguments I do not
> find the current wording adequate.

Again: I have not said that the current wording is adequate. I have said
that its meaning can be determined with some effort.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Sun, 23 Jan 2000 11:34:22 CST, Pete Becker <petebecker@acm.org>
wrote:

: Francis Glassborow wrote:

: > Excellent point.  Whatever our other expectations most of us would not
: > expect two successive applications of unique to provide something
: > different from a single one.
: >

: Which implies a constraint on the predicates that can be used with
: unique. I prefer the one that already has a definition in the standard:
: the predicate should be an equivalence relation. I'll leave it to those
: who want more flexibility to figure out how to word a constraint that
: rules out, for instance, a predicate that returns random values. (There
: are less obviously perverse forms of predicates that result in violating
: this property, but I think this makes the problem clear)

Maybe, I am coming around to your point.  It is possible that this
entire thread is nonsense.  Everyone knows that the requirements for
uniq(ue) are that the input is sorted and that the predicate is equal.
Anything else is an imaginary use of an ill defined algorithm.  There
have been no prior complaints because nobody has tried to do anything
else with this algorithm.  My experience is that uniq -c is a very
useful utility, but I have found no use for any of the other forms.
Maybe I lack imagination.  Of course, uniq -c is not possible with the
standard algorithm.  Maybe nobody uses it.

John


[ 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              ]

Pete Becker wrote:
>
> James Kuyper wrote:
> >
> > Pete Becker wrote:
> > >
> > > John Potter wrote:
> > > >
> > > > Common sense is almost always wrong when it comes to algorithms.
> > > >
> > >
> > > It better not be, at least, not when trying to figure out what an
> > > algorithm is intended to do. If it produces results that surprise most
> > > users then it is not useful.
> >
> > By that standard C++ itself is not useful.
> >
>
> Thus demonstrating that C++ is not an algorithm, which is hardly
> surprising.

Your comment did not appear to rely upon the fact that the thing
producing the confusion was an algorithm; it seemed a more widely
(in)applicable criterion than that.

The fact that an algorithm confuses most users doesn't make it useless.
FFT is a prime example to the contrary. Confusing things require more
care to use; people who can't be bothered to exert that care should use
simpler things. Some things are so confusing that they aren't useable by
anybody. Other things (such as C++ or FFT) confuse most users, yet
remain useful for the minority of users who are both willing and able to
get past the confusion.


[ 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              ]

James Kuyper wrote:
>
> Pete Becker wrote:
> >
> > James Kuyper wrote:
> > >
> > > Pete Becker wrote:
> > > >
> > > > John Potter wrote:
> > > > >
> > > > > Common sense is almost always wrong when it comes to algorithms.
> > > > >
> > > >
> > > > It better not be, at least, not when trying to figure out what an
> > > > algorithm is intended to do. If it produces results that surprise most
> > > > users then it is not useful.
> > >
> > > By that standard C++ itself is not useful.
> > >
> >
> > Thus demonstrating that C++ is not an algorithm, which is hardly
> > surprising.
>
> Your comment did not appear to rely upon the fact that the thing
> producing the confusion was an algorithm; it seemed a more widely
> (in)applicable criterion than that.
>
> The fact that an algorithm confuses most users doesn't make it useless.
> FFT is a prime example to the contrary. Confusing things require more
> care to use; people who can't be bothered to exert that care should use
> simpler things. Some things are so confusing that they aren't useable by
> anybody. Other things (such as C++ or FFT) confuse most users, yet
> remain useful for the minority of users who are both willing and able to
> get past the confusion.
>

Thus demonstrating that analyzing humor destroys it, which is hardly
surprising.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pete Becker wrote:
>
> James Kuyper wrote:
> >
> > Pete Becker wrote:
> > ....
> > > Possibly, but my concern is clarity. Consider what happens to an average
> > > programmer who sees unique being called with a predicate that returns
> > > true when its two arguments are unequal.
> >
> > I may have lost track of your point. Are you suggesting that it's wrong
> > to use such a predicate? Why use the form of unique<> that requires a
> > predicate if the non-predicate form would do the same thing?
> >
>
> What I suggested is that unique with UNequal is very confusing.

Ah! You mean specifically std::not_equal_to<>, or equivalent? I thought
you meant any predicate which, for some particular pair of unequal
arguments, returns true.

---
[ 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              ]

James Kuyper wrote:
>
> Pete Becker wrote:
> >
> > James Kuyper wrote:
> > >
> > > Pete Becker wrote:
> > > ....
> > > > Possibly, but my concern is clarity. Consider what happens to an average
> > > > programmer who sees unique being called with a predicate that returns
> > > > true when its two arguments are unequal.
> > >
> > > I may have lost track of your point. Are you suggesting that it's wrong
> > > to use such a predicate? Why use the form of unique<> that requires a
> > > predicate if the non-predicate form would do the same thing?
> > >
> >
> > What I suggested is that unique with UNequal is very confusing.
>
> Ah! You mean specifically std::not_equal_to<>, or equivalent?

Right. It's an example that would look very strange to a casual reader.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper wrote:
>
> True. However, you've been saying that "equal" doesn't mean "equal", but
> instead means something like "in the same equivalence class as defined
> by _pred_".

No, I've been saying that one meaning of "equal" is "in the same
equivalence class." It's not a coincidence that "equivalence" has the
same root as "equal."

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pete Becker wrote:
>
> James Kuyper wrote:
> >
> > True. However, you've been saying that "equal" doesn't mean "equal", but
> > instead means something like "in the same equivalence class as defined
> > by _pred_".
>
> No, I've been saying that one meaning of "equal" is "in the same
> equivalence class." It's not a coincidence that "equivalence" has the
> same root as "equal."

It's also not a coincidence that "equivalent" is a different word than
"equal", with a different meaning. "equal" implies "equivalent", but not
vice-versa. Can you cite any support for the contrary claim? Note: this
must be in a technical context - "All men are created equal" doesn't
count.

---
[ 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 <3883ACAF.8F786DA0@acm.org>, petebecker@acm.org says...
>
> James Kuyper wrote:
> >
> > True. However, you've been saying that "equal" doesn't mean "equal", but
> > instead means something like "in the same equivalence class as defined
> > by _pred_".
>
> No, I've been saying that one meaning of "equal" is "in the same
> equivalence class."

But that is simply not correct. Objects in the same equivalence class are
equivalent. They may or may not be equal.

> It's not a coincidence that "equivalence" has the
> same root as "equal."

Yes, because equivalence behaves similarly to equality, not because they
are the same thing.

Seth Jones

---
[ 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 Tue, 18 Jan 2000 19:49:17 CST, Pete Becker <petebecker@acm.org>
wrote:

: James Kuyper wrote:
: >
: > Pete Becker wrote:
: > > What I suggested is that unique with UNequal is very confusing.
: >
: > Ah! You mean specifically std::not_equal_to<>, or equivalent?
:
: Right. It's an example that would look very strange to a casual reader.

Given that most C++ programs look strange to a casual reader, what would
the serious reader expect?

Given: 1 2 2 3 3 3

Unique with equal_to would produce 1 2 3.

I might expect unique with not_equal_to to produce the others 2 3 3.

I would get the mild surprise that it was really 1 2 3 3 since the
first item is never removed.  That of course assumes that the code
does what the standard says.

I would be shocked by most implementations which would produce 1.

John

---
[ 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              ]

Andrew Koenig wrote:
>
> In article <3884e562.9885792@news.csrlink.net>,
> John Potter <jpotter@falcon.lhup.edu> wrote:
> >On Tue, 18 Jan 2000 19:49:17 CST, Pete Becker <petebecker@acm.org>
> >wrote:
>
> >Given: 1 2 2 3 3 3
>
> >Unique with equal_to would produce 1 2 3.
>
> >I might expect unique with not_equal_to to produce the others 2 3 3.
>
> >I would get the mild surprise that it was really 1 2 3 3 since the
> >first item is never removed.  That of course assumes that the code
> >does what the standard says.
>
> >I would be shocked by most implementations which would produce 1.
>
> Why would you be shocked?

Um, possibly because that's not what the standard says? John is right, a
standard conforming implementation of unique() would produce 1 2 3 3. I
can't see any way to justify 1. (I don't understand why John expected 2
3 3 either.)

> Suppose I describe unique() to you this way:
>
>         It makes a sequential pass through the input and selects
>         the first element and every subsequent element for which
>         the predicate is false when applied to the most recently
>         selected element and the candidate.
>
>         The result is therefore the maximal sequence of elements
>         from the original sequence, without changing the relative
>         order of elements, and with the property that the predicate
>         is false when applied to every adjacent pair of elements
>         within the sequence.

But you're not describing the same algorithm as the standard.

I tested this with GCC (SGI library) and MSVC (Dinkumware library). Both
gave 1 as the output with not_equal_to. I believe both are in violation
of the standard.

--
Ross Smith <ross.s@ihug.co.nz> The Internet Group, Auckland, New Zealand
========================================================================
    "Be careful about using the following code -- I've only proven
    that it works, I haven't tested it."           -- Donald Knuth


[ 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 Thu, 20 Jan 2000 04:52:10 CST, ark@research.att.com (Andrew Koenig)
wrote:

: Now, I think it is entirely reasonable to disagree over whether this
: is how unique() should behave.  However, I think it's plausible behavior,
: and it is how the SGI implementation actually does behave.

Plausible accepted.

I would expect unique with less to be a no-op and less_equal to act the
same as equal_to.  The SGI implementation acts the same with these as
it does with not_equal_to.  Is this also plausible?

Seriously, if unique states that it requires an equivalence relation
for the predicate, the SGI implementation works correctly.  The loss
of other behavior with non-equivalence relations would be no big
loss since I can't really think of a use for them.  I would not like
to see the behavior implied by the standard and the behavior of the
SGI implementation to be opposing standard behaviors.

John

---
[ 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              ]

This thread is really amusing IMHO. A few lines in the standard,
and interpretations so far from each other... Whatever the current
wording really means, I think this discussion should be enough
to justify a rephrasing of the standard.

For the version of unique with a predicate, I think the standard
should either specify the behaviour or explicitly state the
requirements of the predicate, and explicitly state that the
result of unique with predicates that don't fulfill thos
requirements is unspecified.

Following this discussion I have come to believe that it is
possible to gain in optimization if one restrict the predicates
to those that specify an equivalence.

/Niklas Mellin



Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ 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              ]

James Kuyper wrote:
>
> Pete Becker wrote:
> >
> > James Kuyper wrote:
> > >
> > > True. However, you've been saying that "equal" doesn't mean "equal", but
> > > instead means something like "in the same equivalence class as defined
> > > by _pred_".
> >
> > No, I've been saying that one meaning of "equal" is "in the same
> > equivalence class." It's not a coincidence that "equivalence" has the
> > same root as "equal."
>
> It's also not a coincidence that "equivalent" is a different word than
> "equal", with a different meaning. "equal" implies "equivalent", but not
> vice-versa. Can you cite any support for the contrary claim? Note: this
> must be in a technical context - "All men are created equal" doesn't
> count.
>

As I've said too many times, when you interpret documents that aren't
perfectly clear you must apply reasonable meanings of terms, not literal
ones. You are, of course, free to disagree, and insist that the
predicate form of unique can only be the same as the non-predicate form.
I have no further time to waste on this pointless exercise in obstinacy.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <866gjq$kgv$1@nnrp1.deja.com>,
Niklas Mellin  <nimel@my-deja.com> wrote:

>For the version of unique with a predicate, I think the standard
>should either specify the behaviour or explicitly state the
>requirements of the predicate, and explicitly state that the
>result of unique with predicates that don't fulfill thos
>requirements is unspecified.

Of course!  But the question is which of these two alternatives
to follow.  I think the answer is far from clear, and that we
should think carefully about all the alternatives before deciding.
--
Andrew Koenig, ark@research.att.com, http://www.research.att.com/info/ark



[ 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 <3884e562.9885792@news.csrlink.net>, John Potter
<jpotter@falcon.lhup.edu> writes
>Given that most C++ programs look strange to a casual reader, what would
>the serious reader expect?
>
>Given: 1 2 2 3 3 3
>
>Unique with equal_to would produce 1 2 3.
>
>I might expect unique with not_equal_to to produce the others 2 3 3.
>
>I would get the mild surprise that it was really 1 2 3 3 since the
>first item is never removed.  That of course assumes that the code
>does what the standard says.
>
>I would be shocked by most implementations which would produce 1.

Well I wouldn't be.  It took me sometime to work out how you arrived at
the other answers.  For example I would expect 1 2 3 1 2 1 to generate 1
1 1 if I used not_equal as the predicate.  In general I would expect a
list of exactly those elements that compared equal to the first one.


Francis Glassborow      Journal Editor, Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation


[ 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              ]

Niklas Mellin wrote:
....
> Following this discussion I have come to believe that it is
> possible to gain in optimization if one restrict the predicates
> to those that specify an equivalence.

I don't think so - while the existing implementations always compare to
the first element in a sequence of equivalent elements instead of to
*(i-1), there's no obvious advantage to doing so. If the standard
specified that all removals occur after any comparisons involving the
removed elements, and made it clear that the predicate can be arbitrary,
I don't think the changes needed would make unique<> any less efficient.


[ 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 <FoLvyt.MoH@research.att.com>, ark@research.att.com (Andrew
Koenig) wrote:

> And that's the crux of the problem:  When the two major implementations
> contradict the standard, and we've gone this long without anyone
> realizing it, it is at least possible that the standard doesn't
> actually say what everyone was under the impression it said --
> especially when there seems to be some disagreement about exactly
> what the standard says.

That's strange. I thought that my first message (sent on January 2 and
5), the very first response to the original query, addressed this.

I said that I had noticed that there is a traditional implementation
that compares each element to the first in a range. I mentioned that I
assumed that all extant implementations of unique, unique_copy, and
adjacent_find used this traditional implementation, and not what is
described in the standard.

I suggested a defect report that would correct the standard to match the
traditional implementation.

Pete Becker has made the case that the existing standard already
mandates that the equality predicate must satisfy certain invariants
that he claims are implicit in the use of the words "equal" and
"equality" in the standard. If you pass a "bad" predicate, the results
are undefined (or perhaps unspecified).

I don't agree, but I understand his argument.

> The description in the standard of how unique() is supposed to behave
> is not completely clear, and there is a case to be made that the
> committee should correct the description by making the minimum change
> that will clarify it.  I am concerned that if the committee does so,
> it may require existing implementations to change in ways that will
> change the behavior of programs whose authors thought they could rely
> on existing behavior.  I think that it is therefore worth thinking
> about all the alternatives, and the ramifications of each, before
> deciding what to do.

I think there are 4 alternatives:

   A) Leave the standard alone. Agree that Pete Becker is right, the
standard is already clear. Don't expect defined behavior if you provide
a predicate that is not really "equality".

   B) Clarify the wording in the standard to make it clear that the
behavior of unique, unique_copy, and adjacent_find algorithms is
undefined (or unspecified?) if you provide a predicate that doesn't
describe an equivalence relation. I'm not sure how to word this, but I'm
trying to capture Pete's notion of "good" and "bad" predicates.

   C) Correct the standard's description of the algorithm for unique,
unique_copy, and adjacent_find to match the "traditional
implementation". Perhaps clarify the wording to make it clear that you
can pass any predicate you like, and the algorithm presented in the
standard defines what result you'd get, even if it doesn't match
someone's intuitive sense of what "union" means.

   D) Clarify the wording in the standard to make it clear that you can
pass any predicate you like, and the algorithm presented in the standard
defines what result you'd get, even if it doesn't match someone's
intuitive sense of what "union" means.

Alternative A requires no work at all.

Alternative B requires a change to the standard. Implementations won't
need to change anything.

Alternative C requires a change to the standard. Most implementations
won't need to change anything, but some may have to be modified to match
the updated standard.

Alternative D requires a change to the standard, and a change to most
implementations.

People have made convincing arguments that since we are disagreeing
about the requirements in the current standard, alternative A, no
change, is not a good idea.

If I understand his message correctly, I think Andy Koenig is suggesting
that we should think twice before choosing alternative D, since it would
require changes to many library implementations.

I prefer alternative C; I'd like to correct the standard to match the
existing implementations.

    -- Darin


[ 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 Fri, 21 Jan 2000 04:15:49 CST, ark@research.att.com (Andrew Koenig)
wrote:

: In article <3886673f.16264880@news.csrlink.net>,
: John Potter <jpotter@falcon.lhup.edu> wrote:
: >On Thu, 20 Jan 2000 04:52:10 CST, ark@research.att.com (Andrew Koenig)
: >wrote:
:
: >: Now, I think it is entirely reasonable to disagree over whether this
: >: is how unique() should behave.  However, I think it's plausible behavior,
: >: and it is how the SGI implementation actually does behave.
:
: >Plausible accepted.
:
: >I would expect unique with less to be a no-op and less_equal to act the
: >same as equal_to.  The SGI implementation acts the same with these as
: >it does with not_equal_to.  Is this also plausible?
:
: I don't think that's what it does.

I don't think we are communicating.  The data was sorted in ascending
order.  Since the standard says that pred is applied to *i, *(i-1)
the result of pred will always be false for less and only be true
for less_equal when equal_to is true.  Since the SGI implementation
reverses the order of the pred in addition to using *o in place of
*(i-1), the result on 1 2 2 3 3 3 is 1 for both less and less_equal.

The order of application of the pred is not important, but it is
important that the standard and the implementation agree.  Considering
that this thread began with an example which used the wrong pred to
match the implementation, you are likely right that it should be
applied left to right not right to left as the standard states.

: My earlier description of what I think is the actual behavior is
: useful in practice.

Ok.  Consider that uniq -d which has been around for 30 years must
be useful in practice.  [for those not aware of the un*x utility,
uniq -d produces a single copy of all records which occur more than
once 1 2 2 3 3 3 -> 2 3].

vector<T> v;
// fill it and sort it
v.erase(unique_copy(v.begin() + 1, unique(v.begin(), v.end(),
      not_equal_to<T>()), v.begin()), v.end());

should do it.  Using the SGI version?

You have convinced me that other than an equivalence relation may be
useful.  Since your goal is to get the standard and the implementations
to agree, I support your efforts.

John


[ 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              ]

Darin Adler <darin@bentspoon.com> supports:
>    C) Correct the standard's description of the algorithm for unique,
> unique_copy, and adjacent_find to match the "traditional
> implementation". Perhaps clarify the wording to make it clear that you
> can pass any predicate you like, and the algorithm presented in the
> standard defines what result you'd get, even if it doesn't match
> someone's intuitive sense of what "union" means.

over the alternative

>    D) Clarify the wording in the standard to make it clear that you can
> pass any predicate you like, and the algorithm presented in the standard
> defines what result you'd get, even if it doesn't match someone's
> intuitive sense of what "union" means.

(and I think he has written "union" where he means "unique.)

I also prefer (C).  In addition to the advantage of blessing the
common practice, I expect the common definition of unique to produce
a more useful function than the standard definition.

Consider using the traditional unique with the world's favorite
non-equivalence binary relations: less, greater, less_equal, and
greater_equal.  The results are the subsequences of high- or low-water
marks of the original sequence.  Unique with any of these predicates
will produce a monotonic sequence; with less_equal and greater_equal
it will produce a strictly monotonic sequence.

In general, the traditional unique always produces a sequence in
which pred( *i, *i-1 ) is false for all i.  And it is thus idempotent --
applying it a second time will have no effect.

Now consider the algorithm in the standard.  When used with the ordering
relations, it finds the points where the original sequence rose or
fell.  That is also a potentially useful function -- Andrew Koenig's
stock market usage seems to apply equally well in this case.  But
there's no property that can be asserted of the resulting sequence
without reference to the original.  In fact, if our ordering has no
endpoints, then for any sequence S there is a sequence T which
this version of unique would convert to S.

                                             --Lisa Lippincott

---
[ 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              ]

Darin Adler wrote:
....
> I think there are 4 alternatives:
....
>    B) Clarify the wording in the standard to make it clear that the
> behavior of unique, unique_copy, and adjacent_find algorithms is
> undefined (or unspecified?) if you provide a predicate that doesn't
> describe an equivalence relation. I'm not sure how to word this, but I'm
> trying to capture Pete's notion of "good" and "bad" predicates.
>
>    C) Correct the standard's description of the algorithm for unique,
> unique_copy, and adjacent_find to match the "traditional
> implementation". Perhaps clarify the wording to make it clear that you
> can pass any predicate you like, and the algorithm presented in the
> standard defines what result you'd get, even if it doesn't match
> someone's intuitive sense of what "union" means.
....
> Alternative B requires a change to the standard. Implementations won't
> need to change anything.
>
> Alternative C requires a change to the standard. Most implementations
> won't need to change anything, but some may have to be modified to match
> the updated standard.
....
> I prefer alternative C; I'd like to correct the standard to match the
> existing implementations.

I'd have no objection to B or C; but I'd prefer B. I don't like the idea
of the standard defining the algorithm. It should define the
requirements and the effects, but not how they're achieved.


[ 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              ]

Pete Becker wrote:
>
> Andrew Koenig wrote:
> >
> > Suppose I describe unique() to you this way:
> >
> >         It makes a sequential pass through the input and selects
> >         the first element and every subsequent element for which
> >         the predicate is false when applied to the most recently
> >         selected element and the candidate.
> >
> >         The result is therefore the maximal sequence of elements
> >         from the original sequence, without changing the relative
> >         order of elements, and with the property that the predicate
> >         is false when applied to every adjacent pair of elements
> >         within the sequence.
> >
>
> One of the lessons that programmers are supposed to have learned over
> the years is that program entities need descriptive names. A somewhat
> more advanced lesson is that if you cannot come up with a good name for
> some program entity then it probably needs to be redesigned because it
> is doing more than one thing. So here's the challenge: what is the name
> of this algorithm? In particular, it cannot be "unique", because calling
> it with the predicate not_equal produces a sequence of identical
> elements.

adjacent_remove

(See: remove_if, find_if, adjacent_find)


[ 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              ]

Andrew Koenig wrote:
>
> Of course!  But the question is which of these two alternatives
> to follow.  I think the answer is far from clear, and that we
> should think carefully about all the alternatives before deciding.

I will be so presomptuous as to present my take on the effects on
existing code.


Code is divided in three categories:

1. user code using equivalence-relation predicates;
2. user code using non-equivalence predicates;
3. implementor code.


Effects are divided into the following categories:

i.   defined vs. undefined (conforming vs. non-conforming for
implementor);
ii.  expected result vs. unexpected result;
iii. same behavior vs. new behavior.
iv.  same optimizations vs. lost optimizations.


Notes:

i.   Conforming includes behavior more general than the standard
requires.
ii.  Effect describes what the user expected to see. Varies for each
user.
iii. Effect describe that the result of applying unique changed.
iv.  Effect is hard to assess, but we are assuming worst case.


Current implementations are divided in two categories:

a. designed to accept any predicate;
b. designed to accept only equivalence-relation predicates.


In the current situation, where the standard is considered unclear
according to some people, thus all implementations are conforming, we
have the following situations (ignoring effects iii and iv since the
implementation does not change).

a.1. Defined, gets expected result.
a.2. Defined, gets expected result.

b.1. Defined, expected result.
b.2. Undefined, unexpected result.


We have five cases to study if the standard is changed, as shown in the
following list.

A. New standard specifies any predicates and:
  a. current implementation designed to accept any predicate;
  b. current implementation designed to accept only equiv-rel
predicates.

B. New standard specifies only equivalence-relation predicates and:
  a. current implementation designed to accept any predicate and stays;
  b. current implementation designed to accept any predicate and
changes;
  c. current implementation designed to accept only equiv-rel
predicates.


Notes:

A.b.The current implementation is non-conforming, thus it is forced to
change. The result on user code is described after the implementation is
changed to be conforming, otherwise there would be no effect to
describe!

B.a. The implementation is assumed to stay the same and thus allow
on-conforming code by supporting any predicates as an extension.
Otherwise the case folds back to be B.b.


The results of using new standard A and B on implementation a, b, and c,
on categories 1, 2 and 3:

A.a.1. Defined, expected result, same behavior, same optimizations.
A.a.2. Defined, expected result, same behavior, same optimizations.
A.a.3. Conforming.

A.b.1. Defined, expected results, same behavior, lost optimizations.
A.b.2. Defined, expected results, different behavior, lost
optimizations.
A.b.3. Non-conforming.

B.a.1. Undefined, expected results, same behavior, same optimizations.
B.a.2. Defined, expected results, same behavior, same optimizations.
B.a.3. Conforming.

B.b.1. Undefined, unexpected results, different behavior, lost
optimizations.
B.b.2. Defined, expected results, same behavior, lost optimizations.
B.b.3. Conforming.

B.c.1. Undefined, unexpected results, same behavior, same optimizations.
B.c.2. Defined, expected results, same behavior, same optimizations.
B.c.3. Conforming.


So, if all implementation and usages are deemed to have equal value, and
all effects also are given equal value, then the tally would be:

A. 14 positive results, 4 negatives, on two cases, giving an average of
+5 (14/2 - 4/2).

B. 19 positive results, 8 negatives, on three cases, giving an average
of +3.66 (19/3 - 8/3).


So on a pure mathematical scale, option A seems better. But since it
would appear that most implementations currently are supporting only
equivalence relations, the result would be:

A. 5 positives, 4 negatives, giving +1.

B. 7 positives, 2 negatives, giving +5.


Which is reverse! Also, some effect can be seen to have little or a lot
of value according to different priorities, experience and knowledge.
For example, it could be demonstrated wetheir optimization are really
lost or not. At least, I believe this study outlines the different
alternatives and their results.


Pierre Baillargeon


[ 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              ]

Pete Becker wrote:
....
> As I've said too many times, when you interpret documents that aren't
> perfectly clear you must apply reasonable meanings of terms, not literal
> ones. You are, of course, free to disagree, and insist that the
> predicate form of unique can only be the same as the non-predicate form.

No, that's not what I'm insisting - I'm saying that possible reasonable
meanings include the one I've been promoting: that "equal" is meant only
as shorthand term chosen to imply the default behavior when no predicate
is provided, but not as a constraint on the predicate when it is
provided.

If you insist that "equal" constrains the predicate, then it must
constrain it to be equal. If reasonableness applies, then by my
understanding of reasonable, arbitrary predicates that return a type
convertible to bool are allowed. I can't see justification for your
intermediate step where "equal" means "equivalent", rather than "equal".

This is modified by the concession I've already made: using the fact
that the standard doesn't specify the timing of removals from the list
relative to the evaluation of the predicate, you can derive constraints
on the predicate that are similar to, but weaker than, requiring it to
define equivalence classes, but I'm really hesitant to promote those to
a requirement. I'd prefer to modify the description to make it clear
that the algorithm must act as-if the removals occur after any predicate
evaluations that would be affected by the removals; unfortunately, this
would break the currently most common implementations, so I'm not
pressing for such a change.

The fact that we have different ideas about what's reasonable here is a
prime example of why the standard should be written so that its correct
interpretation is as independent as possible of ideas of reasonableness,
because they can vary from one person to the next.


[ 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 <darin-0FE691.10480520012000@fullnews.metawire.com>, Darin
Adler <darin@bentspoon.com> writes
>I prefer alternative C; I'd like to correct the standard to match the
>existing implementations.

I would be interested to learn how many implementations would be
effected by such a change.  I would also like to know if this is because
they have already changed from an earlier version that supported the
'classical' version.  If we are going to make this change we need to
give notice that it is under consideration as soon as possible.

I think option A is a non-starter.  Despite Pete's arguments I do not
find the current wording adequate.  While B is possible it suffers from
most of the problems of C and D while adding what I consider to be a
gratuitous 'undefined behaviour' as there is no (to me) convincing
technical reason why the behaviour should be undefined.

Option D seems to require the maximal change to existing systems while
reducing change to the standard.  The desirability of such is a value
judgement that requires some data to determine 'least damage'.


Francis Glassborow      Journal Editor, Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation


[ 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              ]

John Potter wrote:
>
> Common sense is almost always wrong when it comes to algorithms.
>

It better not be, at least, not when trying to figure out what an
algorithm is intended to do. If it produces results that surprise most
users then it is not useful.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pete Becker wrote:
>
> James Kuyper wrote:
....
> > Yes, but it may be reasonably be interpreted as changing what is meant
> > by the phrase "equal elements", to mean elements for which the predicate
> > is != false, with the predicate defaulting to std::equal_to<> when not
> > explicitly provided.
> >
>
> Seems to me quite clear that "equal" means "equal", not "equal unless
> the user provides some other predicate, in which case it means not
> equal."

That's not what I was suggesting. At no point did I suggest that it
means "std::not1(std::equal_to())", unless that is in fact the predicate
provided by the user. Among other things, I believe that unique<> may
legally be instantiated even for a type for which std::equal_to<> can't
be.

Consider a supposed specialization of unique for a type which supports
'=='. Imagine that it evaluates the predicate with the appropriate
arguments, but only for it's side-effects. For the actual decision
making, it uses '=='. By your arguments, that would be a legal
implementation under the as-if rule, since any predicate which wasn't
functionally equivalent to '==' couldn't be said to define "equal"
elements. Is that what you intend?

If the standard requires something for the predicate other than exact
equivalence to '==', it needs to specify what that is. In the absence of
such a specification, unique<> should do what the standard says it does,
with an arbitrary predicate applied only in the manner specified,
thereby defining what constitute "equal" elements. It doesn't specify
that pred(a,a)==true, that (pred(a,b)&&!pred(b,a))==false, nor that
(pred(a,b)&&pred(b,c)&&!pred(a,c))==false. unique<> doesn't need to make
use of any of those identities to perform it's task, so I see no point
in requiring them.

---
[ 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              ]

nimel@my-deja.com wrote:
>
> It wasn't my copy, it was my reading that went wrong

That's a relief. I'd hate to think that there were peculiar versions of
the standard floating around.

> But even then I think "equal" is defined in the end of the clause
> as beeing pred(*i, *(i-1)) != false.

That would conflict with the meaning that "equal" already has.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper wrote:
>
> If the standard requires something for the predicate other than exact
> equivalence to '==', it needs to specify what that is. In the absence of
> such a specification, unique<> should do what the standard says it does,
> with an arbitrary predicate applied only in the manner specified,
> thereby defining what constitute "equal" elements. It doesn't specify
> that pred(a,a)==true, that (pred(a,b)&&!pred(b,a))==false, nor that
> (pred(a,b)&&pred(b,c)&&!pred(a,c))==false. unique<> doesn't need to make
> use of any of those identities to perform it's task, so I see no point
> in requiring them.

In other words, you think the word "equal" should be ignored. It must
have just been there as a spare, in case some other section ran out of
words.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pete Becker wrote:
>
> James Kuyper wrote:
> >
> > If the standard requires something for the predicate other than exact
> > equivalence to '==', it needs to specify what that is. In the absence of
> > such a specification, unique<> should do what the standard says it does,
> > with an arbitrary predicate applied only in the manner specified,
> > thereby defining what constitute "equal" elements. It doesn't specify
> > that pred(a,a)==true, that (pred(a,b)&&!pred(b,a))==false, nor that
> > (pred(a,b)&&pred(b,c)&&!pred(a,c))==false. unique<> doesn't need to make
> > use of any of those identities to perform it's task, so I see no point
> > in requiring them.
>
> In other words, you think the word "equal" should be ignored. It must
> have just been there as a spare, in case some other section ran out of
> words.

No - I'm suggesting that it was meant to imply the typical use, which is
not the only possible use. Is the person who actually wrote it available
for comment? Is the predicate's return value ignorable or does it define
what "equal" means when a predicate is provided? If "equal" implies
restrictions on the predicate, what specifically are they? Must a valid
predicate return false iff equal_to<> would return false, or are the
restrictions less severe than that? If the restrictions are less severe,
how much less severe are they, and where are they specified? I couldn't
find any such a specification.

---
[ 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              ]

Michiel Salters wrote:
>
> John Potter wrote:
....
> > I agree with you that either the standard should demand an equivalence
> > relation or unique should do what the standard says for any relation.
>
> I think we can demand from the predicate such useful invariants as
>
> pred(A,B)==true iff pred (B,A)==true
> pred(B,C)==pred(A,C) iff pred(A,B)==true
> (any more needed?)

Are even those needed? If so, why?

---
[ 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              ]

John Potter wrote:
>
> On Wed, 12 Jan 2000 03:33:05 CST, James Kuyper <kuyper@wizard.net>
> wrote:
>
> : What's nonsensical about it? It's no more non-sensical than the
> : description of any other algorithm that allows a user-defined function
> : object to be substituted for the default operation. The function object
> : always changes the behavior; that's the whole point of allowing it.
> : Following your argument to it's logical conclusion, the only predicate
> : allowed would be functionally identical to std::equal_to<>. Any other
> : predicate will do something different; in principle, something that
> : could trip up a implementation that was assuming that the standard
> : required std::equal_to<>.
>
> Too strong.  Consider for int a % 3 == b % 3.  It is not equal_to<>
> but it is an equivalence relation.

Yes, but 4 is not equal to 7, so by Pete's argument a predicate that
defines such an equivalence relation would not be valid. In my opinion,
the predicate determines what "equal" means for unique<>. According to
Pete, the word "equal" determines which predicates are legal for
unique<> - he hasn't actually said so, but I don't see how his argument
can be used to justify any requirement less severe than that
pred(a,b)==false iff std::equal_to(a,b)==false.

....
> I agree with you that either the standard should demand an equivalence
> relation or unique should do what the standard says for any relation.

---
[ 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 12 Jan 2000 17:21:42 GMT, Michiel Salters <salters@lucent.com> wrote:

:
: John Potter wrote:
:
: > I agree with you that either the standard should demand an equivalence
: > relation or unique should do what the standard says for any relation.
:
: I think we can demand from the predicate such useful invariants as
:
: pred(A,B)==true iff pred (B,A)==true

Usually: bool(pred(A,B)) == bool(pred(B,A))
Symetric

: pred(B,C)==pred(A,C) iff pred(A,B)==true

I don't think so: for ==, pred(2,3) == pred(1,3) but pred(1,2) != true

You want
bool(pred(A,B)) && bool(pred(B,C)) implies bool(pred(A,C))
Transitive

: (any more needed?)

bool(pred(A,A))
Reflexive

We have just given the definition of an equivalence relation.  :)

My point was that there are equivalence relations other than equal_to.

Pete says the standard implies an equivalence relation, others disagree.
To me, it looks like clarification is needed.  See above.

John

---
[ 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              ]

James Kuyper wrote:

> Michiel Salters wrote:

> > John Potter wrote:

> > > I agree with you that either the standard should demand an equivalence
> > > relation or unique should do what the standard says for any relation.

> > I think we can demand from the predicate such useful invariants as

> > pred(A,B)==true iff pred (B,A)==true
> > pred(B,C)==pred(A,C) iff pred(A,B)==true
> > (any more needed?)

> Are even those needed? If so, why?

Given 3 elements, say { X Y Z },
after determining that pred (X,Y) is true,
it should be possible to compare Z with either
X or Y to determine if that one should be removed,
too. The choice to compare it with X or Y is IMO
best left to the implementor, since he can predict
(perhaps) which one is likely in a register etc.
If the second condition doesn't hold, this
would be impossible. The first condition is
needed to make the second useful.

I've seen the demand for pred(A,A)==true, but
this follows from the two requirements above.
(E.g. let C be A).

Michiel Salters

---
[ 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              ]

James Kuyper wrote:
>
> John Potter wrote:
> >
> > On Wed, 12 Jan 2000 03:33:05 CST, James Kuyper <kuyper@wizard.net>
> > wrote:
> >
> > : What's nonsensical about it? It's no more non-sensical than the
> > : description of any other algorithm that allows a user-defined function
> > : object to be substituted for the default operation. The function object
> > : always changes the behavior; that's the whole point of allowing it.
> > : Following your argument to it's logical conclusion, the only predicate
> > : allowed would be functionally identical to std::equal_to<>. Any other
> > : predicate will do something different; in principle, something that
> > : could trip up a implementation that was assuming that the standard
> > : required std::equal_to<>.
> >
> > Too strong.  Consider for int a % 3 == b % 3.  It is not equal_to<>
> > but it is an equivalence relation.
>
> Yes, but 4 is not equal to 7, so by Pete's argument a predicate that
> defines such an equivalence relation would not be valid.

No, in fact I said just the opposite: that unique requires a predicate
that defines an equivalence relationship. That's the most reasonable
meaning that can be given to the word "equal" in the context of the
definition of the algorithm unique.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Andrew Koenig wrote:
>
> In article <387D1DC6.EA9645E6@acm.org>,
> Pete Becker  <petebecker@acm.org> wrote:
>
> >In other words, you think the word "equal" should be ignored. It must
> >have just been there as a spare, in case some other section ran out of
> >words.
>
> Subclause 25.2.8 talks about two different versions of unique:
> one that takes a predicate and one that doesn't.   To wit:
>
>         template<class ForwardIterator)
>           ForwardIterator unique(ForwardIterator first, ForwardIterator last);
>
>         template<class ForwardIterator)
>           ForwardIterator unique(ForwardIterator first, ForwardIterator last,
>                                  BinaryPredicate pred);
>
> These two versions share a single description:
>
>         Eliminates all but the first element from every consecutive
>         group of equal elements referred to by the iterator i in the
>         range [first, last) for which the following corresponding
>         conditions hold:  *i == *(i - 1) or pred(*i, *(i - 1)) != false.
>
> What could the word ``corresponding'' mean here?  I believe that it
> means that the two alternatives of the ``or'' correspond to the two
> versions of unique, and that whichever alternative applies to the
> given version is the way in which the algorithm is supposed to ascribe
> a meaning to the word ``equal.''

No, it cannot "ascribe a meaning to the word 'equal'". The word "equal"
already has a meaning.

>
> In other words, calling unique(first, last) compares pairs of adjacent
> elements by using ==, and calling unique(first, last, pred) compares
> pairs of adjacent elements by using pred.

Yes, that's clearly what "corresponding" means: the first uses ==, the
second uses pred.

>
> Now, of course that doesn't say what the word "equal" means.  Reading
> the original STL code makes it clear that the author intended it to
> mean that there is an implicit requirement that the predicate be an
> equivalence relation.  The reason I say that is that although the
> description says that the algorithm compares pairs of adjacent elements,
> that's not what the code actually does.  Instead, it uses the first
> element of every range, which is the one it keeps, to compare with
> all subsequent elements.  This works only if the predicate is transitive,
> which every equivalence relation is required to be.
>
> Therefore, I think that as it stands, the standard contains an ambiguity:

That's a big jump, from "the original said it differently" to "the
current one is ambiguous". I don't see it. Either the word "equal"
applies only to the first variation, in which case it is redundant, or
it applies to both. Since it doesn't appear in other algorithm
definitions, it's deliberate, and cannot be dismissed as redundant.

> the words "equal" and "corresponding" both have meaning individually,
> but it is hard to see how they can both be meaningful at the same time.

Seems easy to me: "equal" means "equal", and in the version that takes a
predicate that must be interpreted sensibly, not ignored, which
naturally suggests that it means that pred should be an equivalence
relationship. As I said earlier, there wouldn't be any discussion if
that were, in fact, what the standard said, but any interpretation of
"equal" that doesn't come out there is at best labored, and at worst
deliberate misinterpretation (the latter is not a comment about any of
the discussion here).

> I will request a clarification from the committee at their next meeting.

That, of course, eliminates the cause for the discussion, but doesn't
help people understand how to read standards.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pete Becker wrote:
>
> James Kuyper wrote:
....
> > for comment? Is the predicate's return value ignorable or does it define
> > what "equal" means when a predicate is provided? If "equal" implies
> > restrictions on the predicate, what specifically are they? Must a valid
> > predicate return false iff equal_to<> would return false, or are the
> > restrictions less severe than that? If the restrictions are less severe,
> > how much less severe are they, and where are they specified? I couldn't
> > find any such a specification.
> >
>
> Of course you couldn't. It's not there. That doesn't mean that it can't
> be reasonably inferred from the description of the algorithm as a whole.
> A less-than operator cannot meaningfully be called an equal operator.

James Kuyper wrote:
>
> Pete Becker wrote:
> >
> > James Kuyper wrote:
> > >
> > > If the standard requires something for the predicate other than exact
> > > equivalence to '==', it needs to specify what that is. In the absence of
> > > such a specification, unique<> should do what the standard says it does,
> > > with an arbitrary predicate applied only in the manner specified,
> > > thereby defining what constitute "equal" elements. It doesn't specify
> > > that pred(a,a)==true, that (pred(a,b)&&!pred(b,a))==false, nor that
> > > (pred(a,b)&&pred(b,c)&&!pred(a,c))==false. unique<> doesn't need to make
> > > use of any of those identities to perform it's task, so I see no point
> > > in requiring them.
> >
> > In other words, you think the word "equal" should be ignored. It must
> > have just been there as a spare, in case some other section ran out of
> > words.
>
> No - I'm suggesting that it was meant to imply the typical use, which is
> not the only possible use. Is the person who actually wrote it available
> for comment? Is the predicate's return value ignorable or does it define
> what "equal" means when a predicate is provided? If "equal" implies
> restrictions on the predicate, what specifically are they? Must a valid
> predicate return false iff equal_to<> would return false, or are the
> restrictions less severe than that? If the restrictions are less severe,
> how much less severe are they, and where are they specified? I couldn't
> find any such a specification.
>

Of course you couldn't. It's not there. That doesn't mean that it can't
be reasonably inferred from the description of the algorithm as a whole.
A less-than operator cannot meaningfully be called an equal operator.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Michiel Salters wrote:
>
> James Kuyper wrote:
>
> > Michiel Salters wrote:
>
> > > John Potter wrote:
>
> > > > I agree with you that either the standard should demand an equivalence
> > > > relation or unique should do what the standard says for any relation.
>
> > > I think we can demand from the predicate such useful invariants as
>
> > > pred(A,B)==true iff pred (B,A)==true
> > > pred(B,C)==pred(A,C) iff pred(A,B)==true
> > > (any more needed?)
>
> > Are even those needed? If so, why?
>
> Given 3 elements, say { X Y Z },
> after determining that pred (X,Y) is true,
> it should be possible to compare Z with either
> X or Y to determine if that one should be removed,

I thought at first that this wasn't needed; since Y would be removed
before Z is checked, and that therefore Z is necessarily checked against
X rather than against Y. However, the description of unique<> doesn't
specify the order of comparison relative to the removal of duplicates;
which implies, as you suggest, that the predicate must be such that the
order doesn't matter. Finally - a reason for constraining the predicate.

> too. The choice to compare it with X or Y is IMO
> best left to the implementor, since he can predict
> (perhaps) which one is likely in a register etc.
> If the second condition doesn't hold, this
> would be impossible. The first condition is
> needed to make the second useful.

Why? Your second condition already has the predicate's arguments in the
order needed to justify this. You don't need the additional requirement
that the arguments can be reversed.

---
[ 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              ]

The discussion is getting a bit theoretical, so lets clearify
it with an example:

template <int N>
struct equal_modulo
{
  bool operator()(int x, int y)
  {
    return (x % N) == /y % N);
  }
};

Is the above predicate class an equivalence relation?
Is it okay to say:
std::equal(container.begin(), container.end(), equal_modulo<3>());

/Niklas Mellin


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ 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              ]

James Kuyper wrote:
>
> Michiel Salters wrote:
> >
> > John Potter wrote:
> ....
> > > I agree with you that either the standard should demand an equivalence
> > > relation or unique should do what the standard says for any relation.
> >
> > I think we can demand from the predicate such useful invariants as
> >
> > pred(A,B)==true iff pred (B,A)==true
> > pred(B,C)==pred(A,C) iff pred(A,B)==true
> > (any more needed?)
>
> Are even those needed? If so, why?

No, the first one follows from the second one (assuming
pred(A, B) is a pure function, i.e. pred(A, B) == pred(A, B)
always holds):

First, pred(A, A) == true holds, since pred(A, A) == pred(A, A)
holds.
Now set C=A in invariant 2, and you get

pred(B, A) == pred(A, A) iff pred(A, B) == true

Since pred(A, A) == true, this is invariant 1.

Also, transitivity follows from this:

if pred(A, B) and pred(B, C) are both true,
then pred(A, C) == pred(B, C) == true.

Therefore pred(A, B) is an equivalence relation.

Now assume that for given A and B, pred(A, B)==false.
>From invariant 2, it follows that for an arbitrary C,
pred(B, C)!=pred(A, C).

It follows that exactly one of pred(B, C) and pred(A, C)
must be true, that is, C is either in the equivalence
class of A, or in the equivalence class of B.

Therefore pred describes an equivalence relation with
exactly two equivalence classes. Or stated differently,
there exists an unary predicate pred1 which is unique
except for negation, so that
pred(A, B)==true iff pred1(A) == pred1(B).

Note that except for types with only two values,
equal_to<> doesn't comply to this condition.

(All the above assumes that pred only returns true or false)

I definitely hope that std::unique isn't related to this
quite limited set of predicates...

---
[ 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              ]

Pete Becker wrote:
>
> James Kuyper wrote:
> >
> > John Potter wrote:
> > >
> > > On Wed, 12 Jan 2000 03:33:05 CST, James Kuyper <kuyper@wizard.net>
> > > wrote:
....
> > > : Following your argument to it's logical conclusion, the only predicate
> > > : allowed would be functionally identical to std::equal_to<>. Any other
> > > : predicate will do something different; in principle, something that
> > > : could trip up a implementation that was assuming that the standard
> > > : required std::equal_to<>.
> > >
> > > Too strong.  Consider for int a % 3 == b % 3.  It is not equal_to<>
> > > but it is an equivalence relation.
> >
> > Yes, but 4 is not equal to 7, so by Pete's argument a predicate that
> > defines such an equivalence relation would not be valid.
>
> No, in fact I said just the opposite: that unique requires a predicate
> that defines an equivalence relationship. That's the most reasonable
> meaning that can be given to the word "equal" in the context of the
> definition of the algorithm unique.

Perhaps, but that's a matter of judgment - my judgment of what's most
reasonable differs from yours. The words themselves either require
exactly "equal", or they allow room for interpretation. My
interpretation is just more flexible than yours; neither interpretation
has more textual support. My interpretation is consistent with the only
implementation of unique<> I've have an opportunity to examine.

---
[ 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:

> James Kuyper wrote:

> > Michiel Salters wrote:

> > > John Potter wrote:

> > > > I agree with you that either the standard should demand an equivalence
> > > > relation or unique should do what the standard says for any relation.

> > > I think we can demand from the predicate such useful invariants as

> > > pred(A,B)==true iff pred (B,A)==true
> > > pred(B,C)==pred(A,C) iff pred(A,B)==true
> > > (any more needed?)

> > Are even those needed? If so, why?

> No, the first one follows from the second one (assuming
> pred(A, B) is a pure function, i.e. pred(A, B) == pred(A, B)
> always holds):

> First, pred(A, A) == true holds, since pred(A, A) == pred(A, A)
> holds. Now set C=A in invariant 2, and you get

> pred(B, A) == pred(A, A) iff pred(A, B) == true

> Since pred(A, A) == true, this is invariant 1.

Well, in another, parallel post I showed that I didn't need
to include pred(A, A) == true, because you can invert your
proof. But I think we should just add the basic mathematical
requirements for equivalence relations to the standard.
(I'm not sure about the correct English mathematical terms,
but transitivity is one of them, and there are two others. )

Michiel Salters

---
[ 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              ]

James Kuyper wrote:
>
> Pete Becker wrote:
> >
> > James Kuyper wrote:
> ....
> > > for comment? Is the predicate's return value ignorable or does it define
> > > what "equal" means when a predicate is provided? If "equal" implies
> > > restrictions on the predicate, what specifically are they? Must a valid
> > > predicate return false iff equal_to<> would return false, or are the
> > > restrictions less severe than that? If the restrictions are less severe,
> > > how much less severe are they, and where are they specified? I couldn't
> > > find any such a specification.
> > >
> >
> > Of course you couldn't. It's not there. That doesn't mean that it can't
> > be reasonably inferred from the description of the algorithm as a whole.
> > A less-than operator cannot meaningfully be called an equal operator.
>
> From the description of the algorithm, I gather that it applies the
> predicate in order to consecutive pairs of elements in the iterator
> range provided, with the earlier element in the list always provided as
> the second argument to the predicate.

That is part of the description of what the function does. The full
description begins with the name, continues through the text that says
that it removes elements that compare equal, and goes into the
description of a possible implementation.

> The second element is removed if
> the predicate is not equal to false. From these facts I can't derive a
> single meaningful restriction on the predicate other than that it's
> return type must be convertible to bool.

Agreed. It's always dangerous to start reading in the middle.

>
> Now, if I take the word "equal" as constraining the predicate, rather
> than being simply verbal shorthand for it, then I can derive the
> requirements that std::equal_to<> must be instantiatiable for the given
> type, and that the predicate must return false iff std::equal_to<> would
> return false.

The function removes equal elements. If you interpret "equal" to mean
"equal_to returns true" you end up with something that's almost useless.
If you interpret "equal" to mean "whatever the predicate does" you end
up with "equal" adding nothing to the definition of the function. On the
other hand, if "equal" means that the predicate must define an
equivalence relationship, there's no violence to the meaning of "equal"
and no violence to the meaning of "unique."

>
> How do you derive contraints that fall somewhere in between these two
> extremes?
>

You apply common sense, remembering that human languages and human
writers are imperfect, and try to come up with a reasonable meaning for
the words that were used. Interpreting a standard is not an exercise in
cold mathematical deduction, nor in law-school style hunts for ways to
twist meanings in unlikely ways (that's not a comment on any of the
discussion here).

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pete Becker wrote:
>
> James Kuyper wrote:
....
> That is part of the description of what the function does. The full
> description begins with the name, continues through the text that says
> that it removes elements that compare equal, and goes into the
> description of a possible implementation.

And I think you'll agree that when provided with a predicate that
defines equivalence classes rather that equality, it removes elements
that do NOT compare equal, but are in the same equivalence class. If
that's not the case, then there's no point in allowing a predicate. That
phrase cannot usefully be taken as constraining the predicate, because
the only constraint it can imply is one that's too strict.

....
> The function removes equal elements. If you interpret "equal" to mean
> "equal_to returns true" you end up with something that's almost useless.
> If you interpret "equal" to mean "whatever the predicate does" you end
> up with "equal" adding nothing to the definition of the function. On the

Not quite - it adds a shorthand summary of what the rest of the same
sentence says, implying the connection between the behavior when no
predicate is provided with that when a predicate is provided. I would
have preferred two separate descriptions, but that's not how they chose
to write it.

....
> > How do you derive contraints that fall somewhere in between these two
> > extremes?
> >
>
> You apply common sense, remembering that human languages and human
> writers are imperfect, and try to come up with a reasonable meaning for
> the words that were used. Interpreting a standard is not an exercise in
> cold mathematical deduction, nor in law-school style hunts for ways to
> twist meanings in unlikely ways (that's not a comment on any of the
> discussion here).

A computer language standard IS mathematics; it IS law. It calls for a
level of rigor almost as high as required of either of those
disciplines, because it shares goals with them. It defines an abstract
symbolic system like mathematics. It defines a contract between the
language user and the language implementor similar to but less strictly
enforced than a legal contract. It cannot be useful if it relies upon
common sense, because so-called "common" sense means different things to
different people. There is no such thing as truly "common" sense - the
concept is just a fantasy created by people who think human beings have
more uniformity than they really do. That's the same reason why both
mathematics and (to a lesser degree) the law place low importance on
common sense. A document which relies upon common sense for its
interpretation does not describe a standard, it describes a set of
customs which varies depending upon who's reading it.


[ 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              ]

Pete Becker wrote:
>
> James Kuyper wrote:
> >
> > Yes, but 4 is not equal to 7, so by Pete's argument a predicate that
> > defines such an equivalence relation would not be valid.
>
> No, in fact I said just the opposite: that unique requires a predicate
> that defines an equivalence relationship. That's the most reasonable
> meaning that can be given to the word "equal" in the context of the
> definition of the algorithm unique.

But elsewhere in this thread Pete Becker also wrote:

> Andrew Koenig wrote:
> > What could the word ``corresponding'' mean here?  I believe that it
> > means that the two alternatives of the ``or'' correspond to the two
> > versions of unique, and that whichever alternative applies to the
> > given version is the way in which the algorithm is supposed to ascribe
> > a meaning to the word ``equal.''
>
> No, it cannot "ascribe a meaning to the word 'equal'". The word "equal"
> already has a meaning.

So Im just curious as to the difference between "ascribing a meaning" to
equal, and "giving a meaning" to equal?

Mark Williams


[ 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              ]

"John E. Potter" wrote:
>
> On Thu, 13 Jan 2000, James Kuyper wrote:
>
> > Incidentally, I've started to come around - I now concede that there's
> > at least one requirement implied by the description of unique<>:
> > pred(A,B)!=false must imply that (pred(B,C)!=false) ==
> > (pred(A,C)!=false); otherwise the standard would have to specify whether
> > removal of an element from the iterator range comes before or after
> > application of the predicate to the next element in the range.

The arguments below derive from this one; they seem like an awful lot to
derive simply from the standard's silence on the timing of the removals.

> Hum.  Using ab as pred(A,B)!=false ...
>
> False works as a pred for that.  Otherwise
>
>   ab -> bc == ac
> let c = b
>   ab -> bb == ab
> but ab is true and it is reflexive

Almost, but not quite. You've shown only that ab -> bb. There could be a
false-set such that for all b which are elements of the false-set, ab is
false for all a, including a==b.

> let c = a
>   ab -> ba == aa
> but aa is true and it is symmetric

Per above, aa isn't guaranteed true in itself, but ab -> aa, therefore
ab  -> ba. Conceded - std::greater_than<> doesn't qualify.


>   ab && bc -> (bc == ac) && (ca == ba)
> but bc is true and ba == ab is true and it is transitive

Conceded.

> Pred must be either an equivalence relation or the relation false.

Or a mixture of the two: an almost-equivalence relation with a subset on
which it always returns false.

> Oh well.  Andy is going to get it clarified and the existing stl
> code will be declared valid because an equivalence relation is
> required.  I don't think anything other than discussion will be
> lost. ;)


[ 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 Fri, 14 Jan 2000 01:44:57 CST, ark@research.att.com (Andrew Koenig)
wrote:

: Now, of course that doesn't say what the word "equal" means.  Reading
: the original STL code makes it clear that the author intended it to
: mean that there is an implicit requirement that the predicate be an
: equivalence relation.  The reason I say that is that although the
: description says that the algorithm compares pairs of adjacent elements,
: that's not what the code actually does.  Instead, it uses the first
: element of every range, which is the one it keeps, to compare with
: all subsequent elements.  This works only if the predicate is transitive,
: which every equivalence relation is required to be.

Note also that the code uses pred(*(i-k), *i) not pred(*i, *(i-k)).
This works only if the predicate is symmetric ...

John


[ 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              ]

Michiel Salters wrote:
....
> proof. But I think we should just add the basic mathematical
> requirements for equivalence relations to the standard.
> (I'm not sure about the correct English mathematical terms,
> but transitivity is one of them, and there are two others. )

They're already there. See section 20.1.1, describing the
EqualityComparable requirements. They are requirements for "==" rather
than for a user-provided predicate, so they'd have to be re-worded to
apply to unique<>. However, the fact that such re-wording wasn't done is
one of the reasons why I don't think they apply.

---
[ 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              ]

Since Andrew Koenig said that he would mention the matter at the next
meeting of the committee, I'd like to ask the following pragmatic
question to the debate.

There are two differing interpretation of how unique could be understood
to behave with a predicate:

1. the predicate defines an equivalence relation;

2. the predicate can be anything that returns a consistent boolean
result.

It is clear that the option 2 encompasses option 1. It is also clear
that option 1. does not encompasses option 2. So my question is:

Would any optimization opportunities be lost by option 2?

The point being that if not then option 2 provides more power and
flexibility. I don't consider arguments that it allows twisting the
meaning of "unique" since the standard allows the meaning of all other
functions to be twisted. That is, any user-defined operator or function
can do whatever pleases the programmer, and even some standard ones must
be used counter-intuitively (ex: std::set::count() must be used to
acertain if the set contains an element, as there is no contains()
function in std::set). So I see no reason to restrict unique() more than
the others.

---
[ 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              ]

James Kuyper wrote:
>
> Pete Becker wrote:
> >
> > You apply common sense, remembering that human languages and human
> > writers are imperfect, and try to come up with a reasonable meaning for
> > the words that were used. Interpreting a standard is not an exercise in
> > cold mathematical deduction, nor in law-school style hunts for ways to
> > twist meanings in unlikely ways (that's not a comment on any of the
> > discussion here).
>
> A computer language standard IS mathematics; it IS law. It calls for a
> level of rigor almost as high as required of either of those
> disciplines, because it shares goals with them. It defines an abstract
> symbolic system like mathematics. It defines a contract between the
> language user and the language implementor similar to but less strictly
> enforced than a legal contract. It cannot be useful if it relies upon
> common sense, because so-called "common" sense means different things to
> different people. There is no such thing as truly "common" sense - the
> concept is just a fantasy created by people who think human beings have
> more uniformity than they really do. That's the same reason why both
> mathematics and (to a lesser degree) the law place low importance on
> common sense. A document which relies upon common sense for its
> interpretation does not describe a standard, it describes a set of
> customs which varies depending upon who's reading it.
>

Then there is nothing left to say. Since documents written by humans are
inherently imperfect, there is nothing useful that can be done with
them.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pierre Baillargeon wrote:
>
> There are two differing interpretation of how unique could be understood
> to behave with a predicate:
>
> 1. the predicate defines an equivalence relation;
>
> 2. the predicate can be anything that returns a consistent boolean
> result.
>
> It is clear that the option 2 encompasses option 1. It is also clear
> that option 1. does not encompasses option 2. So my question is:
>
> Would any optimization opportunities be lost by option 2?

Possibly, but my concern is clarity. Consider what happens to an average
programmer who sees unique being called with a predicate that returns
true when its two arguments are unequal.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Mark Williams wrote:
>
> Pete Becker wrote:
> >
> > James Kuyper wrote:
> > >
> > > Yes, but 4 is not equal to 7, so by Pete's argument a predicate that
> > > defines such an equivalence relation would not be valid.
> >
> > No, in fact I said just the opposite: that unique requires a predicate
> > that defines an equivalence relationship. That's the most reasonable
> > meaning that can be given to the word "equal" in the context of the
> > definition of the algorithm unique.
>
> But elsewhere in this thread Pete Becker also wrote:
>
> > Andrew Koenig wrote:
> > > What could the word ``corresponding'' mean here?  I believe that it
> > > means that the two alternatives of the ``or'' correspond to the two
> > > versions of unique, and that whichever alternative applies to the
> > > given version is the way in which the algorithm is supposed to ascribe
> > > a meaning to the word ``equal.''
> >
> > No, it cannot "ascribe a meaning to the word 'equal'". The word "equal"
> > already has a meaning.
>
> So Im just curious as to the difference between "ascribing a meaning" to
> equal, and "giving a meaning" to equal?
>

The difference is in degree. If the code in the definition is taken as a
definition of "equal" then "equal" is merely empty syllables. If "equal"
is interpreted as meaning "compare equal under an equivalence
relationship" it fits with reasonable notions of what the word "equal"
means.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 14 Jan 2000 17:39:17 GMT, James Kuyper <kuyper@wizard.net> wrote:

: "John E. Potter" wrote:
: >
: > On Thu, 13 Jan 2000, James Kuyper wrote:
: >
: > > Incidentally, I've started to come around - I now concede that there's
: > > at least one requirement implied by the description of unique<>:
: > > pred(A,B)!=false must imply that (pred(B,C)!=false) ==
: > > (pred(A,C)!=false); otherwise the standard would have to specify
: > > whether removal of an element from the iterator range comes before or
: > > after application of the predicate to the next element in the range.
:
: The arguments below derive from this one; they seem like an awful lot to
: derive simply from the standard's silence on the timing of the removals.

Comments on that below.

: > Hum.  Using ab as pred(A,B)!=false ...
: >
: > False works as a pred for that.  Otherwise
: >
: >   ab -> bc == ac
: > let c = b
: >   ab -> bb == ab
: > but ab is true and it is reflexive
:
: Almost, but not quite. You've shown only that ab -> bb. There could be a
: false-set such that for all b which are elements of the false-set, ab is
: false for all a, including a==b.

Yep, I knew that and suspected that you would catch me.  I let it go
because those are really contrived discrete set relations and I didn't
want to look for a counter example.  Well, of the 16 binary functions
on bool, 7 of them satisfy your requirement and only 2 of those 7 are
reflexive.  Maybe not so contrived.

: > let c = a
: >   ab -> ba == aa
: > but aa is true and it is symmetric
:
: Per above, aa isn't guaranteed true in itself, but ab -> aa, therefore
: ab  -> ba. Conceded - std::greater_than<> doesn't qualify.

Nope.  ab -> bb not aa.  If it is reflexive then it is symmetric.  Of
the 5 non-reflexive relations, 2 are also not symmetric.  The relations
are b and !b.  ab is true when b is true(false).  The implicand is
bc == ac which reduces to c == c which is true.

: >   ab && bc -> (bc == ac) && (ca == ba)
: > but bc is true and ba == ab is true and it is transitive
:
: Conceded.

Yes, the first part is sufficient.  ab -> bc == ac so ab && bc -> ac.

Going back to the timing thing.  If we remove all Pete^H^H^H^Hcommon
sense we are left with:

Eliminates all referents of i in (first, last) for which
pred(*i,*(i-1)) != false.

It clearly applies the pred to the original range and there is no need
for your requirement.

The worst case occurs for unique_copy with input/output iterators.  Here
is some old library code for it.  Note that first != last was tested
prior to getting here.

template <class InputIterator, class OutputIterator,
      class BinaryPredicate, class T>
OutputIterator __unique_copy (InputIterator first, InputIterator last,
      OutputIterator result, BinaryPredicate binary_pred, T*) {
   T value = *first;
   *result = value;
   while (++first != last)
      if (!binary_pred(value, *first)) {
         value = *first;
         *++result = value;
         }
   return ++result;
   }

Making it match what the standard seems to say is easy.

template <class InputIterator, class OutputIterator,
      class BinaryPredicate, class T>
OutputIterator __unique_copy (InputIterator first, InputIterator last,
      OutputIterator result, BinaryPredicate binary_pred, T*) {
   T value = *first;
   *result = value;
   while (++first != last) {
      if (!binary_pred(*first, value)) // reversed args
         *++result = *first;           // changed code, not effect
      value = *first;                  // made unconditional
      }
   return ++result;
   }

The wording of the standard is not clear.

1.  Did the standard fail to specify the code or does the code fail
    to meet the specification?

2.  Is there a real cost in the revised code?  For forward iterator,
    the extra copy is an iterator not a T.

3.  Is there a real use for the revised code?

4.  The original poster has been silent.  Was this a successful troll?

John

---
[ 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              ]

Pete Becker wrote:
>
> James Kuyper wrote:
> >
> > Pete Becker wrote:
> > >
> > > You apply common sense, remembering that human languages and human
> > > writers are imperfect, and try to come up with a reasonable meaning for
> > > the words that were used. Interpreting a standard is not an exercise in
> > > cold mathematical deduction, nor in law-school style hunts for ways to
> > > twist meanings in unlikely ways (that's not a comment on any of the
> > > discussion here).
> >
> > A computer language standard IS mathematics; it IS law. It calls for a
> > level of rigor almost as high as required of either of those
> > disciplines, because it shares goals with them. It defines an abstract
> > symbolic system like mathematics. It defines a contract between the
> > language user and the language implementor similar to but less strictly
> > enforced than a legal contract. It cannot be useful if it relies upon
> > common sense, because so-called "common" sense means different things to
> > different people. There is no such thing as truly "common" sense - the
> > concept is just a fantasy created by people who think human beings have
> > more uniformity than they really do. That's the same reason why both
> > mathematics and (to a lesser degree) the law place low importance on
> > common sense. A document which relies upon common sense for its
> > interpretation does not describe a standard, it describes a set of
> > customs which varies depending upon who's reading it.
> >
>
> Then there is nothing left to say. Since documents written by humans are
> inherently imperfect, there is nothing useful that can be done with
> them.

Sure, human writing are inherently imperfect, but that's not what I'm
talking about. You seem to be arguing that it's OK for the standard to
define something ambiguously even if it wasn't meant to be ambiguous,
relying on common sense to lead all readers to resolve that ambiguity
the same way, despite the fact that so-called "common" sense isn't. I'm
arguing that it should be written to standards of precision closer to
those used in mathematics or law. If the term "equal" in the definition
of unique doesn't actually mean "equal", but instead means "either equal
or in the same equivalence class defined by _pred_", then the standard
should say so. If, instead, it means "either equal, or _pred_(*i,
*(i-1))!=false", then it should say that. I believe that the second
meaning is the one intended, because the full sentence as actually
written contains many more points of similarity to the second
description than to the first one. In particular, the term "equivalence"
occurs nowhere in the description, whereas the C++ expression given
above occurs in the very same sentence. I think that we're both in
agreement that the one thing it can't mean is what it literally says,
since that would make the predicate pointless.
It's not as if the standard makes a habit of avoiding specifying such
things - look at the definition of EqualityComparable, for instance.


[ 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              ]

James Kuyper wrote:
>
> Pete Becker wrote:
> >
> > James Kuyper wrote:
> > >
> > > Pete Becker wrote:
> > > >
> > > > You apply common sense, remembering that human languages and human
> > > > writers are imperfect, and try to come up with a reasonable meaning for
> > > > the words that were used. Interpreting a standard is not an exercise in
> > > > cold mathematical deduction, nor in law-school style hunts for ways to
> > > > twist meanings in unlikely ways (that's not a comment on any of the
> > > > discussion here).
> > >
> > > A computer language standard IS mathematics; it IS law. It calls for a
> > > level of rigor almost as high as required of either of those
> > > disciplines, because it shares goals with them. It defines an abstract
> > > symbolic system like mathematics. It defines a contract between the
> > > language user and the language implementor similar to but less strictly
> > > enforced than a legal contract. It cannot be useful if it relies upon
> > > common sense, because so-called "common" sense means different things to
> > > different people. There is no such thing as truly "common" sense - the
> > > concept is just a fantasy created by people who think human beings have
> > > more uniformity than they really do. That's the same reason why both
> > > mathematics and (to a lesser degree) the law place low importance on
> > > common sense. A document which relies upon common sense for its
> > > interpretation does not describe a standard, it describes a set of
> > > customs which varies depending upon who's reading it.
> > >
> >
> > Then there is nothing left to say. Since documents written by humans are
> > inherently imperfect, there is nothing useful that can be done with
> > them.
>
> Sure, human writing are inherently imperfect, but that's not what I'm
> talking about. You seem to be arguing that it's OK for the standard to
> define something ambiguously even if it wasn't meant to be ambiguous,
> relying on common sense to lead all readers to resolve that ambiguity
> the same way, despite the fact that so-called "common" sense isn't.

Where on Earth did you get that impression? The entire discussion here
has been about what the definition of 'unique' in the standard means,
not about how it could have been written differently.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <388079A5.B0AB34EA@wizard.net>, James Kuyper
<kuyper@wizard.net> writes
>I'm
>arguing that it should be written to standards of precision closer to
>those used in mathematics or law.

And in the UK, at least, an ISO standard is a legal document.



Francis Glassborow      Journal Editor, Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation

---
[ 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              ]

Pete Becker wrote:
....
> Possibly, but my concern is clarity. Consider what happens to an average
> programmer who sees unique being called with a predicate that returns
> true when its two arguments are unequal.

I may have lost track of your point. Are you suggesting that it's wrong
to use such a predicate? Why use the form of unique<> that requires a
predicate if the non-predicate form would do the same thing?

---
[ 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              ]

James Kuyper wrote:
>
> Pete Becker wrote:
> ....
> > Possibly, but my concern is clarity. Consider what happens to an average
> > programmer who sees unique being called with a predicate that returns
> > true when its two arguments are unequal.
>
> I may have lost track of your point. Are you suggesting that it's wrong
> to use such a predicate? Why use the form of unique<> that requires a
> predicate if the non-predicate form would do the same thing?
>

What I suggested is that unique with UNequal is very confusing.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pete Becker wrote:
>
> James Kuyper wrote:
> >
> > Pete Becker wrote:
....
> > > James Kuyper wrote:
> > > Then there is nothing left to say. Since documents written by humans are
> > > inherently imperfect, there is nothing useful that can be done with
> > > them.
> >
> > Sure, human writing are inherently imperfect, but that's not what I'm
> > talking about. You seem to be arguing that it's OK for the standard to
> > define something ambiguously even if it wasn't meant to be ambiguous,
> > relying on common sense to lead all readers to resolve that ambiguity
> > the same way, despite the fact that so-called "common" sense isn't.
>
> Where on Earth did you get that impression? The entire discussion here
> has been about what the definition of 'unique' in the standard means,
> not about how it could have been written differently.

True. However, you've been saying that "equal" doesn't mean "equal", but
instead means something like "in the same equivalence class as defined
by _pred_". You defend this discrepancy between what the standard says
and what you think it means, by making an appeal to common sense. From
this I concluded, possibly falsely, that you find it acceptable for the
wording of the standard to be left unchanged when the intended meaning
differs from the literal one, so long as you can figure out the intended
meaning based upon your own personal concept of "common" sense.

I would not find that acceptable. The C++ standard is a technical
document, not a romance novel or a self-help manual. It needs to be
clear and precise, and understandable by people from many different
backgrounds, especially since this is an international standard. Relying
on so-called "common" sense is inappropriate for such a document.

---
[ 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              ]

Michiel Salters wrote:
>
> Christopher Eltschka wrote:
>
> > James Kuyper wrote:
>
> > > Michiel Salters wrote:
>
> > > > John Potter wrote:
>
> > > > > I agree with you that either the standard should demand an equivalence
> > > > > relation or unique should do what the standard says for any relation.
>
> > > > I think we can demand from the predicate such useful invariants as
>
> > > > pred(A,B)==true iff pred (B,A)==true
> > > > pred(B,C)==pred(A,C) iff pred(A,B)==true
> > > > (any more needed?)
>
> > > Are even those needed? If so, why?
>
> > No, the first one follows from the second one (assuming
> > pred(A, B) is a pure function, i.e. pred(A, B) == pred(A, B)
> > always holds):
>
> > First, pred(A, A) == true holds, since pred(A, A) == pred(A, A)
> > holds. Now set C=A in invariant 2, and you get
>
> > pred(B, A) == pred(A, A) iff pred(A, B) == true
>
> > Since pred(A, A) == true, this is invariant 1.
>
> Well, in another, parallel post I showed that I didn't need
> to include pred(A, A) == true, because you can invert your
> proof.

Well, if you look closely, I also showed that from
invariant 2 it follows that pred(A, A) == true.
I just continued showing that invariant 1 follows as well.
That is, by simply demanding invariant 2
(pred(B, C) == pred(A, B) iff pred(A, B) == true),
you get an equivalence relation with exactly two
equivalence classes.

> But I think we should just add the basic mathematical
> requirements for equivalence relations to the standard.

Agreed. Restricting the number of equivalence classes
to two is not very productive ;-)

> (I'm not sure about the correct English mathematical terms,
> but transitivity is one of them, and there are two others. )

AFAIK the English terms are "reflexivity" (A eq A) and
"symmetry" (A eq B iff B eq A).


[ 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 <3877602E.5B9DA166@acm.org>,
  Pete Becker <petebecker@acm.org> wrote:
>
> For unique, the standard says: "eliminates all but the first element
> from every consecutive group of equal elements..." It does not say
> "eliminates all but the first element from every consecutive group for
> which pred returns true...", which would be the more natural wording
if
> the algorithm were required to make sense for every predicate. It
would
> be nice if the standard actually said that pred must be an equivalence
> relationship, but there's no other reasonable interpretation of the
word
> "equal."

My copy of the standard reads:

Effects: Eliminates all but the first from every consecutive group
of elements referred to by the iterator i in the range [first, last)
for which the following corresponding condition hold:
*i == *(i - 1) or pred(*i, *(i - 1)) != false

Nothing about "equal" at all.

/Niklas Mellin


Sent via Deja.com http://www.deja.com/
Before you buy.


[ 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              ]

James Kuyper <kuyper@wizard.net> writes:

> > the algorithm were required to make sense for every predicate. It would
> > be nice if the standard actually said that pred must be an equivalence
> > relationship, but there's no other reasonable interpretation of the word
> > "equal."
>
> I interpret "equal" as only a shorthand term for what is stated more
> precisely at the end of the very same sentence, and not as a requirement
> that _pred_() define an equivalence relationship. If an equivalence
> relationship is required, what kind - weak or strong? The very fact that
> the standard doesn't specify implies to me that it is not required.

The standard doesn't distinguish between two different kinds of
equivalence relations, nor does ordinary mathematics.

I think Pete's interpretation of 'equal' is a reasonable one, and I
encourage him to open a library working group issue.  More generally,
we should be cautious about spinning too many inferences about the
committee's intent from subtle details of wording in the algorithm
descriptions.  The wording for the description of 'unique' is taken
almost verbatim from the original Stepanov-Lee documentation ("The
Standard Template Library," HPL-95-11 (R1), 1995).  The one change is
from "== true" to "!= false", which was motivated by a desire not to
rule out predicates that return some type other than bool.

There are some corner cases where all there is to say is that nobody
thought very carefully about them.  The descriptions in the standard
just aren't precise enough to cover those cases.  This may be one of
them.


[ 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              ]

nimel@my-deja.com wrote:
>
> In article <3877602E.5B9DA166@acm.org>,
>   Pete Becker <petebecker@acm.org> wrote:
> >
> > For unique, the standard says: "eliminates all but the first element
> > from every consecutive group of equal elements..." It does not say
> > "eliminates all but the first element from every consecutive group for
> > which pred returns true...", which would be the more natural wording
> if
> > the algorithm were required to make sense for every predicate. It
> would
> > be nice if the standard actually said that pred must be an equivalence
> > relationship, but there's no other reasonable interpretation of the
> word
> > "equal."
>
> My copy of the standard reads:
>
> Effects: Eliminates all but the first from every consecutive group
> of elements referred to by the iterator i in the range [first, last)
> for which the following corresponding condition hold:
> *i == *(i - 1) or pred(*i, *(i - 1)) != false
>
> Nothing about "equal" at all.
>

Your copy of the standard is wrong. I haven't checked earlier versions
to see if that's what they say, but the text I quoted is from the final
version.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper wrote:
>
> Pete Becker wrote:
> >
> > James Kuyper wrote:
> > >
> > > Pete Becker wrote:
> ....
> > > > For unique, the standard says: "eliminates all but the first element
> > > > from every consecutive group of equal elements..." It does not say
> > > > "eliminates all but the first element from every consecutive group for
> > > > which pred returns true...", which would be the more natural wording if
> > >
> > > Later in that very same sentence it says " ... for which the following
> > > corresponding conditions hold: *i == *(i - 1) or _pred_(*i, *(i - 1)) !=
> > > false". It uses C code rather than english. It says "!= false" rather
> > > than "returns true". It mixes together the description of the
> > > operator-based version of the template with the function-object based
> > > version, in the same fairly confusing way the standard does for all such
> > > algorithm pairs.
> >
> > That's all true. It doesn't change the fact that the description says
> > that it eliminates equal elements.
>
> Yes, but it may be reasonably be interpreted as changing what is meant
> by the phrase "equal elements", to mean elements for which the predicate
> is != false, with the predicate defaulting to std::equal_to<> when not
> explicitly provided.
>

Seems to me quite clear that "equal" means "equal", not "equal unless
the user provides some other predicate, in which case it means not
equal."

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pete Becker wrote:
>
> John Potter wrote:
> >
> > Pete Becker claims
> >
> > : unique uses its predicate argument as a test for equality. It is only
> > : required to work when that predicate defines an equivalence
> > : relationship. greater<int> is not an equivalence relationship, so the
> > : call can't be expected to do anything sensible.
> >
> > That makes good sense; however, I can't find that requirement in the
> > standard.  In his book, Matt notes that the predicate is not required to
> > be an equivalence relation and warns that you may get unexpected
> > results if it is not.
> >
>
> For unique, the standard says: "eliminates all but the first element
> from every consecutive group of equal elements..." It does not say
> "eliminates all but the first element from every consecutive group for
> which pred returns true...", which would be the more natural wording if

Later in that very same sentence it says " ... for which the following
corresponding conditions hold: *i == *(i - 1) or _pred_(*i, *(i - 1)) !=
false". It uses C code rather than english. It says "!= false" rather
than "returns true". It mixes together the description of the
operator-based version of the template with the function-object based
version, in the same fairly confusing way the standard does for all such
algorithm pairs. However, modulo those variations that phrase carries
essentially the same meaning as the alternative wording that you suggest
would have had to be used.

> the algorithm were required to make sense for every predicate. It would
> be nice if the standard actually said that pred must be an equivalence
> relationship, but there's no other reasonable interpretation of the word
> "equal."

I interpret "equal" as only a shorthand term for what is stated more
precisely at the end of the very same sentence, and not as a requirement
that _pred_() define an equivalence relationship. If an equivalence
relationship is required, what kind - weak or strong? The very fact that
the standard doesn't specify implies to me that it is not required.

---
[ 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              ]

James Kuyper wrote:
>
> Pete Becker wrote:
> >
> > John Potter wrote:
> > >
> > > Pete Becker claims
> > >
> > > : unique uses its predicate argument as a test for equality. It is only
> > > : required to work when that predicate defines an equivalence
> > > : relationship. greater<int> is not an equivalence relationship, so the
> > > : call can't be expected to do anything sensible.
> > >
> > > That makes good sense; however, I can't find that requirement in the
> > > standard.  In his book, Matt notes that the predicate is not required to
> > > be an equivalence relation and warns that you may get unexpected
> > > results if it is not.
> > >
> >
> > For unique, the standard says: "eliminates all but the first element
> > from every consecutive group of equal elements..." It does not say
> > "eliminates all but the first element from every consecutive group for
> > which pred returns true...", which would be the more natural wording if
>
> Later in that very same sentence it says " ... for which the following
> corresponding conditions hold: *i == *(i - 1) or _pred_(*i, *(i - 1)) !=
> false". It uses C code rather than english. It says "!= false" rather
> than "returns true". It mixes together the description of the
> operator-based version of the template with the function-object based
> version, in the same fairly confusing way the standard does for all such
> algorithm pairs.


That's all true. It doesn't change the fact that the description says
that it eliminates equal elements.

> > the algorithm were required to make sense for every predicate. It would
> > be nice if the standard actually said that pred must be an equivalence
> > relationship, but there's no other reasonable interpretation of the word
> > "equal."
>
> I interpret "equal" as only a shorthand term for what is stated more
> precisely at the end of the very same sentence,

Note that the adjacent descriptions of algorithms do not use the word
"equal" to describe inequality operations. The word "equal" has a
meaning. You cannot ignore that, especially when the result of ignoring
it is to make the description of this function nonsensical.


--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Pete Becker wrote:
>
> James Kuyper wrote:
> >
> > Pete Becker wrote:
....
> > > For unique, the standard says: "eliminates all but the first element
> > > from every consecutive group of equal elements..." It does not say
> > > "eliminates all but the first element from every consecutive group for
> > > which pred returns true...", which would be the more natural wording if
> >
> > Later in that very same sentence it says " ... for which the following
> > corresponding conditions hold: *i == *(i - 1) or _pred_(*i, *(i - 1)) !=
> > false". It uses C code rather than english. It says "!= false" rather
> > than "returns true". It mixes together the description of the
> > operator-based version of the template with the function-object based
> > version, in the same fairly confusing way the standard does for all such
> > algorithm pairs.
>
> That's all true. It doesn't change the fact that the description says
> that it eliminates equal elements.

Yes, but it may be reasonably be interpreted as changing what is meant
by the phrase "equal elements", to mean elements for which the predicate
is != false, with the predicate defaulting to std::equal_to<> when not
explicitly provided.

....
> Note that the adjacent descriptions of algorithms do not use the word
> "equal" to describe inequality operations. The word "equal" has a
> meaning. You cannot ignore that, especially when the result of ignoring
> it is to make the description of this function nonsensical.

What's nonsensical about it? It's no more non-sensical than the
description of any other algorithm that allows a user-defined function
object to be substituted for the default operation. The function object
always changes the behavior; that's the whole point of allowing it.
Following your argument to it's logical conclusion, the only predicate
allowed would be functionally identical to std::equal_to<>. Any other
predicate will do something different; in principle, something that
could trip up a implementation that was assuming that the standard
required std::equal_to<>.

Let's put the issue differently. Is there any advantage to requiring
that the predicate define an equivalence relationship? Would requiring
unique<> to accept predicates that don't define such a relationship
force a less efficient implementation? Naively, I'd expect unique<> to
be implemented in such a way that it wouldn't matter.

---
[ 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              ]

James Kuyper wrote:
>
> Pete Becker wrote:
> >
> > Note that the adjacent descriptions of algorithms do not use the word
> > "equal" to describe inequality operations. The word "equal" has a
> > meaning. You cannot ignore that, especially when the result of ignoring
> > it is to make the description of this function nonsensical.
>
> What's nonsensical about it?

The name of the algorithm is "unique", not
"apply_an_arbitrary_predicate_in_the_prescribed_manner."

> Let's put the issue differently. Is there any advantage to requiring
> that the predicate define an equivalence relationship?

Yup: it means that "unique" will do what its name suggests.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

nimel@my-deja.com writes:
> My copy of the standard reads:
> Effects: Eliminates all but the first from every consecutive group
> of elements referred to by the iterator i in the range [first, last)
> for which the following corresponding condition hold:
> *i == *(i - 1) or pred(*i, *(i - 1)) != false
> Nothing about "equal" at all.

My purchased copy of the Standard says

Effects: Eliminates all but the first element from every consecutive group
of equal elements referred to by the iterator i in the range [first, last)
for which the following corresponding condition hold:
*i == *(i - 1) or pred(*i, *(i - 1)) != false

The draft predecessor said the same thing. Where are you reading from?

---
[ 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              ]

Matt Austern wrote:
>
> I think Pete's interpretation of 'equal' is a reasonable one, and I
> encourage him to open a library working group issue.

If I didn't think it was a reasonable interpretation I'd be inclined to
suggest an issue. I think the meaning is clear, despite the possibility
of hostile readings.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Matt Austern wrote:
>
> James Kuyper <kuyper@wizard.net> writes:
>
> > > the algorithm were required to make sense for every predicate. It would
> > > be nice if the standard actually said that pred must be an equivalence
> > > relationship, but there's no other reasonable interpretation of the word
> > > "equal."
> >
> > I interpret "equal" as only a shorthand term for what is stated more
> > precisely at the end of the very same sentence, and not as a requirement
> > that _pred_() define an equivalence relationship. If an equivalence
> > relationship is required, what kind - weak or strong? The very fact that
> > the standard doesn't specify implies to me that it is not required.
>
> The standard doesn't distinguish between two different kinds of
> equivalence relations, nor does ordinary mathematics.

Sorry, I mispoke - I was thinking about weak and strong ordering, which
the standard does speak about, but of course they aren't directly
relevant here.

> I think Pete's interpretation of 'equal' is a reasonable one, and I
> encourage him to open a library working group issue.  More generally,
> we should be cautious about spinning too many inferences about the
> committee's intent from subtle details of wording in the algorithm
> descriptions.  The wording for the description of 'unique' is taken
> almost verbatim from the original Stepanov-Lee documentation ("The
> Standard Template Library," HPL-95-11 (R1), 1995).  The one change is
> from "== true" to "!= false", which was motivated by a desire not to
> rule out predicates that return some type other than bool.

I checked the implementation of unique<> on the compiler I use at work,
and it is implemented almost exactly the way I would have done it. In no
way does it require an equivalence relation, so there's at least some
existing practice that's consistent with my interpretation. I really
find it hard to imagine any point in writing unique<> so it would
require an equivalence relationship, and therefore no point in making it
illegal to provide a predicate which doesn't define one.


[ 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 Wed, 12 Jan 2000 03:33:05 CST, James Kuyper <kuyper@wizard.net>
wrote:


: What's nonsensical about it? It's no more non-sensical than the
: description of any other algorithm that allows a user-defined function
: object to be substituted for the default operation. The function object
: always changes the behavior; that's the whole point of allowing it.
: Following your argument to it's logical conclusion, the only predicate
: allowed would be functionally identical to std::equal_to<>. Any other
: predicate will do something different; in principle, something that
: could trip up a implementation that was assuming that the standard
: required std::equal_to<>.

Too strong.  Consider for int a % 3 == b % 3.  It is not equal_to<>
but it is an equivalence relation.

The only reason existing code does not do what the OP wanted is that
it assumes the relation is commutative.  Reverse the two arguments
to the relation and the code will work.

I agree with you that either the standard should demand an equivalence
relation or unique should do what the standard says for any relation.

John


[ 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 <387B6D0E.B053EFC1@acm.org>,
  Pete Becker <petebecker@acm.org> wrote:
>
> nimel@my-deja.com wrote:

[...]

> > My copy of the standard reads:
> >
> > Effects: Eliminates all but the first from every consecutive group
> > of elements referred to by the iterator i in the range [first, last)
> > for which the following corresponding condition hold:
> > *i == *(i - 1) or pred(*i, *(i - 1)) != false
> >
> > Nothing about "equal" at all.
> >
>
> Your copy of the standard is wrong. I haven't checked earlier versions
> to see if that's what they say, but the text I quoted is from the
> final version.

It wasn't my copy, it was my reading that went wrong, and since
copy and paste isn't possible I had to type it all in. It indeed does
say "... from every consecutive group of *equal* elements..."

But even then I think "equal" is defined in the end of the clause
as beeing pred(*i, *(i-1)) != false.

/Niklas Mellin


Sent via Deja.com http://www.deja.com/
Before you buy.


[ 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              ]

John Potter wrote:

> On Wed, 12 Jan 2000 03:33:05 CST, James Kuyper <kuyper@wizard.net>
> wrote:

> : What's nonsensical about it? It's no more non-sensical than the
> : description of any other algorithm that allows a user-defined function
> : object to be substituted for the default operation. The function object
> : always changes the behavior; that's the whole point of allowing it.
> : Following your argument to it's logical conclusion, the only predicate
> : allowed would be functionally identical to std::equal_to<>. Any other
> : predicate will do something different; in principle, something that
> : could trip up a implementation that was assuming that the standard
> : required std::equal_to<>.

> Too strong.  Consider for int a % 3 == b % 3.  It is not equal_to<>
> but it is an equivalence relation.

> The only reason existing code does not do what the OP wanted is that
> it assumes the relation is commutative.  Reverse the two arguments
> to the relation and the code will work.

> I agree with you that either the standard should demand an equivalence
> relation or unique should do what the standard says for any relation.

I think we can demand from the predicate such useful invariants as

pred(A,B)==true iff pred (B,A)==true
pred(B,C)==pred(A,C) iff pred(A,B)==true
(any more needed?)

which will disallow operator<, but allow other predicates.

Allowing implementation defined behavior if the equal-predicate
doesn't meet the requirements seems like a fitting "penalty"

Michiel Salters


[ 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 <386E8DB9.3A10AF2@acm.org>,
  Pete Becker <petebecker@acm.org> wrote:

> unique uses its predicate argument as a test for equality. It is only
> required to work when that predicate defines an equivalence
> relationship. greater<int> is not an equivalence relationship, so the
> call can't be expected to do anything sensible.

I don't agree. The standard 25.2.8/1 reads:

Effects: Eliminates all but the first from every consecutive group
of elements referred to by the iterator i in the range [first, last)
for which the following corresponding condition hold:
*i == *(i - 1) or pred(*i, *(i - 1)) != false

It doesn't say anything in this clause or any other clause that I can
find that the predicate must define an equvalence predicate. The same
holds also for the std::list::unique member function and for
unique_copy.

/Niklas Mellin



Sent via Deja.com http://www.deja.com/
Before you buy.
---
[ 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              ]

Stefan <cool@worblehat.wifo.uni-mannheim.de> wrote:

> Effects:
> Copies only the first element from every consecutive group of equal
> elements referred to by the iterator i in the range [first, last)
> for which the following corresponding conditions hold:
> *i == *(i - 1) or pred(*i, *(i - 1)) == true
>
> Therefor the output should be 1 3 7 2, or what do you think?

Wow. Good point!

The traditional implementation (from the original HP STL) uses code that
compares each element to the first of the "equal range" rather than code
that compares each element with its immediate predecessor. I believe this is
done to minimize copying. The standard does not match existing practice!

The same issue exists for std::adjacent_find and std::unique_copy.

When the predicate has equality semantics, it doesn't matter if you're
comparing with the first item of the "equal range" or the current item. But
in the case you present here, 2 is compared with 7 (the first item in the
"equal range") rather than being compared with 1 (the previous item).

I would be willing to bet that all extant implementations of adjacent_find,
unique, and unique_copy match the original HP STL rather than the standard.

It's time for someone to write a defect report.

    -- Darin
---
[ 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              ]

John Potter wrote:
>
> Pete Becker claims
>
> : unique uses its predicate argument as a test for equality. It is only
> : required to work when that predicate defines an equivalence
> : relationship. greater<int> is not an equivalence relationship, so the
> : call can't be expected to do anything sensible.
>
> That makes good sense; however, I can't find that requirement in the
> standard.  In his book, Matt notes that the predicate is not required to
> be an equivalence relation and warns that you may get unexpected
> results if it is not.
>

For unique, the standard says: "eliminates all but the first element
from every consecutive group of equal elements..." It does not say
"eliminates all but the first element from every consecutive group for
which pred returns true...", which would be the more natural wording if
the algorithm were required to make sense for every predicate. It would
be nice if the standard actually said that pred must be an equivalence
relationship, but there's no other reasonable interpretation of the word
"equal."


--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 2 Jan 2000 21:21:35 GMT, Darin Adler <darin@bentspoon.com> wrote:

:
: Stefan <cool@worblehat.wifo.uni-mannheim.de> wrote:
:
: > Effects:
: > Copies only the first element from every consecutive group of equal
: > elements referred to by the iterator i in the range [first, last)
: > for which the following corresponding conditions hold:
: > *i == *(i - 1) or pred(*i, *(i - 1)) == true
: >
: > Therefor the output should be 1 3 7 2, or what do you think?

The original data was 1 3 7 1 2 using greater<int> as the pred.

I think there is a real problem here.  The comparison is *i, *(i - 1)
and the predicate is greater.  3 > 1, remove 3, etc.  The result should
be 1 1.  Changing the pred to less<int> and using unique_copy, the
result should be 1 3 7 2.

: Wow. Good point!

Note that the quote is for unique_copy and the code used unique.

For unique and the list specialization, it could be argued that
when i reaches an element, the removed elements are no longer
present.  Using less<int> and unique would yeild 1 3 7 because
at the 2, the 1 is gone and *(i - 1) is 7.

Daren notes that existing code is slighlty different from the
standard.

Pete Becker claims

: unique uses its predicate argument as a test for equality. It is only
: required to work when that predicate defines an equivalence
: relationship. greater<int> is not an equivalence relationship, so the
: call can't be expected to do anything sensible.

That makes good sense; however, I can't find that requirement in the
standard.  In his book, Matt notes that the predicate is not required to
be an equivalence relation and warns that you may get unexpected
results if it is not.

In conclusion, the standard requires nonsense, implementations use
different nonsense, and Matt advises that if it hurts, you should not
do that.  Is that a defect or intentional?

John

---
[ 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              ]

What is the correct output of the following program?

#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;

int main() {
 int f[] = { 1, 3, 7, 1, 2 };
 int* z = unique(f, f+5, greater<int>());
 copy(f, z, ostream_iterator<int>(cout, " "));
}

Compiled with Borland C++-Builder 4 or Visual C++ 5.0 the result is 1 3
7, but that seems to be wrong! The C++ standard says (25.2.8):

  template<class InputIterator, class OutputIterator,
           class BinaryPredicate>
    OutputIterator
      unique_copy(InputIterator first, InputIterator last,
                  OutputIterator result, BinaryPredicate pred);

  Effects:
    Copies only the first element from every consecutive group of equal
    elements referred to by the iterator i in the range [first, last)
    for which the following corresponding conditions hold:
    *i == *(i - 1) or pred(*i, *(i - 1)) == true

Therefor the output should be 1 3 7 2, or what do you think?

BTW, the iterator i should be in the range [first + 1, last), because
for i = first the iterator first - 1 is not defined.

Thanks for your time,
  Stefan



[ 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 Jan 2000 21:50:55 GMT, Stefan <cool@worblehat.wifo.uni-mannheim.de>
wrote:

:  int* z = unique(f, f+5, greater<int>());

:       unique_copy(InputIterator first, InputIterator last,

: Therefor the output should be 1 3 7 2, or what do you think?

I think you should expect the result of unique when you use it, or
use unique_copy when you expect those results.

John
---
[ 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              ]

Stefan wrote:
>
> What is the correct output of the following program?
>
> #include <algorithm>
> #include <functional>
> #include <iostream>
> using namespace std;
>
> int main() {
>         int f[] = { 1, 3, 7, 1, 2 };
>         int* z = unique(f, f+5, greater<int>());
>         copy(f, z, ostream_iterator<int>(cout, " "));
> }
>
> Compiled with Borland C++-Builder 4 or Visual C++ 5.0 the result is 1 3
> 7, but that seems to be wrong!

unique uses its predicate argument as a test for equality. It is only
required to work when that predicate defines an equivalence
relationship. greater<int> is not an equivalence relationship, so the
call can't be expected to do anything sensible.

--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Stefan <cool@worblehat.wifo.uni-mannheim.de> wrote:

> Effects:
> Copies only the first element from every consecutive group of equal
> elements referred to by the iterator i in the range [first, last)
> for which the following corresponding conditions hold:
> *i == *(i - 1) or pred(*i, *(i - 1)) == true
>
> Therefor the output should be 1 3 7 2, or what do you think?

Wow. Good point!

The traditional implementation (from the original HP STL) uses code that
compares each element to the first of the "equal range" rather than code
that compares each element with its immediate predecessor. I believe this is
done to minimize copying. The standard does not match existing practice!

The same issue exists for std::adjacent_find and std::unique_copy.

When the predicate has equality semantics, it doesn't matter if you're
comparing with the first item of the "equal range" or the current item. But
in the case you present here, 2 is compared with 7 (the first item in the
"equal range") rather than being compared with 1 (the previous item).

I would be willing to bet that all extant implementations of adjacent_find,
unique, and unique_copy match the original HP STL rather than the standard.

It's time for someone to write a defect report.

    -- Darin



[ 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              ]