Re: STL algorithm member function problem

From:

Alberto Ganesh Barbati <AlbertoBarbati@libero.it>

Newsgroups:

comp.lang.c++.moderated

Date:

15 Nov 2006 21:07:47 -0500

Message-ID:

<c1N6h.44482$uv5.303499@twister1.libero.it>

lists@givemefish.com ha scritto:

class Rule : public std::unary_function<std::string, bool> {
public:
   virtual result_type operator()(const argument_type&) const =0;
};

typedef boost::shared_ptr<Rule> RulePtr;

///////////////
// Concrete rules are inherited from the Rule class and define
// the operator()

.....

    vector<string> fileList;
    // .... fill fileList with a series of file names ...

     //Now remove items from the fileList according to the rules.
     //Iterate over all the rules in the rules vector. Apply the rule
to each of
     // items in the fileList and remove it if the rule returns true.
     for(vector<RulePtr>::const_iterator ruleIter = m_rules.begin();
    ruleIter != m_rules.end(); ++ruleIter) {

           // This is the problem line...
           std::remove_if(fileList.begin(), fileList.end(), ptr_fun(
xxx );
     }

This code suffer of a common but very serious bug. But let's answer the
question first and the bug later.

If Rule wasn't a polymorphic class, the correct answer would be the
simplest one:

    std::remove_if(fileList.begin(), fileList.end(), *ruleIter);

However in your case it won't work, because the static type of *ruleIter
is Rule which is an abstract class which can't be passed by-value to
remove_if. Notice that making Rule non-abstract doesn't help because of
the slicing problem: as it's passed by-value the dynamic type is lost.

Passing by-value and polymorphism are things that don't go together
well. Functors and predicate are usually passed by-value, so you should
have realized by now that having a polymorphic predicate wasn't a good
idea in the first place.

What I suggest is to change the design like this:

class RuleBase {
public:
   virtual bool operator()(const std::string&) const =0;
};

class Rule : public std::unary_function<std::string, bool> {
   boost::shared_ptr<RuleBase> rule;

public:
   Rule(const boost::shared_ptr<RuleBase>& r) : rule(r)
   {}

   // nonvirtual!
   result_type operator()(const argument_type& s) const
   {
      return (*rule)(s);
   }
};

Of course now all your rules shall inherit from RuleBase, not Rule.

Then you have two alternatives:

1) you replace your vector<RulePtr> with vector<Rule> (a Rule is nothing
more than a RulePtr after all) and write:

    std::remove_if(fileList.begin(), fileList.end(), *ruleIter);

2) you keep using your vector<RulePtr> and write:

    std::remove_if(fileList.begin(), fileList.end(), Rule(*ruleIter));

Now for the bug...

The bad news is that despite what the name remove_if suggests, the
algorithm std::remove_if does *not* actually remove elements from the
container (read very carefully the footnote [1] in
http://www.sgi.com/tech/stl/remove_if.html again and again until you
understand this point, before continuing to read).

So the correct loop to do all removal is (using suggestion n.1 above):

   vector<string> end = fileList.end();
   for(vector<Rule>::const_iterator ruleIter = m_rules.begin();
     ruleIter != m_rules.end(); ++ruleIter)
   {
     end = std::remove_if(fileList.begin(), end, *ruleIter);
   }
   fileList.erase(end, fileList.end());

However, if you have a lot of strings and a lot of predicates, the
performance of this loop are suboptimal because strings are moved a lot
of times. It is much better IMHO to move the loop *in the predicate*, as in:

struct RuleSet // add unary_function here if you want, it's not needed
{
   const vector<RulePtr>& rules;

   RuleSet(const vector<RulePtr>& r) : rules(r)
   {}

   bool operator()(const string& s) const
   {
     for(vector<RulePtr>::const_iterator ruleIter = m_rules.begin();
       ruleIter != m_rules.end(); ++ruleIter)
     {
       if((*ruleIter)(s))
         return true;
     }
     return false;
   }
};

(notice that in this case you don't need to follow neither of my two
advices described above)

Now the entire code will magically turn up to be, simply:

   fileList.erase(
     std::remove_if(fileList.begin(), fileList.end(), RuleSet(m_rules)),
     fileList.end());

Simple, isn't it?

HTH,

Ganesh

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]