This message is part of an experiment I hope will end up being useful. I
intend to compose a list of minor fixes to the standard library, which I
will bundle up and submit for the TR2 library proposal, to (hopefully)
improve any small weaknesses which have been found after extensive usage
of the C++ standard library. I'm very interested in any suggestions
anyone has!

As a vague guide, any suggestions should:

A) Be  minor extensions to the existing library.
B) Be expressable in a paragraph or two at most.
C) Take a good C++ programmer no longer than a long afternoon to implement.
D) Not break any existing code.

Bad:

- I want a tree container
     Far too major an extension
- std::pair should specialise swap
     While useful, you can write (freakish) code it would break.

Here are a few examples. Not that a) this list is by no means supposed
to be exaustive or final, b) are written less informally than a final
submitted version would be and c) have all been implemented.

Sort, nth_element -

Sort should only require bidirectional iterators. The worst case
requirements for random access iterators should be tightened to
O(n.log(n)) (as all implementations I know of already meet that anyway).
Bidirectional iterators would be worst case O(n^2) as present.

I'm unconvinced that allowing sorting forward iterators would be useful.
Would anyone ever use it?

Stable sort, inplace_merge -

These only require only bidirectional iterators.
(Once again.. would anyone want forward iterators?)

Partition -
Require only forward iterators.

search_n -
Strengthen complexity requirements to at most (last1 - first1)
applications of the predicate.

copy_if -
Add this algorithm in the obvious way.

find, find_if -

Instead of saying something like "n applications of the predicate", say
  "if an iterator is found which satisfies the predicate, at most (last
- first + i) applications of the predicate, otherwise last - first
applications".


Chris

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

wade@stoner.com wrote:
>
> chris jefferson wrote:
>
>>Sort, nth_element -
>>
>>Sort should only require bidirectional iterators.
>>Bidirectional iterators would be worst case O(n^2) as present.
>
> You can write sort (and stable sort and friends) in terms of
> inplace_merge, with the complete sort taking only O(n log(n)^2) time,
> so why allow quadratic behavior?

Part of the reason is that inplace_merge without an extra buffer has
quite a "large constant", and in most cases a quick-sort would replace
it. We could of course add the "extra buffer" requirement, but my
personal opinion is that the whole "If an extra buffer can be allocated
then.." parts of the standard are a disaster, particularily because as
far as I know, no-one actually implements them correctly, and it's
probably not possible to do so.

>
>>find, find_if -
>>
>>Instead of saying something like "n applications of the predicate", say
>>  "if an iterator is found which satisfies the predicate, at most (last
>>- first + i) applications of the predicate, otherwise last - first
>>applications".
>
>
> You probably meant "(i-first)" rather than "(last-first)"
>
Yes, I did. Thanks :)

Chris

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

Stephen Howe wrote:
>>Part of the reason is that inplace_merge without an extra buffer has quite
>>a "large constant"...
>
>
> There has been some algorithmic research in the past 15 years, some
> improvements on this tough problem, the constant is not as large as you
> think.

I'm more than happy to stand corrected on this issue, and will go away
and read some up-to-date algorithm papers :)

>  We could of course add the "extra buffer" requirement, but my
>
>>personal opinion is that the whole "If an extra buffer can be allocated
>>then.." parts of the standard are a disaster, particularily because as far
>>as I know, no-one actually implements them correctly, and it's probably
>>not possible to do so.
>
>
> All the implementations I know implement inplace_merge() correctly.
> And stable_sort()
> And stable_partition()
>

The only time I've personally wanted the low-memory versions of these
algorithms to be activated was stable_sorting a large
vector<vector<int>>s and vector<list<int>>s, when the internal
vectors/lists were of a large size (>1,000 elements).

I expected the low-memory versions to be used, however instead what
happened is that they checked they could allocate enough memory for
sizeof(iterator_traits<iterator>::value_type) * (length of range),
suceeded, started copying my vector<vector<int> > into their copy, and
died horribly. Are there any implementations that don't do this? I'm not
convinced if you can argue these implementations violate the standard,
as I'm not sure how you could do it any other way (other than say they
have to always swap in and out of these vectors, or always use the low
memory algorithms for non-PODs, or always use a "build temporary vector
of pointers, and stable_sort that" for non-PODs).

