🚀 go-pugleaf

In article <48h0vg$8i6@meg.tesser.com> ralphs@tesser.com (Ralph Shnelvar) writes:

> I haven't even peeked at the STL but am wondering if there is support
> for a disk based sorting and/or indexing algorithms.
> 
> That is, is there support for sorting monster arrays.

No.  The closest thing the STL has to what you're looking for is its
istream_iterator and ostream_iterator.  I don't think they'd really 
be appropriate for this task, though.

The good news, though, is that the STL isn't a container class library
in any conventional sense; it isn't even a container, iterator, and
algorithm library either, although that comes closer.  What it really
is is a set of requirements that containers, iterators, and algorithms
must satisfy if they are to work together, and a fairly large but
deliberately incomplete set of predefined containers, iterators, and
algorithms.

In other words: if you define iterators that point into data files
(depending on your design, and on your OS's file I/O capabilities, you
might choose to use input iterators, forward iterators, or even random
access iterators), then you can use all of the STL algorithms that
make sense for iterators of that category.

If you look in the draft standard, by the way, you'll see no mention
of the STL in the table of contents.  It's a very important part of
the standard C++ class library, so the original STL manual has been
distributed into various parts of the draft standard.  The most
important places to look are Chapter 20 (General Utilities), Chapter
23 (Containers), Chapter 24 (Iterators), and Chapter 25 (Algorithms).
Other parts of the standard library are influenced by the STL too,
though; strings, for example, are now STL containers.
-- 
  Matt Austern                             He showed his lower teeth.  "We 
  matt@physics.berkeley.edu                all have flaws," he said, "and 
  http://dogbert.lbl.gov/~matt             mine is being wicked."

---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

Distribution:
In article <48h0vg$8i6@meg.tesser.com> ralphs@tesser.com (Ralph Shnelvar) writes:

> I haven't even peeked at the STL but am wondering if there is support
> for a disk based sorting and/or indexing algorithms.

Sure.  All you have to do is write a class that meets the
relevant iterator constraints and grants access to your
disk file.  Then all the algorithms will work.
-- 
				--Andrew Koenig
				  ark@research.att.com


---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

In article <DI8rpv.H5x@research.att.com>,
Andrew Koenig <ark@research.att.com> wrote:
>Distribution:
>In article <48h0vg$8i6@meg.tesser.com> ralphs@tesser.com (Ralph Shnelvar) writes:
>
>> I haven't even peeked at the STL but am wondering if there is support
>> for a disk based sorting and/or indexing algorithms.
>
>Sure.  All you have to do is write a class that meets the
>relevant iterator constraints and grants access to your
>disk file.  Then all the algorithms will work.
>-- 
>				--Andrew Koenig
>				  ark@research.att.com

A cleaner way to do it is to make C++ persistent, and then use normal
"in memory" data structures to do your sorting.  Of course, you need
to pick data structures and algorithms that have good locality.

Mumit Khan has used our Texas persistent store (an efficient, high-tech,
but fairly portable p-store) for Persistent GNU STL.  Unfortunately,
GNU STL's current allocator scheme breaks orthogonal persistence, but if
you want all of your data structures to be persistent anyway, that's OK.

The next release of Texas will contain better support for STL.  (The
current release has trouble with nested classes, and requires a little
hand-fiddling to make it work.  The next release will handle nested
classes semiautomatically---you'll have to provide a list of header
files relevant to nested classes so that we can correctly generate
type descriptor information for them.)

