13

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

到目前为止，我的实现使用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;
}

澄清

我有一个向量things。但他们有时会重复这个值，我想迭代 unique things 并为每个独特的做一些事情。这个“东西”需要知道它thing出现在向量上的时间量。

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

我只是遵循 Stackoverflow 指南：我告诉我我的问题是什么，我告诉我（尝试过的）解决方案。

如果真的需要一个带问号的句子，你就去吧：有没有办法在 a 上迭代独特的元素multiset？

4

1 回答 1

16

三种可能的方法：

  • 用于std::unique创建唯一值的临时集合。这可能会使代码更具可读性，但效率较低。
  • 通过使用std::multiset::upper_bound而不是增量来推进你的迭代器：for( auto each = a.begin(); each != a.end(); each=a.upper_bound(*each))- 这样你就不需要if检查你的循环内部，而且它的大小保证是对数的。很酷（在我查找之前不知道）。对于以下建议，所有功劳归于@MarkRansom：使用std::upper_boundfrom <algorithm>，您可以指定查找上限的范围。在您的情况下，您已经有一个很好的候选范围开始，因此此方法可能更有效，具体取决于您的标准库中的实现。
  • 如果这对您来说是一个真正的性能问题，并且以前的解决方案仍然不够好，请考虑切换到map<thing, unsigned>甚至只是跟踪您拥有的等效 s数量的unordered_map<thing,unsigned>地方。这意味着尽管重写您的插入/删除代码。unsignedthing
于 2013-02-07T14:42:29.527 回答