VC STL - Request to Dinkumware

Author

Request to Dinkumware

Stephen Howe

2006-03-10, 7:01 pm

Hi

Could I request, as library extensions, that the template functions

is_sorted()
is_heap()

be added, as documented here:
http://www.cs.vassar.edu/mirror/STL_doc/is_heap.html
http://www.cs.vassar.edu/mirror/STL_doc/is_sorted.html

is_sorted() is extremely useful if you insert, change elements in a sorted
sequence and wish to check that it is still sorted before invoking the full
power of sort() or stable_sort().

I have no idea if they have/have not been put forward to forthcoming library
(I will check), or the next one, or the next standard.

Thanks

Stephen Howe

Stephen Howe

2006-03-10, 7:01 pm

> be added, as documented here:
> http://www.cs.vassar.edu/mirror/STL_doc/is_heap.html
> http://www.cs.vassar.edu/mirror/STL_doc/is_sorted.html

And it should be such that is_sorted(), is_heap() returns true for 0 or 1
elements.

Stephen Howe

P.J. Plauger

2006-03-10, 7:01 pm

"Stephen Howe" <stephenPOINThoweATtns-globalPOINTcom> wrote in message
news:eutqYJFRGHA.2176@TK2MSFTNGP10.phx.gbl...

> Could I request, as library extensions, that the template functions
>
> is_sorted()
> is_heap()
>
> be added, as documented here:
> http://www.cs.vassar.edu/mirror/STL_doc/is_heap.html
> http://www.cs.vassar.edu/mirror/STL_doc/is_sorted.html

Been in our library for years, guarded by _HAS_TRADITIONAL_STL.
Unfortunately, we strip such things out before delivering updates
to Microsoft. (We also provide STLport compatibility for hash
maps and sets, through partial specialization, guarded by
_HAS_STLPORT_EMULATION; but that also gets left out of the
updates.) It's always possible that Microsoft will someday ask
us to leave such thing in, and we'll happily oblige.

> is_sorted() is extremely useful if you insert, change elements in a sorted
> sequence and wish to check that it is still sorted before invoking the
> full
> power of sort() or stable_sort().

Grep for _DEBUG_ORDER and _DEBUG_HEAP, the functions we use for
checking integrity of ordered sequences and heaps when
_HAS_ITERATOR_DEBUGGING is turned on. Copy the functions, change
them to return bool, stick a return (true) at the end, and change
every _DEBUG_ERROR call to return (false). Maybe that'll tide you
over until you get formally supported versions of is_sorted/heap.

> I have no idea if they have/have not been put forward to forthcoming
> library
> (I will check), or the next one, or the next standard.

Don't think so.

HTH,

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

P.J. Plauger

2006-03-10, 7:01 pm

"Stephen Howe" <stephenPOINThoweATtns-globalPOINTcom> wrote in message
news:eu40sZFRGHA.1728@TK2MSFTNGP11.phx.gbl...

>
> And it should be such that is_sorted(), is_heap() returns true for 0 or 1
> elements.

Of course.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

Jerry Coffin

2006-03-10, 7:01 pm

In article <eutqYJFRGHA.2176@TK2MSFTNGP10.phx.gbl>,
"Stephen Howe" <stephenPOINThoweATtns-globalPOINTcom>
says...
> Hi
>
> Could I request, as library extensions, that the template functions
>
> is_sorted()

This strikes me as a rather pointless extension. Rather
than having an is_sorted, I think it would be better to
just implement sort() (for example) so it's really fast
if the data's already sorted. A good implementation of
quicksort will do that more or less automatically anyway.

> is_heap()

There might be more use for this, but my first guess is
that it's a bit like is_sorted -- it'd be better to make
this internal to make_heap, so it's really fast if the
elements are already arranged as a heap.

--
Later,
Jerry.

The universe is a figment of its own imagination.

Stephen Howe

2006-03-10, 7:01 pm

> > is_sorted()
>
> This strikes me as a rather pointless extension. Rather
> than having an is_sorted, I think it would be better to
> just implement sort() (for example) so it's really fast
> if the data's already sorted. A good implementation of
> quicksort will do that more or less automatically anyway.

Two things:

1) It can mount up.
If I have 5000000 items, all sorted, I push_back another 10 items and I have
reason to believe that the sort order might still be intact, I can
conditionally sort on the basis of what is_sorted() returns. It is O(N) and
at most N-1 comparisons are necessary to establish this. Better that than
O(N * lg N) every time.

2) You are forgetting that stable_sort() can also be called which is more
expensive to call that sort() with possible auxiliary memory required.
And it can also be used with list's sort() as is_sorted() only requires
forward only iterators. Further, sorting deques might be more expensive than
sorting vectors, so not sorting them might be faster.

This

if (!is_sorted(v.begin(), v.end()))
stable_sort (v.begin(), v.end());

might be more reasonable than unconditionally doing

stable_sort (v.begin(), v.end());

if you strongly suspect the sort order might be unchanged.
You can always leave the test out if you are certain it is changed.

And also for list

if (!is_sorted(l.begin(), l.end()))
l.sort(l.begin(), l.end());

I have no idea of the speed of list's sort() compared to sort()'ing a
vector. It would depend on the size of object in the container with list's
sort() getting better the larger the object is (links are reformed rather
than copying objects).

Similar comments apply to is_heap() where at most N/2 comparisons are
necessary compared to 3 * N for make_heap()

Stephen Howe

Stephen Howe

2006-03-10, 7:01 pm

> It's always possible that Microsoft will someday ask
> us to leave such thing in, and we'll happily oblige.

I have made such a suggestion in MS's feedback

Stephen Howe

Jerry Coffin

2006-03-11, 7:00 pm

In article <#yNh2fHRGHA.336@TK2MSFTNGP12.phx.gbl>,
"Stephen Howe" <stephenPOINThoweATtns-globalPOINTcom>
says...
>
> Two things:
>
> 1) It can mount up.
> If I have 5000000 items, all sorted, I push_back another 10 items and I have
> reason to believe that the sort order might still be intact, I can
> conditionally sort on the basis of what is_sorted() returns. It is O(N) and
> at most N-1 comparisons are necessary to establish this. Better that than
> O(N * lg N) every time.

I guess I must have expressed myself poorly. I meant that
sort would be implemented something like (skipping the
template stuff and such for now):

void sort(iterator a, iterator b) {
if (is_sorted(a, b))
return;
do_sort(a,b);
}

Likewise, stable_sort would be something like:

void stable_sort(iterator a, iterator b) {
if (is_sorted(a,b))
return;
do_stable_sort(a,b);
}

I haven't looked recently to see if it still is, but at
one time Microsoft's implementation of qsort worked this
way, scanning the data to see if it was sorted before
attempting to sort it. This costs you something if the
data isn't sorted, but since you normally exit the
is_sorted part as soon as you find something out of
order, the cost for using it on unsorted data is usually
trivial.

This can also lead to another significant optimization.
The initial scan finds a subset that's sorted. If you
find that this is a significant percentage of the whole,
you can sort the remainder separately, and then merge the
two sorted sections. This is particularly useful when a
few elements have been appended to an otherwise sorted
collection.

> 2) You are forgetting that stable_sort() can also be called which is more
> expensive to call that sort() with possible auxiliary memory required.

The whole point is for stable_sort to _avoid_ actually
doing any sorting at all on data that's already sorted.

--
Later,
Jerry.

The universe is a figment of its own imagination.

Sponsored Links