34.了解算法对容器的要求

前言

 
并非所有算法都可以用于任意区间。如果你违背了算法要求，编译器会提供给你一个复杂且难以理解的报错信息。

---

有序区间算法

 
以下算法只能作用于有序区间:

• binary_serach
• lower_bound upper_bound equal_range
• set_union set_intersection set_difference seT_symmetric_difference
• merge inplace_merge
• includes

另外，unique与unique_copy一般作用于有序区间，虽然它们对此不作要求。

为何需要有序区间

（建议阅读数据结构·向量篇，其练习几乎解答了下述所有问题）

• binary_search，lower_bound，upper_bound以及equal_range
  上述算法均基于二分查找，因此必须提供有序区间。
  其具体效率实际上取决于迭代器。如果不支持随机访问，其效率会由对数时间退化至线性时间。
• set_union，set_intersection，set_difference，set_symmetric_difference
  如果不提供有序区间，则它们无法在线性时间内完成工作。
• merge与inplace_merge
  提供了单遍合并排序。
• includes
  检测是否一个区间的所有对象也在另一个区间中，有序保证了其线性时间的效率
• unique
  其功能是去重，但为了保证元素值唯一，你必须保证这些相似的元素一个接着一个，这也就是排序的一种弱化形式。（22211333）

---

确保算法的排序方式与容器的排序方式相同

反例

vector<int> v;
sort(v.begin(), v.end(), greater<int>());//降序排列
bool a5Exists = binary_search(v.begin(), v.end(), 5);//binary_search默认升序排列

这段代码将直接导致未定义行为。

正确使用方式

bool a5Exists =binary_search(v.begin(), v.end(), 5. greater<int>());

---

判同验证

 
所有需要有序区间的算法通过等价来判断两个值是否相同，类似于关联容器。unique系列通过相等来判断。