寒鸽儿のBlog

有些STL里的东西总是要忘记 , 故而开个坑 , 用到的时候存一下 , 随缘更新。

有序序列操作

二分

ForwardIterator lower_bound(ForwardIterator _First, ForwardIterator _Last, const Type& _Val, BinaryPredicate _Comp)
ForwardIterator upper_bound(ForwardIterator _First, ForwardIterator _Last, const Type& _Val, BinaryPredicate _Comp)
Boolean binary_search(ForwardIterator _First, ForwardIterator _Last, const Type& _Val, BinaryPredicate _Comp)

binary_search()返回 true/false 表示 能/不能 搜到某个值 , 基本上用不到。

讨论 lower_bound() 和 upper_bound() 。

前三个为必选参数。_First 和 _Last 两个迭代器指定了查询区间。 _Val 指定了查询的量。 _Comp 为比较器(可选参数)。

在 $[\_First, \_Last)$ 区间中查找。lower_bound表示可以取等。upper_bound表示严格大于/小于。

第四个参数默认的情况下 , 原区间需已经按照升序排列。lower_bound()查找第一个 $\geqslant key$ 的元素并返回其迭代器 , 如果找不到(即全部[first, last)中的元素 $<key$ ) 则 return _Last。upper_bound() 查找第一个 $>key$ 的元素并返回其迭代器 , 找不到则return _Last。

(以下所提及的"第一个"定义为在不满足条件的元素和满足条件的元素交界处的满足条件的元素)。

若在降序区间查找第一个 $\geqslant$ 或者 $>$ 则需要传入一个反序的比较器。例如 greater<Type>() 。相当于重新定义了大小关系。

若在升序区间查找第一个 $\leqslant$ 或者 $<$ , 同样可以传入反序比较器重新定义大小关系。

(具体的可以画图 greater<Type>() 相当于把图中走向取反来推 , 记住第一个是分界处的元素)。

总结 :

1. 两者的区别在于等号(lower取等)。
2. 默认 $> / \geqslant$ 。
3. greater<type>() 调成小于。
4. 返回指针(需要减去头指针得到下标) , 找不到return _Last。

容器

vector

vector::assign()

void assign(const_iterator first, const_iterator last);
void assign(size_type n, const T& x = T());
vector::assign()将原vector清空 , 并且赋值为iterator指定的区间值(第一个)或者 $n$ 个T(第二个)。