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?

Answer 1

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.

Answer 2

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.

Answer 3

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"));

Answer 4

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.

Answer 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);