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

 //针对已序区间的查找算法，如set,multiset关联容器-自动排序

 lower_bound()--第一个可能的位置

 upper_bound()--查找最后一个可能的位置

 equal_range()--同时查找第一个和最后一个可能的位置.做了两件事，先做lower_bound(),再upper_bound()

 pair<list<int>::iterator, list<int>::iterator> range;//pair（一对迭代器）

     range = equal_range(ilist.begin(), ilist.end(), 5);

     cout << distance(ilist.begin(),range.first) << endl;

     cout << distance(ilist.begin(),range.second) << endl;

 关联式容器有等效的成员函数。性能更佳

 multiset<int>::iterator iter1a,iter2a,iter3a;

     iter1a=iset.lower_bound(5);

     cout << "5的索引位置1a：" << distance(iset.begin(), iter1a) << endl;

     iter2a=iset.upper_bound(5);

     cout << "最后一个5的下一个索引位置2a：" << distance(iset.begin(), iter2a) << endl;

     pair<multiset<int>::iterator, multiset<int>::iterator> range2;

     range2 = iset.equal_range(5);

     cout << "lower索引："<<distance(iset.begin(),range2.first) << endl;

     cout << "upper索引："<<distance(iset.begin(),range2.second) << endl;

 distance(ilist.begin(), pos2) + 1, 用于计算数据的位置。pos2是迭代器，*pos2可以输入所指向的值

 ilist.sort();//排序

 */

 #include <iostream>

 #include <algorithm>

 #include <list>

 #include <set>

 using namespace std;

 int main()

 {

     list<int> ilist;

     for (int i = ; i <= ; ++i)

         ilist.insert(ilist.end(), i);

     for (int i = ; i <= ; ++i)

         ilist.insert(ilist.end(), i);

     ilist.push_back();

     ilist.push_back();

     ilist.push_back();

     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(), );

     cout << "第一个5的位置： " << distance(ilist.begin(), pos1) +  << endl;

     pos2 = upper_bound(ilist.begin(), ilist.end(), );//大于5的下一个位置。upper:大于。

     cout << "找到最后一个5的下一个位置：" << distance(ilist.begin(), pos2) +  << endl;//加1就是从1开始数，第几个位置。用索引表示就0开始咯

     cout <<"指向的值是："<< *pos2 << endl;

     cout << "插入数据" << endl;

     ilist.insert(pos1, );//迭代器pos1前面插入3

     for (list<int>::iterator iter = ilist.begin(); iter != ilist.end(); ++iter)

         cout << *iter << ' ';

     cout << endl;

     ilist.insert(pos2, );//迭代器pos2前面插入8

     for (list<int>::iterator iter = ilist.begin(); iter != ilist.end(); ++iter)

         cout << *iter << ' ';

     cout << endl;

     ilist.sort();

     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(), );

     cout << distance(ilist.begin(),range.first) << endl;

     cout << distance(ilist.begin(),range.second) << endl;

     cout << "关联式容器有等效的成员函数。性能更佳,示范如下：" << endl;

     multiset<int> iset;

     for (int jj = ; jj <= ; ++jj)

         iset.insert(jj);

     for (int jj = ; jj <= ; ++jj)

         iset.insert(jj);

     for (multiset<int>::iterator iter = iset.begin(); iter != iset.end(); ++iter)

         cout << *iter << ' ';

     cout << endl;

     multiset<int>::iterator iter1a,iter2a,iter3a;

     iter1a=iset.lower_bound();

     cout << "5的索引位置1a：" << distance(iset.begin(), iter1a) << endl;

     iter2a=iset.upper_bound();

     cout << "最后一个5的下一个索引位置2a：" << distance(iset.begin(), iter2a) << endl;

     pair<multiset<int>::iterator, multiset<int>::iterator> range2;

     range2 = iset.equal_range();

     cout << "lower索引："<<distance(iset.begin(),range2.first) << endl;

     cout << "upper索引："<<distance(iset.begin(),range2.second) << endl;

     return ;

 }