是否有BOOST池固定大小的分配器？

Question

我想创建unordered_map(因为我特别想要一个哈希映射).我想在开头分配它的最大尺寸(根据我的约束).
所以,如果我想分配256个条目,每个条目的大小是1B(只是一个例子.假设1Byte包括Key和Value).然后我的unordered_map键+条目的总大小是256B.我想在分配器中预先分配256B.
然后,当unordered_map将调用allocate()/时deallocate(),allocator将从已分配的内存中给它1B.

typedef boost::unordered::unordered_map<int, MyClass, boost::hash<int>, std::equal_to<MyClass>, ??? > > myMap

它是否存在于BOOST中？或者别的地方？

----编辑----

正如我所看到的(感谢此处的答案) - 我的问题有两个解决方案:

1. 实现一个allocator,持有一个boost::pool<>.这pool是在allocator构造函数中构建的.当allocate()被调用时unordered_map,它实际上调用pool.malloc(),并且当deallocate()调用unordered_map它时,它实际调用pool.free().

2. 使用已经实现的allocator,pool_allocator如下所示:

typedef pool_allocator<std::pair<MyKey, MyClass>, boost::default_user_allocator_new_delete, boost::mutex, 1024 >) MyAllocator;
typedef unordered_map<MyKey, MyClass, hash, eq, MyAllocator> MyUnorderedMap;

秒选项对我来说仍然不清楚,因为:
a.我只能声明一个MyUnorderedMap吗？
湾 我怎样才能申报使用不同的新MyUnorderedMap next_block大小比1024在运行时间？

Answer 1

您所描述的实际上只能通过诸如 Boost Intrusive“Maps”（实际上是设置）之类的东西来实现。

\n\n

然而，要获得真正的 1B 分配元素，您需要定义自定义有状态值 Traits，以便您可以将节点索引元数据与元素有效负载分开存储。

\n\n

然而，从您声称元素类型为 1B 的事实来看（对于具体的键和值类型来说，这显然永远不会成立），我不会假设您实际上出于“某种原因”想要这个人为的解决方案。

\n\n

相反，让我建议三种更普通的方法：

\n\n

\n
• 用一个flat_map
\n
• 使用 Boost Intrusive 无序集
\n
• 使用带有 Boost Pool 固定大小分配器\xc2\xb9 的无序集
\n

\n\n

促进flat_map

\n\n

如果哈希查找不是强制性的，您可以通过预先保留连续元素存储并存储有序映射来简化很多工作：

\n\n

Live On Coliru

\n\n

#include <boost/container/flat_map.hpp>\n#include <iostream>\n\nusing Elements = boost::container::flat_map<std::string, std::string>;\n\nint main() {\n    Elements map;\n    map.reserve(256); // pre-allocate 256 "nodes"!\n\n    map.insert({\n            { "one",   "Eins"  },\n            { "two",   "Zwei"  },\n            { "three", "Drei"  },\n            { "four",  "Vier"  },\n            { "five",  "Fuenf" },\n        });\n\n    for (auto& e : map) {\n        std::cout << "Entry: " << e.first << " -> " << e.second << "\\n";\n    }\n\n    std::cout << "map[\\"three\\"] -> " << map["three"] << "\\n";\n}\n

\n\n

印刷

\n\n

Entry: five -> Fuenf\nEntry: four -> Vier\nEntry: one -> Eins\nEntry: three -> Drei\nEntry: two -> Zwei\nmap["three"] -> Drei\n

\n\n

增强侵入式

\n\n

\n

注意事项侵入式容器有其自身的一系列权衡。管理元素的底层存储可能容易出错。挂钩的自动链接行为会抑制 和 类似的恒定时间实现size()（empty()在某些无序集配置上），因此这可能不适合您。

\n

\n\n

Live On Coliru

\n\n

#include <boost/intrusive/unordered_set.hpp>\n#include <boost/intrusive/unordered_set_hook.hpp>\n#include <iostream>\n\nnamespace bi = boost::intrusive;\n\nstruct Element;\n\nnamespace boost {\n    template <> struct hash<Element> {\n        size_t operator()(Element const& e) const;\n    };\n}\n\nstruct Element : bi::unordered_set_base_hook<> {\n    std::string key;\n    mutable std::string value;\n\n    Element(std::string k = "", std::string v = "") \n        : key(std::move(k)), value(std::move(v)) { }\n\n    bool operator==(Element const& other) const { return key == other.key; }\n};\n\nsize_t boost::hash<Element>::operator()(Element const& e) const {\n    return hash_value(e.key); \n}\n\nusing Elements = bi::unordered_set<Element>;\n\nint main() {\n    std::array<Element, 256> storage;               // reserved 256 entries\n    std::array<Elements::bucket_type, 100> buckets; // buckets for the hashtable\n\n    Elements hashtable(Elements::bucket_traits(buckets.data(), buckets.size()));\n\n    storage[0] = { "one",   "Eins"  };\n    storage[1] = { "two",   "Zwei"  };\n    storage[2] = { "three", "Drei"  };\n    storage[3] = { "four",  "Vier"  };\n    storage[4] = { "five",  "Fuenf" };\n\n    hashtable.insert(storage.data(), storage.data() + 5);\n\n    for (auto& e : hashtable) {\n        std::cout << "Hash entry: " << e.key << " -> " << e.value << "\\n";\n    }\n\n    std::cout << "hashtable[\\"three\\"] -> " << hashtable.find({"three"})->value << "\\n";\n}\n

\n\n

印刷

\n\n

Hash entry: two -> Zwei\nHash entry: four -> Vier\nHash entry: five -> Fuenf\nHash entry: three -> Drei\nHash entry: one -> Eins\nhashtable["three"] -> Drei\n

\n\n

池固定大小分配器\xc2\xb9

\n\n

如果您绝对需要基于节点的存储，请考虑使用自定义分配器。

\n\n

\n

\xc2\xb9 您会注意到（至少对于 Boost 的 unordered_map 实现）分配器用于两种类型（桶指针和值节点），因此可能有两种固定大小的分配。

\n\n

^{（请参阅示例底部的清理调用）}

\n

\n\n

住在科里鲁

\n\n

#include <boost/pool/pool_alloc.hpp>\n#include <boost/unordered/unordered_map.hpp>\n#include <iostream>\n\nusing RawMap = boost::unordered_map<std::string, std::string>;\nusing Elements = boost::unordered_map<\n        std::string, std::string,\n        RawMap::hasher, RawMap::key_equal,\n        boost::fast_pool_allocator<RawMap::value_type>\n    >;\n\nint main() {\n    {\n        Elements hashtable;\n\n        hashtable.insert({\n                { "one",   "Eins"  },\n                { "two",   "Zwei"  },\n                { "three", "Drei"  },\n                { "four",  "Vier"  },\n                { "five",  "Fuenf" },\n                });\n\n        for (auto& e : hashtable) {\n            std::cout << "Hash entry: " << e.first << " -> " << e.second << "\\n";\n        }\n\n        std::cout << "hashtable[\\"three\\"] -> " << hashtable.find("three")->second << "\\n";\n    }\n\n    // OPTIONALLY: free up system allocations in fixed size pools\n    // Two sizes, are implementation specific. My 64 system has the following:\n    boost::singleton_pool<boost::fast_pool_allocator_tag, 8>::release_memory();  // the bucket pointer allocation\n    boost::singleton_pool<boost::fast_pool_allocator_tag, 32>::release_memory(); // the ptr_node<std::pair<std::string const, std::string> >\n}\n

\n