std::multimap中是否存在可迭代访问唯一键的迭代器？

Question

有没有一种简单或标准的方法可以拥有一个multimap迭代器，它可以遍历multimap中唯一的键？

即，对于这样的集合：{1, "a"}, {1, "lemon"}, {2, "peacock"}, {3, "angel"}，一个迭代器从{1, "a"}开始，然后递增指向{2, "peacock"}，再次递增指向{3, "angel"}？

- Bingo

Answer 1

您可以使用 upper_bound 来增加迭代器位置而不是使用 ++：

#include <map>
#include <string>
#include <iostream>

using namespace std;

int main()
{
  multimap<int,string> mm;
  mm.insert(make_pair(1, "a"));
  mm.insert(make_pair(1, "lemon"));
  mm.insert(make_pair(2, "peacock"));
  mm.insert(make_pair(3, "angel"));

  for( auto it = mm.begin(), end = mm.end();
       it != end;
       it = mm.upper_bound(it->first)
  )
    cout << it->first << ' ' << it->second << endl;
  return 0;
}

这个的结果是：

1 a
2 peacock
3 angel

- Pablo

---

但要注意这会涉及O(n log n)的复杂度，而不是正常的O(n)遍历，如@user3701170的回答中所提到的。 - ddevienne

@ddevienne 很遗憾，现在每个人都选择优雅而不是性能。 - GreenScape

性能可能取决于数据布局。给定N为键的数量，M为条目的数量，普通循环的复杂度为O（M），而二分查找循环的复杂度为O（N log M）。如果N << M，则很容易证明后者更小。 - Andrei R.

Answer 2

使用upper_bound会得到一个易于阅读的循环，但每次调用都会执行二叉树搜索，导致遍历的时间复杂度为O(n log n)而不是O(n)。如果效率差异很重要，您可以像这样构建遍历：

typedef std::multimap<std::string, int> MapType;
MapType container;
for (MapType::iterator it = container.begin(); it != container.end(); ) {
  std::string key = it->first;

  doSomething(key);

  // Advance to next non-duplicate entry.
  do {
    ++it;
  } while (it != container.end() && key == it->first);
}

- user3701170

---

谢谢，这个可行。一个 while(true) + goto 版本：https://dev59.com/_2ox5IYBdhLWcg3wLhei#41523639 - Ciro Santilli OurBigBook.com

Answer 3

正如所选答案中所指出的那样，反复使用multimap::upper_bound会导致对地图进行O(n log n)遍历。使用外部upper_bound函数可使您获得O(n)。但是，您需要确保仅比较地图的键：

std::multimap<int, std::string> myMap = ... ;
const auto compareFirst = [](const std::pair<const int, std::string>& lhs, const std::pair<const int, std::string>& rhs) {
    return lhs.first < rhs.first;
};

for(auto it = myMap.begin(); it != myMap.end(); it = std::upper_bound(it, myMap.end(), *it, compareFirst)) {
    // Do stuff...

}

本质上，这种方法与user3701170的解决方案基本相同 - 即线性搜索 - 但我们将增量步骤放在for语句中，而不是循环体中。除了将增量放在“通常”位置外，这还意味着循环中的任何continue语句都将按预期工作。

- Stewart Becker

Answer 4

可运行的示例

这是对https://dev59.com/_2ox5IYBdhLWcg3wLhei#24212648的略微改进，附带了可运行的单元测试:

#include <cassert>
#include <map>
#include <vector>

int main() {

    // For testing.
    auto m = std::multimap<int, int>{
        {1, 2},
        {1, 3},
        {2, 4}
    };
    std::vector<int> out;

    // The algorithm.
    auto it = m.begin();
    auto end = m.end();
    while (it != end) {
        auto key = it->first;

        // Do what you want to do with the keys.
        out.push_back(key);

        do {
            if (++it == end)
                break;
        } while (it->first == key);
    }

    // Assert it worked.
    assert(out == std::vector<int>({1, 2}));
}

- Ciro Santilli OurBigBook.com

---

