Populacja czasu kompilacji struktur danych innych niż tablice?

Question

W C++, można to zrobić:

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

... i który daje piękny tylko do odczytu tablicy danych struktura, która nie ponosi cykli procesora, aby zainicjować w czasie wykonywania, ponieważ wszystkie dane został ustawiony dla ciebie (na stronach pamięci tylko do odczytu) przez kompilator.

Ale co, jeśli wolałbym używać innej struktury danych zamiast tablicy? Na przykład, jeśli chciałem moją strukturę danych, aby miał szybki wyszukiwań za pomocą klucza, muszę zrobić coś takiego:

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

... co jest mniej eleganckie i mniej skuteczne, jak struktura danych jest mapa zapełnianie w czasie wykonywania, mimo że wszystkie niezbędne dane były znane w czasie kompilacji, a zatem praca mogła zostać (teoretycznie) wykonana.

Moje pytanie brzmi, czy istnieje sposób w C++ (lub C++ 11) do utworzenia struktury danych tylko do odczytu (takiej jak mapa), której dane są całkowicie skonfigurowane w czasie kompilacji, a zatem wstępnie wypełnione i gotowy do użycia w czasie wykonywania, tak jak może być tablica?

Answer 1

Nie łatwo, no. Jeśli spróbujesz zrobić pierwszy przykład używając malloc, oczywiście nie będzie działać podczas kompilacji. Ponieważ każdy standardowy kontener używa new (cóż, std::allocator<T>::allocate(), ale będziemy udawać, że jest to na razie new), nie możemy tego zrobić w czasie kompilacji.

To, co zostało powiedziane, zależy od tego, ile bólu chcesz przejść i ile chcesz przywrócić do kompilacji. Z pewnością nie możesz tego zrobić, używając tylko standardowych funkcji biblioteki. Korzystanie boost::mpl z drugiej strony ...

#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

Jeśli chcesz mapę (lub zestaw), rozważ zamiast tego, używając binary tree stored as an array. Możesz potwierdzić, że jest poprawnie uporządkowany w środowisku wykonawczym w kompilacjach debugowania, ale w zoptymalizowanych kompilacjach możesz po prostu założyć, że wszystko jest poprawnie ustawione, a następnie możesz wykonać te same operacje wyszukiwania binarnego, które byłyby w std :: map, ale z pamięć jest tablicą. Wystarczy napisać mały program, aby zilustrować dane przed wklejeniem do programu.

Answer 3

Tak, C++ 11 pozwala inicjalizatory karczkiem:

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

Answer 4

Warto wspomnieć, że problem wynika z faktu, używasz mapę. Mapy są często nadużywane. Alternatywnym rozwiązaniem dla mapy jest posortowany wektor/tablica. Mapy stają się "lepsze" niż mapy, gdy są używane do przechowywania danych o nieznanej długości lub (i tylko czasami), gdy dane często się zmieniają.

Funkcje std :: sort, std :: lower_bound/std :: upper_bound są tym, czego potrzebujesz. Jeśli możesz samodzielnie sortować dane, potrzebujesz tylko jednej funkcji, lower_bound, a dane mogą być stałe.