编译时数据结构的数量结构？

Question

在C++中,您可以这样做:

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

...这为您提供了一个很好的只读数组数据结构,它不需要在运行时初始化任何CPU周期,因为所有数据都已经为您(在可执行文件的只读存储器页面中)布局了编译器.

但是如果我宁愿使用不同的数据结构而不是数组呢？例如,如果我希望我的数据结构通过密钥快速查找,我必须做这样的事情:

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

如果您想要一个地图(或集合),请考虑使用存储为数组的二叉树.您可以断言它在调试版本中在运行时正确排序,但在优化版本中,您可以假设所有内容都已正确排列,然后可以执行与std :: map中相同的二进制搜索操作,但使用底层存储是一个数组.在将数据粘贴到程序之前,只需编写一个小程序来为您堆积数据.

Answer 2

不容易，不。如果您尝试使用 做第一个示例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";
}