c++boostboost-bimap

Intersection between various values from boost::bimap


I am trying to use boost::bimap for one of my requirements. Below is sample code

typedef bimap<
        multiset_of< string >,
        multiset_of< string >,
        set_of_relation<>
        > bm_type;

 bm_type bm;

 assign::insert( bm )

 ( "John" , string("lazarus" ) )
 ( "Peter", string("vinicius") )
 ( "Peter", string("test") )
 ( "Simon", string("vinicius") )
 ( "John", string("viniciusa") )
 ( "John", string("vinicius") )

I would like to do something as finding matching values for John & Peter, in other words intersection between values for John & Peter for ex: In this case it will be ("vinicius"). Can someone provide some limelight over it?


Solution

  • Here's what I came up with initially:

    template <typename Value = std::string, typename Bimap, typename Key>
    std::set<Value> projection(Bimap const& bm, Key const& key)
    {
        std::set<Value> p;
        auto range  = bm.left.equal_range(key);
        auto values = boost::make_iterator_range(range.first, range.second);
    
        for (auto& relation : values)
            p.insert(relation.template get<boost::bimaps::member_at::right>());
    
        return p;
    }
    
    auto john  = projection(bm, "John");
    auto peter = projection(bm, "Peter");
    
    std::multiset<std::string> intersection;
    std::set_intersection(
             john.begin(), john.end(),
             peter.begin(), peter.end(),
             inserter(intersection, intersection.end())
         );
    

    I think it can be more efficient. So I tried replacing the projection on the fly using Boost Range's adaptors:

    struct GetRightMember
    {
        template <typename> struct result { typedef std::string type; };
    
        template <typename T>
        std::string operator()(T const& v) const {
            return v.template get<boost::bimaps::member_at::right>();
        }
    };
    
    const GetRightMember getright;
    std::cout << "Intersection: ";
    
    // WARNING: broken: ranges not sorted
    boost::set_intersection(
            bm.left.equal_range("John")  | transformed(getright),
            bm.left.equal_range("Peter") | transformed(getright),
            std::ostream_iterator<std::string>(std::cout, " "));
    

    Sadly it doesn't work - presumably because the transformed ranges aren't sorted.

    So I'd stick with the more verbose version (or reconsider my data structure choices). See it Live On Coliru