"Daniel Kr   gler" <daniel.kruegler@googlemail.com> wrote in message
news:5fc46bb9-0aef-4984-8939-860930167f83@y11g2000yqh.googlegroups.com...
> On 28 Feb., 03:39, "Christopher Yeleighton" <giecr...@stegny.2a.pl>
> wrote:
>> "Daniel Kr gler" <daniel.krueg...@googlemail.com> wrote in message
>>
>> news:c40e3c89-f6a5-4da5-8728-f1e4ef9fd791@t23g2000yqt.googlegroups.com...
>>
>> > Note that the upcoming C++0x standard will provide
>> > is_sorted, see the most recent working draft:
>>
>> >http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3035.pdf
>>
>> Oh I see, here it is:http://www.open-std.org/jtc1/sc22/wg21/docs/
> papers/2007/n2246.html#is...
>
> Therefore it seemed more appropriate to
> point to the current working draft (WD).

I needed more meat because I needed a workaround for my compiler.

>
>> === Process ===
>> Is there an easier process to find the definitive paper for a feature?  I
>> think at least the draft could be annotated.
>
> I don't think so. This is an awful lot of work, and the
> library editor does already provide support to
> recognize the changes relative to the previous draft
> version by marking changes in colored font since
> some time. I'm not sure, what you precisely mean
> with "annotations" here, could you elaborate?

Practically, is_sorted [N2246] in the section would be enough, typeset as
metadata.  This information is readily available when the
addition/modification is being discussed so I cannot see why it would be
much work to put it there.  It could go away when the draft becomes a
standard.
A stand-alone table of record (section_name, document_number) would also do,
although it would be harder to use and maintain.

  Best regards,
Chris



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

== Problem statement ==
There are algorithms in the standard library, e.g. binary search, that work
reasonably if the input range is ordered.  However, there is no facility to
test that.

== Remarks ==
The SGI implementation provides an algorithm called is_sorted [1].

If the sort algorithm were guaranteed to work in linear time on ordered
input, the problem would be partially solved.  However, I would still prefer
throwing in some circumstances.

If sorting an ordered sequence is guaranteed not to modify the sequence in
any way, that could be done with a custom iterator that throws on
assignment; at present, it seems to be the only way to go-but I am not sure
whether I can count on that assumption.  Alternatively, I can roll my own
(trivial) algorithm-but I feel such a thing should be standard, just like
partition and partial sort.

== References ==
[1] <URL:http://www.sgi.com/tech/stl/is_sorted.html>



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

Christopher Yeleighton wrote:
> == Problem statement ==
> There are algorithms in the standard library, e.g. binary search, that work
> reasonably if the input range is ordered.  However, there is no facility to
> test that.

There is in draft C++0x.  See the specification for std::is_sorted in 25.4.1.5
of N3035.

Scott

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

Christopher Yeleighton wrote:
> == Problem statement ==
> There are algorithms in the standard library, e.g. binary search, that work
> reasonably if the input range is ordered.  However, there is no facility to
> test that.

Oddly enough, C++0x will provide std::is_sorted.

--
    Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of
"The Standard C++ Library Extensions: a Tutorial and Reference"
(www.petebecker.com/tr1book)

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

On 25 Feb., 17:33, "Christopher Yeleighton" <giecr...@stegny.2a.pl>
wrote:
> == Problem statement ==
> There are algorithms in the standard library, e.g. binary search, that work
> reasonably if the input range is ordered.  However, there is no facility to
> test that.
>
> == Remarks ==
> The SGI implementation provides an algorithm called is_sorted [1].
>
> If the sort algorithm were guaranteed to work in linear time on ordered
> input, the problem would be partially solved.  However, I would still prefer
> throwing in some circumstances.
>
> If sorting an ordered sequence is guaranteed not to modify the sequence in
> any way, that could be done with a custom iterator that throws on
> assignment; at present, it seems to be the only way to go-but I am not sure
> whether I can count on that assumption.  Alternatively, I can roll my own
> (trivial) algorithm-but I feel such a thing should be standard, just like
> partition and partial sort.
>
> == References ==
> [1] <URL:http://www.sgi.com/tech/stl/is_sorted.html>

Note that the upcoming C++0x standard will provide
is_sorted, see the most recent working draft:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3035.pdf

HTH & Greetings from Bremen,

Daniel Kr   gler


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

"Daniel Kr   gler" <daniel.kruegler@googlemail.com> wrote in message
news:c40e3c89-f6a5-4da5-8728-f1e4ef9fd791@t23g2000yqt.googlegroups.com...
> Note that the upcoming C++0x standard will provide
> is_sorted, see the most recent working draft:
>
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3035.pdf
>

Oh I see, here it is:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2246.html#is-sorted
And, for the record, that following remark provides a handy workaround:

> It does exist in stl. One can use "adjacent_find" with predicate "less" to
> obtain the same result .

And the thing is copied from boost so users of the current standard can get
it from there.
I am rather surprised it is not in the FAQ.

== Remarks ==

=== Terminology ===
While we are at that, I think that the terminology used by the standard (and
by the original implementation) is jargon.  The term "sorted" comes from
basket sorting where you have a bag of items that you put to baskets
according to what they are, i.e. according to their _sort_.  That requires
an
equivalence relation, not an ordering, and a range is _sorted_ when it is
appropriate for SELECT UNIQUE.  OTOH, a range is _ordered_ when it is
appropriate for BINARY SEARCH.  It seems that because basket sorting is not
very very common in software, a semantic shift occurred.

=== Process ===
It was a lot of work to find the definitive paper N2246; it involved binary
search over the working drafts.
Is there an easier process to find the definitive paper for a feature?  I
think at least the draft could be annotated.

Thanks a lot,
Chris






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

On 28 Feb., 03:39, "Christopher Yeleighton" <giecr...@stegny.2a.pl>
wrote:
> "Daniel Kr gler" <daniel.krueg...@googlemail.com> wrote in message
>
> news:c40e3c89-f6a5-4da5-8728-f1e4ef9fd791@t23g2000yqt.googlegroups.com...
>
> > Note that the upcoming C++0x standard will provide
> > is_sorted, see the most recent working draft:
>
> >http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3035.pdf
>
> Oh I see, here it is:http://www.open-std.org/jtc1/sc22/wg21/docs/
papers/2007/n2246.html#is...

<nod> I could have provided the link to you, but
I didn't because a paper is just a proposal and
the recommended wording changes suggested
in such a paper may or may not be accepted.
People sometimes reference these papers as
a proof that a compiler does not satisfy what
the paper describes. But the papers are just
the foundation on which a final standardeze
will be formed. Nevertheless they are of
additional usefulness, because they typically
give some rationale for the addition.

In general such a paper goes through several
iterative steps and final wording is decided on
during a committee meeting. If accepted, the
*consensus* wording goes into the working draft.
Therefore it seemed more appropriate to
point to the current working draft (WD).

> === Process ===
> Is there an easier process to find the definitive paper for a feature?  I
> think at least the draft could be annotated.

I don't think so. This is an awful lot of work, and the
library editor does already provide support to
recognize the changes relative to the previous draft
version by marking changes in colored font since
some time. I'm not sure, what you precisely mean
with "annotations" here, could you elaborate?

There exists the so-called editor report, where the
recent changes are described. But I don't believe
that this would have helped you to find the addition
of is_sorted to the WD, though.

HTH & Greetings from Bremen,

Daniel Kr   gler



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