возвращение набора ключей на карте, соответствующей критериям

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

Я думаю, что ваше решение довольно хорошее: это понятно, и если только вы не можете «угадать» хеш-значения на основе условия, я не думаю, что вы могли бы быть намного более результативными. Тем не менее, вы можете изменить свою функцию, чтобы сделать его более универсальным:

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 2

Какой хороший способ реализовать это?

Посмотрите ниже. Это непроверенный материал, хотя вам, возможно, понадобится его исправить.

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

}

Кроме того, что это хороший способ для реализации общей задачи, когда я хочу, чтобы фильтровать карту, используя Algos?

Взгляните на std::transform.

Answer 3

Во-первых, некоторые очень незначительные предложения:

• Вы можете кэшируют значение m.end()
• Вы можете использовать ++iter, что экономит вам одну копию итератора
• Вы могли бы улучшить ясность, переместив тест на очень явно названную функцию, такую ​​как '' KeyContainsSubstring (const std :: string &) '' или подобное.

Что касается более общей работы с такими задачами, я, как правило, предпочитаю явные петли, как и вы. В любом случае std :: map не обеспечивает более эффективный механизм итерации ключей.

Альтернативы будут включать std::for_each в сочетании с boost::bind, или boost::lambda.

Answer 4

Это выглядит как кандидат на 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 будет выглядеть намного лучше с лямбда-выражениями.

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