In article <rhtvg.272$5H.39@dukeread06>,
ol****@att.net says...
I have used the standard template library quite a bit, and std::sort has been
very useful. Now I have reached the point where my memory requirements are
exceeded. Is there some standard way to sort a binary file with a specifically
defined structure?
The only thing that I could think of would be to std::sort portions of this file
in memory, and then later manually merge these sorted portions together using a
home brewed merge sort . Does anyone have any better ideas?
Yup, that seems pretty much correct. A few points: first of all,
std::merge may simplify writing the merge portion of the sort. It'll
handle most of the details of an individual merge run, so from there
it's mostly a matter of deciding what merge pattern you want.
Traditionally, the polyphase merge was generally considered the best,
but I can't say I've done any recent testing to see how well it does
for hard-drive based sorting. My immediate reaction is that it'll
probably do quite well, but may not improve efficiency enough to be
worth the trouble.
To create your sorted runs, you're probably better off using a
priority_queue than reading data into something like a vector,
sorting it, and then writing it out. In particular, a priority_queue
will typically allow you to create longer runs in your initial sorted
files -- as you write out each record, you can read in another from
the original input. As long as it doesn't precede those that have
already been written out, you can add it to the priority queue, and
from there it'll end up in the same file. On average this can nearly
double the length of the initial runs, which generally helps quite a
bit.
--
Later,
Jerry.
The universe is a figment of its own imagination.
