retournant un ensemble de clés dans la carte correspondant aux critères

Question

Je vais d'abord donner un cas spécifique, et je voudrais voir si elle peut être appliquée à un problème général.

Dites que j'ai une carte. Et je veux que toutes les clés répondent à certains critères. Par exemple toutes les clés contenant "COL". Ma mise en œuvre naïve sera

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

} 

quelle est la bonne façon de mettre en œuvre cela?

Aussi, quel est un bon moyen de mettre en œuvre un problème général lorsque je veux filtrer la carte en utilisant algos?

Answer 1

Je pense que votre solution est plutôt bonne: c'est clair, et sauf si vous pouvez "deviner" les valeurs de hachage en fonction de la condition, je ne pense pas que vous pourriez être beaucoup plus performant. Cependant, vous pouvez changer votre fonction pour le rendre plus générique:

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

Votre exemple peut alors être écrit en utilisant un foncteur comme prédicat:

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

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

    string substr_; 
}; 

L'appel à filtrer ressemblera alors à ceci:

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

Answer 2

Quelle est la bonne façon de mettre en œuvre cela?

Regardez ci-dessous. Ceci est des choses non testées si vous avez besoin de le réparer.

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

}

En outre, ce qui est une bonne façon de mettre en œuvre problème général quand je veux filtrer carte à l'aide algos?

Regardez std::transform.

Answer 3

d'abord, quelques suggestions mineures:

• Vous pouvez mettre en cache la valeur de m.end()
• Vous pouvez utiliser ++iter, qui vous sauve une copie du iterator
• Vous pouvez améliorer clarté en déplaçant le test vers une fonction très explicitement nommée comme '' KeyContainsSubstring (const std :: string &) '' ou similaire.

Sur la gestion plus générale de ce genre de tâches, j'ai tendance à préférer les boucles explicites comme vous l'avez fait. std :: map ne fournit pas de mécanisme d'itération de clés plus efficace.

Les alternatives comprennent std::for_each couplé avec boost::bind ou boost::lambda.

Answer 4

Cela ressemble à un candidat pour remove_copy_if. J'ai écrit quelque chose en utilisant boost qui semble probablement plus que dégoûtant, mais fournit une généralisation de votre algorithme.

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

Je préférerais probablement la boucle manuelle. C++ 1x fera vraiment beaucoup mieux avec les expressions lambda.

Answer 5

Vous pouvez aussi le faire comme ceci:

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

Dans le code d'appel:

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