Where developers come to connect, share, build and be inspired.


Associative/sparse arrays in pure C? Give it a trie!



http://www.nedprod.com/programs/portable/nedtries/ https://github.com/ned14/nedtries/blob/master/test.c

While we usually take associative array/dictionary/hash data structure as granted in modern programming languages, there is no such thing builtin in a good old C. It might be tempting to use SQLite or even Berkeley DB to fullfil that urge in many project, but the extra dependency handling is a PITA. Plus, there are many tasks that do not require ACID neither persistent storage. Even a red-black tree could be an overkill sometimes. Then, there is a bitwise trie. One particular implementation, nedtries, caught my attention:

  1. It is distributed as a single header file (nedtrie.h);
  2. It is really fast;
  3. It is really tiny;
  4. It requires no dynamic memory allocation;
  5. It is both C/C++ compatible.

Add a comment