有BOOST池固定大小的分配器吗? [英] Is there a BOOST pool fixed-sized allocator?

问题描述

我想创建unordered_map(因为我特别想要一个哈希图).我想在一开始分配其最大大小(根据我的约束).
因此，如果我要分配256个条目，并且每个条目的大小为1B(仅作为示例.假设1Byte包含键和值).然后，我的unordered_map键和条目的总大小为256B.我想在分配器中预分配256B.
然后，当unordered_map调用allocate()/deallocate()时，allocator将从已分配的内存中给它1B.

I want to create unordered_map(Because I specifically want a hash map). I want to allocate its max size (according to my constraints) in the beginning.
So, if I want to allocated 256 entries, and the size of each entry is 1B (just an example. Let's say 1Byte includes the Key and the Value). Then the total size of my unordered_map keys + entries is 256B. I want to pre-allocate 256B in the allocator.
Then, when the unordered_map will call allocate()/deallocate(), the allocator will give it 1B from the already-allocated memory.

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

BOOST中是否存在?还是其他地方?

Does it exists in BOOST? or somewhere else?

----编辑----

---- edit ----

我看到了(感谢这里的答案)-我的问题有两种解决方案:

As I see it (Thanks to the answers here) - there are two solutions for my problem:

1. 实现一个allocator，该allocator保存一个boost::pool<>.此pool是在allocator构造函数中构建的.从unordered_map调用allocate()时，实际上会调用pool.malloc()，而从unordered_map调用deallocate()时，实际上会调用pool.free().

1. Implement an allocator, which holds a boost::pool<>. This pool is built in the allocator constructor. When allocate() is being called from unordered_map, it actually calls pool.malloc(), and when deallocate() is called from unordered_map, it actually calls pool.free().

使用已经实现的allocator，例如pool_allocator，如下所示:

Use an already implemented allocator, such as pool_allocator like this:

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;

对于我来说，秒选项仍然不清楚，原因是:
一种.我只能声明一个MyUnorderedMap吗?
b.如何在运行时声明一个新的MyUnorderedMap，其大小不同于1024?

The seconds option is still unclear to me, because:
a. Can I declare only one MyUnorderedMap?
b. How can I declare a new MyUnorderedMap with different next_block size than 1024 in run time?

推荐答案

您所描述的内容实际上只能通过Boost Intrusive地图"之类的东西来实现(实际上，

What you describe can actually only achieved with something like Boost Intrusive "Maps" (actually, sets then).

但是要获得真正的1B-分配的元素，您需要定义

However to get truly 1B - allocated elements you'd need to define a custom stateful value traits, so you can store the node-index metadata separately from the element payload.

但是，从您声称元素类型为1B(对于具体的键和值类型显然永远不可能为真)的事实出发，我不认为您出于某些原因"而实际上想要这种人为设计的解决方案.

However, from the fact that you claim the element type to be 1B (which can obviously never be true for a concrete key and value type), I'll not assume you actually wanted this contrived solution for "some reason".

相反，让我提出另外三种平凡的方法:

Instead, let me suggest three more mundane approaches:

• 使用flat_map
• 使用Boost Intrusive无序集
• 使用带有Boost Pool固定大小分配器的无序集合

如果不是必须进行散列查找，则可以通过保留前面的连续元素存储并存储有序映射来简化很多事情:

If hash lookup is not mandatory, you can simplify a lot by just reserving contiguous element storage up front and storing an ordered map instead:

在Coliru上直播

#include <boost/container/flat_map.hpp>
#include <iostream>

using Elements = boost::container::flat_map<std::string, std::string>;

int main() {
    Elements map;
    map.reserve(256); // pre-allocate 256 "nodes"!

    map.insert({
            { "one",   "Eins"  },
            { "two",   "Zwei"  },
            { "three", "Drei"  },
            { "four",  "Vier"  },
            { "five",  "Fuenf" },
        });

    for (auto& e : map) {
        std::cout << "Entry: " << e.first << " -> " << e.second << "\n";
    }

    std::cout << "map[\"three\"] -> " << map["three"] << "\n";
}

打印

Entry: five -> Fuenf
Entry: four -> Vier
Entry: one -> Eins
Entry: three -> Drei
Entry: two -> Zwei
map["three"] -> Drei

加强干扰

CAVEAT (侵入式容器)带有它们自己的权衡取舍.管理元素的基础存储可能容易出错.挂钩的自动链接行为会抑制size()和类似内容(在某些无序集合配置中为empty())的恒定时间实现，因此这可能不是您的事.

CAVEAT Intrusive containers come with their own set of trade offs. Managing the underlying storage of the elements can be error-prone. Auto-link behaviour of the hooks inhibits the constant-time implementation of size() and similar (empty() on some of the unordered set configurations) so this might not be your thing.

在Coliru上直播

#include <boost/intrusive/unordered_set.hpp>
#include <boost/intrusive/unordered_set_hook.hpp>
#include <iostream>

namespace bi = boost::intrusive;

struct Element;

namespace boost {
    template <> struct hash<Element> {
        size_t operator()(Element const& e) const;
    };
}

struct Element : bi::unordered_set_base_hook<> {
    std::string key;
    mutable std::string value;

    Element(std::string k = "", std::string v = "") 
        : key(std::move(k)), value(std::move(v)) { }

    bool operator==(Element const& other) const { return key == other.key; }
};

size_t boost::hash<Element>::operator()(Element const& e) const {
    return hash_value(e.key); 
}

using Elements = bi::unordered_set<Element>;

int main() {
    std::array<Element, 256> storage;               // reserved 256 entries
    std::array<Elements::bucket_type, 100> buckets; // buckets for the hashtable

    Elements hashtable(Elements::bucket_traits(buckets.data(), buckets.size()));

    storage[0] = { "one",   "Eins"  };
    storage[1] = { "two",   "Zwei"  };
    storage[2] = { "three", "Drei"  };
    storage[3] = { "four",  "Vier"  };
    storage[4] = { "five",  "Fuenf" };

    hashtable.insert(storage.data(), storage.data() + 5);

    for (auto& e : hashtable) {
        std::cout << "Hash entry: " << e.key << " -> " << e.value << "\n";
    }

    std::cout << "hashtable[\"three\"] -> " << hashtable.find({"three"})->value << "\n";
}

打印

Hash entry: two -> Zwei
Hash entry: four -> Vier
Hash entry: five -> Fuenf
Hash entry: three -> Drei
Hash entry: one -> Eins
hashtable["three"] -> Drei

池固定大小分配器¹

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

Pool fixed size allocator¹

If you absolutely require the node-based storage, consider using a custom allocator.

¹您会注意到(至少使用Boost的unordered_map实现)分配器用于两种类型(存储桶指针和值节点)，因此有 two 可以进行固定大小的分配.

¹ You'll note that (at least with Boost's unordered_map implementation) the allocator is used for two types (bucket pointers and value nodes) and as such there are two fixed size allocations possible.

