Question

关于equal_range函数

//multmapl.cpp--use a multimap
#pragma warning(disable:4786)
#include<iostream>
#include<string>
#include<map>
#include<algorithm>

typedef int KeyType;
typedef std::pair<const KeyType,std::string> Pair;
typedef std::multimap<KeyType,std::string> MapCode;
int main()
{
using namespace std;
MapCode codes;

codes.insert(Pair(415,"San Francisco"));
codes.insert(Pair(510,"Oakland"));
codes.insert(Pair(718,"Brooklyn"));
codes.insert(Pair(718,"Staten Island"));
codes.insert(Pair(415,"San Rafael"));
codes.insert(Pair(510,"Berkeley"));

cout<<"Number of cities with area code 415: "

<<codes.count(415)<<endl;
cout<<"Number of cities with area code 718: "
<<codes.count(718)<<endl;
cout<<"Number of cities with area code 510: "
<<codes.count(510)<<endl;
cout<<"Area Code City\n";
MapCode::iterator it;
for(it=codes.begin();it!=codes.end();++it)
cout<<" "<<(*it).first<<" "
<<(*it).second<<endl;
pair<MapCode::iterator,MapCode::iterator>range
=codes.equal_range(718);
cout<<"Cities with area code 718:\n";
for(it=range.first;it!=range.second;++it)
cout<<(*it).second<<endl;
return 0;
}

typedef std::pair<const KeyType,std::string> Pair; 与
pair<MapCode::iterator,MapCode::iterator>range
=codes.equal_range(718);
中的pari尖括号内的类型为何不同？
还有for(it=range.first;it!=range.second;++it)这个差别条件中的.first和.second与这个
cout<<" "<<(*it).first<<" "
<<(*it).second<<endl;中的.first和.second什么不同呀，糊涂了，菜鸟求解呀

Answer 1

equal_range函数其实是upper_bound函数+lower_bound函数构成的，它的作用是求一个有序的容器中 与ask相等元素的上界与下界，可能我说的不太清楚，看一下函数的说明：
equal_range(first,last,ask,compare) first 是容器的首指针，last是容器的末指针，ask是要查找的元素，compare（可省略）。
例如：
输入：
10
7 8 9 8 4 3 1 2 7 8 //未排序
8 //我们需要查询8
输出：
1 2 3 4 7 7 8 8 8 9 //排序后
9 6 //下标从1开始

注意：equal_range的返回值是两个迭代器，假如我们使用vector保存数列（ vector <int> V ）;
如果我们调用equal_range函数，那么应该这么写：
equal_range(V.begin(),V.end(),ask);
如何存这两个迭代器呢？ 函数返回的是一个pair类型。关于上个例子，我的写法是这样的：
pair <vector <int> :: iterator,vector <int> ::iterator> bound;//定义一个存2个迭代器的pair 名字叫bound
bound=equal_range(V.begin(),V.end(),ask);

那么
up=(bound.first-V.begin())=9
down=(bound.second-V.begin())=6
既然我们已经知道了等于ask 元素序列的上界与下界，那么我们就可以确定一共有(up-down)个与ask相等的元素。
说明
模板函数
头文件: <algorithm>
函数名: std::equal_range

函数1
template <class ForwardIterator, class T>
pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val);

函数2
template <class ForwardIterator, class T, class Compare>
pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

获取相等元素的子范围.
对于给定的范围[first,last), 返回所有值和val等价的元素的范围.

对于函数1. 使用operator<来进行元素比较. 对于函数2. 用comp进行元素比较. 两个元素a,b,当条件if(!(a<b) && !(b<a)) 或者if(!comp(a,b) && !comp(b,a))成立时,认为这2个元素等价.

原始范围中的元素应该是已经拍好序的.至少是对val进行过分区( patition) 操作的.

如果范围中没有与val等价的值存在.返回的子范围长度就为零.两个迭代器都指向大于val的最小值(如果有的话).如果val比范围中的所有值都大,那么返回的两个迭代器都指向last.
这个函数模板的行为等价于:
template<classForwardIterator,classT>
pair<ForwardIterator,ForwardIterator>
equal_range(ForwardIteratorfirst,ForwardIteratorlast,constT&val)
{
ForwardIteratorit=std::lower_bound(first,last,val);
returnstd::make_pair(it,std::upper_bound(it,last,val));
}

