c++ - 迭代 `std::multiset` 的唯一元素

Question

我只需要知道某个东西是否存在以及它存在多少次。我将遍历现有的事物并查询其中有多少存在。

到目前为止，我的实现使用了multiset，我的做法如下:

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 vector 。但他们有时会重复这个值，我想遍历独特的 thing 并为每个独特的东西做一些事情。这个“东西”需要知道这个东西出现在 vector 上的时间。

我上面发布的代码是我现在如何解决我的问题，它似乎不是做我想做的事情的最优雅的方式。

我只是遵循 Stackoverflow 指南:我告诉我的问题是什么，然后我告诉我(尝试过的)解决方案。

如果真的需要一个带问号的句子，那就这样吧:有没有办法在 multiset 上迭代唯一元素？

Answer 1

三种可能的方法:

• 使用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> , 您可以指定一个范围来查找上限。在您的情况下，您已经有一个很好的候选范围开始，因此此方法可能更有效，具体取决于您的标准库中的实现。
• 如果这对您来说是一个真正的性能问题并且以前的解决方案仍然不够好，请考虑切换到 map<thing, unsigned>甚至 unordered_map<thing,unsigned> unsigned在哪里只记录等价物 thing 的数量你有。不过，这意味着要重写您的插入/删除代码。