Question

c++ stl 中 lower_bound 的第四个参数的用法

是这样子的，我有一个结构体数组，每个存储了一对字符串，还有两个整型数组，分别存储的是结构体数组的下标。
我使用sort方法为两组下标按结构体中字符串的大小排序，以此作为索引。
然后我想使用lower_bound()方法查找某个字符串的下标，然后我就弄不能明白第四个参数也就是比较函数应该怎么写了，请帮忙赐教！
题目：http://acm.hdu.edu.cn/showproblem.php?pid=1880

Answer 1

使用find_if()函数查找到第一个符合条件的数据后,it就指向了该符合条件的数据,
对于vector的iterator使用++操作时,就指向了当前的下一个元素,但是,下一个元素
并不一定是满足条件的数据,所以不能使用++操作来指向下一个元素,而是要用循环
来获取所有满足条件的元素,如下:
...
vector<int>::iterator it = find_if(intVector.begin(), intVector.end(), fun);
if ( it != intVector.end() )
{
//此时it指向第一个满足条件的元素了
}

while ( it != intVecotr.end() )
{
it++;//让it指想满足条件的元素的下一个元素,即,再次搜索时从满足条件的元素的下一个位置开始
it = find_if(it, intVector.end(), fun);
if ( it != intVector.end() )
{
//此时的it是再次找到的符合要求的元素
}
}
...

=====================================
别的办法最简单的就是排序了,你自定义一个针对你的数据类型做一个排序函数,排好序后,符合你要求的元素就排到了一起了,找到第一个符合你要求的元素后,就可以使用++来挨个访问他们,直到访问到不符合你要求的元素为止.

Answer 2

使用find_if()函数查找到第一个符合条件的数据后,it就指向了该符合条件的数据,
对于vector的iterator使用++操作时,就指向了当前的下一个元素,但是,下一个元素
并不一定是满足条件的数据,所以不能使用++操作来指向下一个元素,而是要用循环
来获取所有满足条件的元素,如下:
...
vector<int>::iterator it = find_if(intVector.begin(), intVector.end(), fun);
if ( it != intVector.end() )
{
//此时it指向第一个满足条件的元素了
}

while ( it != intVecotr.end() )
{
it++;//让it指想满足条件的元素的下一个元素,即,再次搜索时从满足条件的元素的下一个位置开始
it = find_if(it, intVector.end(), fun);
if ( it != intVector.end() )
{
//此时的it是再次找到的符合要求的元素
}
}
...

=====================================
别的办法最简单的就是排序了,你自定义一个针对你的数据类型做一个排序函数,排好序后,符合你要求的元素就排到了一起了,找到第一个符合你要求的元素后,就可以使用++来挨个访问他们,直到访问到不符合你要求的元素为止.

Answer 3

m.lower_bound(键) 返回值指的是某个键的迭代器（若该键不存在，则返回挨着这个键的下一个键的迭代器）， m.upperbound（键）的返回值是这个键（无论该键是否存在）都返回挨着这个键的下一个键的迭代器
在map里面 m.lower_bound(键) 就是大于或等于键值的第一个迭代器， m.lower_bound(键) 是大于键值的下一个迭代器。
比方说
（键1， 值2）
（键2， 值4）
（键4， 值9）
（键5， 值9）
若m.lower_bound(3) 由于有键3，所以的他值就是键3 的迭代器
m.lower_bound(3) 无论有没有键3，他都是键4的迭代器

再比如
（键1， 值2）
（键2， 值4）
（键4， 值9）
（键5， 值9）
若m.lower_bound(3) 由于没有键3，所以的他值就是键4 的迭代器

----------------------------------------------分割线--------------------------------
若是在multimap中
由于multimap的键值是可以重复的，同一个键对应多个值。
m.lower_bound 指的是某个键的第一个值的迭代器， upperbound指的是这个所有相同键的最后一个值的下一个值的迭代器；
比如
（键1， 值2）
（键2， 值4）
（键2， 值7）
（键2， 值8）
（键4， 值9）
（键5， 值9）
m.lower_bound（2）指的是 （键2， 值4）的迭代器。
而m.upperbound( 2 ) 指的是 （键4， 值9）的迭代器