cb34a_c++_STL_算法_查找算法_(7)_lower_bound

  1 /*cb34a_c++_STL_算法_查找算法_(7)_lower_bound
  2 //针对已序区间的查找算法，如set,multiset关联容器-自动排序
  3 lower_bound()--第一个可能的位置
  4 upper_bound()--查找最后一个可能的位置
  5 equal_range()--同时查找第一个和最后一个可能的位置.做了两件事，先做lower_bound(),再upper_bound()
  6 
  7 pair<list<int>::iterator, list<int>::iterator> range;//pair（一对迭代器）
  8     range = equal_range(ilist.begin(), ilist.end(), 5);
  9     cout << distance(ilist.begin(),range.first) << endl;
 10     cout << distance(ilist.begin(),range.second) << endl;
 11 
 12 
 13 关联式容器有等效的成员函数。性能更佳
 14 multiset<int>::iterator iter1a,iter2a,iter3a;
 15     iter1a=iset.lower_bound(5);
 16     cout << "5的索引位置1a：" << distance(iset.begin(), iter1a) << endl;
 17     iter2a=iset.upper_bound(5);
 18     cout << "最后一个5的下一个索引位置2a：" << distance(iset.begin(), iter2a) << endl;
 19 
 20     pair<multiset<int>::iterator, multiset<int>::iterator> range2;
 21     range2 = iset.equal_range(5);
 22     cout << "lower索引："<<distance(iset.begin(),range2.first) << endl;
 23     cout << "upper索引："<<distance(iset.begin(),range2.second) << endl;
 24 
 25 distance(ilist.begin(), pos2) + 1, 用于计算数据的位置。pos2是迭代器，*pos2可以输入所指向的值
 26 ilist.sort();//排序
 27 */
 28 
 29 #include <iostream>
 30 #include <algorithm>
 31 #include <list>
 32 #include <set>
 33 
 34 using namespace std;
 35 
 36 int main()
 37 {
 38     list<int> ilist;
 39     for (int i = 1; i <= 9; ++i)
 40         ilist.insert(ilist.end(), i);
 41     for (int i = 1; i <= 9; ++i)
 42         ilist.insert(ilist.end(), i);
 43     ilist.push_back(5);
 44     ilist.push_back(5);
 45     ilist.push_back(5);
 46     ilist.sort();
 47 
 48     for (list<int>::iterator iter = ilist.begin(); iter != ilist.end(); ++iter)
 49         cout << *iter << ' ';
 50     cout << endl;
 51     list<int>::iterator pos1,pos2;
 52     pos1 = lower_bound(ilist.begin(), ilist.end(), 5);
 53     cout << "第一个5的位置： " << distance(ilist.begin(), pos1) + 1 << endl;
 54 
 55     pos2 = upper_bound(ilist.begin(), ilist.end(), 5);//大于5的下一个位置。upper:大于。
 56     cout << "找到最后一个5的下一个位置：" << distance(ilist.begin(), pos2) + 1 << endl;//加1就是从1开始数，第几个位置。用索引表示就0开始咯
 57     cout <<"指向的值是："<< *pos2 << endl;
 58 
 59     cout << "插入数据" << endl;
 60 
 61     ilist.insert(pos1, 3);//迭代器pos1前面插入3
 62     for (list<int>::iterator iter = ilist.begin(); iter != ilist.end(); ++iter)
 63         cout << *iter << ' ';
 64     cout << endl;
 65 
 66     ilist.insert(pos2, 8);//迭代器pos2前面插入8
 67     
 68     for (list<int>::iterator iter = ilist.begin(); iter != ilist.end(); ++iter)
 69         cout << *iter << ' ';
 70     cout << endl;
 71     ilist.sort();
 72     for (list<int>::iterator iter = ilist.begin(); iter != ilist.end(); ++iter)
 73         cout << *iter << ' ';
 74     cout << endl;
 75 
 76     pair<list<int>::iterator, list<int>::iterator> range;
 77     range = equal_range(ilist.begin(), ilist.end(), 5);
 78     cout << distance(ilist.begin(),range.first) << endl;
 79     cout << distance(ilist.begin(),range.second) << endl;
 80 
 81 
 82     cout << "关联式容器有等效的成员函数。性能更佳,示范如下：" << endl;
 83     multiset<int> iset;
 84 
 85     for (int jj = 1; jj <= 8; ++jj)
 86         iset.insert(jj);
 87     for (int jj = 1; jj <= 8; ++jj)
 88         iset.insert(jj);
 89     for (multiset<int>::iterator iter = iset.begin(); iter != iset.end(); ++iter)
 90         cout << *iter << ' ';
 91     cout << endl;
 92     multiset<int>::iterator iter1a,iter2a,iter3a;
 93     iter1a=iset.lower_bound(5);
 94     cout << "5的索引位置1a：" << distance(iset.begin(), iter1a) << endl;
 95     iter2a=iset.upper_bound(5);
 96     cout << "最后一个5的下一个索引位置2a：" << distance(iset.begin(), iter2a) << endl;
 97     
 98     pair<multiset<int>::iterator, multiset<int>::iterator> range2;
 99     range2 = iset.equal_range(5);
100     cout << "lower索引："<<distance(iset.begin(),range2.first) << endl;
101     cout << "upper索引："<<distance(iset.begin(),range2.second) << endl;
102 
103     return 0;
104 }