-- 
| Paul R. Wilson, Comp. Sci. Dept., U of Texas @ Austin (wilson@cs.utexas.edu)
| Papers on memory allocators, garbage collection, memory hierarchies,
| persistence and  Scheme interpreters and compilers available via ftp from 
| ftp.cs.utexas.edu, in pub/garbage (or http://www.cs.utexas.edu/users/wilson/)      


---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

ralphs@tesser.com (Ralph Shnelvar) wrote:
>
>I haven't even peeked at the STL but am wondering if there is support
>for a disk based sorting and/or indexing algorithms.
>
>That is, is there support for sorting monster arrays.

YES. STL sort is a completely generic algorithm. It can
sort "anything".

However, STL does not come pre-packaged with a
"Monster_Disk_Array" container. but you can write
one yourself, and if you follow the requirements
for such containers, STL sort will sort it,
reverse it, permute it or copy it.

[Note some algorithms might require some local storage.
It _should_ be documented how much if the amount
is not fixed. if it isn't we'd better complain
because programmers need to know about space
as well as time requirements]


-- 
John Max Skaller               voice: 61-2-566-2189
81 Glebe Point Rd              fax:   61-2-660-0850
GLEBE NSW 2037                 email: maxtal@suphys.physics.oz.au
AUSTRALIA                      email: skaller@maxtal.com.au
---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

ark@research.att.com (Andrew Koenig) writes:

>ralphs@tesser.com (Ralph Shnelvar) writes:
>
>> I haven't even peeked at the STL but am wondering if there is support
>> for a disk based sorting and/or indexing algorithms.
>
>Sure.  All you have to do is write a class that meets the
>relevant iterator constraints and grants access to your
>disk file.  Then all the algorithms will work.

That misses the point a bit doesn't it?  To get reasonable efficiency,
wouldn't you want to use a different algorithm for disk based sorting
than for in-memory sorting?

--
Fergus Henderson             	WWW: http://www.cs.mu.oz.au/~fjh
fjh@cs.mu.oz.au              	PGP: finger fjh@128.250.37.3

[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

matt@cyclops5.berkeley.edu (Matt Austern) wrote:
>
>The good news, though, is that the STL isn't a container class library
>in any conventional sense; it isn't even a container, iterator, and
>algorithm library either, although that comes closer.  What it really
>is is a set of requirements that containers, iterators, and algorithms
>must satisfy if they are to work together, and a fairly large but
>deliberately incomplete set of predefined containers, iterators, and
>algorithms.

   I agree STRONGLY with this characterisation. In fact,
I'd venture to do one step further (as I usual do :-)

   STL isn't even a set of requirements (to be met by various
components). It's a FRAMEWORK for creating such requirements,
for ANY kind of generic component. (See Stepanov's papers,
available from various WEB servers)

  TO explain: it is impossible to divorce C++ from STL,
especially the template facilities. What Stepanov, Musser and Lee
have done is provided the bootstrap, namely the notion of
sequences. The framework is implicit, but it is a DOCUMENTATION
STANDARD, not a piece of software, or even specs for such software,
or even specs for that category of software: its a specification
(by example) of how to specify generic library architectures.

  For example, how would you do a graphics library
after seeing STL? [The same way STL is done]. How about
doing a matrix library with optimisation opportunities
for parallel execution? [The same way as STL]

  None of this would have been possible in C++ without
Bjarne Stroustrup's patient and persistent efforts to
upgrade the C++ language -- despite the difficulties
presented by the standardisation effort.

>If you look in the draft standard, by the way, you'll see no mention
>of the STL in the table of contents.  It's a very important part of
>the standard C++ class library, .....

  .. according to my interpretation the WHOLE Working Paper is
nothing but a particular component of the STL standard,
so you have it backwards -- ISO Standard C++ is (will be)
part of STL, not the other way around :-)

  STL makes a number of things clear not present in other C++ libraries:

* the way to handle errors (DONT, document what leads to them),

