STL::multimap - 如何获得数据组？

Question

Multimap基本上有按键排序的数据组。我希望有一种方法可以访问这些单独的组并获取它们的聚合值。

例如，在std :: multimap< string，int >中存储了

{"Group1", 1}, 
{"Group1", 2}, 
{"Group1", 3}, 

{"Group2", 10}, 
{"Group2", 11}, 
{"Group2", 12}

存储了这些值后，应该能够迭代此multimap并获取每个“组”的聚合值。问题是STL中没有定义访问MultiMap的任何函数。我可以使用lower_bound，upper_bound手动迭代multimap并总计组的内容，但我希望STL已经定义了更好的方法？是否有人能够提出解决方案，以便我可以获取上面示例中组的聚合值。

- the_Saint

---

这里描述了非常优雅的Lambda方法： https://dev59.com/Y3E85IYBdhLWcg3w3Xr6#37680747 - Patricio Astudillo

https://en.cppreference.com/w/cpp/container/multimap/equal_range - Rick

Answer 1

pair<Iter, Iter> range = my_multimap.equal_range("Group1");
int total = accumulate(range.first, range.second, 0);

只是一种方式。

编辑:

如果您不知道要查找的组，只是按照每个组进行操作，并且想获取下一个组的范围，则可以像下面这样操作：

template <typename Pair>
struct Less : public std::binary_function<Pair, Pair, bool>
{
    bool operator()(const Pair &x, const Pair &y) const
    {
        return x.first < y.first;
    }
};

Iter first = mmap.begin();
Iter last = adjacent_find(first, mmap.end(), Less<MultimapType::value_type>());

- Greg Rogers

---

难道不应该是 x.first == y.first; 吗？为什么要使用 operator<？根据 adjacent_find 的文档，谓词参数应该返回与 true（非零）比较的结果，表示它们被视为相等，而 false（零）则表示不相等。为什么你对于不相等的结果返回 true？ - B Faley

是的，这似乎是一个错误。adjacent_find 需要一个“相等”的谓词。此外，我确定有 std::equal_to<T> 可以直接使用。 - leemes

@leemes，我认为你的编辑更改了不正确的行为。 "小于"运算符应该在键值改变之前找到最后一个元素（可以通过advance到具有新键的第一个元素），而使用等号运算符它只会返回指向相同（first）元素的迭代器。 - slawekwin

我已经将最后一次编辑回滚到原始的@Greg版本。 - slawekwin

Answer 2

// samekey.cpp -- Process groups with identical keys in a multimap

#include <iostream>
#include <string>
#include <map>
using namespace std;

typedef multimap<string, int> StringToIntMap;
typedef StringToIntMap::iterator mapIter;

int main ()
{
    StringToIntMap mymap;

    mymap.insert(make_pair("Group2", 11));
    mymap.insert(make_pair("Group1",  3));
    mymap.insert(make_pair("Group2", 10));
    mymap.insert(make_pair("Group1",  1));
    mymap.insert(make_pair("Group2", 12));
    mymap.insert(make_pair("Group1",  2));

    cout << "mymap contains:" << endl;

    mapIter m_it, s_it;

    for (m_it = mymap.begin();  m_it != mymap.end();  m_it = s_it)
    {
        string theKey = (*m_it).first;

        cout << endl;
        cout << "  key = '" << theKey << "'" << endl;

        pair<mapIter, mapIter> keyRange = mymap.equal_range(theKey);

        // Iterate over all map elements with key == theKey

        for (s_it = keyRange.first;  s_it != keyRange.second;  ++s_it)
        {
           cout << "    value = " << (*s_it).second << endl;
        }
    }

    return 0;

}   //  end main

// end samekey.cpp

- Roger House

---

@RogerHouse 有没有办法在我们从第一个到最后一个条目迭代相同键之前获取计数。 - Abhishek Mane

Answer 3

如果您已经知道关键字，您可以使用 multimap::equal_range来获取组的开头和结尾的迭代器；使用任何标准算法从这个范围中获取所需的结果。 如果您不知道关键字，则可以从 begin() 开始自己迭代，比较关键字以找到每个新组的开头。

- Mark Ransom

Answer 4

您可以使用一个备用容器来包含每个组的聚合总和。为此，您可以执行以下操作：

template <class KeyType, class ValueType>
struct group_add {
  typedef map<KeyType, ValueType> map_type;
  map_type & aggregates;
  explicit group_add(map_type & aggregates_)
    : aggregates(aggregates_) { };
  void operator() (map_type::value_type const & element) {
    aggregates[element.first] += element.second;
  };
};

template <class KeyType, class ValueType>
group_add<KeyType, ValueType>
make_group_adder(map<KeyType, ValueType> & map_) {
  return group_add<KeyType, ValueType>(map_);
};

// ...
multimap<string, int> members;
// populate members
map<string, int> group_aggregates;
for_each(members.begin(), members.end(),
  make_group_adder(group_aggregates));
// group_aggregates now has the sums per group

当然，如果你在C++0x中使用Lambda表达式，它可能会更简单：

multimap<string, int> members;
map<string, int> group_aggregates;
for_each(members.begin(), members.end(),
  [&group_aggregates](multimap<string, int>::value_type const & element) {
    group_aggregates[element.first] += element.second;
  }
  );

- Dean

Answer 5

equal_range

语法：

#include <map>
pair<iterator, iterator> equal_range( const key_type& key );

equal_range() 函数返回两个迭代器 - 一个指向第一个包含 key 的元素，另一个指向最后一个包含 key 的元素之后的位置。

- Hayek.Yu

Answer 6

虽然不是multimap的答案，但如果您愿意，可以执行以下操作。

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <boost/assign/list_of.hpp>
#include <boost/foreach.hpp>
using namespace std;
using namespace boost;
using namespace boost::assign;

int main() {
    typedef map<string, vector<int> > collection;
    collection m;
    m["Group 1"] = list_of(1)(2)(3);
    m["Group 2"] = list_of(10)(11)(12);
    collection::iterator g2 = m.find("Group 2");
    if (g2 != m.end()) {
        BOOST_FOREACH(int& i, g2->second) {
            cout << i << "\n";
        }
    }
}

- Shadow2531