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

One solution would be to shift the algorithm out of both functions, and those functions simply iterate over their container, and call the algo function to determine whether a specific item belongs in the return list or not.

Answer 2

Write a function that accepts two forward iterators as it's parameters ( the beginning and end), then the function just tests the iterator's value, adding it to the list if it passes the test, increments the iterator, and tests that it doesn't reach the end (break if it does.)

Then you just call the function and pass it the begin() and end() iterators of the collections.

Answer 3

You're probably right that your suggested method isn't the only solution, but it's likely the easiest to write correctly and understand. If you're writing production code, I would definitely start there. Profile the code and get fancier only if you need to.

In exploring other options, you might take a look at boost::bind. I received this answer when I was trying to do something similar a while back. And I think std::tr1::bind is basically the same, so you should be able to substitute the TR1 version if you don't have Boost.

Answer 4

How about something like:

template<typename T>
struct func {
    std::list<T>& r;
    func(std::list<T>& r_) : r(r_) {}

    bool algorithm(const T& t) {
        return t<5; // obviously meant to be replaced :)
    }

    void operator()(const T& t) {
        if (algorithm(t)) r.push_back(t);
    }

    void operator()(const std::pair<int, T>& t) {
        if (algorithm(t.second)) r.push_back(t.second);
    }

};

template<typename T, typename ForwardIterator>
std::list<T> subset(ForwardIterator begin, ForwardIterator end) {
    std::list<T> r;
    std::for_each(begin, end, func<T>(r));
    return r;
}

Answer 5

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.