Использование шаблона для генерации статической таблицы поиска - PullRequest
Новая
       1

Использование шаблона для генерации статической таблицы поиска

5 голосов
/ 14 сентября 2011

у меня есть: 

const char kLetters[] = "QWERTYUIOPASDFGHJKLZXCVBNM";

Я могу позвонить kLetters[n], чтобы получить n-ю букву алфавита клавиатуры за O (1) раз. Однако мне придется перебирать kLetter (принимая O (n) или, по крайней мере, O (log n)) для обратного поиска.

Я хотел бы создать таблицу обратного просмотра в виде статической таблицы поиска во время компиляции с использованием шаблонов, и мне было интересно, есть ли способы сделать это.

РЕДАКТИРОВАТЬ - как упоминалось в комментариях, обратный поиск означал бы, что я поставляю 'E' и получаю обратно 2. Также мой пример с алфавитом был не лучшим примером, я не хотел бы делать никаких предположений относительно порядка. По этой причине я изменил алфавит в порядке клавиатуры.

Ответы [ 6 ]

5 голосов
/ 14 сентября 2011

Как насчет этого? Позволяет указать диапазон, а не полную строку. 

#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;
}
3 голосов
/ 14 сентября 2011

Хорошо, узнав, что такое обратный поиск, я думаю, вы можете сделать это: 

const char kLetters[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

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

В конце концов, буква A находится в индексе 0, B в 1, C в 2 ... и так далее. Это дает достаточно подсказки.

My O (1) раствор

.

Пока что другие решения работают для непроизвольной последовательности букв, а решение @awoodland предполагает, что буква, индекс которой должен быть получен, известна во время компиляции , что делает ее менее полезен

Но это решение попыталось решить оба ограничения; то есть должно работать:

  • С произвольной последовательностью букв, такой как 

       const char Letters[] = "ZBADCEWFVGHIUXJTKSLYQMROPN";

  • И буквы могут быть неизвестно во время компиляции. Функция, которая получает индекс, имеет следующую подпись: 

    int Index(char letter);

Вот полный код, который использует технику, описанную @ David Rodríguez в его блоге : 

#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']();
}

А вот и код теста: 

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;
}

Выход: 

2
0
1
16

Онлайн демо: http://ideone.com/uzE2t

Ну, на самом деле это два вызова функций: один на Index(), другой на один в indexLookup. Вы можете легко избежать первого вызова функции, написав ( 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;
}

Это выглядит громоздко, но эй, мы можем сделать Index() inline: 

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

Это выглядит нормально, и, скорее всего, теперь компилятор сделает это эквивалентным одному вызову функции!

Простое, но O (1) решение

Подождите. Я только что понял, что все решение сводится к таблице поиска, которая инициализируется как: 

 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'];
 }

, что выглядит невероятно просто!

1 голос
/ 14 сентября 2011

Если вы можете использовать Boost и вам нужен только поиск во время компиляции: 

using namespace boost::mpl;
typedef vector_c<char, 'A', 'B', 'C', 'D'> Chars;   

// lookup by index:
std::cout << at_c<Chars, 1>::type::value << std::endl; // B 

// lookup by value:
typedef find<Chars, integral_c<char, 'C'> >::type Iter;
std::cout << Iter::pos::value << std::endl; // 2
0 голосов
/ 15 сентября 2011

Так как есть несколько решений, которые не генерируют таблицу, но все же позволяют просматривать время компиляции, вот еще одно 

constexpr char kLetters[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
constexpr int get(char const x, int const i = 0) {
  return kLetters[i] == x ? i : get(x, i + 1);
}

Использовать во время компиляции 

int x[get('F')];
static_assert(sizeof(x) == sizeof(int[5]), "");

Указание несуществующего символа приведет к ошибке. Если вы используете функцию во время выполнения, вы получите неопределенное поведение, если вы укажете несуществующий символ. Надлежащая проверка может быть добавлена ​​для этих случаев.

Возвращает индекс первого найденного символа. Ошибка не отображается, если персонаж дважды появляется в стоге сена.

0 голосов
/ 14 сентября 2011

Если вы можете использовать c ++ 0x (протестировано с gcc 4.5), это работает: 

#include<initializer_list>
#include<iostream>
#include<map>
constexpr int getLetterNumber(char a){ return std::map<char,int>({{'a',2},{'b',1},{'c',4}})[a]; }
int main(){
    const char ch='b';
    std::cout<<ch<<": "<<getLetterNumber(ch)<<std::endl;
}

constexpr обеспечивает оценку во время компиляции.

РЕДАКТИРОВАТЬ : это решение, как указано, не является правильным. constexpr не включает оценку во время компиляции. Это действительно делает поиск во время компиляции (аналогично решениям, опубликованным тем временем). 

#include<iostream>
template<char C> int ch2Num();
#define CHR(c,i) template<> int ch2Num<c>(){ return i; }
CHR('a',2); CHR('b',1); /* ... */
#undef CHR
int main(void){
    const char ch='b';
    std::cout<<ch<<": "<<ch2Num<ch>()<<std::endl;
};
0 голосов
/ 14 сентября 2011

Это предполагает, что 'Z'> 'A', но не предполагает, что буквы являются смежными. (Хотя это занимает меньше памяти, если они есть) У меня было соблазн поставить условные выражения if (numrLetters>26), чтобы умный компилятор мог использовать сложение, а не таблицы для ASCII, но затем решил, что в случае менее умные компиляторы. 

const char kLetters[] = "ABCDEFGHJJKLMNOPQRSTUVWXYZ";
const int numLetters = sizeof(kLetters);
const char rkLetters['Z'-'A'] = {};
const int numrLetters = sizeof(rkLetters);
struct LetterInit {
    LetterInit() {
        for(int i=0; i<numLetters; ++i)
            rkLetters[kLetters[i]-'A'] = i;
    }
}LetterInitInst;

char findChar(int index) {
    assert(index>=0 && index<numLetters);
    return kLetters[index];
}
int findIndex(char letter) { 
    assert(letter>='A' && letter<='Z');
    return rkLetters[letter-'A'];
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...