Replacing mapped vector with boost multi_index reasonable?

Question

In my application I'm storing a huge(!) container: A vector of vectors. Each of the vectors has a unique name and I use a map to store the index to the vector for further access. Storing the data in vectors is needed in my application as I have to do a lot of processing and therefore need fast access to the elements in it.

Unfortunately std::map doesn't care for the insertion order which is important in my use case and I came across this topic:

A std::map that keep track of the order of insertion?

Unfortunately the proposed solution is not exactly what I need and I now wonder:

• Is it possible to make boost_multi_index use vectors to store the data?
• Is it reasonable at all (in my case) to replace vector/map usage with boost multi_index or
• Use something like bimap or
• Is there a more elegant way for "my problem"?

Sample code:

#include <vector>
#include <map>
#include <string>
#include <iostream>

using payload_t = std::vector<uint32_t>;
using container_t = std::vector<payload_t>;
using container_map_t = std::map<std::string, size_t>;
using connectionMask_t = std::map<std::string, uint32_t>;

int main()
{
    container_t container;
    container_map_t container_map;

    // Store 1st payload
    container.push_back(std::move(payload_t{1,2,3}));
    container_map["One"] = container.size() - 1;

    // Store 2nd payload
    container.push_back(std::move(payload_t{4,5,6,7}));
    container_map["Two"] = container.size() - 1;

    // Store 3rd payload
    container.push_back(std::move(payload_t{8,9}));
    container_map["Three"] = container.size() - 1;

    // Assign unique mask to each layer (name)
    connectionMask_t masks;
    for (auto const&[name, data] : container_map)
    {
        // Assign mask to each layer
        masks[name] = 1UL << masks.size();
    }

    // Iterating vector access
    for (auto& outer : container)
        for (auto& inner : outer)
            std::cout << inner;
    std::cout << std::endl << std::endl;

    // Direct vector access
    for (auto& inner : container[1])
        std::cout << inner;
    std::cout << std::endl << std::endl;

    // Access via name
    for (auto& inner : container.at(container_map.at("Two")))
        std::cout << inner;
    std::cout << std::endl << std::endl;

    // Iterating access via map; order not preserved
    for (auto& [key, vec] : container_map)
    {
        std::cout << key << ": ";
        for (auto& inner : container[vec])
            std::cout << inner;
        std::cout << std::endl;
    }

    return 0;
}

Answer 1

• Is it possible to make boost_multi_index use vectors to store the data?

No. All the containers are implemented on node-based storage so iterator/reference stability is guaranteed.

• Is it reasonable at all (in my case) to replace vector/map usage with boost multi_index [or]

It seems so, but see below.

• Use something like bimap

It's unclear to me how it will fill any gap.

• Is there a more elegant way for "my problem"?

Perhaps. Simplest wins, IMO:

Live On Coliru

#include <cassert>
#include <cstdint>
#include <map>
#include <vector>

#include <fmt/ranges.h>

using payload_t = std::vector<uint32_t>;
using map_t     = std::map<std::string, payload_t>;
using entry_t   = map_t::value_type;
using ref_t     = std::reference_wrapper<entry_t>;

int main() {
    map_t              container;
    std::vector<ref_t> index;

    auto insert = [&](std::string name, payload_t element) {
        auto [it, ok] = container.emplace(std::move(name), std::move(element));
        if (ok)
            index.push_back(*it);
        else
            assert(false); // TODO decide on how to behave
    };

    for (auto&& [name, data] : { std::tuple //
             {"One", payload_t{1, 2, 3}},
             {"Two", payload_t{4, 5, 6, 7}},
             {"Three", payload_t{8, 9}},
         })
    {
        insert(std::move(name), data);
    }

    fmt::print("All (order not preserved): {}\n", container);

    for (int i = 0; entry_t& inner : index)
        fmt::print("At #{}, {}: {}\n", i++, inner.first, inner.second);

    fmt::print("Access via name: {}\n", container.at("Two"));
}

Printing

All (order not preserved): {"One": [1, 2, 3], "Three": [8, 9], "Two": [4, 5, 6, 7]}
At #0, One: [1, 2, 3]
At #1, Two: [4, 5, 6, 7]
At #2, Three: [8, 9]
Access via name: [4, 5, 6, 7]

From Here

Sprinkle in what you need to taste:

• Boost Container

  • stable vector (for ... stability)
  • flat map (for locality of reference and reducing allocations)
  • small_vector (e.g. for the payloads. In the example they are very samll, small_vector or even static_vector will be a huge performance improvement)

• Boost Interprocess

  To put all of this in shared memory/memory mapped files. This will allow you to deal with data structures way bigger than available RAM and also persisting across runs