How to create a sortable collection of string-integer pairs in C?

Question

I am trying to create a sortable collection of objects in C. Each object consists of a unique string and a possibly non-unique integer, kind of like a dictionary or hash. The trick, however, is I need to be able to sort the collection by the integer portion. For example, if the collection looks like so:

a =
    {
    {"string 1", 10},
    {"another string", 4},
    {"yet another string", 74}
    }

sorting a in ascending order results in:

    {
    {"another string", 4},
    {"string 1", 10},
    {"yet another string", 74}
    }

or if sorting in descending order results in:

    {
    {"yet another string", 74},
    {"string 1", 10},
    {"another string", 4}
    }

The idea is, once sorted, I can say get_the_first_sorted_item(a) or something like it, followed by get_the_next_sorted_item(a) or something like it until reaching the end of the collection.

While I thought Judy arrays would be helpful, I now see they have their own sorting scheme based on the 'key' and not the 'value'.

Can Anyone point Me in the direction of where to find such a solution?

Answer 1

I might store the elements in a hash table, so that you still have name lookup, and also construct a priority queue containing pointers to the hashed elements, so you have fast get-next lookup.

Answer 2

qsort is defined by ISO C, takes a comparison function to allow for sorting of structs, and should work well for your purpose;

// The type of the entries.
typedef struct { const char* str; int num; } A;

// A comparison function
int compar(const void* a, const void* b)
{
    return ((A*)a)->num - ((A*)b)->num;
}

...

A a[] = {
  { "string 1", 10 },
  { "another string", 4},
  { "yet another string", 74}
};

// Sort the entries
qsort(a, sizeof(a)/sizeof(A), sizeof(A), compar);