c++boostsetintrusive-containersboost-intrusive

Merge two boost intrusive sets in C++?


I have two boost intrusive sets which I need to merge it together. I have map_old.m_old_attributes boost intrusive set which I need to merge it to m_map_new_attributes boost intrusive set

void DataTest::merge_set(DataMap& map_old)
{

    // merge map_old.m_old_attributes set into m_map_new_attributes
}

What is the best way to do this? I am not able to find a function which can do the merge for me? I recently started working with boost intrusive sets and I am not able to find predefined methods which can do the merge, or may be I am wrong?


Solution

  • Indeed intrusive sets are a different beast. They don't manage their element allocations.

    So when merging you need to decide what that means. I'd say a reasonable interpretation would be that you want to move the elements contained inside the map_old container into the DataMap.

    This would leave map_old empty. Here's such an algorithm:

    template <typename Set>
    void merge_into(Set& s, Set& into) {
        std::vector<std::reference_wrapper<Element> > tmp(s.begin(), s.end());
        s.clear(); // important! unlinks the existing hooks
        into.insert(tmp.begin(), tmp.end());
    }
    

    Update Alternately you can do it with O(1) memory complexity by using the slightly trickier iterater-erase-loop (beware of iterating mutating containers): Live On Coliru as well

        for (auto it = s.begin(); it != s.end();) {
            auto& e = *it;
            it = s.erase(it);
            into.insert(e);
        }
    

    See it Live On Coliru

    #include <boost/intrusive/set.hpp>
    #include <boost/intrusive/set_hook.hpp>
    #include <string>
    #include <vector>
    #include <functional>
    #include <iostream>
    
    namespace bive = boost::intrusive;
    
    struct Element : bive::set_base_hook<> {
        std::string data;
    
        Element(std::string const& data = "") : data(data) {}
    
        bool operator< (Element const& rhs) const  { return data < rhs.data; }
        bool operator==(Element const& rhs) const  { return data ==rhs.data; }
    };
    
    using Set = bive::set<Element>;
    
    template <typename Set>
    void merge_into(Set& s, Set& into) {
        std::vector<std::reference_wrapper<Element> > tmp(s.begin(), s.end());
        s.clear(); // important! unlinks the existing hooks
        into.insert(tmp.begin(), tmp.end());
    }
    
    int main() {
        std::vector<Element> va {{"one"},{"two"},{"three"},{"four"},{"five"},{"six"},{"seven"},{"eight"},{"nine"} };
        Set a;
        for(auto& v : va) a.insert(v);
    
        std::vector<Element> vb {{"two"},{"four"},{"six"},{"eight"},{"ten"} };
        Set b;
        for(auto& v : vb) b.insert(v);
    
        assert(9==a.size());
        assert(5==b.size());
    
        merge_into(a, b);
    
        assert(a.empty());
        assert(10==b.size());
    }
    

    Of course you can come up with different semantics for the merge operation (which would be more akin to 'copy' instead of 'move')