为什么 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 不提供提示迭代器？

Answer 1

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

Answer 2

在考虑迭代器的 == 运算符的传递性和对称性时，这会很麻烦。

让 i1 和 i2 成为通过 find 为 set.

中不同的不存在对象检索的提示

我们有

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

因此 i1 == i2，所以我们希望这种提示在插入时具有相同的行为，但是您描述的所需行为是不同的行为（通过 emplace 时改进的性能通过 find 检索的迭代器与您正在放置的值相同）。

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

Why does std::set::find not provide a hint iterator?

c++

performance

standards

c++11

c++17