参数
first, last
前向迭代器. 指向排好序的序列的第一个和最后一个位置.包括first,但不包括last.
val
用来比较的值.
comp
二元函数. 接受两个参数,返回bool. 表明是否第一个参数应该排在第二个参数的前面.此函数不能修改任何参数的内容.这个参数可以是一个函数指针或者函数对象.

返回值
一个pari对象. pair::first是指向子范围左边界的迭代器. pair::last是指向子范围有边界的迭代器.它们的值和lower_bound,upper_bound分别返回的值相同.

实例
//equal_rangeexample
#include<iostream>//std::cout
#include<algorithm>//std::equal_range,std::sort
#include<vector>//std::vector

boolmygreater(inti,intj){return(i>j);}

intmain(){
intmyints[]={10,20,30,30,20,10,10,20};
std::vector<int>v(myints,myints+8);//1020303020101020
std::pair<std::vector<int>::iterator,std::vector<int>::iterator>bounds;

//usingdefaultcomparison:
std::sort(v.begin(),v.end());//1010102020203030
bounds=std::equal_range(v.begin(),v.end(),20);//^^

//using"mygreater"ascomp:
std::sort(v.begin(),v.end(),mygreater);//3030202020101010
bounds=std::equal_range(v.begin(),v.end(),20,mygreater);//^^

std::cout<<"boundsatpositions"<<(bounds.first-v.begin());
std::cout<<"and"<<(bounds.second-v.begin())<<'\n';

return0;
}

输出

Answer 2

equal_range函数其实是upper_bound函数+lower_bound函数构成的，它的作用是求一个有序的容器中 与ask相等元素的上界与下界，可能我说的不太清楚，看一下函数的说明：
equal_range(first,last,ask,compare) first 是容器的首指针，last是容器的末指针，ask是要查找的元素，compare（可省略）。
例如：
输入：
10
7 8 9 8 4 3 1 2 7 8 //未排序
8 //我们需要查询8
输出：
1 2 3 4 7 7 8 8 8 9 //排序后
9 6 //下标从1开始

注意：equal_range的返回值是两个迭代器，假如我们使用vector保存数列（ vector <int> V ）;
如果我们调用equal_range函数，那么应该这么写：
equal_range(V.begin(),V.end(),ask);
如何存这两个迭代器呢？ 函数返回的是一个pair类型。关于上个例子，我的写法是这样的：
pair <vector <int> :: iterator,vector <int> ::iterator> bound;//定义一个存2个迭代器的pair 名字叫bound
bound=equal_range(V.begin(),V.end(),ask);

那么
up=(bound.first-V.begin())=9
down=(bound.second-V.begin())=6
既然我们已经知道了等于ask 元素序列的上界与下界，那么我们就可以确定一共有(up-down)个与ask相等的元素。
那么关于这篇博文上的例题：http://blog.sina.com.cn/s/blog_6d79d83a0100wbgw.html 使用equal_range函数完成，代码是这样的：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
freopen("equal_range.in","r",stdin);
freopen("equal_range.out","w",stdout);
vector <int> V;
int n,ask;
cin>>n;
for(int i=0;i<n;i++)
{
int temp;
cin>>temp;
V.push_back(temp);
}
sort(V.begin(),V.end());
for(vector <int> ::iterator iter=V.begin();iter!=V.end();iter++)
cout<<*iter<<endl;
cin>>ask;
pair <vector <int> ::iterator,vector <int> ::iterator> bound;
bound=equal_range(V.begin(),V.end(),ask);
int down=(bound.first)-V.begin();
int up=(bound.second)-V.begin();
//cout<<up<<" "<<down<<endl;
cout<<up-down<<endl;
return 0;
}
equal_range 函数的效率是很高的，因为它是二分法解决的。
注意：如果在一个容器中找不到ask这个元素，那么pair中的两个迭代器的值都会是upper_bound(V.begin(),V.end(),ask);
例：
10
7 8 9 8 4 3 1 2 7 8
5
输出：
4 4
0

Answer 3

第一个，一个是表示键-值对的。
另外一个是表示区间范围的。所以类型不一样。
first是获取迭代器指向元素的键的。
second是获取值的。