泛型算法，排序的相关操作，lower_bound、upper_bound、equal_range
2024-08-26 07:57:35
body, table{font-family: 微软雅黑; font-size: 13.5pt}
table{border-collapse: collapse; border: solid gray; border-width: 2px 0 2px 0;}
th{border: 1px solid gray; padding: 4px; background-color: #DDD;}
td{border: 1px solid gray; padding: 4px;}
tr:nth-child(2n){background-color: #f8f8f8;}
|
template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value ); 返回第一个不小于（>=）指定的数的迭代器。如果没找到就返回last 这个版本内部比较默认使用<
|
template< class ForwardIt, class T, class Compare >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );
这个版本内部比较默认使用comp函数
|
|
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void print(vector<int>& ve)
{
for(auto elem:ve)
cout<<elem<<" ";
cout<<endl;
}
int main()
{
//容器有序
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> ve1(arr,arr+10);
print(ve1);
auto it = lower_bound(ve1.begin(),ve1.end(),2);
cout<<*it<<endl;
auto it2 = lower_bound(ve1.begin(),ve1.end(),11);
if(it2==ve1.end())
{
cout<<"not found!"<<endl;
}
//容器无序
int arr2[10] = {2,1,4,3,6,8,5,7,9,10};
vector<int> ve2(arr2,arr2+10);
print(ve2);
auto it3 = lower_bound(ve2.begin(),ve2.end(),5);
cout<<*it3<<endl;
}
//1 2 3 4 5 6 7 8 9 10
//2
//not found!
//2 1 4 3 6 8 5 7 9 10
//6
|
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void print(vector<int>& ve)
{
for(auto elem:ve)
cout<<elem<<" ";
cout<<endl;
}
bool comp(const int& a,const int& b)
{
return a<b; //从小到大
}
int main()
{
//容器有序
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> ve1(arr,arr+10);
print(ve1);
auto it = lower_bound(ve1.begin(),ve1.end(),2,comp);
cout<<*it<<endl;
print(ve1);
auto it2 = lower_bound(ve1.begin(),ve1.end(),11,comp);
print(ve1);
if(it2==ve1.end())
{
cout<<"not found!"<<endl;
}
//容器无序
int arr2[10] = {2,1,4,3,6,8,5,7,9,10};
vector<int> ve2(arr2,arr2+10);
print(ve2);
auto it3 = lower_bound(ve2.begin(),ve2.end(),5,comp);
print(ve2);
cout<<*it3<<endl;
}
//1 2 3 4 5 6 7 8 9 10
//2
//1 2 3 4 5 6 7 8 9 10
//1 2 3 4 5 6 7 8 9 10
//not found!
//2 1 4 3 6 8 5 7 9 10
//2 1 4 3 6 8 5 7 9 10
//6
|
|
template< class ForwardIt, class T >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );
返回第一个大于(>)指定的数的迭代器指针。内部元素之间比较规则采用<
|
template< class ForwardIt, class T, class Compare >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );
内部元素之间比较规则采用comp
|
|
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void print(vector<int>& ve)
{
for(auto elem:ve)
cout<<elem<<" ";
cout<<endl;
}
int main()
{
//容器有序
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> ve1(arr,arr+10);
print(ve1);
auto it = upper_bound(ve1.begin(),ve1.end(),2);
cout<<*it<<endl;
auto it2 = lower_bound(ve1.begin(),ve1.end(),11);
if(it2==ve1.end())
{
cout<<"not found!"<<endl;
}
//容器无序
int arr2[10] = {2,1,4,3,6,8,5,7,9,10};
vector<int> ve2(arr2,arr2+10);
print(ve2);
auto it3 = lower_bound(ve2.begin(),ve2.end(),3);
cout<<*it3<<endl;
}
//1 2 3 4 5 6 7 8 9 10
//3
//not found!
//2 1 4 3 6 8 5 7 9 10
//4
|
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void print(vector<int>& ve)
{
for(auto elem:ve)
cout<<elem<<" ";
cout<<endl;
}
bool comp(const int& a,const int& b)
{
return a<b; //从小到大
}
int main()
{
//容器有序
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> ve1(arr,arr+10);
print(ve1);
auto it = upper_bound(ve1.begin(),ve1.end(),2,comp);
cout<<*it<<endl;
print(ve1);
auto it2 = upper_bound(ve1.begin(),ve1.end(),11,comp);
print(ve1);
if(it2==ve1.end())
{
cout<<"not found!"<<endl;
}
//容器无序
int arr2[10] = {2,1,4,3,6,8,5,7,9,10};
vector<int> ve2(arr2,arr2+10);
print(ve2);
auto it3 = upper_bound(ve2.begin(),ve2.end(),5,comp);
print(ve2);
cout<<*it3<<endl;
}
//1 2 3 4 5 6 7 8 9 10
//3
//1 2 3 4 5 6 7 8 9 10
//1 2 3 4 5 6 7 8 9 10
//not found!
//2 1 4 3 6 8 5 7 9 10
//2 1 4 3 6 8 5 7 9 10
//6
|
|
template< class ForwardIt, class T >
std::pair<ForwardIt,ForwardIt>
equal_range( ForwardIt first, ForwardIt last,
const T& value );
返回的是两个迭代器指针，第一个迭代器指针相当于lower_bound返回的，第二个相当于upper_bound返回的,内部比较规则，默认<
如果没有不小于指定元素的数，就返回ForwardIt first，同理，后面一个没有满足要求的元素就返回ForwardIt last
|
template< class ForwardIt, class T, class Compare >
std::pair<ForwardIt,ForwardIt>
equal_range( ForwardIt first, ForwardIt last,
const T& value, Compare comp );
内部比较规则，comp
|
|
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void print(vector<int>& ve)
{
for(auto elem:ve)
cout<<elem<<" ";
cout<<endl;
}
int main()
{
//容器有序
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> ve1(arr,arr+10);
print(ve1);
auto pair = equal_range(ve1.begin(),ve1.end(),5); //返回一个pair<vector<int>::iterator,vector<int>::iterator>,第一个指向第一个不小于5的元素，第二个指向第一个大于5的元素
for(auto it = pair.first;it<=pair.second;++it)
cout<<*it<<" ";
cout<<endl;
auto pair2 = equal_range(ve1.begin(),ve1.end(),11);
if(pair2.first==ve1.end() && pair2.second==ve1.end())
cout<<"not found"<<endl;
//容器无序
int arr2[10] = {2,1,4,3,6,8,5,7,9,10};
vector<int> ve2(arr2,arr2+10);
print(ve2);
auto pair3 = equal_range(ve2.begin(),ve2.end(),5);
for(auto it = pair3.first;it<=pair3.second;++it)
cout<<*it<<" ";
cout<<endl;
}
//1 2 3 4 5 6 7 8 9 10
//5 6
//not found
//2 1 4 3 6 8 5 7 9 10
//6
|
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void print(vector<int>& ve)
{
for(auto elem:ve)
cout<<elem<<" ";
cout<<endl;
}
bool comp(const int&a ,const int&b)
{
return a<b;
}
int main()
{
//容器有序
int arr[10] = {1,2,3,4,5,6,7,8,9,10};
vector<int> ve1(arr,arr+10);
print(ve1);
auto pair = equal_range(ve1.begin(),ve1.end(),5,comp); //返回一个pair<vector<int>::iterator,vector<int>::iterator>,第一个指向第一个不小于5的元素，第二个指向第一个大于5的元素
for(auto it = pair.first;it<=pair.second;++it)
cout<<*it<<" ";
cout<<endl;
auto pair2 = equal_range(ve1.begin(),ve1.end(),11,comp);
if(pair2.first==ve1.end() && pair2.second==ve1.end())
cout<<"not found"<<endl;
//容器无序
int arr2[10] = {2,1,4,3,6,8,5,7,9,10};
vector<int> ve2(arr2,arr2+10);
print(ve2);
auto pair3 = equal_range(ve2.begin(),ve2.end(),5,comp);
for(auto it = pair3.first;it<=pair3.second;++it)
cout<<*it<<" ";
cout<<endl;
}
//1 2 3 4 5 6 7 8 9 10
//5 6
//not found
//2 1 4 3 6 8 5 7 9 10
//6
|
|
std::pair<iterator,iterator> equal_range( const Key& key );
std::pair<const_iterator,const_iterator> equal_range( const Key& key ) const;
Returns a range containing all elements with key key in the container. The range is defined by two iterators, the first pointing to the first element of the wanted range and the second pointing past the last element of the range.
//1 a
//1 b
//1 d
//请按任意键继续. . .
|
#include<iostream>
#include<unordered_map>
using namespace std;
int main()
{
pair<int,char> arr[4] = {
pair<int,char>(1,'a'),
pair<int,char>(1,'b'),
pair<int,char>(1,'d'),
pair<int,char>(2,'b')
};
unordered_multimap<int,char> ump(arr,arr+4);
pair<unordered_multimap<int,char>::iterator,unordered_multimap<int,char>::iterator> it = ump.equal_range(1);
for(unordered_multimap<int,char>::iterator iit = it.first;iit!=it.second;++iit)
{
cout<<iit->first<<" "<<iit->second<<endl;
}
system("pause");
}
|
最新文章
- 日常工作bug总结
- 不可变字符串NSString
- 《python核心编程》读书笔记——列表解析
- SRC单一职责原则
- 如何阻止h5body的滑动
- CSS语法
- 安装Arch Linux
- hdu2243考研路茫茫——单词情结（ac+二分矩阵）
- Python OpenCV —— geometric
- c#winform如何通过控件名查找控件
- 浅谈Linux下的五种I/O模型
- NSS_08 extjs表单验证
- 用开源AOP简化MVVM框架
- Mysql的联合查询
- Service 如何知道caller
- ECSHOP_百度收录网址后面有?from=rss
- iOS_21团购_发送请求【点评】数据
- Linux 学习 (二) 文件处理命令
- JS获取验证码后倒计时不受刷新及关闭影响
- Fruit HDU - 2152 -上下界生成函数