以下三个算法对所有容器都是可以使用的（一定要先排序）
lower_bound() // 查找第一个可能的位置
upper_bound() // 查找最后一个可能的位置
equal_range() // 同时可以查找上面的两个
但是 关联式容器（主要是multiset,multimap）有等效的成员函数，性能更佳
STL 算法-查找算法
find()
find_if()
search_n()
search()
find_end()
find_first_of()
adjacent_find()
已序空间查找算法
binary_search()
includes()
lower_bound()
upper_bound()
#include<iostream> #include<algorithm> #include<list> using namespace std; int main() { list<int> ilist; for (int i = 1; i <= 9; i++) ilist.insert(ilist.end(), i); for (int i = 1; i <= 9; i++) ilist.insert(ilist.end(), i); ilist.push_back(5); ilist.push_back(5); ilist.push_back(5); ilist.sort(); for (list<int>::iterator iter = ilist.begin(); iter != ilist.end(); iter++) { cout << *iter << " "; } cout << endl; list<int>::iterator pos1, pos2; pos1 = lower_bound(ilist.begin(), ilist.end(), 5); cout << "第一个5的位置：" << distance(ilist.begin(), pos1) + 1 << endl; pos2 = upper_bound(ilist.begin(), ilist.end(), 5); // >5的最后一个5的位置下一个位置 cout << "大于5的第一个位置：" << distance(ilist.begin(), pos2) + 1 << endl; ilist.insert(lower_bound(ilist.begin(), ilist.end(), 5), 5);// 在第一个5的位置之前插入一个5 ilist.insert(upper_bound(ilist.begin(), ilist.end(), 5), 5);// 在最后一个5的位置之后插入一个5 // lower_bound() 和 upper_bound()经常一起使用 也就是equal_range for (list<int>::iterator iter = ilist.begin(); iter != ilist.end(); iter++) { cout << *iter << " "; } cout << endl; // pair<list<int>::iterator, list<int>::iterator> range; range = equal_range(ilist.begin(), ilist.end(), 5); cout << distance(ilist.begin(), range.first) + 1 << endl; cout << distance(ilist.begin(), range.second) + 1 << endl; // system("pause"); return 0; } #include<iostream> #include<algorithm> #include<list> #include<set> using namespace std; int main() { list<int> ilist; //set<int> iset; multiset<int> imset; // 插入数据 imset.lower_bound(5); imset.upper_bound(5); imset.equal_range(5); // 返回pair 一对儿迭代器 for (int i = 1; i <= 9; i++) ilist.insert(ilist.end(), i); for (int i = 1; i <= 9; i++) ilist.insert(ilist.end(), i); ilist.push_back(5); ilist.push_back(5); ilist.push_back(5); ilist.sort(); for (list<int>::iterator iter = ilist.begin(); iter != ilist.end(); iter++) { cout << *iter << " "; } cout << endl; list<int>::iterator pos1, pos2; pos1 = lower_bound(ilist.begin(), ilist.end(), 5); cout << "第一个5的位置：" << distance(ilist.begin(), pos1) + 1 << endl; pos2 = upper_bound(ilist.begin(), ilist.end(), 5); // >5的最后一个5的位置下一个位置 cout << "大于5的第一个位置：" << distance(ilist.begin(), pos2) + 1 << endl; ilist.insert(lower_bound(ilist.begin(), ilist.end(), 5), 5);// 在第一个5的位置之前插入一个5 ilist.insert(upper_bound(ilist.begin(), ilist.end(), 5), 5);// 在最后一个5的位置之后插入一个5 // lower_bound() 和 upper_bound()经常一起使用 也就是equal_range for (list<int>::iterator iter = ilist.begin(); iter != ilist.end(); iter++) { cout << *iter << " "; } cout << endl; // pair<list<int>::iterator, list<int>::iterator> range; range = equal_range(ilist.begin(), ilist.end(), 5); cout << distance(ilist.begin(), range.first) + 1 << endl; cout << distance(ilist.begin(), range.second) + 1 << endl; // system("pause"); return 0; }
