C++> STL equal()，equal_range()笔记

equal函数

equal也是C++ STL模板函数，用于比较指定的2个迭代器范围元素是否完全相等。
比较方式：==（判断相等的符号，要求迭代器指向元素支持），或者指定的谓词pred
返回值：只有[first1, last1)所有元素都与[first2, last2)所有元素都相等时，才返回true；否则返回false。
注意：

1. 要求比较的元素支持对应运算符，或者自定义谓词，判断是否相等。
2. 比较的时候，是依照[first1, last1)元素个数来的，要求[first2, last2)元素个数不能小于前者，否则可能产生未定义行为。

头文件algorithm

// 使用== 版本equality (1)
template <class InputIterator1, class InputIterator2>
  bool equal (InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2);

// 使用比较器版本predicate (2)
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
  bool equal (InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2, BinaryPredicate pred); 

示例：

// equal algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::equal
#include <vector>       // std::vector

bool mypredicate (int i, int j) {
  return (i==j);
}

int main () {
  int myints[] = {20,40,60,80,100};               //   myints: 20 40 60 80 100
  std::vector<int>myvector (myints,myints+5);     // myvector: 20 40 60 80 100 // 必须要myvector元素个数 >= myints，否则调用equal可能产生异常行为

  // using default comparison:
  if ( std::equal (myvector.begin(), myvector.end(), myints) )
    std::cout << "The contents of both sequences are equal.\n";
  else
    std::cout << "The contents of both sequences differ.\n";

  myvector[3]=81;                                 // myvector: 20 40 60 81 100

  // using predicate comparison:
  if ( std::equal (myvector.begin(), myvector.end(), myints, mypredicate) )
    std::cout << "The contents of both sequences are equal.\n";
  else
    std::cout << "The contents of both sequences differ.\n";

  return 0;
}

参见：std::equal

equal_range函数

equal_range 是C++ STL模板函数，用于在前向迭代器范围中，查找值等于指定的val的子范围。比如指定迭代器范围[first, last)，找到子范围[lower_bound, upper_bound]满足子范围所有元素都等于val。
前提条件：指定迭代器范围元素必须是有序的。所以用equal_range之前，经常应用sort进行排序。
比较方式：比较可以用2种方式：< ，或指定的比较器comp。
返回值：如果成功找到，就以pair形式返回lower_bound，upper_bound；如果没有找到，子范围的长度就为0，就返回距离val最近且比val大的迭代器（如果有），或者last（如果没有）。

注意：排序的目的是让相同元素连续，而且适合使用二分查找算法。

头文件：algorithm
函数原型

// default (1)
template <class ForwardIterator, class T>
  pair<ForwardIterator,ForwardIterator>
    equal_range (ForwardIterator first, ForwardIterator last, const T& val);

// custom (2)
template <class ForwardIterator, class T, class Compare>
  pair<ForwardIterator,ForwardIterator>
    equal_range (ForwardIterator first, ForwardIterator last, const T& val,
                  Compare comp); 

equal_range的作用相当于

template <class ForwardIterator, class T>
  pair<ForwardIterator,ForwardIterator>
    equal_range (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it = std::lower_bound (first,last,val);
  return std::make_pair ( it, std::upper_bound(it,last,val) );
}

使用示例

// equal_range example
#include <iostream>     // std::cout
#include <algorithm>    // std::equal_range, std::sort
#include <vector>       // std::vector

bool mygreater (int i,int j) { return (i>j); }

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  std::vector<int> v(myints,myints+8);                         // 10 20 30 30 20 10 10 20
  std::pair<std::vector<int>::iterator,std::vector<int>::iterator> bounds;

  // using default comparison(指的是int类型支持的 == ):
  std::sort (v.begin(), v.end());                              // 10 10 10 20 20 20 30 30
  bounds=std::equal_range (v.begin(), v.end(), 20);            //          ^        ^
  // 注意使用equal_range时，必须确保迭代器指定范围有序，或者以指定值20进行了划分，确保与20相等的元素位置连续

  // using "mygreater" as comp （指的是自定义比较器）:
  std::sort (v.begin(), v.end(), mygreater);                   // 30 30 20 20 20 10 10 10
  bounds=std::equal_range (v.begin(), v.end(), 20, mygreater); //       ^        ^

  std::cout << "bounds at positions " << (bounds.first - v.begin());
  std::cout << " and " << (bounds.second - v.begin()) << '\n';

  return 0;
}

因为查找时用的二分查找算法，因此，
时间复杂度：logN次元素比较（N代表first和last距离，也就是元素个数）

参见：std::equal_range