返回映射中符合条件的一组键

Question

首先我将给出一个具体案例，然后我想看看它是否可以应用于一般问题。

说我有地图。 我想让所有的钥匙都满足一定的标准。 例如，所有包含“COL”的键。 我天真的实现将是

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

}

什么是实现这个的好方法？

另外，当我想使用算法过滤地图时，实现一般问题的好方法是什么？

Answer 1

这看起来像是 remove_copy_if 的候选者。 我使用 boost 写了一些东西，它看起来可能不仅仅是恶心，但提供了算法的概括。

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

我可能更喜欢手动循环。 C++1x 会让 lambda 表达式看起来更好。

Answer 2

我认为你的解决方案相当好：它很清楚，除非你可以根据条件“猜测”哈希值，否则我认为你的性能不会更高。 但是，您可以更改函数以使其更加通用：

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

然后可以使用函子作为谓词来编写示例：

struct Contains {
    Contains(const string & substr) : substr_(substr) {}

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

    string substr_;
};

对过滤器的调用将如下所示：

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

Answer 3

实现这个的好方法是什么？

看看下面。 不过，这是未经测试的东西，因此您可能需要修复它。

/* 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();

}

另外，当我想使用算法过滤地图时，实现一般问题的好方法是什么？

看一下 std::transform。

Answer 4

首先，一些非常小的建议：

• 您可以缓存 m.end() 的值
• 您可以使用 ++iter，它可以为您节省迭代器的一份副本
• 您可以通过将测试移至非常明确命名的函数，例如 ''KeyContainsSubstring(const std::string&)'' 或类似函数。

在更一般地处理此类任务时，我实际上更喜欢像您一样的显式循环。 std::map 无论如何都没有提供更有效的键迭代机制。

替代方案包括 std::for_each 加上boost::bind，或boost::lambda 。

Answer 5

您也可以这样做：

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;
};

在调用代码中：

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