Once move symantics come around, this problem will actually be solved,
as then the vectors and lists would be moved around instead of copied,
and the memory usage shouldn't shoot up mid-algorithm.

Chris

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

David Abrahams wrote:
> caj@cs.york.ac.uk (chris jefferson) writes:
>
>
>>The only time I've personally wanted the low-memory versions of these
>>algorithms to be activated was stable_sorting a large
>>vector<vector<int>>s and vector<list<int>>s, when the internal
>>vectors/lists were of a large size (>1,000 elements).
>>
>>I expected the low-memory versions to be used, however instead what
>>happened is that they checked they could allocate enough memory for
>>sizeof(iterator_traits<iterator>::value_type) * (length of range),
>>suceeded, started copying my vector<vector<int> > into their copy, and
>>died horribly. Are there any implementations that don't do this? I'm not
>>convinced if you can argue these implementations violate the standard,
>>as I'm not sure how you could do it any other way (other than say they
>>have to always swap in and out of these vectors, or always use the low
>>memory algorithms for non-PODs, or always use a "build temporary vector
>>of pointers, and stable_sort that" for non-PODs).
>
>
> Were you on Linux?  More than likely you ran into the problem that the
> system will "allocate" you as much memory as you want, but it only
> really tries to _get_ your virtual memory when you step outside the
> page cache... when it's too late even for throwing C++ exceptions.
> If so, you have to look into how to disable this behavior.  It's not a
> C++ issue.
>
I am aware of such behaviour, but my problem was the C++ library, not my
operating system!

If I look at three implementations (roguewave, stlport and libstdc++.
I'm not picking on these at all, it's just they are the currently open
source ones, so I don't feel guilty about quoting bits of their code)
the behaviour is something like:

rougewave: If we are trying to stable_sort a range of Ts, then call
get_temporary_buffer(Dist(last-first), T*), and then once you have this
buffer, there is no attempt at try/catch at all, so if when you actually
fill the buffer you run out of memory (say you are filling it with
vector<int>s), everything will die horribly.

libstdc++ & stlport: Better, here get_temporary_buffer is called again,
to get as large a buffer as possible (under the assumption that only
sizeof(T) will be needed for each element). It then tries to fill it
with copies of the first element in the range to be stable_sorted, and
if this fails the elements are deleted and attempts to get a buffer are
abandoned.

Mylib: Allocate as big a buffer as possible and try to fill it with a
copy of the first n elements of the range to be stable_sorted (where n
is the size of the buffer). If this fails fall back on the cheap
implementation, else carry on and assume we won't run out out memory.

One interesting question is which of the following did the standard mean
should be done?

(a) Once a buffer of raw memory to copy elements into is acquired, we
doesn't have to worry any more (roguewave)

(b) Once the buffer is filled with copies of the first element, we don't
have to worry about memory any more (and if the very first attempt to do
this fails, then we can give up and use the low-memory implementation,
not try a smaller buffer) (libstdc++, stlport).

(c) Same as (b) but copy the first n elements of the range into the
buffer instead of just the first element (in particular if we can get a
buffer as big as the vector, then in this case we know there won't be a
failure after we start). (Mylib)

(d) It has to cope with running out of memory at any point and falling
back on a simpler implementation.

Also is it only necessary to try getting the maximum size buffer (which
is probably safer), or is it necessary to try getting progressively
smaller buffers?

In my particular case, (b) failed as it happened the first vector in the
array I was sorting was empty. I'm happy to accept this is probably
unusual however.

I have implemented (d), but it is very slightly slower due to the
quantity of try/catches you need. If thats what the standard requires
however, thats what should be implemented :)

Chris

---
[ 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://www.jamesd.demon.co.uk/csc/faq.html                       ]