* the way to make things efficient (DON'T, document complexity requirements),

* the way to make the system meet the widest needs:
   (DONT, make it extensible, flexible, generic and reusable,
   DECOUPLE the components, and document the requirements for coupling
   them together), 

* the way to make things comprehensible
  (DON'T, define the notions rigorously, and make them mathematically
   simple -- leave comprehension to book writers).


In ISO C++, we have the categories Matt mentions: iterators,
containers (which are used to source the iterators), and
algorithms (which do work on the values stored in containers
via the iterators). These three _categories_ form a fairly
minimal sequential processing model. They're NOT
enough to handle real world requirments, which include
GUI's, databases, real time interactive I/O, and other 
things. But they show the way so that these things can be
decoupled into categories, analysed mathematically,
and specifications formulated, to allow interoperable
and reusable software components covering a larger
range of requirements to be developed.

Isn't that, more than anything else, what is needed
in the software industry?

-- 
John Max Skaller               voice: 61-2-566-2189
81 Glebe Point Rd              fax:   61-2-660-0850
GLEBE NSW 2037                 email: maxtal@suphys.physics.oz.au
AUSTRALIA                      email: skaller@maxtal.com.au



[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

In article <9532600.2695@mulga.cs.mu.OZ.AU>,
Fergus Henderson <fjh@munta.cs.mu.OZ.AU> wrote:
>ark@research.att.com (Andrew Koenig) writes:
>
>>ralphs@tesser.com (Ralph Shnelvar) writes:
>>
>>> I haven't even peeked at the STL but am wondering if there is support
>>> for a disk based sorting and/or indexing algorithms.
>>
>>Sure.  All you have to do is write a class that meets the
>>relevant iterator constraints and grants access to your
>>disk file.  Then all the algorithms will work.
>
>That misses the point a bit doesn't it?  To get reasonable efficiency,
>wouldn't you want to use a different algorithm for disk based sorting
>than for in-memory sorting?

Not necessarily.  Given that processor and disk speeds keep getting
further apart, locality of reference is increasingly important
for "in memory" data structures, so the same principles apply to
file sorting as to in-memory sorting.   What really matters is
the size and of the data set and the patterns of access, not whether
it's file data or a heap-allocated data structure.  A sort routine
for a large data structure should have good locality if you want
it to have good and robust performance.  In a virtual memory environment,
you don't want to assume that random access is actually a good idea.

In principle, a p-store should be more efficient than using files,
because you don't have to translate formats to move things into ad
out of virtual memory, and because the operating system doesn't
have to cache recently-transferred stuff in both the file cache
and the virtual memory cache.  After all, it's kinda silly that we
have two parallel memory hierarchies, both consisting of RAM and
disk, and we copy back and forth between them when doing I/O.

This is the motivation behind our work with persistent object stores.
Rather than having to read and write your C++ data structures to
and from files, you get the effect of a virtual memory that lives
forever.  If you want to operate on it, just follow pointers and
page it in automatically.

This means, of course, that data structure designers have to write
good classes for large data structures.  E.g., we've implemented B+
trees as a C++ class, so that you can get the nice locality effects
of B+ trees without having to externalize all of your data and go
through a krufty file interface.  We want to make the B+ trees STL
compatible, so that you can replace another collection implementation
with B+ trees if you decide that's more appropriate, locality-wise.

The nice thing about persistent C++ is that you can plug in different
data structures without worrying so much whether they should be coded
to be stored in files or "in memory".  The same code works for either.

Of course, you *do* have to pay attention to locality.  Getting
rid of the file/memory distinction doesn't make deep problems go
away;  it just makes tedious annoying unnecessary problems go away
by getting rid of the so-called "impedance mismatch" between file
and in-memory data.  

-- 
| Paul R. Wilson, Comp. Sci. Dept., U of Texas @ Austin (wilson@cs.utexas.edu)
| Papers on memory allocators, garbage collection, memory hierarchies,
| persistence and  Scheme interpreters and compilers available via ftp from 
| ftp.cs.utexas.edu, in pub/garbage (or http://www.cs.utexas.edu/users/wilson/)

---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]

Robert Buren <erarobu@era-t.ericsson.se> wrote:
>(This is mailed and posted to comp.std.c++)
>
>I agree with everything you say here. However, I would really
>appreciate it if you could expand on the quote below:
>
>John Max Skaller wrote:
>> 
>>   For example, how would you do a graphics library
>> after seeing STL? [The same way STL is done]. How about
>> doing a matrix library with optimisation opportunities
>> for parallel execution? [The same way as STL]
>
>Could you give just a tiny example of what you mean here?
>I think STL is great, but I feel that I can still only imagine
>STL as a set of container utilities. How would you make an
>STL-like graphics library?

One could do several things. For example, consider an image
as an 2 dimensional array of pixels. What kinds of navigations
are required for two dimensions?

For image processing, perhaps the notion of "iterator"
is replaced by a notion of "sampler", which takes a
weighted average near a point. 

Exactly how to do this would require study of the
application domain, and the existing algorithms
and data structures. 


-- 
John Max Skaller               voice: 61-2-566-2189
81 Glebe Point Rd              fax:   61-2-660-0850
GLEBE NSW 2037                 email: maxtal@suphys.physics.oz.au
AUSTRALIA                      email: skaller@maxtal.com.au



[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]