Using template to generate a static lookup table

Question

I have:

const char kLetters[] = "QWERTYUIOPASDFGHJKLZXCVBNM";

I can call kLetters[n] to obtain the nth letter of the Keyboard alphabet in O(1) time. However I will have to iterate through kLetter (taking O(n) or at least O(log n) ) time for the reverse lookup.

I would like to create a reverse lookup table as a compile-time static lookup table using templates and was wondering if there is a ways of doing this.

EDIT - as mentioned in the comments, a reverse lookup would mean I supply 'E' and get back 2. Also my alphabet example was not the best example, I would like to make no assumptions about the order. For that reason I have change the alphabet to keyboard order.

Answer 1

How about something like this? It lets you specify the range rather than a complete string.

#include <iostream>

template <int Start, int End, int N>
struct lookup {
        static_assert(Start != End, "Can't have 0 length lookup table");
        enum { value =  lookup<Start+(Start < End ? 1:-1),End,N-1>::value };
};

template <int Start, int End>
struct lookup<Start,End,0> {
        enum { value = Start };
};

template <int Start, int End, int V, int P=0>
struct reverse_lookup {
        static_assert(Start != End, "V isn't in the range Start, End");
        static_assert(Start != End || !P, "Can't have 0 length range");
        enum { value = reverse_lookup<Start+(Start < End ? 1:-1),End,V,P+1>::value };
};

template <int Start, int End, int P>
struct reverse_lookup<Start,End,Start,P> {
        enum { value = P };
};

int main() {
   std::cout << char(lookup<'A', 'Z', 3>::value) << std::endl;
   std::cout << char(lookup<'Z', 'A', 3>::value) << std::endl;
   std::cout << int(reverse_lookup<'A','Z','F'>::value) << std::endl;
}

Answer 2

Alright, after knowing what reverse lookup is, I think you can do this:

const char kLetters[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int get_index(char letter)
{
     return letter - 'A';
}

After all, the letter A is at index 0, B at 1, C at 2... and so on. That gives enough hint.

---

My O(1) solution

.

So far other solutions work for non-arbitrary sequence of letters, and @awoodland solution assumes that the letter whose index is to be obtainted is known at compile time which makes it less useful.

But this solution has attempted to solve both limitations; that is, it should work:

• With arbitrary sequence of letters, such as

     const char Letters[] = "ZBADCEWFVGHIUXJTKSLYQMROPN";
  

• And the letters may be unknown at compile time. The function that gets the index has this signature:

  int Index(char letter);
  

Here is the complete code which uses a technique described by @ David Rodríguez in his blog:

#include <iostream>

const char Letters[] = "ZBADCEWFVGHIUXJTKSLYQMROPN";

template<char L> int Index();

template<> int Index<'Z'>() { return 0; }
template<> int Index<'B'>() { return 1; }
template<> int Index<'A'>() { return 2; }
template<> int Index<'D'>() { return 3; }
template<> int Index<'C'>() { return 4; }
template<> int Index<'E'>() { return 5; }
template<> int Index<'W'>() { return 6; }
template<> int Index<'F'>() { return 7; }
template<> int Index<'V'>() { return 8; }
template<> int Index<'G'>() { return 9; }
template<> int Index<'H'>() { return 10; }
template<> int Index<'I'>() { return 11; }
template<> int Index<'U'>() { return 12; }
template<> int Index<'X'>() { return 13; }
template<> int Index<'J'>() { return 14; }
template<> int Index<'T'>() { return 15; }
template<> int Index<'K'>() { return 16; }
template<> int Index<'S'>() { return 17; }
template<> int Index<'L'>() { return 18; }
template<> int Index<'Y'>() { return 19; }
template<> int Index<'Q'>() { return 20; }
template<> int Index<'M'>() { return 21; }
template<> int Index<'R'>() { return 22; }
template<> int Index<'O'>() { return 23; }
template<> int Index<'P'>() { return 24; }
template<> int Index<'N'>() { return 25; }

typedef int (*fptr)();
const int limit = 26;
fptr indexLookup[ limit ];

template <char L>
struct init_indexLookup {
    static void init( fptr *indexLookup ) {
        indexLookup[ L - 'A' ] = &Index<L>;
        init_indexLookup<L-1>::init( indexLookup );
    }
};

template <>
struct init_indexLookup<'A'> {
    static void init( fptr *indexLookup ) {
        indexLookup[ 0 ] = &Index<'A'>;
    }
};

const int ignore = (init_indexLookup<'Z'>::init(indexLookup),0);

int Index(char letter)
{
    return indexLookup[letter-'A']();
}

And here is the test code:

int main()
{
    std::cout << Index('A') << std::endl;
    std::cout << Index('Z') << std::endl;
    std::cout << Index('B') << std::endl;
    std::cout << Index('K') << std::endl;
}

Output:

2
0
1
16

Online demo : http://ideone.com/uzE2t

Well, that actually is two function calls: one to Index(), other to from one in the indexLookup. You can easily avoid first function call by writing (ideone):

int main()
{
    std::cout << indexLookup['A'-'A']() << std::endl;
    std::cout << indexLookup['Z'-'A']() << std::endl;
    std::cout << indexLookup['B'-'A']() << std::endl;
    std::cout << indexLookup['K'-'A']() << std::endl;
}

That looks cumbersome, but hey, we can make Index() inline:

inline int Index(char letter)
{
    return indexLookup[letter-'A']();
}

That looks fine, and most likely now compiler will make it equivalent to one function call!

---

Simple yet O(1) solution

Wait. I just realized that the whole solution reduces to a lookup table which is initialized as:

 const int indexLookup[] = {2,1,4,3,5,7,9,10,11,14,16,18,21,
                            25,23,24,20,22,17,15,12,8,6,13,19,0};

 inline int Index(char letter)
 {
       return indexLookup[letter-'A'];
 }

which looks unbelievably simple!