vector<int>迭代器p,然后调用find(v.begin(),v.end(),3)
这个是干嘛?就是在整个容器,整个V容器上面去查找3这个元素
呃,然后下面这条语句就判断是不是找到了。
那在1,2,3,4里面找3呢当然是能够
找得到的,对吧?所以说这个时候,呃,P就会指向被找到的那个元素,也就是3
那你输出*p的话,当然输出的结果就是3。
啊,那我们再来看看find这边用到的这个,这个区间
它查找的区间v.begin,v.end,它是左闭右开的,也就是说v.begin
是位于查找区间之内,但是这个呢,v.end不位于查找区间
之内,这是很合理的对吧?因为v.end本来就v里面最后一个元素的后面的那个位子。
也就是说v.end实际上没指向任何有效的元素,那在 find在进行查找的时候,v.end并不位于查找范围之内也就是很合理的。
那实际山在STL的各种算法里面 只要是提到了这个区间,啊这个区间都是左闭右开的。
再看下面,呃 p等于find v.begin v.end
9,啊,就在V里面去查找9这个元素,v里面有什么啊?是1,2,3,4,那当然就找不到对吧
所以我们看,看到,如果v等于,啊,如果P等于v.end那就说明找不到,这个输出not
found,那当然确实会输出not found 找不到9,。然后p等于find v.begin加1
然后v.end减2,啊,就是在v.begin加1到v.end减2这个区间里面去查找
元素1,但是要注意的v.end减2这个,元素实际上并不在查找范围之内。
那我们看到整个容器是1,2,3,4,那v.
,v.begin加1是什么啊?就是2对吧?那v.end减2是什么呢
呃,这个4是v.end减1,3是v.end减2,啊所以v.end减2是3
但是由于v.end减2实际上并不位于查找区间范围之内
也就是说查找区间2,3是个左闭右开的,但真正有效的元素实际上就只有一个2
所以,你在这里面去,嗯,进行查找1的话,啊,实际上是找不到的。
那找不到的话,这个时候P的值会是什么呢?我们说
p的值它会等于这个查找区间的终点,也就是说p的值是 等于一个迭代器它指向什么?指向这个3
那p当然就不等于end了,所以你输出*p的时候呢就会输出3
呃因为这个时候查找区间的终点实际上就是这个,这个3了。
现在再看int*pp等于find array array加4, 20
啊,这个时候我们在一个普通数组里面也能进行,用find进行查找 这个时候数组的名字就是迭代器,因为数组的名字就是int
*array这个指针 呃,在这个容器里面进行查找,嗯然后
查找区间好像是从array到array加4,array加4并不位于
查找范围内,在这里面查找20,呃,然后呢,我们就
根据查找的结果输出这个*pp,啊输出的结果呢就是这个
20,因为在这个array里面能找到20,啊,那么array定义的它里面是有20的
那我们知道在这个STL里面啊,这个关联容器内部的元素是从小到大排序的。
然后呢有些算法吧它要求它操作的区间是从小到大排序的,这类算法我们称之为“有序区间算法”。
比如说binary_search折半查找,它就要求查找的那个区间 必须是从小到大排好序的,然后才能进行二分查找
然后呢有些算法它会对区间进行从小到大排序,这称为“排序算法”
比如sort,它就能够把处理的那个区间变成从小到大排好序。
还有一些其它算法也会用到这个什么大小的这个这个概念
但但要注意了我这里所说的从小到大可不见得就是什么1一定是小于2这么简单
这个大和小的定义程序员可以自己去设定的
比方说程序员可以规定,哎我在这个呃,呃,容器里面
从小到,这容器里虽然放的都是整数,但我这个从小到大的意思是
按照个位数从小到大排序,也就是说这两个整数谁的个位数小谁就算小 这就叫做自定义大小的这个概念
呃也就是说前面这里说的所有的从小到大,从小到大啊,它的具体的含义都是可以发生变化的
对于两个整数你也可以说绝对值大的就算是小,绝对值小的就算是大,你也可以这么定义,没有问题的。
但是呢在缺省的情况下,就是你没有对这个大小给出任何
自己定义的情况下,在缺省的情况下,那么下面三个说法是等价的
呃,如果我们说x比y小,这个说法就等价于表达式x小于y为真
这也等价于y比x大。哦,这三个说法是等价的。
在缺省的你没有自己定义大小的概念的这个情况下
以下三个表达,以下三个说法等价,然后
在STL里面x和y相等也不见得就是我们那么简单理解的相等的概念。
啊,就有的时候x和y相等,它等价于表达式x等等y为真
在什么情况下,嗯,是这样子的呢?
比如说我们在没有经过排序的区间上进行的算法,比如顺序查找find,我们说在一个区间里面
查找某一个元素,那你要查找的那个,呃查找某一个值,那你要查找那个元素肯定要等于这个值,对吧
那这个时候这个等于就是用等等这个运算符来进行判断的
但有的时候呢x和y相等
它就不再等价与上面的这个,呃,x等等y为真了,它跟这个等等
这个,呃,运算没有关系 有的时候x和y相等,它等价于下面这个描述
就是x小于y和y小于x同时为假,啊
注意这里的小于呢,它还未必就是小于号的那个意义,在这里的小于
也是可以自定义的,反正你在自定义的,就是说有些情况下你自定义了
小于的含义,然后在然后呢x和y相等,它就变成x如果
小于y,和y小于y x同时都不成立,那我们就认为x和y是相等的
哪怕x等等y这个表达式实际上它的访问值是false,我们也认为
x和y是相等的,在什么情况下会是这样呢?啊就是
对有序区间上,比如说birary_search来说 x和y相等,就是上述的这个含义。
还有对于关联容器自身的成员函数find来说,x和y相等,也是这里所说的含义。
呃,那关联容器就是用来查找的,查找速度快,但是你不能用find算法
或者是什么其他的birary_search算法去查找关联容器,关联容器它自身带有成员函数find 可以用来进行查找。
那下面我们就看一个这个关于这个“相等”的概念 的这个这个演示,啊,我们这里有个classA
呃,它里面有成员变量v,然后呢在这里我们
呃,重载了小于运算符,规定了,呃,两个classA
对象比大小的规则,在这运算符里面呢我们先输出了待比较的两个元素的这个
呃,这v的值,然后返回false,返回false意味着什么啊
意味着任何两个classA的对象,一个都不会小于另外一个
任意两个classA的对象x,y,x小于y总是不成立的,y小于x也总是不成立的。
然后我们也定义了一个,一个等等号,呃,它它用来判断两个classA的对象是否相等
呃,呃那是否相等的这个规则比较传统,啊,就是两个的V相等,它就是相等了。
好了,我们在定义了这种小于和等于这种规则的前提下,我们看看用birary_search会发生什么事情
注意,再强调一遍,这里的小于被定义成任何两个classA的对象
一个都不会小于另外一个,好我们在main里面,啊
定义了这样一个classA的数组,呃它们是A1,A2,A3,A4,A5
然后我们用birary_search在这个数组里面去查找A9这个元素
是二分查找 那你想是不是应该能找得到呢?这是,数组里面是1,2,3,4,5,你要查找的是A9,当然应该找不到,对吧
也就是说,birary_search这个函数调用它的返回值应该是0,是false才对。
但实际上的结果呢却是毁三观的,呃它的返回值是1 它告诉你在A1到A5这里面找到了A9
为什么会是这样的结果呢?我们看到输出结果前面还有,前面这四行
也就是说,我们看到在这个程序运行的过程中
呃,程序运行的过程中呢这个,呃,等等号并没有
被调用,这个小于号被多次调用
那也就是说,呃,这个birary_search在执行的过程中,它判断呃这个
数组里面有没有哪一个元素的值跟A9相等,它用的不是等等号 用的是小于号
这就是我们前面所说的那个相等的概念了,就是说如果x小于y不成立,y小于x也不成立
那就认为x和y相等 根据x等等y没有关系,这就是birary_search工作的这个原理。
所以我们看到,呃,birary_search,birary_search首先
看看3小于9是不是成立?结果是不成立,不成立的话
birary_search就应该,就认为我应该在,呃3前面那一半去找,所以它又去找
2小于9是不是成立?又不成立,那它认为应该再到前面一半去找,于是就
判断1小于9是不是成立,还是不成立,那这时候已经不能再向前啦,已经没有啦
所以,birary_search就判断9小于1是不是成立?也不成立,好了,那1小于9不成立,9小于1也不成立
那birary_search就认为1和9是相等的,所以它就认为,呃找到了A9,于此输出一个它的返回值就是1
看上去是不是很奇怪,但它就是这么工作的。