STL中的查找

摘要:
返回搜索元素的最后一个可放置位置,即“元素值”˃“搜索值”中第一个元素的位置。如果搜索范围中不存在,则返回a.end()。请注意,End()不在搜索范围内。字符串是一种顺序存储结构。其find函数返回下标索引。count函数统计容器中值元素的数量。
一、查找

1.头文件

#include <algorithm>

2.使用方法

1.binary_search:查找某个元素是否出现。O(logn)

a.函数模板:binary_search(arr[],arr[]+size , indx)

b.参数说明:

arr[]: 数组首地址
size:数组元素个数
indx:需要查找的值

c.函数功能: 在数组中以二分法检索的方式查找,若在数组(要求数组元素非递减)中查找到indx元素则真,若查找不到则返回值为假。

2.lower_bound:查找第一个大于或等于某个元素的位置。O(logn)

a.函数模板:lower_bound(arr[],arr[]+size , indx):

b.参数说明:

arr[]: 数组首地址
size:数组元素个数
indx:需要查找的值

c.函数功能: 函数lower_bound()在first和last中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置(注意是地址)。如果所有元素都小于val,则返回last的位置

d.举例如下:

  一个数组number序列为:4,10,11,30,69,70,96,100.设要插入数字3,9,111.pos为要插入的位置的下标,则 /注意因为返回值是一个指针,所以减去数组的指针就是int变量了/
  pos = lower_bound( number, number + 8, 3) - number,pos = 0.即number数组的下标为0的位置。
  
  pos = lower_bound( number, number + 8, 9) - number, pos = 1,即number数组的下标为1的位置(即10所在的位置)。
  
  pos = lower_bound( number, number + 8, 111) - number, pos = 8,即number数组的下标为8的位置(但下标上限为7,所以返回最后一个元素的下一个元素)。
  

e.注意:函数lower_bound()在first和last中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置。如果所有元素都小于val,则返回last的位置,且last的位置是越界的!

返回查找元素的第一个可安插位置,也就是“元素值>=查找值”的第一个元素的位置

3.upper_bound:查找第一个大于某个元素的位置。O(logn)

a.函数模板:upper_bound(arr[],arr[]+size , indx):

b.参数说明:

arr[]: 数组首地址
size:数组元素个数
indx:需要查找的值

c.函数功能:函数upper_bound()返回的在前闭后开区间查找的关键字的上界,返回大于val的第一个元素位置

  例如:一个数组number序列1,2,2,4.upper_bound(2)后,返回的位置是3(下标)也就是4所在的位置,同样,如果插入元素大于数组中全部元素,返回的是last。(注意:数组下标越界)
  返回查找元素的最后一个可安插位置,也就是“元素值>查找值”的第一个元素的位置 。

4.find函数:O(n)

1、algorithm中的函数

其调用形式为
find(start,end,value)
start搜寻的起点,end搜寻的终点,要寻找的value值
容器的表示方法
find(a.begin(),a.end(),value)
数组的表示方法
find(a,a+length,val)
所有的返回,均是迭代器(容器)或指针(数组),而非是直观感觉上的索引下标。如果在查找范围内不存在,返回a.end(),这里需要注意的是,a.end()不在查找范围内。

2、各个容器自己实现的成员函数

vector没有实现find函数,除此之外,常见容器都实现了自己的find函数。
String是这一种顺序存储结构,其find函数返回的是下标索引。set,map,multiset,multimap都不是顺序索引的数据结构,所以返回的是迭代器。

3、如果元素不在

对于返回迭代器的查找,通过判断find(a.begin(),a.end(),value)==a.end(),来判断元素是否存在

对于string,通过a.find(val)==string::npos判断

5.count函数:0(n)

1)count(first,last,value):first是容器的首迭代器,last是容器的末迭代器,value是询问的元素,整个函数返回int型。count函数的功能是:统计容器中等于value元素的个数。

2)count_if(first,last,comp) (在comp为true的情况下计数) 或者 count_if(first,last,value,comp) (这个是在comp为true的情况下统计容器中等于value的元素):first为首迭代器,last为末迭代器,value为要查询的元素,comp为比较bool函数,为true则计数,函数返回型是int。

/注:此两个函数复杂度是线性的,适用于小规模运算。/

免责声明:文章转载自《STL中的查找》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇nopCommerce 数据缓存Oracle10g 表分区下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

Linux last命令后面的时间

gtmm@GTMM:/$ last rebootreboot system boot 2.6.38-8-server Thu Jun 7 13:29 - 12:34 (3+23:05) wtmp begins Tue Jun 5 09:42:13 2012gtmm@GTMM:/$ last rebootreboot system boot 2.6.38-8...

php实现SESSION跨域

稍微大一点的网站,通常都会有不只一个服务器,每个服务器运行着不同的功能模块或者不同的子系统,他们使用不同的二级域名,比如www.a.com、i.a.com、bbs.a.com。而一个整体性强的网站,用户系统是统一的,即一套用户名、密码在整个网站的各个子系统中都是可以登录使用的。各个服务器共享用户数据是比较容易实现的,只需要在后端放个数据库服务器,各个服务器...

【DB宝46】NoSQL数据库之CouchBase简介、集群搭建、XDCR同步及备份恢复

目录 一、 CouchBase概述 1.1、简述 1.2、CouchDB和CouchBase比对 1.2.1、CouchDB和CouchBase的相同之处 1.2.2、CouchDB和CouchBase的不同之处 1.3、CouchBase的社区版和企业版的区别 1.4、Couchbase名词术语 1.5、Couchbase和RMDB对比...

Huawei-R&amp;amp;S-网络工程师实验笔记20190607-STP生成树协议(基本配置、桥优先级、根桥选举、根端口、路径开销、边缘端口)

》Huawei-R&S-网络工程师实验笔记20190607-STP生成树协议(基本配置、桥优先级、根桥选举、根端口、路径开销、边缘端口) 》》实验开始,先上拓扑图参考: <Huawei>system-view Enter system view, return user view with Ctrl+Z. [Huawei]sysna...

.htaccess 文件使用手册

1、apache开启.htaccess vi编辑httpd.conf文件,修改这两个地方: (1) Options FollowSymLinks AllowOverride None 改为 Options FollowSymLinks AllowOverride All (2)去掉下面的注释 LoadModule rewrite_module module...

Oracle如何迁移、管理、清除Audit数据(AUD$和FGA_LOG$表)

Oracle如何迁移、管理、清除Audit数据(AUD$和FGA_LOG$表) 前言 版本:11.2.0.4.0。 Oracle 11G中没特殊要求还是要建议关闭审计功能:alter system set audit_trail = none scope=spfile  sid='*'; 由于默认审计数据的AUD$和FGA_LOG$表在system表空间,...