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

Question

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

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

I add std :: map <int, X *> to my application (let's call it M), and I need to determine that F (M) works the same as F (L), i.e. F (M) should return std :: list <X *> and also determined by the internal state of each X on the map.

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

One approach was to take X * from F (M) (that is, the "values" from the key value map), drop them into std :: list <X *>, and punt the processing to F (std :: list <X *>), passing the returned std :: list <X *>; back. I do not see how this will be the only way.

My question is: how can I support the main algorithm in one place, but still retain the ability to iterate over either the sequence or the values ​​of the pair associative container?

Thanks!

Answer 1

First, everything except the condition for both can be done using std::remove_copy_if . Despite its name, remove_copy_if does not remove anything from the original collection. I think people would understand this more easily if it was called something like filtered_copy . It copies items from one collection to another. For each element, it calls a predicate, and the element is copied if and only if the predicate returns false for this element.

This leaves you with only one responsibility: implement a test function that looks at every X * and says whether to leave it outside the copy you are creating. Since you have one logic that you want to apply in two different ways, I would encapsulate the logic in a private function of the class. These two methods can be sent to the outside world as overloaded versions of operator() for a 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 pure thunk before do_test() , you can get rid of it, but IMO, which is likely to do more harm than good.

In any case, this completely eliminates your logic in one place ( F::do_test ). It also provides a simple, consistent syntax for creating a filtered copy of either list<X *> or 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 redesigned collection. Although it has its uses, they are indeed quite rare. std::vector and std::deque are often better.

Answer 2

Write a function that takes two iterators forward as parameters (start and end), then the function simply checks the value of the iterator, adding it to the list, if it passes the test, increments the iterator and checks that it doesn't reach the end (break if it will happen.)

Then you simply call the function and pass it the iterators begin () and end () from the collections.

Answer 3

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 4

One solution would be to shift the algorithm from both functions, and these functions will simply go through their container and call the algo function to determine whether a particular item belongs in the return list or not.

Answer 5

You are probably right that your proposed method is not the only solution, but it is most likely the easiest way to write and understand. If you are writing production code, I would definitely start there. Profile the code and get fancier only if you need to.

When exploring other options, you can take a look at boost::bind . I got this answer when I tried to do something similar some time ago. And I think std::tr1::bind is basically the same, so you can replace the TR1 version if you don't have Boost.