以高效的方式创建、访问、存储和加载 boost：：bimap

您根据具有位集的无序映射来构建整个问题。目标是什么？你用这个设计模拟了哪些现实生活中的问题？

您的位集到底有多大？大小的差异有多大？位的某些子集的分布是什么？假设某些事情，使用快速而肮脏的临时哈希可能比这种通用方法要好得多（请参阅下面的 ¹ 和 ²）

您将希望减少分配，将“打包”的数据加载到非基于节点的容器中，控制元素的排序时间（而不是一直携带该不变性）。

我有很好的结果，将这样的容器放在一个 Boost 进程间共享内存段/内存映射文件中。

基准

我使用以下代码对生成/保存/加载数据进行了基准测试。

请注意，这不会实现上述任何建议，只是它选择退出哈希表选项。不必在每次插入或查找密钥时实例化存档将有很大帮助。此外，请记住，当达到负载因子时，哈希表会重新哈希。调整对于它们真正顺利工作至关重要。

在Wandbox上直播

#include <boost/archive/binary_iarchive.hpp>
#include <boost/archive/binary_oarchive.hpp>
#include <boost/bimap.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <boost/dynamic_bitset/serialization.hpp>
#include <fstream>
#include <vector>
#include <random>
#include <chrono>
#include <iostream>

namespace bimaps = boost::bimaps;
using Block = uint32_t;
using Bitset = boost::dynamic_bitset<Block>;

typedef boost::bimap<bimaps::set_of<Bitset>, bimaps::multiset_of<Bitset>> Index;

template <typename Caption, typename F>
auto timed(Caption const& task, F&& f) {
    using namespace std::chrono;
    using namespace std::chrono_literals;
    struct _ {
        high_resolution_clock::time_point s;
        Caption const& task;
        ~_() { std::cout << " -- (" << task << " completed in " << (high_resolution_clock::now() - s) / 1.0s << "s)\n"; }
    } timing { high_resolution_clock::now(), task };

    return f();
}

int main(int argc, char**) {
    using namespace std::string_literals;

    auto gen_bitset = [
        data=std::vector<Block>(64), // max 2048 bits
        prng=std::mt19937{42} // { std::random_device{}() }
    ]() mutable {
        auto length_gen = std::uniform_int_distribution<size_t>(data.size()/2, data.size());
        auto block_gen = std::uniform_int_distribution<Block>{};

        size_t n = length_gen(prng);
        std::generate_n(data.begin(), n, [&]{ return block_gen(prng); });

        return Bitset(data.begin(), data.begin()+n);
    };

    if (argc>1) {
        std::cout << "# Creating ... " << std::endl;
        Index index;

        timed("Generating data set", [&] {
            for (size_t i = 0; i < 52<<19; ++i) {
                index.insert({gen_bitset(), gen_bitset()});
            }
        });

        timed("Writing binary file", [&] {
            std::ofstream ofs("binaryfile", std::ios::binary);
            boost::archive::binary_oarchive oa(ofs);
            oa << index;
        });
        std::cout << "Written " << index.size() << " key/value pairs\n";
    } else {
        std::cout << "# Loading ... " << std::endl;
        Index index;

        timed("Loading binary file", [&] {
            std::ifstream ifs("binaryfile", std::ios::binary); // name of loading file
            boost::archive::binary_iarchive ia(ifs);
            ia >> index;
        });

        std::cout << "Roundtripped " << index.size() << " key/value pairs\n";
    }
}

这将创建一个包含 27262976 个键/值对的 11G 文件。所有键和值都是均匀随机的位集，长度均匀分布在 1024..2048 位之间。

 rm binaryfile                                                                    
 time ./sotest 1                                                                  
     -- (Generating data set completed in 228.499s)
     -- (Writing binary file completed in 106.083s)
    Written 27262976 key/value pairs

    real    5m48.362s
    user    5m32.876s
    sys     0m14.704s
 ls -ltrah binaryfile 
    -rw-rw-r-- 1 sehe sehe 11G dec 14 01:16 binaryfile
 time ./sotest
    # Loading binary file ... 
     -- (Loading binary file completed in 135.167s)
    Roundtripped 27262976 key/value pairs

    real    2m19.397s
    user    2m11.624s
    sys     0m7.764s

将数据集减少到 .25 百万个条目时，我得到一个 106MiB¹ 的文件，时间如下：

 rm binaryfile 
 time ./sotest 1
    # Creating ... 
     -- (Generating data set completed in 1.13267s)
     -- (Writing binary file completed in 0.586325s)
    Written 262144 key/value pairs

    real    0m1.825s
    user    0m1.676s
    sys     0m0.140s
 ls -ltrah binaryfile 
    -rw-rw-r-- 1 sehe sehe 106M dec 14 01:44 binaryfile
 time ./sotest
    # Loading ... 
     -- (Loading binary file completed in 0.776928s)
    Roundtripped 262144 key/value pairs

    real    0m0.823s
    user    0m0.764s
    sys     0m0.056s

¹ 这基本上告诉我您的位集要小得多 - 我认为这可能非常有利于其他数据结构选择

² 我注意到 Richard Hodges 在较旧的答案中编写了较旧的非缩放哈希实现。你看到发生了什么吗？你问X，提供的信息太少，人们无法真正了解你的问题，所以你得到了X的答案。但这不是最佳选择。你真正的问题是别的什么。

StackOverflow 可能拥有最优秀的程序员，但他们不会神奇地看穿你的 X/Y 问题，即使他们可能会嗅到它并试图把它画出来。归根结底，我们不是通灵者。与高级导师/同事一起工作是无可替代的，他们可以指导您的每一步。