为什么std::set::find没有提供提示迭代器？

Question

#include <set>
#include <vector>

using Value = std::vector<int>;

int main()
{
    auto coll = std::set<Value>{};

    // ......
    // Insert many values here.
    // ......

    auto new_value = Value{1, 2, 3};
    auto const pos = coll.find(new_value);

    if (pos != coll.end())
    {
        // Good
        coll.emplace_hint(coll.erase(pos), std::move(new_value));
    }
    else
    {
        // Performance penalty!
        // No hint here, though coll.find(new_value) knows that.
        coll.emplace(std::move(new_value));
    }
}

为什么std::set::find没有提供提示迭代器？

- xmllmx

---

我不确定那个迭代器会是什么样子。或许你可以使用 std::set::lower_bound 代替。 - Ted Lyngmo

Answer 1

std::set::lower_bound()返回的结果可以用作emplace_hint()的提示。因此，只需使用lower_bound()而不是find()，然后检查lower_bound()返回的键是否与您要查找的键匹配，而不是检查find()返回的迭代器是否为end()。

- John Zwinck

---

这个应该宣传得更好一些。或许我只是无知... - undefined

@CostantinoGrana：我有点同意，但实际上，真实世界的代码很少在任何容器中使用“提示”功能，而且追求最佳性能的人可能不会使用std::set。鉴于这个功能很少被使用，更多的宣传似乎是不必要的。 - undefined

谢谢你的回答。如果可以的话，unordered_set 有没有其他的替代方案？ - undefined

Answer 2

考虑迭代器的传递性和对称性，== 运算符可能会带来麻烦。

假设 i1 和 i2 是通过 set 中不同不存在的对象使用 find 检索到的提示。

我们有

• i1 == set.end()
• set.end() == i2

因此，i1 == i2，所以我们期望这种类型的提示在插入时具有相同的行为，但您描述的期望行为是不同的（当通过在要插入的相同值上使用 find 检索到的迭代器传递给 emplace 时，可以提高性能）。

- fabian