Combining two std::lists of differing types: Possible?

Question

I have a std::list of type Foo* and another of type Bar* of unequal size. Both types implement a positioning system that allows the list to be sorted by z-coordinate for draw order (really just a Point with x, y, z values with them being sorted with a less than Predicate function by z value).

Other than the above mentioned, they are completely different. Is there a way to combine the lists so I can compare ALL the z values against each other instead of just their own types?

Right now, for example, either all the Foos are sorted, or all the Bars are sorted; then either all the Foos are drawn, or all the Bars are drawn. This makes it where even if a Bar has a lower z than a Foo it will be drawn on top. Obviously not the intended consequence.

While typing this I did have an epiphany, would parallel processing work? Sort each list separately, but then alternate drawing them, Foo, Bar, Foo, Bar, etc. or would that result in the same problem? Some drawing above others regardless of z value?

Thanks.

Answer 1

You might try having both types inherit from a base that includes the position, perhaps with a virtual Draw():

struct Base
{
    Point pos;

    virtual ~Base() {}
    virtual void Draw() = 0;
};

struct Foo : base {};
struct Bar : base {};

std::list<Base*> list;

//...

list.sort([](Base *left, Base *right)
{
    return left->pos.z < right->pos.z;
});

for(auto iter = list.begin(), end = list.end(); iter != end; ++iter)
{
    (*iter)->Draw();
}

If you want to keep the lists separate, alternating between drawing Foo and Bar won't work if two of the Foo would have come before one Bar.

But you're thinking on the right track. You can sort individually and then merge the two lists while drawing:

foo_list.sort();
bar_list.sort();

auto fiter = foo_list.begin(), fend = foo_list.end();
auto biter = bar_list.begin(), bend = bar_list.end();

while(fiter != fend && biter != bend)
{
    // draw whichever Foo or Bar is closest, and increment only that iterator.

    if((*fiter)->z_pos < (*biter)->z_pos)
    {
        (*fiter)->Draw();
        ++fiter;
    }
    else
    {
        (*biter)->Draw();
        ++biter;
    }
}

// reached the end of one of the lists. flush out whatever's left of the other.

for(; fiter != fend; ++fiter)
{
    (*fiter)->draw();
}

for(; biter != bend; ++biter)
{
    (*biter)->draw();
}

You could also use a variant, if you want to keep only a single list but have two completely separate types:

struct visitor
{
    float operator()(Foo* f) const { return f->z_position; }
    float operator()(Bar* b) const { return b->z_position; }
};

std::list<boost::variant<Foo*, Bar*>> list;

//...

list.sort([](boost::variant<Foo*, Bar*> const &left, boost::variant<Foo*, Bar*> const &right)
{
    return apply_visitor(visitor(), left) < apply_visitor(visitor(), right);
});

for(auto iter = list.begin(), end = list.end(); iter != end; ++iter)
{
    (*iter)->Draw();
}