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

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

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...]
}

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

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

Ответы

Ответ 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";
}

Ответ 2

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

Ответ 3

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

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

Ответ 4

Да, С++ 11 разрешает инициализаторы:

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