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

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

Answer 2

Вы также можете сделать это так:

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

Answer 3

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

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

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

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

Answer 4

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

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 5

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

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

/* 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.