在map中计算相同值的数量

Question

有没有命令可以计算地图中相同值的数量？

例如：

map<int, string> m;
m[1] = "A";
m[22] = "A";
m[53] = "C";
m[12] = "A";
m[6] = "A";

int count = m.count("A");// 4

或者我自己写，因为这不太难？

- calccrypto

---

脑海中首先想到的是创建另一个std::map<string, int>，用于计算每个.second的频率。 - user418748

@Muggen：那应该是你最后想到的事情。你只是引入了大量复杂性来完成一个非常简单的任务，而已经有工具可以做到这一点。 - John Dibling

@John Dibling：您所说的“大量复杂性”是什么意思？如果您从下面的答案中查看，如果您正在利用STL count_if而没有C++0x支持，则需要编写相当数量的代码。我倾向于认为使用另一个map将需要更少的代码量。而且，使用map具有更好的运行时复杂度，即O（log n），而如果使用count_if，您需要遍历所有map元素，即O（n）。 - ryaner

@ryaner：如果您需要执行大量计数，则使用第二个“map”存储频率更好。这种方法还要求容器中存储的元素是可比较的。如果您只需要执行单个计数，则最好使用“count_if”枚举项目。 - James McNellis

@James McNellis：我理解你的观点，也认为你的回答很好，当然很有教育意义。但仍然没有回答John Dibling关于使用第二个map会带来何种复杂性的问题，与需要定义函数对象相比。是的，它需要实现operator<（如果键是std :: string，则可能无关紧要）。是的，如果您只计算一次，则浪费了内存（尽管发布者未指定）。但是在实现中出现复杂性吗？我不接受这个观点 =) - ryaner

Answer 1

你可以使用具有自定义谓词函数对象的count_if算法：

template <typename Pair>
struct second_equal_to
    : std::unary_function<const Pair&, bool>
{
    second_equal_to(const typename Pair::second_type& value)
        : value_(value) { }

    bool operator()(const Pair& p) const
    {
        return p.second == *value_;
    }

private:
    typename Pair::second_type value_;
};

使用方法：

typedef std::map<int, std::string> Map;
typedef Map::value_type MapEntry;
std::count_if(m.begin(), m.end(), second_equal_to<MapEntry>("A"));

或者，为了得到更通用的解决方案，你可以编写一个apply_to_second谓词变换器：

template <typename Pair, typename Predicate>
struct apply_to_second_f
    : std::unary_function<const Pair&, bool>
{
    apply_to_second_f(const Predicate& p)
        : predicate_(p) { }

    bool operator()(const Pair& p) const
    {
        return predicate_(p.second);
    }

    Predicate predicate_;
};

template <typename Pair, typename Predicate>
apply_to_second_f<Pair, Predicate> apply_to_second(const Predicate& p)
{
    return apply_to_second_f<Pair, Predicate>(p);
}

用法：

std::count_if(m.begin(), m.end(), 
    apply_to_second<MapEntry>(std::bind2nd(std::equal_to<std::string>(), "A")));

如果您有支持lambda表达式的编译器，则根本不需要任何自定义谓词函数对象；您可以使用更简单的lambda：

std::count_if(m.begin(), m.end(), [](const MapEntry& e) { 
    return e.second == "A";
});

- James McNellis

---

那个 Lambda 很性感，只使用一次时不需要太多额外的代码行。 - Tek

Answer 2

您可以使用自定义值参数与std::count一起使用：

struct Compare {
    std::string str;
    Compare(const std::string& str) : str(str) {}
};
bool operator==(const std::pair<int, std::string>&p, const Compare& c) {
    return c.str == p.second;
}
bool operator==(const Compare& c, const std::pair<int, std::string>&p) {
    return c.str == p.second;
}


int  main() {
    std::map<int, std::string> m;
    m[1] = "A";
    m[22] = "A";
    m[53] = "C";
    m[12] = "A";
    m[6] = "A";

    int count = std::count(m.begin(), m.end(), Compare("A"));

    std::cout << count << "\n";
}

- Robᵩ

---

std::count 或 std::count_if 根据谓词来使用。同时，我没有看到谓词可以接收两个参数的方法：http://en.cppreference.com/w/cpp/algorithm/count - Narek

Answer 3

STL的count_if和手动实现相比很容易。

编辑：抱歉应该是count_if而不是count。

- nevets1219

Answer 4

map::count 正在计算键而不是元素，所以你问题中的示例是错误的。你可能想考虑使用额外的 map 来跟踪每个值的计数。

map<string, int> value_count;
// use like this
++value_count[val];

- ryaner

---

当携带额外变量不是问题时，绝对是更简单的解决方案。 - Quentin Pradet

现在你必须保持两个映射同步。每次修改第一个映射时，必须确保相应地修改第二个映射。我相信这就是先前提到的“很大的复杂性”。除非你将其重构为一个适当的容器类来处理保持两个映射同步，否则我建议不要这样做。 - Andreas Haferburg

Answer 5

这应该足够通用：

template< class T1, class T2 >
class Condition
{
    public:
        Condition( const T2& val ) : _val( val ) {};
        bool operator()( const typename std::pair< const T1, T2 >& aPair )
        {
            return (aPair.second == _val);
        }
    private:
        const T2 _val;
};

然后你可以像这样使用它：

Condition< int, std::string > comp( "A" );
size_t count = std::count_if( m.begin(), m.end(), comp );

请注意，这与以前的答案并没有太大区别，但它可以与任何迭代对一起重复使用。只需将“Condition”重命名为更有意义的名称即可。

- broc