如何获取multimap中的所有唯一键

Question

我有一个multimap，我想获取其中所有唯一的键，并将其存储到一个向量中。

  multimap<char,int> mymm;
  multimap<char,int>::iterator it;
  char c;

  mymm.insert(pair<char,int>('x',50));
  mymm.insert(pair<char,int>('y',100));
  mymm.insert(pair<char,int>('y',150));
  mymm.insert(pair<char,int>('y',200));
  mymm.insert(pair<char,int>('z',250));
  mymm.insert(pair<char,int>('z',300));

我该怎么做？有一种方法可以计算多重映射中具有特定键的元素数量，但没有一种方法可以计算多重映射中唯一键的数量。 添加： 我所说的唯一是指多重映射中所有键仅出现一次或重复出现的情况。

因此，在这里唯一的键是 - x，y和z。

- AJ.

---

可能是重复的问题：在std::multimap中是否有跨唯一键的迭代器？ - Ciro Santilli OurBigBook.com

Answer 1

我尝试了这个，它起作用了

for(  multimap<char,int>::iterator it = mymm.begin(), end = mymm.end(); it != end; it = mymm.upper_bound(it->first))
  {
      cout << it->first << ' ' << it->second << endl;
  }

- Jeeva

---

它将打印所有元素 - AJ.

@AJ 看看 upper_bound 部分，这将只打印每个键一次。 - Fiktik

每次迭代都需要在整个地图中搜索。 - Roman

@Roman：不，它并没有。请参阅http://en.cppreference.com/w/cpp/container/multimap/upper_bound。 - Bklyn

我在使用upper_bound时收到了弃用警告，并提示使用equal_range().second。更改后，一切正常运行。 - Andreas Walter

Answer 2

由于std::multimap<>的条目是隐式排序的，并且在通过它们进行迭代时按排序顺序出现，因此您可以使用std::unique_copy算法：

#include <iostream>
#include <map>
#include <algorithm>
#include <vector>

using namespace std;

int main() {

  /* ...Your existing code... */

  /* Create vector of deduplicated entries: */
  vector<pair<char,int>> keys_dedup;
  unique_copy(begin(mymm),
              end(mymm),
              back_inserter(keys_dedup),
              [](const pair<char,int> &entry1,
                 const pair<char,int> &entry2) {
                   return (entry1.first == entry2.first);
               }
             );

  /* Print unique keys, just to confirm. */
  for (const auto &entry : keys_dedup)
    cout << entry.first << '\n';

  cout.flush();
  return 0;
}

使用这种方法增加的额外工作量与multimap中条目的数量成线性关系，而使用std::set或Jeeva的去重方法都会增加O(n log n)的计算步骤。

注：我使用的lambda表达式假定是C++11。可以将其改写为C++03。

- jogojapan

---

为什么std::multimap中没有一个简单的向量/列表/集合/映射，包含所有唯一键。这似乎很有用，而且开销不大。这个功能不存在是因为人们不会经常使用它，还是因为开销比我猜测的要大？我认为空间不应该是一个要求（对吧？）。 - Fractal

@Fractal 我不确定我完全理解你的建议。为此增加一个额外的数据结构将需要O(n)的额外空间，是吗？不过有一件事情很好，那就是提供一个接口（例如特殊迭代器），可以逐个返回唯一的键。 - jogojapan

是的，真的……这将需要额外的O(n)空间。我认为空间实际上并不是一个问题，但也许在我的工作中，我没有处理足够大的数据组来理解它会成为一种压力/问题。是的，一个特殊的迭代器会是理想的。 - Fractal

我不确定这是否比@jeeva的方法更有效。对于我的数据集，我的基准测试显示这需要大约1-2秒，而Jeeva的方法只需要0.3秒。我的数据集大约有470万个值，其中3642个是唯一的。 - road_to_quantdom

@road_to_quantdom 感谢您的测试！ - jogojapan

Answer 3

遍历 mymm 的所有元素，并将 it->first 存储在一个 set<char> 中。

- Donotalo

---

-1. 它不会提供唯一的键。它会提供所有的键。例如，如果有两个键'a'，你的集合中将会有键'a'，但它并不是唯一的。 - Andrew

@Andrew set 只会保留唯一的元素。它将会给出唯一的键。 - Fiktik

+1，如我在其他答案中所写的那样，使用集合作为注释！;) - Mare Infinitus

@Fiktik：通常唯一意味着某种类型只有一个对象。如果在 multimap 中有两个“a”键，则该键不是唯一的。 - Andrew

我同意两种解释都是可能的。抱歉，在回答被编辑之前无法删除-1。 - Andrew

Answer 4

最简单的方法是将multimap的键放入unordered_set中。

unordered_multimap<string, string> m;

//insert data in multimap

unordered_set<string> s;         //set to store the unique keys

for(auto it = m.begin(); it != m.end(); it++){
    if(s.find(it->first) == s.end()){
        s.insert(it->first);
        auto its = m.equal_range(it->first);
        for(auto itr=its.first;itr!=its.second;itr++){
            cout<<itr->second<<" ";
        }
    }
}

- Gautam Jain

Answer 5

如果你所说的unique是指在multimap中只出现一次的键，那么我认为你可以这样做：

1）构建一个按键排序的list

2）遍历这个列表并找到唯一的键。由于所有重复的键都会在排序后的容器中靠在一起，所以这很简单。

如果你只想要所有的键 - 可以像Donotalo建议的那样使用std::set。

- Andrew

---

为什么要使用排序列表而不是集合？集合已经可以证明唯一性了。 - Mare Infinitus

@MareInfinitus：因为如果multimap中有两个键'a'，那么键'a'将会在集合中，但它不是唯一的。 - Andrew

a是一个关键字，即使它被多次使用，它仍然是需要存储的关键字。至少我理解这个问题不是想要一个未被多次使用的关键字列表，而是一个关键字列表。 - Mare Infinitus

Answer 6

另一个选择是将它们插入到向量中，然后只需使用std::sort和std::unique即可。

template<typename Container> static
std::vector<typename Container::key_type> unique_keys(Container A)
{

    using ValueType = typename Container::key_type;

    std::vector<ValueType> v;

    for(auto ele : A)
    {
        v.push_back(ele.first);
    }

    std::sort(v.begin(), v.end());
    auto it = std::unique(v.begin(), v.end());
    v.resize(distance(v.begin(),it));

    return v;
}

- newandlost

Answer 7

这可以在O(N)的时间复杂度内完成，其中N是您的映射表的大小；您的键不需要具有排序运算符：

template<typename Container>
std::vector<typename Container::key_type> UniqueKeys (const Container &A)
{
std::vector<typename Container::key_type> v;
auto prevIter = A.begin ();

for (auto iter = A.begin (); iter != A.end(); ++iter)
    {
    if (prevIter->first == iter->first)
        continue;

    v.push_back (prevIter->first);
    prevIter = iter;
    }

if (prevIter != A.end ())
    v.push_back (prevIter->first);

return v;
}

- Catriel