使用模板生成静态查找表

Question

我有:

const char kLetters[] = "QWERTYUIOPASDFGHJKLZXCVBNM";

我可以打电话kLetters[n]在O(1)时间内获得键盘字母的第n个字母.但是,我将不得不遍历kLetter(取O(n)或至少O(log n))时间进行反向查找.

我想使用模板创建一个反向查找表作为编译时静态查找表,并想知道是否有这样做的方法.

编辑 - 如评论中所述,反向查找意味着我提供'E'并返回2.此外,我的字母表示例不是最好的例子,我不想对订单做任何假设.因此我将字母表更改为键盘顺序.

Answer 1

这样的事怎么样？它允许您指定范围而不是完整的字符串.

#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

好吧，在知道什么是反向查找之后，我想你可以这样做：

\n\n

const char kLetters[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";\n\nint get_index(char letter)\n{\n     return letter - \'A\';\n}\n

\n\n

毕竟，这封信A位于index 0、Bat 1、Cat 2...等等。这给出了足够的暗示。

\n\n\n\n

我的 O(1) 解决方案

。

\n\n

到目前为止，其他解决方案适用于非任意字母序列，并且 @awoodland 解决方案假设要获取索引的字母在编译时已知，这使得它不太有用。

\n\n

但该解决方案试图解决这两个限制；也就是说，它应该起作用：

\n\n

\n

• 具有任意字母序列，例如

  \n\n

     const char Letters[] = "ZBADCEWFVGHIUXJTKSLYQMROPN";\n

\n

• 并且这些字母在编译时可能是未知的。获取索引的函数具有以下签名：

  \n\n

  int Index(char letter);\n

\n

\n\n

这是完整的代码，使用了 @ David Rodr\xc3\xadguez 在他的博客中描述的技术：

\n\n

#include <iostream>\n\nconst char Letters[] = "ZBADCEWFVGHIUXJTKSLYQMROPN";\n\ntemplate<char L> int Index();\n\ntemplate<> int Index<\'Z\'>() { return 0; }\ntemplate<> int Index<\'B\'>() { return 1; }\ntemplate<> int Index<\'A\'>() { return 2; }\ntemplate<> int Index<\'D\'>() { return 3; }\ntemplate<> int Index<\'C\'>() { return 4; }\ntemplate<> int Index<\'E\'>() { return 5; }\ntemplate<> int Index<\'W\'>() { return 6; }\ntemplate<> int Index<\'F\'>() { return 7; }\ntemplate<> int Index<\'V\'>() { return 8; }\ntemplate<> int Index<\'G\'>() { return 9; }\ntemplate<> int Index<\'H\'>() { return 10; }\ntemplate<> int Index<\'I\'>() { return 11; }\ntemplate<> int Index<\'U\'>() { return 12; }\ntemplate<> int Index<\'X\'>() { return 13; }\ntemplate<> int Index<\'J\'>() { return 14; }\ntemplate<> int Index<\'T\'>() { return 15; }\ntemplate<> int Index<\'K\'>() { return 16; }\ntemplate<> int Index<\'S\'>() { return 17; }\ntemplate<> int Index<\'L\'>() { return 18; }\ntemplate<> int Index<\'Y\'>() { return 19; }\ntemplate<> int Index<\'Q\'>() { return 20; }\ntemplate<> int Index<\'M\'>() { return 21; }\ntemplate<> int Index<\'R\'>() { return 22; }\ntemplate<> int Index<\'O\'>() { return 23; }\ntemplate<> int Index<\'P\'>() { return 24; }\ntemplate<> int Index<\'N\'>() { return 25; }\n\ntypedef int (*fptr)();\nconst int limit = 26;\nfptr indexLookup[ limit ];\n\ntemplate <char L>\nstruct init_indexLookup {\n    static void init( fptr *indexLookup ) {\n        indexLookup[ L - \'A\' ] = &Index<L>;\n        init_indexLookup<L-1>::init( indexLookup );\n    }\n};\n\ntemplate <>\nstruct init_indexLookup<\'A\'> {\n    static void init( fptr *indexLookup ) {\n        indexLookup[ 0 ] = &Index<\'A\'>;\n    }\n};\n\nconst int ignore = (init_indexLookup<\'Z\'>::init(indexLookup),0);\n\nint Index(char letter)\n{\n    return indexLookup[letter-\'A\']();\n}\n

\n\n

这是测试代码：

\n\n

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

\n\n

输出：

\n\n

2\n0\n1\n16\n

\n\n

在线演示： http: //ideone.com/uzE2t

\n\n

嗯，这实际上是两个函数调用：一个是 to Index()，另一个是 from 中的一个indexLookup。您可以通过编写（ ideone ）轻松避免第一次函数调用：

\n\n

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

\n\n

这看起来很麻烦，但是嘿，我们可以Index()内联：

\n\n

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

\n\n

看起来不错，现在编译器很可能会将其等同于一个函数调用！

\n\n\n\n

简单但 O(1) 的解决方案

\n\n

等待。我刚刚意识到整个解决方案简化为一个查找表，其初始化为：

\n\n

 const int indexLookup[] = {2,1,4,3,5,7,9,10,11,14,16,18,21,\n                            25,23,24,20,22,17,15,12,8,6,13,19,0};\n\n inline int Index(char letter)\n {\n       return indexLookup[letter-\'A\'];\n }\n

\n\n

这看起来简单得令人难以置信！

\n