Union iterator for maps?

Question

[Preface: The associative C++ containers like std::map are a bit like micro-databases with just one key column. Boost's bimap elevates this to a two-column table with lookup in both columns, but that that's as far as the analogy goes -- there's no "polymap" that generalizes the idea.]

In any event, I want to keep thinking of maps as databases, and I now wonder if there is an iterator (or some other solution) that allows me to do a UNION of several constituent maps. That is, all maps have the same type (or value type and comparator, at least), and I want a single iterator that treats the entire collection as a big multimap (repeated keys are OK) and lets me traverse it in the correct unioned order.

Does such a thing exist, perhaps within Boost? Or is it easy to rig one up? In pseudo code:

std::map<K, M> m1, m2;
union_iterator<K, M> u(m1, m2)
for(auto it = u.begin(); it != u.end(); ++it) { /* ... */ }

For example, if we had:

m1 = { { 9:00, "Check in"}, { 12:00, "Break" }, { 16:00, "Check out"} };
m2 = { { 10:30, "coffee" }, { 12:15, "baked beans" }, { 15:00, "lies" } };

then I want the iterator to produce:

9:00, "Check in"; 10:30, "coffee"; 12:00, "Break"; 12:15, "baked beans"; ...

Answer 1

There is a "polymap": Boost.MultiIndex.

Answer 2

As I announced, I have got something pretty cool.

I'm posting it now, because I wouldn't be sure whether I'd be back in time tonight to post it. I will be spending a few words in explanation. (in this post)

PS. The includes will be trimmed down (to about 20%); I will probably do some more general work on the code too.

A lot can be said about this code: it is not very efficient, and not very clean (yet). It is, however, nearly infinitely generic and should scale like anything else. All code can be found in a github gist:

• merge_maps_iterator.hpp
• Makefile
• test.cpp - a rather arcane set of test-cases showing off the genericity
  _{(I'm not saying that it would be a good idea to have maps keyed with ints and floats (let alone both at the same time) - just showing that it can be done)}

Here is the output of the test.cpp as you can find it:

 == input ========================================
{ 2, aap }      { 23, mies }    { 100, noot }   { 101, broer }  
{ b, 3.14 }     
 == output =======================================
     2: aap;
    23: mies;
    98: 3.14;
   100: noot;
   101: broer;

 == input ========================================
{ b, 3.14 }     
{ 2, aap }      { 23, mies }    { 100, noot }   { 101, broer }  
 == output =======================================
     2: aap;
    23: mies;
    98: 3.14;
   100: noot;
   101: broer;

 == input ========================================
{ 2, aap }      { 23, mies }    { 100, noot }   { 101, broer }  
{ 2, aap }      { 23, mies }    { 100, noot }   { 101, broer }  
 == output =======================================
     2: aap;aap;
    23: mies;mies;
   100: noot;noot;
   101: broer;broer;

 == input ========================================
{ b, 3.14 }     
{ b, 3.14 }     
 == output =======================================
     b: 3.14;3.14;

 == input ========================================
{ 1.0, dag }    { 22.0, bye }   { 24.0, Tschüß }
{ 1, true }     { 22, false }   { 24, true }    
{ b, 3.14 }     
{ 2, aap }      { 23, mies }    { 100, noot }   { 101, broer }  
 == output =======================================
   1.0: dag;true;
   2.0: aap;
  22.0: bye;false;
  23.0: mies;
  24.0: Tschüß;true;
  98.0: 3.14;
 100.0: noot;
 101.0: broer;

 == input ========================================
{ 1.0, dag }    { 2.0, EXTRA }  { 22.0, bye }   { 24.0, Tschüß }
{ 1, true }     { 22, false }   { 24, true }    
{ b, 3.14 }     
{ 2, aap }      { 23, mies }    { 100, noot }   { 101, broer }  
 == output =======================================
   1.0: dag;true;
   2.0: EXTRA;aap;
  22.0: bye;false;
  23.0: mies;
  24.0: Tschüß;true;
  98.0: 3.14;
 100.0: noot;
 101.0: broer;

Answer 3

Either copying both mapS into a temporary, appending one to the other (in case you can modify them) or using a vector as a temporary with std::set_union and a custom comparator are the easiest alternative solutions.

Answer 4

Here's how I would implement thiton's answer:

template <class container> class union_iterator
{
private:
    typedef std::pair<typename container::const_iterator, typename container::const_iterator> container_range;
    class container_range_compare
    {
    public:
        bool operator()(const container_range &lhs, const container_range &rhs) const
        {
            return typename container::value_compare()(*lhs.first, *rhs.first);
        }
    };

    std::priority_queue<container_range, container_range_compare> m_range_queue;
    container::const_iterator m_current_iterator;
    bool m_is_valid;

    void add_container(const container &cont)
    {
        add_container_range(std::make_pair(cont.begin(), cont.end()));
    }

    void add_container_range(const container_range &range)
    {
        if (range.first!=range.second)
        {
            m_range_queue.push(range);
        }
    }

public:
    union_iterator(const container &a): m_valid(false)
    {
        add_container(a);
    }

    bool next()
    {
        m_is_valid= false;

        if (!m_range_queue.empty())
        {
            container_range range= m_range_queue.pop();
            m_current_iterator= range.first;

            ++range.first;
            add_container_range(range);

            m_is_valid= true;
        }

        return m_is_valid;
    }

    typename const container::value_type &operator *() const
    {
        return *m_current_iterator;
    }

    typename const container::value_type *operator ->() const
    {
        return m_current_iterator.operator ->();
    }
};

It has slightly different usage than union_iterator<K, V> but it implements the basic idea. You can expand the constructor to accept multiple maps however you fit, and use it in a while (iterator.next()) loop instead of a for (...) loop.

EDIT: I simplified next() by doing all the popping and pushing at once. So now it's even simpler! (One could also expend some effort making it like a STL iterator, but that gets tedious.)