我鼓励大家避免使用goto。这里通过将“goto end;”替换为“break;”和“while(true)”替换为“while(it != end)”来避免使用它。 - bebbo

@bebbo 感谢您的编辑，但我认为代码可能无法正常工作，因为key没有更新。请确保您编译并运行它;-) - Ciro Santilli OurBigBook.com

@bebbo 我也得睡觉了 :-) 我希望有一种方法可以避免两个 it == end 的比较，即使需要使用 goto。 - Ciro Santilli OurBigBook.com

你需要至少检查一下空映射。因此，代码中总共有两个比较。 - bebbo

Answer 5

如果你需要快速遍历所有唯一键，则可以使用std::map代替；

typedef std::map< KeyType, std::list< ValueType > > MapKeyToMultiValue;

插入操作会更加困难，但是你可以迭代所有的键而不必担心重复条目。插入操作如下：

void insert_m(MapKeyToMultiValue &map, const KeyType key, const ValueType value )
{
  auto it = map.find( key );
  if (it == map.end())
  {
     std::list<ValueType> empty;
     std::pair< MapKeyToMultiValue::iterator, bool > ret =
        map.insert( MapKeyToMultiValue::value_type( key, empty ) );
     it = ret.first;
  }

  it->second.push_back( value );
}

或者你可以将其制作为非常模板化的形式：

template<typename KeyType, typename ValueType, 
     typename MapType = std::map< KeyType, std::list< ValueType > > >
void insert_multi( MapType &map, const KeyType key, const ValueType value )
{

  auto it = map.find( key );
  if (it == map.end())
  {
     std::list<ValueType> empty;
     std::pair< typename MapType::iterator, bool > ret =
        map.insert( typename MapType::value_type( key, empty ) );
     it = ret.first;
  }

  it->second.push_back( value );
}

完整的测试程序如下所示：

#include <map>
#include <list>
#include <string>
#include <stdio.h>

typedef std::string KeyType;  
typedef int ValueType;

typedef std::map< KeyType, std::list< ValueType > >  MapKeyToMultiValue;

void insert_m(MapKeyToMultiValue &map, const KeyType key, const ValueType value )
{
  auto it = map.find( key );
  if (it == map.end())
  {
     std::list<ValueType> empty;
     std::pair< MapKeyToMultiValue::iterator, bool > ret =
        map.insert( MapKeyToMultiValue::value_type( key, empty ) );
     it = ret.first;
  }

  it->second.push_back( value );
}


template<typename KeyType, typename ValueType, 
   typename MapType = std::map< KeyType, std::list< ValueType > > >
void insert_multi( MapType &map, const KeyType key, const ValueType value )
{

  auto it = map.find( key );
  if (it == map.end())
  {
     std::list<ValueType> empty;
     std::pair< typename MapType::iterator, bool > ret =
        map.insert( typename MapType::value_type( key, empty ) );
     it = ret.first;
  }

  it->second.push_back( value );
}


int main()
{
    MapKeyToMultiValue map;


    insert_m(map, std::string("aaa"), 1 );
    insert_m(map, std::string("aaa"), 2 );
    insert_m(map, std::string("bb"), 3 );
    insert_m(map, std::string("cc"), 4 );


    insert_multi(map, std::string("ddd"), 1 );
    insert_multi(map, std::string("ddd"), 2 );
    insert_multi(map, std::string("ee"), 3 );
    insert_multi(map, std::string("ff"), 4 );


    for(auto i = map.begin(); i != map.end(); ++i)
    {
      printf("%s\n", i->first.c_str() );
    }


    return 0;
}

- MichaelMoser

---

这太复杂了。std::map<int，std::list<int> > map;的插入只需使用map[1].push_back(2);。如果operator[]查找未找到任何内容，则默认构造列表，在此非常方便。 - JDiMatteo

Answer 6

尝试使用equal_range:

http://en.cppreference.com/w/cpp/container/multimap/equal_range

那必须是完全匹配。

- Red.Wave

---

equal_range 接受 multimap 中的键作为输入，因此如果需要检索键，则不是一个好选择... - Sandburg