The proposed resolution to Library issue 780 ( std::merge()
specification incorrect/insufficient) is still not sufficient.  The
proposed resolution gives the effects of merge as the following:

"Copies all the elements of the two sorted ranges [first1,last1) and
[first2,last2) into the range [result,result + (last1 - first1) +
(last2 - first2)) , such that resulting range will be sorted in
non-decreasing order; that is for every pair of iterators i and j of
either input ranges, where *i was copied to the output range before *j
was copied to the output range, the condition *j < *i or,
respectively, comp(*j, *i) will be false."

This ignores the question of the order in which equivalent elements
are copied.  If an element x1 of [first1, last1) is equivalent to an
element x2 of [first2, last2), then x1 should be copied to the output
range before x2 is.  Otherwise, it would be impossible to implement
stable_sort() with a mergesort algorithm that uses std::merge().


Joe Gottman

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

"Joe Gottman" <jgottman@carolina.rr.com> wrote in message
news:FYAUm.366901$Jp1.44134@en-nntp-02.dc1.easynews.com...
The proposed resolution to Library issue 780 ( std::merge()
specification incorrect/insufficient) is still not sufficient.  The
proposed resolution gives the effects of merge as the following:

"Copies all the elements of the two sorted ranges [first1,last1) and
[first2,last2) into the range [result,result + (last1 - first1) +
(last2 - first2)) , such that resulting range will be sorted in
non-decreasing order; that is for every pair of iterators i and j of
either input ranges, where *i was copied to the output range before *j
was copied to the output range, the condition *j < *i or,
respectively, comp(*j, *i) will be false."

This ignores the question of the order in which equivalent elements
are copied.  If an element x1 of [first1, last1) is equivalent to an
element x2 of [first2, last2), then x1 should be copied to the output
range before x2 is.  Otherwise, it would be impossible to implement
stable_sort() with a mergesort algorithm that uses std::merge().

Agreed. I will note that the current specification of merge has a
remark of stable, but it does not specify that it is stable with
respect to the result of the conncationation of sequence 1 and
sequence 2. So with the above definition combined with this remark the
required results are:

Result sequence is sorted.
All elements of sequence 1 will be found in result in the same relative order.
All elements of sequence 2 will be found in result in the same relative order.
But it imposes no constraint on the relative ordering of equal
elements from both sequences.

That is close to what is desired. Perhaps all that is needed is to
change the remark to specify that it is
stable relative to the concationation of the first and second
sequences. That would imply that equal elements must be present in the
order they are found in sequence 1, followed by the order they are
found in sequence 2, which is the desired result.

This is also a trivial fix, since it would not require reworking that
monster of a sentance you quote above, but it does require that the
the "remark" section be considered as placing normative requirements
on implementations. If not, I would simply add a second sentance to
the effect section that states "The result range shall be stable with
respect to the concatonation of [first1,last1) and [first2,last2)." or
something similar.

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

Since my last copy of this message came out formatted so poorly that it was
not possible to distinguish Joe Gottman's text from mine, I'm resubmitting
my mesage.

Joe Gottman wrote:
> This ignores the question of the order in which equivalent elements
> are copied.  If an element x1 of [first1, last1) is equivalent to an
> element x2 of [first2, last2), then x1 should be copied to the output
> range before x2 is.  Otherwise, it would be impossible to implement
> stable_sort() with a mergesort algorithm that uses std::merge().
>

I wrote:

Agreed. I will note that the current specification of merge has a
remark of stable, but it does not specify that it is stable with
respect to the result of the conncationation of sequence 1 and
sequence 2. So with the above definition combined with this remark the
required results are:

Result sequence is sorted.
All elements of sequence 1 will be found in result in the same relative
order.
All elements of sequence 2 will be found in result in the same relative
order.
But it imposes no constraint on the relative ordering of equal
elements from both sequences.

That is close to what is desired. Perhaps all that is needed is to
change the remark to specify that it is
stable relative to the concationation of the first and second
sequences. That would imply that equal elements must be present in the
order they are found in sequence 1, followed by the order they are
found in sequence 2, which is the desired result.

This is also a trivial fix, since it would not require reworking that
monster of a sentance you quote above, but it does require that the
the "remark" section be considered as placing normative requirements
on implementations. If not, I would simply add a second sentance to
the effect section that states "The result range shall be stable with
respect to the concatonation of [first1,last1) and [first2,last2)." or
something similar.



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