Reputation: 471

In C, How can I use an array of strings as a lookup table?

I'm so stuck. I'm learning C and have this question:

How can I use an array of strings as a lookup table?

I have a list of 'keys:

"A", "A#", "B", "Bb", "C", "C#", "D", "D#", "E", "F", "F#", "G", "G#"

And each will refer to a specific int 'value' (which isn't unique). e.g. "A" -> 9, "A#" -> 10, "Bb" -> 10

I found an answer (store known key/value pairs in c) that I think is pointing me in the right direction when it says "I would...recommend just using an array of strings as a lookup table"

BUT I don't know how to actually implement an array of strings as a lookup table?

Upvotes: 3

Answers (4)

Gene

Reputation: 46960

Since you intend to use the strings as keys with integer values, it's best to use a struct to contain such a pair. Then build a table of them. Finally, since you've been careful to keep the keys in sorted order, you can use the C library function bsearch for lookups:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct pair {
  char *key;
  int value;
} PAIR;

// Key strings must be in strcmp() sorted order!
PAIR table[] = {
  {"A",  9}, {"A#", 10}, {"B",  11}, {"Bb", 10}, {"C", 11}, {"C#", 12}, {"D", 13},
  {"D#", 14}, {"E", 15}, {"F", 16}, {"F#", 17}, {"G", 18}, {"G#", 19},
};

static int compare_keys(const void *va, const void *vb) {
  const PAIR *a = va, *b = vb;
  return strcmp(a->key, b->key);
}

int get_value(char *key) {
  PAIR key_pair[1] = {{key}};
  PAIR *pair = bsearch(key_pair, table,
      sizeof table / sizeof table[0], sizeof table[0], compare_keys);
  return pair ? pair->value : -1;
}

int main(void) {
  // Partial test: verify we can look up all the valid keys.
  for (int i = 0; i < sizeof table / sizeof table[0]; ++i) {
    int value = get_value(table[i].key);
    printf("%s -> %d\n", table[i].key, value);
  }
  return 0;
}

Upvotes: 6

sg7

Reputation: 6298

I'm learning C [...] how to actually implement an array of strings as a lookup table?

Two solutions are presented.

First solution is fulfilling OP's criteria (simple for the C beginner and has indexed lookup table). The solution comes from the analyses of the domain: the nature of the keys. After proper arrangement of the keys in the str_key table, the process of the deriving corresponding index to the lookup table is very simple. No intensive computation is needed. No strcmp or other search function is used.

I truly believe that this is the shortest, simplest and the fastest solution for the presented problem.

#include <stdio.h> 
// int index   =  { 0,  1,  2,  3,  4,  5,  6,   7,  8,   9,   10,  11,  12, 13,  14  };
int value[]    =  { 9, 10, 11, 13, 17, 19,  7,  10, 10,  12,   15,  -1,  20,  8,   0  }; 

char *str_key[] = {"A","B","C","D","E","F","G","A#","Bb","C#","D#","Eb","F#","G#",NULL};

int get_value(char *key, int v[])      // magic happens here!
{
    // From string key we build corresponding index to the `value` array
                                      // Note: index for key "A" == 0  
    int index = (int) (key[0] - 'A'); // One letter key will have index from 0 to 6

    if( key[1] !=0 )                  // two letter key have his index from 7 to 13   
    {
        index = index + 7;            // index for "A#" == 7
    }

    if( (index < 0) || (index > 13) ) // protection from bad keys
        return -1;  

    return v[index];                  // return the value
}

int main(void)
{
    for (int i = 0; str_key[i] != NULL; i++) {

        int v = get_value( str_key[i], value);

        printf("%2s -> %2d\n", str_key[i], v);
    }
    return 0;
}

Test:

Second simple solution:

Second solution does not use lookup table but is also easy to implement, flexible and easy to understand.

It is based on the fact that

set of keys is small
keys are maximum 2 characters long.

The solution is very fast. It avoids strcmp or any other searching function. The particular key is build from the string in very simple fashion.

The solution is based on multi-character constant.

From Wikipedia

Multi-character constants (e.g. 'xy') are valid, although rarely used — they let one store several characters in an integer (e.g. 4 ASCII characters can fit in a 32-bit integer, 8 in a 64-bit one).

6.4.4.4 Character constants: An integer character constant is a sequence of one or more multibyte characters enclosed in single-quotes, as in 'x'.

The code should compile without warning under gcc with-Wall, and a “multi-character character constant” warning with -pedantic. You can disable the warning with -Wno-multichar.

#include <stdio.h>

char *str_key[] = {"A","B","C","D","E","F","G","A#","Bb","C#","D#","Eb","F#","G#",NULL};

int build_index (char *key)
{
 // The magic happens here:
 // We take the string eg. "A#" 
 // and we construct corresponding multi-character constant 'A#'
 //                 A                  # 
    int index;

    if( key[1] == 0 )
        index = (int) key[0]; 
    else
        index = (int) ( (key[0] << 8) | key[1] );

    return index;   
}

int get_value (int key)
{
  switch (key)
    {
    case 'A':   return 9;
    case 'A#':  return 10;
    case 'B':   return 10;
    case 'Bb':  return 10;
    case 'C':   return 11;
    case 'C#':  return 12;
    case 'D':   return 13;
    case 'D#':  return 15;
    case 'E':   return 17;        
    case 'F':   return 19;
    case 'F#':  return 20;
    case 'G':   return 7;          
    case 'G#':  return 8;      
    deafult:
      break;
    }
  return -1;
}

int main (void)
{
    for (int i = 0; str_key[i] != NULL; i++) {

        int v = get_value( build_index( str_key[i] ) );

        printf("%2s -> %2d\n", str_key[i], v);
    }
    return 0;
}

Test:

Look over the solutions and let me know if you have further questions. Thanks!

Upvotes: 0

David C. Rankin

Reputation: 84561

There is a lot of learning you can pack into this exercise. An optimal solution, short of a hash table, would be to use a stuct to form the pairs as Gene has shown in his answer. Any time you need to coordinate unrelated values of differing types, you should think struct.

However, based on your question, it is unclear whether you are able to use a struct for your solution. If not, then a beginning way to associate values of differing types would be the simple use of two arrays where the key/value association is provided by array index.

As mentioned in my comment to your question, you can easily map your keys into an array of pointers, e.g.:

    char *arr[] = { "A", "A#", "B", "Bb", "C", "C#", "D", /* array of pointers */
                    "D#", "E", "F", "F#", "G", "G#" };

You can then hold your values in a separate integer array with the same number of elements where the index for key "A" (e.g. 0) corresponds to its associated value in your values array (e.g. values[0] = 10;). That provides a simple mapping of "A" to 10.

Then given your array of pointers and a 'key' you can then loop over your array attempting to match key against each string. When a match is found at index, your associated key is values[index];.

Putting that together in a simple function that loops over each of 'n' strings in your array of pointers (s below) to locate the provided key and returns the index on success, or -1 if key-not-found, you could do something like the following:

/* locate index in 's' associated with 'key'.
 * for 'n' keys in 's' return 'index' of matching 'key',
 * otherwise return -1 if key not found.
 */ 
int getvalue (char **s, char *key, int n)
{
    for (int i = 0; i < n; i++) {           /* loop over all keys */
        int found = 1;                      /* flag for key found */
        for (int j = 0; key[j]; j++) {      /* loop over all chars in key */
            if (key[j] != s[i][j]) {        /* if key doesn't match s[i] */
                found = 0;                  /* set not found, break */
                break;
            }
        }
        if (found)          /* if all chars in key match s[i] */
            return i;       /* return index of matching key */
    }
    return -1;
}

(note: you can replace the inner-loop with strcmp, but without knowing whether you have the functions in sting.h available, a simple looping over the characters in key works every time. However, if you do have string.h available, then strcmp would be much better than rolling your own. You could even use strncmp (key, s[i], KEYSIZE) to limit the comparison in a large buffer to just the characters of interest)

Putting all the pieces together in a short example that simply randomly assigns values to each of the keys in the range of the number of 0 -> No. keys - 1, and takes input having the user enter a key to get the associated value until "quit" is entered or the user cancels input with a manually generated EOF (e.g. Ctrl+d on Linux or Ctrl+z on windoze - if legacy mode enabled), you could do something like the following:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

enum { KEYSZ = 2, BUFSZ = 256 };    /* if you need a constant, define it */

/* simply print of all mappings */
void prnmapping (char **s, int *a, int n)
{
    for (int i = 0; i < n; i++)
        printf ("  %-2s : %2d\n", s[i], a[i]);
}

/* locate index in 's' associated with 'key'.
 * for 'n' keys in 's' return 'index' of matching 'key',
 * otherwise return -1 if key not found.
 */ 
int getvalue (char **s, char *key, int n)
{
    for (int i = 0; i < n; i++) {           /* loop over all keys */
        int found = 1;                      /* flag for key found */
        for (int j = 0; key[j]; j++) {      /* loop over all chars in key */
            if (key[j] != s[i][j]) {        /* if key doesn't match s[i] */
                found = 0;                  /* set not found, break */
                break;
            }
        }
        if (found)          /* if all chars in key match s[i] */
            return i;       /* return index of matching key */
    }
    return -1;
}

int main (void) {

    char *arr[] = { "A", "A#", "B", "Bb", "C", "C#", "D", /*array of pointers*/
                    "D#", "E", "F", "F#", "G", "G#" };
    int nelem = sizeof arr / sizeof *arr,           /* number of elements */
        values[nelem];                              /* VLA for values */

    srand (time (NULL));                /* initialize random seed */

    for (int i = 0; i < nelem; i++)     /* initialize values array */
        values[i] = rand() % nelem;

    printf ("initial string mappings:\n");  /* just dump initial mappings */
    prnmapping (arr, values, nelem);
    putchar ('\n');

    for (;;) {  /* loop continually prompting for key input until 'quit' */
        char buf[BUFSZ] = "",       /* buffer for line */
            key[KEYSZ + 1] = "";    /* buffer for key (can just use buf) */
        int index = 0;              /* int to hold index matching key */
        size_t len = 0;             /* length of input string */
        printf ("enter key ('quit' to exit): ");    /* prompt */
        if (fgets (buf, BUFSZ, stdin) == NULL) {    /* catch manual EOF */
            printf ("user canceled input.\n");
            break;
        }
        if ((len = strlen (buf)) <= 1) {    /* continue if empty line */
            fprintf (stderr, "error: insufficient input.\n");
            continue;
        }
        if (buf[len - 1] == '\n')   /* check buf for trailing '\n' */
            buf[--len] = 0;         /* overwrite with nul-terminating char */
        else {  /* otherwise input equals or exceeds buffer length */
            fprintf (stderr, "error: input exceeds %d chars.\n", BUFSZ - 2);
            break;
        }
        if (strcmp (buf, "quit") == 0)  /* compare for 'quit' */
            break;
        strncpy (key, buf, KEYSZ);  /* copy KEYSZ chars from buf to key */
        key[len] = 0;  /* nul-terminate key (already done by initialization) */
        if ((index = getvalue (arr, key, nelem)) == -1) /* key not found */
            fprintf (stderr, "error: key not found.\n");
        else    /* success - key found, output associated value */
            printf ("  key: '%s'  -  value: %d\n", key, values[index]);
    }

    return 0;
}

(note: reasonable error handling is provided. Regardless of which manner you use to take user-input (though your are encouraged to use fgets or POSIX getline over scanf due to numerous pitfalls in scanf), you must validate all input. That means checking the return of whatever input function you use -- at a minimum, and handling the user canceling input by generating an EOF)

Example Use/Output

$ ./bin/array_map_values
initial string mappings:
  A  :  4
  A# :  4
  B  :  1
  Bb :  7
  C  :  1
  C# : 11
  D  :  8
  D# :  3
  E  :  4
  F  :  2
  F# :  6
  G  :  8
  G# : 10

enter key ('quit' to exit): A
  key: 'A'  -  value: 4
enter key ('quit' to exit): A#
  key: 'A#'  -  value: 4
enter key ('quit' to exit): D
  key: 'D'  -  value: 8
enter key ('quit' to exit): D#
  key: 'D#'  -  value: 3
enter key ('quit' to exit): G#
  key: 'G#'  -  value: 10
enter key ('quit' to exit): g@
error: key not found.
enter key ('quit' to exit): B
  key: 'B'  -  value: 1
enter key ('quit' to exit): quit

Look things over and let me know if you have further questions. As I said at the beginning, you can pack a lot of learning into this exercise.

Upvotes: 0

Daniel

Reputation: 1287

In the simplest way, you can just keep two parallel arrays of values to help map a string to an integer, like so:

const char *keys[13];
int keytoindex[13];

/* build table */
keys[0] = "A";
keys[1] = "A#";
/* etc. */

keytoindex[0] = 9; /* Value for 'A' */
keytoindex[1] = 10;
/* etc. */

/* later */
char *userInput = ...; /* somehow get input */
int keyvalue = -1; /* I assume -1 is not in the value array, so it can be an error condition that we didn't find that key when searching in the first array */
for( int i = 0; i < 13; i++ ) {
     if(strcmp(userInput,keys[i]) == 0 )) {
          keyvalue = keytoindex[i];
          break;
     }
}

if(keyvalue == -1) exit(1); /* send an error */
/* otherwise, keep going */

Naturally, this code can be re-written such that the parallel arrays are dynamically allocated, which would allow you to adjust their size during run-time. But the concept is the same.

Upvotes: 2

In C, How can I use an array of strings as a lookup table?

Answers (4)

Related Questions