C++ 如何获取多映射中的所有唯一键
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/11554932/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How can I get all the unique keys in a multimap
提问by AJ.
I have a multimap and I want get all the unique keys in it to be stored in a vector.
我有一个多映射，我想将其中的所有唯一键存储在一个向量中。
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));
How can I do this? there is way to count number of elements with a key but none to count number of unique keys in a multimap.
我怎样才能做到这一点？有一种方法可以计算带有键的元素数量，但没有方法可以计算多映射中唯一键的数量。
Added:By unique I mean all the keys in multimap once - they can be repeated or occur once in multimap.
补充：唯一我的意思是 multimap 中的所有键一次 - 它们可以在 multimap 中重复或出现一次。
So unique keys here are - x, yand z
所以这里的唯一键是 - x, y和z
回答by Jeeva
I tried this and it worked
我试过了，它奏效了
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;
}
回答by jogojapan
Since the entries of a std::multimap<>are implicitly sorted and come out in sorted order when iterating through them, you can use the std::unique_copyalgorithm for this:
由于 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;
}
The extra work added by this is linear in the number of entries of the multimap, whereas using a std::setor Jeeva's approach for deduplication both add O(n log n) computational steps.
由此增加的额外工作与多重映射的条目数量呈线性关系，而使用 astd::set或 Jeeva 的重复数据删除方法都增加了 O(n log n) 计算步骤。
Remark:The lambda expression I use assumes C++11. It is possible to rewrite this for C++03.
备注：我使用的 lambda 表达式假定 C++11。可以为 C++03 重写它。
回答by Donotalo
Iterate through all elements of mymm, and store it->firstin a set<char>.
遍历 的所有元素mymm，并存储it->first在set<char>.
回答by Gautam Jain
easiest way would be to put the keys of multimap in an unordered_set
最简单的方法是将 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<<" ";
}
}
}
回答by Andrew
I think you can do something like this in case by uniqueyou mean the key that is contained in the multimaponly once:
我认为你可以做这样的事情，以防unique你的意思是包含在multimap唯一一次的密钥：
1) construct a sorted listof all keys in your map
1）构造一个排序list的地图中的所有键
2) iterate over the list and find unique keys. It's simple since all duplicates will be near each other in a sorted container
2）遍历列表并找到唯一键。这很简单，因为所有重复项都将在已排序的容器中彼此靠近
If you want just all keys - use std::setas Donotalo suggested
如果你只想要所有的钥匙 -std::set按照 Donotalo 的建议使用
回答by newandlost
Other option would be to insert them into a vector and then just use, std::sortand std::unique
其他选择是将它们插入到一个向量中，然后就可以使用，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;
}
回答by Catriel
This can be done in O(N) where N is the size of your map; your keys do not need to have an order operator:
这可以在 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;
}
