0

In C, can you create a dictionary? I come from a Objective-C background so I would like to know if there is anything similar to NSDictionary.

Ry-
  • 218,210
  • 55
  • 464
  • 476
John Wheal
  • 9,908
  • 6
  • 29
  • 39
  • 1
    See http://stackoverflow.com/questions/6118539/hashtable-as-part-of-standard-c-library – Avi Feb 23 '12 at 00:18

4 Answers4

7

You can create anything you want in C. You just won't have native language support for most of it.

Ry-
  • 218,210
  • 55
  • 464
  • 476
Oliver Charlesworth
  • 267,707
  • 33
  • 569
  • 680
2

You can create a dictionary in C, but there is no dictionary built in to the standard C library.

A quick search on Google code shows that there are open-source (and generously licensed) C dictionary implementations here and here.

Adam Mihalcin
  • 14,242
  • 4
  • 36
  • 52
1

Posix does have a limited hash table -- see hcreate(), hsearch() and hdestroy() that can be used by a C program.

A discussion of the limitations appears in this stackoverflow question.

Community
  • 1
  • 1
Jay Elston
  • 1,978
  • 1
  • 19
  • 38
  • 1
    The GNU library adds `hcreate_r()`, `hsearch_r()`, and `hdestroy_r()`, which allow more than one hash table in a program. – Alex Measday Feb 23 '12 at 04:49
0

Without OOP and templates, it would be hard to implement a hash table or a balanced tree that is truly general, easy to use and performant, and therefore worthy to be in the run-time library that comes with the language.

That being said, you can always implement your own, or just use C++ (see unordered_map or map).

Branko Dimitrijevic
  • 50,809
  • 10
  • 93
  • 167
  • `Performant` is not really a word, although it will become one because people keep using it. I assume you mean it in the sense that the data structure/functions must be efficient. Why do you think C implementations of hash tables and balanced trees would be any less efficient than OOP C++ implementations? – Alex Measday Feb 23 '12 at 04:58
  • (Didn't get to finish my comment - got the dreaded "only edit every 5 seconds" message!) I wrote a general-purpose hash table package in C that was easy-to-use and fast - a table of 80,000 telemetry points had a mean number of comparisons slightly over 1, points within 1 standard deviation were still under 2 comparisons, and points within 2 standard deviations were slightly over 2 comparisons. – Alex Measday Feb 23 '12 at 05:15
  • 1
    @ranko: Huh? You build a tree/hash that stores void pointers and accepts a comparison function with a prototype of int cmp(void *, void *); and returns -1/0/1. This has been done for years, is easy to use, and creates a general-purpose tree/hash in C (e.g., see the standard C library bsearch API). – tbert Feb 23 '12 at 05:42
  • @AlexMeasday I said "general, easy to use and performant", not just performant. One can certainly hand-code a performant implementation specific to a particular element type and hash and equality functions, but to do it so it works for **any** type and hash/equality functions, you'd need data and function pointers, compromising the ease of use and probably performance. You could possibly use macros, but this no longer qualifies as "C" and has its own problems. I can't judge your implementation, but it would be interesting to benchmark it against C++ `unordered_set`... – Branko Dimitrijevic Feb 23 '12 at 06:00
  • @tbert And you have thrown the type safety out of the window. And what is not "safe" also tends not to be "easy" when you start chasing bugs in a real piece of software. Also, this can represent a sub-optimal memory layout (because elements are not really "embedded" into the hashtable) and possibly decreased opportunities for inlining. – Branko Dimitrijevic Feb 23 '12 at 06:09
  • 1
    @BrankoDimitrijevic C is not a type-safe language. And I've chased (and solved!) these bugs in software myself. Helper functions exist for just this purpose (i.e., make sure that your calls to the tree/whatevah are correct by abstracting it into a get/set interface). – tbert Feb 23 '12 at 07:27
  • @tbert If you need helper functions the solution is no longer general. And adding more layers of functions may interfere with inlining. There is a reason why nobody in C++ uses `qsort` anymore - C++ is rich enough to have a solution in the standard library that fulfills **all** 3 conditions mentioned above. I'm simply saying C is not rich enough for a _standard_ solution, but I'm not saying it isn't rich enough for _any_ solution. – Branko Dimitrijevic Feb 23 '12 at 13:24