Common algorithm for std::list and std::map?

Question

I have a class of interest (call it X).
I have a std::list<X*> (call it L).
I have a function (call it F).

F(L) returns a subset of L (a std::list<X*>) according to an algorithm that examines the internal state of each X in the list.

I'm adding to my application a std::map<int,X*> (call it M), and I need to define F(M) to operate in the same fashion as F(L) - that is to say, F(M) must return a std::list<X*> as well, determined by examining the internal state of each X in the map.

Being a self-described lazy programmer, immediately I see that the algorithm is going to be [logically] the same and that each data type (the std::list and the std::map) are iterable templates. I don't want to maintain the same algorithm twice over, but I'm not sure how to move forward.

One approach would be to take the X*'s from F(M) (that is, the 'values' from the key-value map), throw them into a std::list<X*>, and punt the processing over to F(std::list<X*>), passing the return std::list<X*>; back through. I can't see how this would be the only way.

My question: How can I maintain the core algorithm in one place, but retain the ability to iterate over either a sequence or the values of a pair associative container?

Thanks!

Answer 1

First, all but the condition for both can be done with std::remove_copy_if. Despite the name, remove_copy_if, doesn't remove anything from the original collection. I think people would understand it more easily if it was called something like filtered_copy. It copies elements from one collection to another. For each element, it calls a predicate, and the item gets copied if and only if the predicate returns false for that element.

That leaves you with only one responsibility: to implement the test function that looks at each X *, and says whether it should be left out of the copy you're making. Since you have one piece of logic you want to apply in two different ways, I'd encapsulate the logic in a private function of a class. The two ways it can then be supplied to the outside world as overloaded versions of operator() for the class:

class F { 
    bool do_test(X const *x) const { return x.internal_stuff; }
public:
    bool operator()(X const *x) const { return do_test(x); }

    bool operator()(std::pair<int, X const *> const &p) const { 
        return do_test(p.second);
    }
};

Since operator()(X const *) is a pure thunk to do_test(), you might want to get rid of it, but IMO that would probably do more harm than good.

In any case, this leaves your logic entirely in one place (F::do_test). It also gives a simple, consistent syntax for creating a filtered copy of either a list<X *> or a std::map<int, X *>:

std::list<X *> result;   
std::remove_copy_if(coll.begin(), coll.end(), std:back_inserter(result), F());

As a final note: std::list is probably the most over-used collection in existence. While it does have its uses, they're really quite rare. std::vector and std::deque are very frequently better.