c++booststlboost-multi-index

Index retrieval as a function of the boost::multi_index::sequenced<> offset


I am in a situation where I am forced to use a std::vector container as my underlying data structure. I'm trying to exploit boost::multi_index::sequenced<> to shadow the vector offset, and provide a mechanism for richer data queries. I really don't want to unnecessarily copy all the data from one container to another.

In the example code snippet below I have a class BarInterface that manages the insertion and removal of elements to the Bar::foos container. Initially I tried to store references to the vector elements as elements of the typedef boost::multi_index_container, but these are not stable against insertions.

What I'd like to do is have a custom key extractor that is a function of the _bar container and the boost::multi_index::sequenced<> index. So, for example to get the name of an element, I'd find the sequence offset x, and then _bar.foos[x].name. So, I'm really just using boost::multi_index as a proxy for richer queries against a vector of variable size.

struct Foo {
    std::string name;
};

struct Bar {
    std::vector<Foo> foos;
};

class BarInterface {
public:
    struct Dummy {};
    BarInterface(Bar& bar) : _bar(bar) {
        for (auto& foo : bar.foos) {
            _idx.get<1>().insert(Dummy{});
        }
    }

    // Index
    struct Name {};
    typedef boost::multi_index_container<
        Dummy, // We're not actually storing anything here
        boost::multi_index::indexed_by<
            boost::multi_index::sequenced<>,   // Kept inline with vector order!
            boost::multi_index::ordered_unique<
                boost::multi_index::tag<Name>,
                // I need something here that takes the boost::multi_index::sequenced<>
                // key to get the offset x, and then returns this->_bar.foos[x].name!
            >
        >
    > MultiIndex;

    // Insert
    void insert(const Foo& foo) {
        _bar.foos.push_back(foo);
        _idx.get<1>().insert(Dummy{});
    }

    // Remove
    template <typename T>
    void remove(T it) {
        _bar.foos.erase(_bar.foos.begin() + std::distance(_idx.begin(), _idx.project<0>(it)));
        _idx.erase(_idx.project<0>(it));
    }

protected:
    Bar& _bar;
    MultiIndex _idx;
};

I know that boost::multi_index supports all sorts of key extractors -- for member variables, member functions, global function, etc. However, I can't seem to find an example showing how to generate a key as a function of a boost::multi_index::sequenced<> index. Is this possible, or is there an elegant alternative?


Solution

  • This is extremely brittle and I wouldn't recommend going to production with such code, but since you asked for it:

    Live Coliru Demo

    #include <boost/multi_index_container.hpp>
    #include <boost/multi_index/ordered_index.hpp>
    #include <boost/multi_index/random_access_index.hpp>
    #include <iostream>
    #include <string>
    #include <vector>
    
    struct Foo {
        std::string name;
    };
    
    struct Bar {
        std::vector<Foo> foos;
    };
    
    class BarInterface;
    
    struct Dummy
    {
        Dummy(const Foo& x): p(&x){}
        Dummy(const Dummy&): p(nullptr){}
        
        const Foo* p;
    };
    
    struct NameExtractor
    {
        NameExtractor(BarInterface* p): p(p){}
        
        using result_type=std::string;
        
        const result_type& operator()(const Dummy& d)const;
    
        BarInterface* p;
    };
    
    class BarInterface {
    public:
        BarInterface(Bar& bar) :
            _idx(boost::make_tuple(
                boost::tuple<>(),
                boost::make_tuple(NameExtractor(this), std::less<std::string>())
            )),
            _bar(bar)
        {
            for (auto& foo : bar.foos) {
                _idx.get<1>().insert(bar.foos.back());
            }
        }
    
        // Index
        struct Name {};
        typedef boost::multi_index_container<
            Dummy, // We're not actually storing anything here
            boost::multi_index::indexed_by<
                boost::multi_index::random_access<>,   // Kept inline with vector order!
                boost::multi_index::ordered_unique<
                    boost::multi_index::tag<Name>,
                    NameExtractor
                >
            >
        > MultiIndex;
    
        // Insert
        void insert(const Foo& foo) {
            _bar.foos.push_back(foo);
            _idx.get<1>().insert(_bar.foos.back());
        }
    
        // Remove
        template <typename T>
        void remove(T it) {
            _bar.foos.erase(_bar.foos.begin() + std::distance(_idx.begin(), _idx.project<0>(it)));
            _idx.erase(_idx.project<0>(it));
        }
        
        void remove(const char* name) {
            remove(_idx.get<1>().find(name));
        }
        
        void print()const
        {
            auto key=_idx.get<1>().key_extractor();
          
            for(const auto& d: _idx.get<1>()){
                std::cout<<key(d)<<" ";
            }
            std::cout<<"\n";
        }
    
    protected:
        friend NameExtractor;
      
        Bar& _bar;
        MultiIndex _idx;
    };
    
    const NameExtractor::result_type& NameExtractor::operator()(const Dummy& d)const
    {
        if(d.p){
            return d.p->name;
        }
        else{
            std::size_t offset=p->_idx.iterator_to(d)-p->_idx.begin();
            return p->_bar.foos[offset].name;
        }
    }
    
    int main()
    {
        Bar bar;
        BarInterface bi(bar);
        
        bi.insert(Foo{"hello"});
        bi.insert(Foo{"bye"});
        bi.insert(Foo{"Boost"});
        
        bi.print();
        
    
        bi.remove("bye");
    
        bi.print();
    
        bi.insert(Foo{"MultiIndex"});
        
        bi.print();
    }
    

    Output

    Boost bye hello 
    Boost hello 
    Boost MultiIndex hello