为什么 std::includes 在条件中使用小于运算符而不是相等运算符?

Question

我有这个算法的实现std::includes来自 https://en.cppreference.com/w/cpp/algorithm/includes

template<class InputIt1, class InputIt2>
bool includes(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2)
{
for (; first2 != last2; ++first1)
{
if (first1 == last1 || *first2 < *first1)
return false;
if ( !(*first1 < *first2) )
++first2;
}
return true;
}

• 它工作得很好，但是我想知道为什么在循环内的第二个if statement中使用小于运算符<而不是相等运算符==？

• 这是我的类似实现：

  template<class InputIt1, class InputIt2>
  bool including(InputIt1 first1, InputIt1 last1,
  InputIt2 first2, InputIt2 last2){
  while (first2 != last2){
  if (first1 == last1 || *first2 < *first1)
  return false;
  if ( *first1 == *first2 )
  ++first2;
  ++first1;
  }
  return true;
  }
  
  int main(){
  std::vector<int> v{1, 5, 7, 23, 24, 57, 77};
  //  std::sort(v.begin(), v.end());
  int a[]{7, 24};
  std::cout << including(v.begin(), v.end(), a, a + 2) << 'n'; // 1
  std::cout << std::includes(v.begin(), v.end(), a, a + 2) << 'n'; // 1
  }
  

• 所以我得出的结论是：

• 第一个条件：*first2 < *first1-> 返回 false。

• 第二个条件：!(*first1 < *firs2)->*first1 >= *first2

因此，*first1 > *first2导致算法返回false，*first1 >= *first2导致firsts2递增，因此first2递增的唯一条件是当*first1 == *first2那么，为什么使用小于<以及否定运算符!运算符，而不是像我的实现中那样使用直接等于运算符==呢？

• 这仅仅是为了某种可读性和兼容性吗？
• 我的分析正确吗？谢谢！

Answer 1

该算法正在处理排序范围。您需要一个<关系来对一系列元素进行排序，但不一定是==关系，因此使用<带来的限制更少，并且更通用。

---

还要考虑到大多数算法和容器使用<而不是==来比较元素。例如，请参阅std::map：

在标准库使用比较要求的所有地方，唯一性都是通过使用等价关系来确定的。在不精确的术语中，如果两个对象 a 和 b 的比较都不比另一个少：！comp(a， b) &&！comp(b， a)。

映射中的两个键在!comp(a,b) && !comp(b,a)时被视为等效(不相等！大多数时候这与a == b相同，但不一定。

Answer 2

所有与元素排序相关的标准算法都只使用<运算符，而不使用<=、>、>=、==或!=运算符。

这意味着一个应该支持排序的类类型只需要定义operator<，而其他的可能不需要。

但另一个原因是，大多数排序/排序算法并不假设对象是"完全有序的"，这意味着a<b或a==b或a>b中的一个总是正确的。相反，他们假设它们具有严格的弱排序，其中具有!(a<b) && !(b<a)真实形式等价类但不一定相等的元素对。

例如，不区分大小写的 ASCII 字符串的简单类：

#include <string>
#include <strings.h>
class ci_string {
public:
explicit ci_string(const char* s) : m_str(s) {}
const char* c_str() const { return m_str.c_str(); }
friend bool operator<(const ci_string& s1, const ci_string& s2)
{ return strcasecmp(s1.c_str(), s2.c_str()) < 0; }
friend bool operator>(const ci_string& s1, const ci_string& s2)
{ return s2 < s1; }
friend bool operator==(const ci_string& s1, const ci_string& s2)
{ return s1.m_str == s2.m_str; }
friend bool operator!=(const ci_string& s1, const ci_string& s2)
{ return !(s1 == s2); }
private:
std::string m_str;
};

(不适用于多字节编码或非 ASCII 字母。

现在ci_string("HELLO")、ci_string("HeLLo")和ci_string("hello")都是等价的，但不相等。对于以下代码：

std::vector<ci_string> v1{
ci_string("alpha"), ci_string("beta"), ci_string("gamma"),
ci_string("delta"), ci_string("epsilon")};
std::vector<ci_string> v2{ci_string("BETA"), ci_string("Delta")};
bool c = std::includes(v1.begin(), v1.end(), v2.begin(), v2.end());

仅使用<

的实现将返回 true，但使用==的实现可能会返回 false。(这个结果是否真的对"包含"有意义是一个有趣的问题，但这就是它的定义。