^{(请参阅示例底部的清理调用)}

在Coliru直播

Live On Coliru

#include <boost/pool/pool_alloc.hpp>
#include <boost/unordered/unordered_map.hpp>
#include <iostream>

using RawMap = boost::unordered_map<std::string, std::string>;
using Elements = boost::unordered_map<
        std::string, std::string,
        RawMap::hasher, RawMap::key_equal,
        boost::fast_pool_allocator<RawMap::value_type>
    >;

int main() {
    {
        Elements hashtable;

        hashtable.insert({
                { "one",   "Eins"  },
                { "two",   "Zwei"  },
                { "three", "Drei"  },
                { "four",  "Vier"  },
                { "five",  "Fuenf" },
                });

        for (auto& e : hashtable) {
            std::cout << "Hash entry: " << e.first << " -> " << e.second << "\n";
        }

        std::cout << "hashtable[\"three\"] -> " << hashtable.find("three")->second << "\n";
    }

    // OPTIONALLY: free up system allocations in fixed size pools
    // Two sizes, are implementation specific. My 64 system has the following:
    boost::singleton_pool<boost::fast_pool_allocator_tag, 8>::release_memory();  // the bucket pointer allocation
    boost::singleton_pool<boost::fast_pool_allocator_tag, 32>::release_memory(); // the ptr_node<std::pair<std::string const, std::string> >
}

这篇关于有BOOST池固定大小的分配器吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！