我要创建 unordered_map (因为我特别想要一个 HashMap )。我想在开始时分配它的最大大小(根据我的限制)。
因此，如果我要分配 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;

秒选项对我来说仍然不清楚，因为:
一种。我可以只声明一个 MyUnorderedMap 吗？
b.我如何用不同的 next_block 声明一个新的 MyUnorderedMap尺寸比1024在运行时？

最佳答案

您所描述的内容实际上只能通过 Boost Intrusive“ map ”(实际上是 sets 然后)之类的东西来实现。

然而，要获得真正的 1B - 分配元素，您需要定义 custom stateful value traits ，因此您可以将节点索引元数据与元素负载分开存储。

但是，从您声称元素类型为 1B(对于具体的键和值类型显然永远不会是真的)这一事实来看，我不会假设您真的出于“某种原因”想要这个人为设计的解决方案。

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

• 使用flat_map
• 使用 Boost Intrusive 无序集
• 将无序集与 Boost Pool 固定大小分配器一起使用¹

boost flat_map

如果散列查找不是强制性的，您可以通过预先保留连续元素存储并改为存储有序映射来简化很多事情:

Live On 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

boost 侵入性

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.

Live On 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

池固定大小分配器¹

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

¹ 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.

^{(See the cleanup calls at the bottom of the sample)}

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

关于c++ - 是否有 BOOST 池固定大小的分配器？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28925143/