c++ - 如何获取多图中的所有唯一键

Question

我有一个多图，我希望将其中的所有唯一键存储在一个向量中。

  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

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

Answer 2

由于 a 的条目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;
}

由此增加的额外工作与多重映射的条目数量呈线性关系，而使用 astd::set或 Jeeva 的重复数据删除方法都增加了 O(n log n) 计算步骤。

备注：我使用的 lambda 表达式假定 C++11。可以为 C++03 重写它。

Answer 3

遍历 的所有元素mymm，并存储it->first在set<char>.

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<<" ";
        }
    }
}

Answer 5

我认为你可以做这样的事情，以防unique你的意思是包含在multimap唯一一次中的密钥：

1）在你的地图中构造一个排序list的所有键

2）遍历列表并找到唯一键。这很简单，因为所有重复项将在排序容器中彼此靠近

如果你只想要所有的钥匙 -std::set按照 Donotalo 的建议使用

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

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