基準に一致するキーのセットを返す

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

} 

これを実装する良い方法は何ですか？

また、algosを使用してマップをフィルタリングするときに一般的な問題を実装するにはどうすればよいでしょうか？

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はより効率的なキー反復メカニズムを提供しません。

代替品には、boost::bindまたはboost::lambdaと結合されたstd::for_eachが含まれます。

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では、ラムダ式の方がはるかに優れています。呼び出し元のコードでは

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

：

Answer 5

ます。また、このようにそれを行うことができます

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