Компиляция времени структур данных, отличных от массивов?

Question

В C++, вы можете сделать это:

static const char * [4] = { 
    "One fish", 
    "Two fish", 
    "Red fish", 
    "Blue fish" 
}; 

... и что дает хороший только для чтения массива структуры данных, которая не принимает каких-либо циклов процессора для инициализации во время выполнения, так как все данные был выложен для вас (в исполняемых файлах памяти только для чтения) компилятором.

Но что, если я предпочитаю использовать другую структуру данных вместо массива? Например, если бы я хотел, чтобы моя структура данных, чтобы иметь быстрый поиск с помощью ключа, я должен был бы сделать что-то вроде этого:

static std::map<int, const char *> map; 

int main(int, char **) 
{ 
    map.insert(555, "One fish"); 
    map.insert(666, "Two fish"); 
    map.insert(451, "Red fish"); 
    map.insert(626, "Blue fish"); 

    [... rest of program here...] 
} 

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

Мой вопрос в том, есть ли какой-либо способ в C++ (или C++ 11) для создания структуры данных только для чтения (например, карты), данные которой полностью настроены во время компиляции и, таким образом, готов к использованию во время выполнения, как может быть массив?

Answer 1

Не легко, нет. Если вы попытались сделать свой первый пример, используя malloc, очевидно, что он не будет работать во время компиляции. Поскольку каждый стандартный контейнер использует new (ну, std::allocator<T>::allocate(), но мы будем делать вид, что это new), мы не можем сделать это во время компиляции.

Это было сказано, это зависит от того, сколько боли вы готовы пройти, и сколько вы хотите отступить, чтобы скомпилировать время. Вы, конечно, не можете этого сделать, используя только стандартные функции библиотеки. Использование boost::mpl с другой стороны ...

#include <iostream> 

#include "boost/mpl/map.hpp" 
#include "boost/mpl/for_each.hpp" 
#include "boost/mpl/string.hpp" 
#include "boost/mpl/front.hpp" 
#include "boost/mpl/has_key.hpp" 

using namespace boost::mpl; 

int main() 
{ 
    typedef string<'One ', 'fish'> strone; 
    typedef string<'Two ', 'fish'> strtwo; 
    typedef string<'Red ', 'fish'> strthree; 
    typedef string<'Blue', 'fish'> strfour; 

    typedef map<pair<int_<555>, strone>, 
     pair<int_<666>, strtwo>, 
     pair<int_<451>, strthree>, 
     pair<int_<626>, strfour>> m; 

    std::cout << c_str<second<front<m>::type>::type>::value << "\n"; 
    std::cout << has_key<m, int_<666>>::type::value << "\n"; 
    std::cout << has_key<m, int_<111>>::type::value << "\n"; 
} 

Answer 2

Если вы хотите использовать карту (или установить), воспользуйтесь binary tree stored as an array. Вы можете утверждать, что он правильно упорядочен во время выполнения в отладочных сборках, но в оптимизированных сборках вы можете просто предположить, что все правильно организовано, а затем может выполнять те же виды операций поиска двоичных данных, которые вы бы использовали на std :: map, но с базовыми хранилище представляет собой массив. Просто напишите небольшую программу для извлечения данных для вас, прежде чем вставлять их в свою программу.

Answer 3

Да, C++ 11 позволяет скобка Инициализаторы:

std::map<int, const char *> map = { 
    { 555, "One fish" }, 
    { 666, "Two fish" }, 
    // etc 
}; 

Answer 4

Стоит отметить, что ваша проблема связана с тем, который вы используете карту. Карты часто злоупотребляют. Альтернативным решением для карты является отсортированный вектор/массив. Карты становятся «лучше», чем карты, когда используются для хранения данных неизвестной длины или (и только иногда), когда данные часто меняются.

Функции std :: sort, std :: lower_bound/std :: upper_bound - это то, что вам нужно. Если вы можете сортировать данные самостоятельно, вам нужна только одна функция, lower_bound, а данные могут быть const.