在 std::set 中查找元素

Question

鉴于我有一个 std::set，我如何确定集合中的一个元素是否在另一个元素之前。例如，像这样的 -

bool before(const std::set &s, const int first, const int second) const {
  auto it_first = s.find(first);
  auto it_second = s.find(second);
  return it_first <= it_second;
}

上面的代码不起作用，因为 <= 没有为双向迭代器定义，但是如何做这样的事情呢？

Answer 1

A set 按 operator< 排序其元素（默认情况下）。比较器本身可以通过 key_comp or value_comp 检索。因此，如果两个元素都在集合中，则顺序由元素本身定义 - 您不需要迭代器：

return s.key_comp()(first, second);

如果一个或两个都不在集合中，那么这取决于您在这些情况下想要做什么：

if (s.count(first)) {
    if (s.count(second)) {
        return s.key_comp()(first, second);
    }
    else {
        /* no second */
    }
}
else {
    /* no first, possibly second */
}

Answer 2

如果您希望寻找比 std::set 更通用的解决方案，此方法适用于具有 forward 迭代器的任何容器：

template <class T>
bool before( const T &cont, typename T::const_iterator first, typename T::const_iterator second )
{
    for( auto it = cont.begin(); true; ++it ) {
        if( it == first ) return true;
        if( it == second ) return false;
    }
 }

假设 first 和 second 是有效的迭代器。现在您可以对 std::set 和 std::map:

进行更优化的专业化

return cont.key_comp()( *first, *second );

对于具有随机访问迭代器的容器：

return first < second;

在 std::set 中查找元素

Finding elements in std::set

c++

stl

stdset

c++11