c++boostboost-multi-index

MultiIndex containers -- offering vector and set access


I have an application where, first, an std::vector<int> object is generated. Then, some operations need to be performed on this object viewed as an std::set<int> where the order does not matter and repetitions don't count.

At present, I explicitly construct an object of type std::set<int> from the std::vector<int> object. An example is presented below:

#include <cstdio>
#include <set>
#include <vector>

void printset(std::set<int>& Set) {
    printf("Printing Set Elements: ");
    for (std::set<int>::iterator siter = Set.begin(); siter != Set.end(); ++siter) {
        int val = *siter;
        printf("%d ", val);
    }
    printf("\n");
}

void printvec(std::vector<int>& Vec) {
    printf("Printing Vec Elements: ");
    for (size_t i = 0, szi = Vec.size(); i < szi; ++i) {
        int val = Vec[i];
        printf("%d ", val);
    }
    printf("\n");
}

int main()
{
    std::vector<int> VecInt{ 6, 6, 5, 5, 4, 4 };
    std::set<int> SetInt(VecInt.begin(), VecInt.end());
    printvec(VecInt);
    printset(SetInt);
}

I am trying to see if I can use Boost.MultiIndex for this purpose. One introduction to Boost.MultiIndex states:

Boost.MultiIndex can be used if elements need to be accessed in different ways and would normally need to be stored in multiple containers. Instead of having to store elements in both a vector and a set and then synchronizing the containers continuously, you can define a container with Boost.MultiIndex that provides a vector interface and a set interface.

and this is precisely what I am doing (using multiple containers and then creating one from the other constantly) while I would like to create a (multi-index) container once and then provide a vector interface and a set interface.

On looking through various examples, for e.g., here and here, it is not clear how those examples can be modified to the code example above.

Ideally, I would like to do the following in the code example above:

MultiIndexContainer vec_set_container;

vec_set_container.push_back(6);//or anything equivalent for the MultiIndexContainer
vec_set_container.push_back(6);
vec_set_container.push_back(5);
vec_set_container.push_back(5);
vec_set_container.push_back(4);
vec_set_container.push_back(4);

printvec(vec_set_container.Some_Function_That_Exposes_Vector_Interface());
printset(vec_set_container.Some_Function_That_Exposes_Set_Interface());

How can this be accomplished using Boost.MultiIndex ?


Solution

  • Random access index would match the "vector" interface.

    An ordered unique index would match the "set" interface.

    However, if you have a unique index, this will prevent insertion of duplicates. So, you would get:

    Live On Compiler Explorer

    #include <boost/multi_index/identity.hpp>
    #include <boost/multi_index/ordered_index.hpp>
    #include <boost/multi_index/random_access_index.hpp>
    #include <boost/multi_index_container.hpp>
    #include <fmt/ranges.h>
    
    namespace bmi = boost::multi_index;
    
    using Table = bmi::multi_index_container< //
        int,
        bmi::indexed_by<
            bmi::random_access<bmi::tag<struct asVector>>,
            bmi::ordered_unique<bmi::tag<struct asSet>, bmi::identity<int>>>>;
    
    int main()
    {
        Table data{ 6, 6, 5, 5, 4, 4 };
    
        fmt::print("As vec {}\nAs set {}\n", //
                   data.get<asVector>(),    //
                   data.get<asSet>());
    }
    

    Printing

    As vec {6, 5, 4}
    As set {4, 5, 6}
    

    Now, I think the "best" you could do with this is to make the order index non-unique (so, mimicking a std::multiset instead of std::set): Live On Compiler Explorer

    bmi::ordered_non_unique<bmi::tag<struct asSet>, bmi::identity<int>>
    

    Printing

    As vec [6, 6, 5, 5, 4, 4]
    As set {4, 4, 5, 5, 6, 6}
    

    If you want to traverse unique elements, using a range adaptor would be minimally costly:

    1. Using Boost Live

      fmt::print("As vec {}\nAs set {}\n", //
                 data.get<asVector>(),     //
                 data.get<asSet>() | boost::adaptors::uniqued);
      
    2. Using RangeV3 Live

      fmt::print("As vec {}\nAs set {}\n", //
                 data.get<asVector>(),     //
                 data.get<asSet>() | ranges::views::unique);
      
    3. Using Standard Ranges; I couldn't make this work but it should really be something like std::ranges::unique(data.get<asSet>())

    All printing

    As vec {6, 6, 5, 5, 4, 4}
    As set {4, 5, 6}
    

    Other Ideas

    If you don't require random access, then sequenced index might be preferrable for you. And note that this interface comes with the handy unique() and sort() methods (just like std::list).

    UPDATE To The Comments

    Here's a rolled-in-one response to the comments:

    Live On Compiler Explorer

    #include <boost/multi_index/identity.hpp>
    #include <boost/multi_index/ordered_index.hpp>
    #include <boost/multi_index/sequenced_index.hpp>
    #include <boost/multi_index_container.hpp>
    #include <fmt/ranges.h>
    #include <random>
    
    namespace bmi = boost::multi_index;
    
    template <typename T>
    using ListSet = bmi::multi_index_container< //
        T,
        bmi::indexed_by<
            bmi::sequenced<bmi::tag<struct byInsertion>>,                   //
            bmi::ordered_unique<bmi::tag<struct Ordered>, bmi::identity<T>> //
            >>;
    
    int main()
    {
        ListSet<int> data;
    
        std::mt19937 prng{99}; // "random" seed
        for (std::uniform_int_distribution d(1, 10); data.size() < 5;) {
            int el = d(prng);
            if (auto [it, unique] = data.push_back(el); not unique) {
                fmt::print("Element {} duplicates index #{}\n", el,
                        std::distance(begin(data), it));
            }
        }
    
        fmt::print("By insertion {}\nOrdered {}\n", data, data.get<Ordered>());
    }
    

    Prints

    Element 9 duplicates index #3
    Element 8 duplicates index #1
    By insertion [7, 8, 5, 9, 1]
    Ordered {1, 5, 7, 8, 9}