Alberto Barbati wrote:
> chris wrote:
>
>>
>> There are two functions in the C++ standard (stable_partition and
>> stable_sort) which discuss using extra buffers if "enough extra memory
>> is available". I am assuming that the following things hold:
>>
>> A) For things like an array of std::vector, std::list, std::map, etc.
>> The implementation could just check to see if there is enough room for
>> a buffer size "arraylength*sizeof(std::vector<foo>)" and then attempt
>> to use the "buffer version", although this might lead to running out
>> of memory, as there is not enough room for the actual contents of the
>> vectors / lists / maps / etc.
>
>
> Where does the size "arraylength*sizeof(std::vector<foo>)" come from?
> Shouldn't it be ""arraylength*sizeof(foo)"?
>
What I mean is, consider the case where you want to stable_parition
(say) a (for example) vector<vector<foo> >. Then the implementation will
probably think that it needs (vector length)*sizeof(vector<foo>) extra
memory.

If however it then implements the stable_sort by copying the entire of
the original vector<vector<foo> > into the temporary buffer, then the
extra memory required is going to be this amount + the contents of each
of the vector<foo>, which will be much more. On one hand I don't see how
the implementation could detect without type-specific code if there was
enough room for this to occur, on the other hand it's irritating that
there is a low-memory version, but no way of triggering it when I can
see that copying the entire vector<vector<foo> > is going to result in
running out of memory.

This may be fixed if at some point most of the standard library, these
functions included, get mandated to use swap() for all the container
moving requirements...

>
> IIRC, stable_sort and stable_partition were designed to rely on the two
> functions get_temporary_buffer and release_temporary_buffer to get the
> "extra memory". In fact the library implementations shipped with both
> VC71 and gcc 3.4.2 do that. However this requirement is not stated
> explicitly in the standard, so the implementation is not obliged to do
> so. Does anyone know the rationale for this omission? Explictly
> requiring stable_sort and stable_partition to eventually obtain the
> memory from get_temporary_buffer/return_temporary_buffer seems a good
> thing to me:
>
> 1) it would avoid the need for the obscure sentence "if there is enough
> extra memory" (or at least provide a clarification)
>
> 2) it would provide the programmer a portable opportunity of
> customization as get_temporary_buffer/return_temporary_buffer could be
> specialized

If such functions are provided, it would seem sensible to mandate their
use :)

Thank you,

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                       ]

Hello,

First I'll quickly apologise for my previous question on std::set.. I'm=20
not sure how I possibly missed all the things on it =AC_=AC This one I'm=20
fairly sure isn't discussed anyway (sorry if it is).

There are two functions in the C++ standard (stable_partition and=20
stable_sort) which discuss using extra buffers if "enough extra memory=20
is available". I am assuming that the following things hold:

A) For things like an array of std::vector, std::list, std::map, etc.=20
The implementation could just check to see if there is enough room for a=20
buffer size "arraylength*sizeof(std::vector<foo>)" and then attempt to=20
use the "buffer version", although this might lead to running out of=20
memory, as there is not enough room for the actual contents of the=20
vectors / lists / maps / etc.

B) An implementation can decide under what conditions "enough extra=20
memory if available" holds, for example if creating a buffer would cause=20
the use of swap space (for example), then an implementation could decide=20
to use the "low memory" version, even if it would actually be possible=20
to run the buffered version, if inefficently.

In general this seems to be a (perhaps unavoidably) poorly defined term,=20
which on modern operating systems with virtual memory, overallocation=20
and similar features becomes very difficult to implement correctly.=20
Perhaps the standard should be changed to say that an implementation=20
"may provide and use" a low-memory version, but doesn't have to? Or=20
allow the user to force the use of either the high-memory or low-memory=20
version?

Thank you,

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                       ]

chris wrote:
>
> There are two functions in the C++ standard (stable_partition and
> stable_sort) which discuss using extra buffers if "enough extra memory
> is available". I am assuming that the following things hold:
>
> A) For things like an array of std::vector, std::list, std::map, etc.
> The implementation could just check to see if there is enough room for a
> buffer size "arraylength*sizeof(std::vector<foo>)" and then attempt to
> use the "buffer version", although this might lead to running out of
> memory, as there is not enough room for the actual contents of the
> vectors / lists / maps / etc.

Where does the size "arraylength*sizeof(std::vector<foo>)" come from?
Shouldn't it be ""arraylength*sizeof(foo)"?

>
> In general this seems to be a (perhaps unavoidably) poorly defined term,
> which on modern operating systems with virtual memory, overallocation
> and similar features becomes very difficult to implement correctly.
> Perhaps the standard should be changed to say that an implementation
> "may provide and use" a low-memory version, but doesn't have to? Or
> allow the user to force the use of either the high-memory or low-memory
> version?
>

IIRC, stable_sort and stable_partition were designed to rely on the two
functions get_temporary_buffer and release_temporary_buffer to get the
"extra memory". In fact the library implementations shipped with both
VC71 and gcc 3.4.2 do that. However this requirement is not stated
explicitly in the standard, so the implementation is not obliged to do
so. Does anyone know the rationale for this omission? Explictly
requiring stable_sort and stable_partition to eventually obtain the
memory from get_temporary_buffer/return_temporary_buffer seems a good
thing to me:

1) it would avoid the need for the obscure sentence "if there is enough
extra memory" (or at least provide a clarification)

2) it would provide the programmer a portable opportunity of
customization as get_temporary_buffer/return_temporary_buffer could be
specialized

Alberto

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