Sorting records using sort()

[Elijah Bailey]

I want to sort a set of records using STL's sort() function,
but dont see an easy way to do it.

I have a

char *data;
which has size mn bytes where m is size of the record and
n is the number of records. Both these numbers are known
only dynamically. I have a function less_than that can compare
two records of size m given the pointers to the two records.

Is there an easy way to call STL sort() on this data and sort it.
The data is big and I do NOT want to allocate a list of pointers
of size n or anything linear in size. Assume that except the data,
we do not have much space...

I thought of tricking sort() using a dummy Record class that is
templated using the size of the record...But since m can change
dynamically this doesnt work.
Thanks in advance for your comments,
--Elijah

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[Peter Koch Larsen]

"Elijah Bailey" <ge******@hotma il.com> skrev i en meddelelse
news:e0******** *************** ***@posting.goo gle.com...

I want to sort a set of records using STL's sort() function,
but dont see an easy way to do it.

I have a

char *data;
which has size mn bytes where m is size of the record and
n is the number of records. Both these numbers are known
only dynamically. I have a function less_than that can compare
two records of size m given the pointers to the two records.

Is there an easy way to call STL sort() on this data and sort it.
The data is big and I do NOT want to allocate a list of pointers
of size n or anything linear in size. Assume that except the data,
we do not have much space...

I thought of tricking sort() using a dummy Record class that is
templated using the size of the record...But since m can change
dynamically this doesnt work.
Thanks in advance for your comments,
--Elijah

Make your own iterator class, which really should not be so difficult. Then
you can use all the C++ algorithms on your container, including std::sort.

Kind regards
Peter

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[Bo Persson]

"Elijah Bailey" <ge******@hotma il.com> skrev i meddelandet
news:e0******** *************** ***@posting.goo gle.com...

I want to sort a set of records using STL's sort() function,
but dont see an easy way to do it.

I have a

char *data;
which has size mn bytes where m is size of the record and
n is the number of records. Both these numbers are known
only dynamically. I have a function less_than that can compare
two records of size m given the pointers to the two records.

Is there an easy way to call STL sort() on this data and sort it.
The data is big and I do NOT want to allocate a list of pointers
of size n or anything linear in size. Assume that except the data,
we do not have much space...

Well, if the data is BIG, the standard method IS of course to sort an array
of pointers...

It will be MUCH faster than actually moving all the data around!

Bo Persson

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[Ron Natalie]

"Elijah Bailey" <ge******@hotma il.com> wrote in message news:e0******** *************** ***@posting.goo gle.com...

Is there an easy way to call STL sort() on this data and sort it.
The data is big and I do NOT want to allocate a list of pointers
of size n or anything linear in size. Assume that except the data,
we do not have much space...

You're confusing me. How is it this data is stored if you don't have
pointers to it. Are you telling me it's all in contiguous memory and you
want it sorted in place without using any additional storage? The standard
C routine qsort will do this.

qsort(ptr_to_be ginning, m, n, compare_func);

The compare func has to return positive if a > b, 0 if a==b and negative if a<b.
(It takes two void*'s as args).
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[Jeff Schwab]

Elijah Bailey wrote:

I want to sort a set of records using STL's sort() function,
but dont see an easy way to do it.

I have a

char *data;
which has size mn bytes where m is size of the record and
n is the number of records. Both these numbers are known
only dynamically. I have a function less_than that can compare
two records of size m given the pointers to the two records.

Is there an easy way to call STL sort() on this data and sort it.
The data is big and I do NOT want to allocate a list of pointers
of size n or anything linear in size. Assume that except the data,
we do not have much space...

I thought of tricking sort() using a dummy Record class that is
templated using the size of the record...But since m can change
dynamically this doesnt work.

Do all records in "data" have the same size m, or do different records
have different values of m?
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[John Potter]

On 31 Dec 2003 11:07:38 -0500, "Peter Koch Larsen" <pk*@mailme.d k>
wrote:

"Elijah Bailey" <ge******@hotma il.com> skrev i en meddelelse
news:e0******** *************** ***@posting.goo gle.com...

I thought of tricking sort() using a dummy Record class that is
templated using the size of the record...But since m can change
dynamically this doesnt work.

Make your own iterator class, which really should not be so difficult. Then
you can use all the C++ algorithms on your container, including std::sort.

Note his thoughts. Now tell us what the value type of that iterator
will be. Sort will likely want to create a temporary of that type.

John

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[Elijah Bailey]

Is there no easy way to solve this problem??
I dont want to use qsort from C...! I cant figure
out how to even write a random access iterator
for this problem. What will be its value type?

I would like to swap the records to sort them,
not copy keys and sort them separately...

Thanks in advance for your help,

Thanks ,
--Elijah

ge******@hotmai l.com (Elijah Bailey) wrote in message news:<e0******* *************** ****@posting.go ogle.com>...

I want to sort a set of records using STL's sort() function,
but dont see an easy way to do it.

I have a

char *data;
which has size mn bytes where m is size of the record and
n is the number of records. Both these numbers are known
only dynamically. I have a function less_than that can compare
two records of size m given the pointers to the two records.

Is there an easy way to call STL sort() on this data and sort it.
The data is big and I do NOT want to allocate a list of pointers
of size n or anything linear in size. Assume that except the data,
we do not have much space...

I thought of tricking sort() using a dummy Record class that is
templated using the size of the record...But since m can change
dynamically this doesnt work.
Thanks in advance for your comments,
--Elijah

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.m oderated. First time posters: Do this! ]

[Ron Natalie]

"Elijah Bailey" <ge******@hotma il.com> wrote in message news:e0******** *************** ***@posting.goo gle.com...

Is there no easy way to solve this problem??
I dont want to use qsort from C...

Why not? The std::sort isn't guaranteed to work any better.

[Jeff Schwab]

Elijah Bailey wrote:

I want to sort a set of records using STL's sort() function,
but dont see an easy way to do it.

I have a

char *data;

which has size mn bytes where m is size of the record and
n is the number of records. Both these numbers are known
only dynamically. I have a function less_than that can compare
two records of size m given the pointers to the two records.

Is there an easy way to call STL sort() on this data and sort it.
The data is big and I do NOT want to allocate a list of pointers
of size n or anything linear in size. Assume that except the data,
we do not have much space...

I thought of tricking sort() using a dummy Record class that is
templated using the size of the record...But since m can change
dynamically this doesnt work. I dont want to use qsort from C...! I cant figure
out how to even write a random access iterator
for this problem. What will be its value type?

I would like to swap the records to sort them,
not copy keys and sort them separately...

If you want to use an existing implementation of a sorting algorithm,
you have to provide a way for the implementation to know where records
begin and end, and how to compare them. This issue is fundamental.

Writing your own iterators would not be trivial, but probably would be a
educational. Having such iterators available would make your data
structure compatible with most of the standard library, and might avoid
countless future headaches.

If you just want to sort your records in place, why not use qsort? It's
part of the C++ standard library. The fact that the function was
inherited from C is no reason to avoid qsort. In fact, it sounds like
almost the perfect fit to your problem.

-Jeff

[Ron Natalie]

"Jeff Schwab" <je******@comca st.net> wrote in message news:Wo******** ************@co mcast.com...

Writing your own iterators would not be trivial, but probably would be a
educational. Having such iterators available would make your data
structure compatible with most of the standard library, and might avoid
countless future headaches.

The trouble with writing iterators for this problem is that he needs it to be
variable size at run time and that the iterators have to be derferenceable
and the derefenced types assignable. Add his requirement to not allocate
even enough memory to hold pointers to each object, I can't figure out how
you could do it.