qsorting & managing struct arrays, pointer arrays 
Author Message
 qsorting & managing struct arrays, pointer arrays

Suppose you have:

   typedef struct struct_name {...} struct_name;
   struct_name list[MAXSIZE], *s_start, *s_one, *s_two;

   main()
   {
      /*load the array of struct here*/
      s_start = list;
      /*other business*/
      qsort( s_start, s_members, sizeof( struct_name ), ncmp );
   }

   int ncmp( struct_name * s_one, struct_name * s_two )
   {
      return strcmp( s_one->elem, s_two->elem );
   }

This arrangement works well (less than 1000 members), but it may
be a poor design.  If we display the structure members, have to
move forward and backward among them interactively, *and may re-
move members*, then there are two nagging problems.

   1) qsort won't know that you'd like to discard members tagged
   as deleted (ncmp could always make such members greater than
   the comparison member).

   2) Going forward (backward) by, say, 20 members isn't as easy
   some pointer arithmetic, as you could land on (a) deleted
   member(s).  You'd have to walk forward (backward) until 20
   valid members had been counted.  That seems like a lot of over-
   head in an interactive environment.

Adding a field to the structure pointing to the next valid member
doesn't seem to obviate the need to deal with these two problems.

Another approach is to instead maintain an array of pointers to
struct_name.  Assuming the members are sorted, then with each
deletion you could move forward all the following elements of the
array of pointers, filling in the gap created by the deletion;
you'd also decrement a variable counting the number of valid
members.  To move forward (backware) by 20 members only requires
bumping the index into the array of pointers by that much.

First, the concrete question:

   Can the standard qsort accept not the array of structures, but
   the array of pointers to structure members?  If yes, how then
   can the declaration of ncmp (the compare function) be changed
   to accept two elements ([i], [j]) from the array of pointers,
   since the call (and i, j) is buried in the library?  If no,
   then I'll have to make my own qsort -- less desirable, since it
   makes more sense to take advantage of the library authors'
   presumed expertise at writing fast sort routines.

Second, a more global question:

   If there are fewer than 1000 members in the struct, am I mis-
   taken to believe there would be less overhead in closing the
   gap in the array of pointers with each deletion, then there
   would be in counting off valid members with *each movement* in
   the array of struct, especially considering the need to
   occasionally resort?  Alternatively, are there approaches to
   managing a list on screen than I've not thought of and that
   have greater merit than either of the ones above?

Unless this seems of general interest, please e-mail.  Thank you
much.

--


Department of Sociology, Indiana University, Bloomington, Indiana 47405



Fri, 19 Mar 1993 19:44:00 GMT  
 qsorting & managing struct arrays, pointer arrays

Quote:

>   Can the standard qsort accept not the array of structures, but
>   the array of pointers to structure members?

qsort() doesn't know what the array it is sorting consists of;
it leaves that up to the comparison function.  Thus, a standard
trick is to have qsort() sort an array of pointers to records
rather than an array of records.  The rest is merely a matter
of getting the type declarations right; this amounts to adding
an extra * to the parameters in the comparison function.  Note
that the comparison function is fed "generic" pointers (void* or
char*), and you ought to cast them into record_type**s before
using them in the comparison function.


Fri, 19 Mar 1993 21:58:00 GMT  
 qsorting & managing struct arrays, pointer arrays

Quote:

>    Can the standard qsort accept not the array of structures, but
>    the array of pointers to structure members?  If yes, how then
>    can the declaration of ncmp (the compare function) be changed
>    to accept two elements ([i], [j]) from the array of pointers,

Your example would be changed to something like:

    typedef struct struct_name {...} struct_name;
    struct_name *list[MAXSIZE], **s_start, *s_one, *s_two;
                ^               ^

    main()
    {
       /*allocate and load the array of struct here*/
         ^^^^^^^^^^^^
       s_start = list;
       /*other business*/
       qsort( s_start, s_members, sizeof( struct_name *), ncmp );
                                                      ^
    }

    int ncmp( struct_name ** s_one, struct_name ** s_two )
                           ^                     ^
    {
       return strcmp( (*s_one)->elem, (*s_two)->elem );
                      ^^^^^^^^        ^^^^^^^^
    }

NOTE: I have not compiled the above, but you should get the idea.

--
+-----------------------------------------------------------------------+
| Conor P. Cahill     uunet!virtech!cpcahil             703-430-9247    !
| Virtual Technologies Inc.,    P. O. Box 876,   Sterling, VA 22170     |
+-----------------------------------------------------------------------+



Fri, 19 Mar 1993 23:33:00 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. Managed array of managed arrays of char

2. array of pointers to array of structs

3. struct.array works - struct->pointer not

4. Array of pointers, pointer to array...

5. array pointer/pointer array

6. arrays pointers array of pointers

7. pointer to managed array

8. Managed arrays and pointer arithmetic

9. arrays / pointers in managed classes

10. How to manage array of __gc pointers

11. Referencing an array of structs in an array of stracts

12. problem realloc array inside array of struct

 

 
Powered by phpBB® Forum Software