Generic Containers & qsort

In a nutshell

qsort is the poster child for C-style generic programming: sort any array of any type, given a pointer to the array, element count, element size, and a comparator function pointer. The same pattern scales up to generic stacks, queues, and hash tables. Your container stores void *, asks the caller to provide element size and any comparison or hashing function, and uses memcpy/memset under the hood to move bytes around without ever looking at the type.

Why it matters

Every reusable C library with a data structure uses this pattern. The GNU C library’s tsearch, bsearch, and qsort all look this way. Writing a small generic container yourself once is the exercise that turns “I know pointers and function pointers” into “I can build the kind of code other people depend on.”

Key takeaways

• qsort(base, nmemb, size, compar) sorts any array. base is the first element, nmemb is the count, size is element size, compar returns <0, 0, or >0 like strcmp.
• A generic-container API has four inputs: opaque element pointer, element size, comparator (if sorting), and sometimes a “free” callback for when the container owns its contents.
• void * plus size_t is the minimum information a container needs to move elements around.
• Ownership matters. If your container stores pointers, who owns the pointed-to memory? The container or the caller? Document it at the API.
• Opaque types. Expose typedef struct Stack Stack; in the header (forward declaration) and keep the full struct Stack { ... } definition in the .c file. Callers cannot reach into the struct’s fields; they can only use the library’s functions.

Lessons in this topic

Practice and deep dives

Practice this topic: Generic Containers drill, or browse the practice gallery.

What comes next

Week 8 moves to Linked Lists — the first data structure whose nodes live on the heap and connect to each other through pointers. Every dynamic data structure (lists, trees, hash tables) builds from here.