迭代在`std :: multiset`的唯一元素 [英] Iterating over unique elements of `std::multiset`
问题描述
我需要的只是知道是否有东西存在以及存在的次数。
All I need is to know if something exists and how many times it exist. I will iterate over the existent things and query how much of that exists.
我的实现目前使用 multiset
我做如下:
My implementation so far uses multiset
, I do as follow:
std::multiset<thing> a;
auto previous = a.end();
for( auto each = a.begin(); each != a.end(); ++each ) {
if( previous == a.end() || *previous != *each ) {
a.count(*each);
}
previous = each;
}
澄清
我有一个向量 thing
s。但是他们有时重复的价值,我想迭代独特的东
s和每个独特的做某事。这个东西需要知道这个东西
出现在向量上的时间。
Clarifications
I have a vector of thing
s. But they repeat the value sometimes, I want to iterate over unique thing
s and for each unique do something. This "something" needs to know the amount of time this thing
appears on the vector.
上面是我现在解决我的问题,它似乎并不是最优雅的方式来做我想要的。
The code I posted above is how I am resolving my problem right now, it does not seems to be the most elegant way to do what I want.
我只是遵循Stackoverflow准则:我告诉我的问题是什么,我告诉我的(尝试的)解决方案。
I am just following the Stackoverflow guidelines: I tell what is my problem, and I tell my (tried) solution.
如果一个带有问号的句子真的需要,你去:通过 multiset
?
If a sentence with a question mark is really needed, there you go: Is there a way to iterate over unique elements over a multiset
?
推荐答案
迭代独特元素三种可能的方法:
Three possible approaches:
- 使用
std :: unique
创建唯一值的临时集合。 - 使用
std :: multiset :: upper_bound
提高迭代器的效率。而不是增量:for(auto each = a.begin(); each!= a.end(); each = a.upper_bound(* each))
您不需要if
检查您的循环内容,并且保证大小对数。很酷(不知道,在我看起来之前)。对于以下建议,所有的信用到 @MarkRansom :使用std :: upper_bound
从< algorithm> code>,可以指定一个范围来查找上限。在你的情况下,你已经有一个很好的候选人的范围的开始,所以这种方法可能会更有效率,这取决于在标准库中的实现。
- 如果这是一个真正的性能问题为你和以前的解决方案仍然不够好,考虑切换到
map< thing,unsingned>
或甚至unordered_map< thing ,unsigned>
其中unsigned
只是跟踪等效有。这意味着重写您的插入/删除代码虽然。
- Use
std::unique
to create a temporary collection of unique values. This might make the code a little more readable, but less efficient. - Advance your iterator by using
std::multiset::upper_bound
rather than increments:for( auto each = a.begin(); each != a.end(); each=a.upper_bound(*each))
- that way you don't need theif
check insider your loop, plus it is guaranteed to be logarithmic in size. Pretty cool (didn't know that before I looked it up). For the following suggestion, all credit goes to @MarkRansom: Usingstd::upper_bound
from<algorithm>
, you can specify a range in which to look for the upper bound. In your case, you already have a good candidate for the start of that range, so this method is likely to be more efficient, depending on the implementation in your standard library. - If this is a real performance problem for you and the previous solution still isn't good enough, consider switching to
map<thing, unsingned>
or evenunordered_map<thing,unsigned>
where theunsigned
just keeps track of the number of equivalentthing
s you have. That implies rewriting your insertion/deletion code though.
这篇关于迭代在`std :: multiset`的唯一元素的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!