ANSI C: Array with string-value pairs

Discussion in 'Mac Programming' started by moonman239, Dec 15, 2015.

  1. moonman239 macrumors 68000

    Joined:
    Mar 27, 2009
    #1
    In C, objects in an array are numbered. Therefore, I can get or set the value of array "a" at 50 using the following statement:

    Code:
    a[50]
    
    But is it possible to use strings instead of numbers? Let's say, for example, that I have an array of char arrays, and I want to create another array whose values correspond to any of the char arrays. Can I do that without finding any indexes?
     
  2. firewood macrumors 604

    Joined:
    Jul 29, 2003
    Location:
    Silicon Valley
    #2
    Anything is possible in a Turing-complete language. But dictionaries or string key-value data structures are not built-into the set of standard C operators or common libraries.

    If you want dictionaries, you will have to add your own functions for dictionary creation and lookup, perhaps using hash tables or hashmaps.
     
  3. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #3
    The most rudimentary and slow way to do this is to use coarrays. Possibly both arrays would be in a single struct to keep them together, and possibly ease use.

    One array would be of type char *, with each entry being a null-terminated C "string". The other array would be whichever type you'd like to "map" to. It would be the same length as the char * array.

    A lookup would be two steps. The first would be a linear search for a string match. If found, the same index is used to retrieve the value from the second array.

    This will be abysmally slow. To improve it, there are plenty of choices. One is to make a struct with a key and value element, and keep an array of those, and sort it by key. Once you have this, you perform a binary search, which will be much quicker than a linear search. Adding elements later will be very slow unless you get awfully clever and keep your backing array sparse and use a clever scheme to avoid the unused spots during your search.

    Next is using a hashing scheme to allow faster lookups. The details aren't fit for a quick summary here, but it comes down to performing an operation on the keys to more quickly determine its position in the backing array. This is the technique used in NSDictionary, Java's HashMap, etc.

    What C provides you with is the basic building blocks. Every language that provides you with data structures built-in or in a standard library have had these created by others from similar building blocks.

    -Lee
     
  4. ArtOfWarfare macrumors 604

    ArtOfWarfare

    Joined:
    Nov 26, 2007
    #4

Share This Page