Tutorial :returning a set of keys in the map matching the criteria



Question:

First I will give a specific case, and the I would like to see if it can be applied to a general problem.

Say I have map. And I want to get all the keys meeting a certain criteria. For example all keys that contain "COL". My naive implementation will be

template<typename T>  void  Filter (map<string, T> & m, std:set<string> & result, const std::string& condition)  {      for(map<string,string> iter=m.begin();iter!m.end();iter++)      {             std::string key=iter->first;              size_t found=key.find(condition);             if (found!=string::npos)                result.insert(key);      }         }  

what is the good way to implement this?

Also, what is a good way to implement general problem when I want to filter map using algos?


Solution:1

I think your solution is rather good: it is clear, and except if you can "guess" hash values based on the condition, I don't think you could be much more performant. However, you could change your function to make it more generic:

template<typename TKey, typename TValue, typename Predicate>  void filter (const map<TKey, TValue> & m,                set<TKey> & result,                Predicate & p)  {      typename map<TKey,TValue>::const_iterator it = m.begin();      typename map<TKey,TValue>::const_iterator end = m.end();        for( ; it != end ; ++it)      {          TKey key = it->first;          if (p(key))              result.insert(key);      }       }  

Your example can then be writen using a functor as predicate:

struct Contains {      Contains(const string & substr) : substr_(substr) {}        bool operator()(const string & s)      {          return s.find(substr_) != string::npos;      }        string substr_;  };  

The call to filter will then look like this:

map<string, Obj> m;  // Insert in m  set<string> res;  filter(m, res, Contains("stringToFind"));  


Solution:2

That looks like a candidate for remove_copy_if. I've written something using boost that probably looks more than disgusting, but provides a generalization of your algorithm.

#include <boost/iterator/transform_iterator.hpp>  #include <boost/bind.hpp>  #include <boost/function.hpp>  #include <algorithm>  #include <map>  #include <set>  #include <string>    struct filter_cond : std::unary_function<std::string, bool> {      filter_cond(std::string const &needle):needle(needle) { }      bool operator()(std::string const& arg) {          return (arg.find(needle) == std::string::npos);      }      std::string needle;  };      int main() {      std::set<std::string> result;      typedef std::map<std::string, int> map_type;      map_type map;        std::remove_copy_if(          boost::make_transform_iterator(map.begin(),                                         boost::bind(&map_type::value_type::first, _1)),          boost::make_transform_iterator(map.end(),                                         boost::bind(&map_type::value_type::first, _1)),          std::inserter(result, result.end()),           filter_cond("foo")      );  }  

I would probably prefer the manual loop. C++1x will make look that really much better with lambda expressions.


Solution:3

what is the good way to implement this?

Take a look below. This is untested stuff though so you may need to fix it.

/* return some value */  /* fix order of input and output instead of having them mixed */  template<typename T>  size_t Filter(map<string, T> m,                string const& condition /* fixed condition; mark it as such */               set<T>& result /* reference to add efficiency */               )  {    typename map<string, T>::const_iterator last = m.end();    typename map<string, T>::const_iterator i = find_if(m.begin(),                                               last,                                               bind2nd(equal(), condition)                                              );    while (i != last) {         result.insert(*i);         i = find_if(i + 1,                     last,                     bind2nd(equal(), condition)                     );    }    return result.size();  

}

Also, what is a good way to implement general problem when I want to filter map using algos?

Take a look at std::transform.


Solution:4

First, some very minor suggestions:

  • You could cache the value of m.end()
  • You could use ++iter, which saves you one copy of the iterator
  • You could improve clarity by moving the test to a very explicitely named function like ''KeyContainsSubstring(const std::string&)'' or similar.

On the more general handling of this sort of tasks, I tend to actually prefer explicit loops like you did. std::map does not provide a more efficient keys iteration mechanism anyway.

Alternatives would include std::for_each coupled with boost::bind, or boost::lambda.


Solution:5

You can also do it like this:

template<class T>  struct StringCollector  {  public:      StringCollector(const std::string& str, std::set<std::string>& selectedKeys) : m_key(str), m_selectedKeys(selectedKeys)      {        }        void operator()(const std::pair<std::string,T>& strPair_in)      {          size_t found = strPair_in.first.find(m_key);          if(found != std::string::npos)          {              m_selectedKeys.insert(strPair_in.first);          }      }    private:      std::set<std::string>& m_selectedKeys;      std::string m_key;  };  

In the calling code:

std::set<std::string> keys;  StringCollector<int> collector("String",keys);  std::for_each(a.begin(), a.end(), collector);  

Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »