1

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?

john
  • 11,311
  • 40
  • 131
  • 251
  • Can't you use [`std::merge`](http://en.cppreference.com/w/cpp/algorithm/merge)? – NathanOliver May 05 '15 at 19:20
  • 1
    I thought boost intrusive sets are different then std::set? – john May 05 '15 at 19:21
  • It would have been a lot more useful if there was even a single container in sight in your code. We can dream up a gazillion different ways in which you manage the lifetime and ownership of the intrusive container elements and it's pretty unlikely we'll accidentally hit the configuration you have. – sehe May 05 '15 at 19:37
  • @sehe I was not able to understand what you said? Is there anything else I should provide in the code which can help you guys understand? – john May 05 '15 at 19:43
  • Understanding is not the issue (I already answered, notice?). The fact that you probably need more specific help is why you need to show more specific code. (Show your intrusive element/containers. Show your lifetime management. Show your expected outcomes. See my answer for how to do [a SSCCE](http://sscce.org) with proper assertions of the expected results) – sehe May 05 '15 at 19:44

1 Answers1

1

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')

sehe
  • 374,641
  • 47
  • 450
  • 633