C++的顺序容器与关联容器

C++ STL中的顺序容器和关联容器概念和用法整理。

顺序容器

顺序容器是容纳特定类型对象的集合。
我们曾经使用过一种容器标准库vector类型这是一种顺序容器(sequential container)，它将单一类型元素聚集起来成为容器，然后根据位置来存储和访问这些元素，这就是顺序容器。

注意：顺序容器的元素排列次序和元素值无关，而是由元素添加到容器里的次序决定的。

标准库定义了三种顺序容器类型：vector、list、deque(双端队列”double-endde queue”的简写，发音”deck”)。
他们的差别在于访问元素的方式，以及添加或删除元素相关操作的运行代价。

标准库还提供了三种容器的适配器，实际上是根据原始容器类型所提供的操作，通过定义新的操作接口，来适应基础的容器类型。顺序容器适配器包括stack、queue和priority_queue类型。

顺序容器类型	数据组织方式
vector	支持快速随机访问
list	支持快速插入/删除
deque	双端队列
顺序容器适配器	数据组织方式
stack	后进后出(LIFO)栈
queue	先进先出(FIFO)队列
priority_queue	有优先级管理的队列
容器只定义了少量操作，大多数额外操作由算法库提供，我们将在泛型算法章节学习算法库。

标准库为由容器定义的操作强加了公共的接口。这些容器的差别在于它们提供哪些操作，但是如果两个容器提供了相同的操作，则它们的接口(名字和参数个数)应该相同。

容器的操作集合形成以下的层次结构：

• 一些操作适用于所有的容器
• 另外一些操作只适用于顺序或关联容器类型
• 还有一些操作是适用于顺序和关联容器类型的一个子集(map/set)

顺序容器的定义

为了定义一个容器类型的对象，必须先包含相关的头文件。
即下列头文件之一:

#include <vector>
#include <list>
#include <deque>

所有的容器都是类模板（可以定义任意多种数据类型）。要定义某种特殊的数据类型，必须在容器名后面添加一对尖括号，尖括号里面提供容器中存放的元素的类型：

vector<string> sevc;
list<int> ilist;
deque<pair<string,int>> strint;

所有的容器类型都定义了默认构造函数，当没有显式初始化式时，用于创建指定类型的空容器对象。默认构造函数不带参数。
容器类型最常用的构造函数就是默认构造函数。在大多数程序中，使用默认构造函数能达到最佳运行时性能，并且使容器更容易使用。

容器元素的初始化

除了默认构造函数，容器类型还提供其他的构造函数，使之可以指定元素初值。

容器构造函数	作用	适用范围
C c;	创建一个名为c的空容器.C是容器类型名，如vectro，T是元素类型，如string和int	所有容器
C c(c2);	创建容器c2的副本c;c和c2必须具有相同的容器类型，并存放同类型的元素	所有容器
C c(b.e);	创建c，其元素是迭代器b和e标示的范围内元素的副本	所有容器
C c(n.t);	用n个值为t的元素创建容器c，其中值t必须是容器类型c的值，或者是可转换为该类型的值	顺序容器
C c(n);	创建有n个值初始化元素的容器c	顺序容器

将一个容器初始化为另一个容器的副本

//创建容器testInitCopy,并将其初始化为容器test的副本
vector<int> testInitCopy(test);
cout<<"vector<int> testInitCopy(test):"<<endl
	<<"C<T> testInitCopy(test)"<<endl;
for(vector<int>::iterator textInitCopyIter=testInitCopy.begin();
	textInitCopyIter!=testInitCopy.end();textInitCopyIter++)
		cout<<*textInitCopyIter<<" ";

• 将一个容器复制给另一个容器时，类型必须匹配：容器类型和元素类型都必须相同。
• 适用于所有容器

初始化为一段元素的副本

注意:使用迭代器初始化一个容器时，不要求容器类型相同。容器内的元素类型也可以不相同，只要他们相互兼容，能够将要复制的元素转换为所构建的新容器的元素类型，即可实现复制。

//容器testInitTwoIter和容器test类型相同，而使用的迭代器则是test.begin()和test.end()
//则在这个实例中也是将容器test完全复制给容器testInitTwoIter
//(与vector<int> testInitCopy(test)结果一致，实现方式不同)
vector<int> testInitTwoIter(test.begin(),test.end());
	cout<<"vector<int> testInitTwoIter(test.begin(),test.end()):"<<endl;
for(vector<int>::iterator testInitTwoIterBegin=testInitTwoIter.begin();
	testInitTwoIterBegin!=testInitTwoIter.end();testInitTwoIterBegin++)
	cout<<*testInitTwoIterBegin<<" ";

//容器testchar和容器testint类型不同
//元素赋值使用类型转换char->int(字符类型的ASCII码值)
vector<char> testchar;
for(char i='A';i!='K';i++){
	testchar.push_back(i);
}
//遍历输出testchar
for(vector<char>::iterator testiter=testchar.begin();
	testiter!=testchar.end();testiter++)
	cout<<*testiter<<"  ";
cout<<endl;
//将testin初始化为testchar的副本(类型转换)
vector<int> testint(testchar.begin(),testchar.end());
//遍历输出testint
for(vector<int>::iterator testintiter=testint.begin();
	testintiter!=testint.end();testintiter++){
	cout<<*testintiter<<" ";
}

输出结果:

A  B  C  D  E  F  G  H  I  J
65 66 67 68 69 70 71 72 73 74

或者初始化一段元素副本:

vector<char>::iterator charIter1=testchar.begin()+2,charIter2=testchar.end()-2;
vector<int> testint(charIter1,charIter2);
//遍历输出testint
for(vector<int>::iterator testintiter=testint.begin();
	testintiter!=testint.end();testintiter++){
	cout<<*testintiter<<" ";
}

输出结果：

67 68 69 70 71 72

分配和初始化指定数目的元素(只适用于顺序容器)

创建指定数目元素的容器并提供初始化式

创建顺序容器时，可显式指定容器大小和一个(可选的)元素初始化式。
容器大小可以是常量或非常量表达式，元素初始化式则必须是可用于初始化其元素类型的对象的值。

const vector<int>::size_type vectorSize=10;
//创建含有vectorSize个元素的vector<string>容器，容器内每个元素都被初始化为"Hi"字符串
vector<string> test(vectorSize,"Hi");
for(vector<string>::iterator testiter=test.begin();
	testiter!=test.end();testiter++){
	cout<<*testiter<<" ";
}

输出结果:

Hi Hi Hi Hi Hi Hi Hi Hi Hi Hi

**注意**：创建容器时，除了指定元素个数，还可以选择是否提供元素初始化式。也可以只指定容器大小。

创建指定数目元素的容器但不提供初始化式

//创建vectorSize个元素的容器，不显式提供初始化式(值初始化为0)
vector<int> testint(vectorSize);

或者这样：

extern unsigned get_word_count(const string &file_name);
vector<string> test(get_word_count("Chimera"))

不提供元素初始化式规则：

不提供元素初始化式时，标准库将为该容器实现值初始化。
采用这种类型的初始化，元素类型必须是内置或者复合类型，或者提供了默认构造函数的类类型。
如果元素类型没有默认构造函数，则必须显式指定其元素初始化式。

知识补充:

值初始化**：如果没有指定元素的初始化式，那么标准库将自行提供一个元素初始值进行值初始化**(value initializationd)。这个由库生成的初始值将用来初始化容器中的每一个元素，具体值为何，取决于存储在容器中元素的数据类型。
元素类型可能是没有定义任何构造函数的类类型，这种情况下，标准库仍产生一股带初始值的对象，这个对象的每个成员进行了值初始化。

注意：接受容器大小做形参的构造函数只适用于顺序容器，而关联容器不支持这种初始化。

###容器内元素的类型约束
C++中，大多数类型都可以用作容器的元素类型。
容器元素类型必须满足以下两个约束:

• 元素类型必须支持赋值运算
• 元素类型的对象必须可以复制

注意：关联容器的键类型还需要满足其他约束。

除了引用类型外，所有内置和复合类型都可以用作元素类型。引用不支持一般意义上的赋值运算，因此没有元素是引用类型的容器。

除输入输出(IO)标准库类型之外（IO对象不可复制或赋值,因此不能创建存放IO类型对象的容器）,所有其他标准库类型都是有效的容器元素类型.

容器本身也满足上述要求,可以定义元素本身就是容器类型的容器.

容器操作的特殊要求

支持复制和赋值功能室容器元素类型的最低要求.此外,一些容器操作队元素类型还有特殊的要求,如果元素类型不支持这些特殊要求,则相关的容器操作就不能执行:可以定义该类型的容器,但不能使用某些特定的操作.

需外加类型要求的容器操作

需外加类型要求的容器操作:指定容器大小并提供单个初始化式的构造函数.如果容器存储类类型的对象,那么只有放其元素类型提供默认构造函数时,容器才能使用这种构造函数.

考虑以下代码:

//假设类foo没有默认构造函数,但提供给了一个需要int型形参的默认构造函数.
vector<foo> empty;	//OK,没有初始化,不需要默认构造函数
vector<foo> bad(10);	//error,该句是创建十个初始化元素容器,但foo没有提供默认构造函数
vector<foo> ok(10,1);	//ok,初始化十个int型元素为1,1的数据类型为int,则使用int型的默认构造函数初始化容器.

**注意:**只有在同时指定每个元素的初始化式时,才能使用给定容器大小的构造函数来创建同类型的容器对象.所以在描述容器操作时,应该留意每个操作队元素类型的约束.

容器的容器

因为容器受容器元素类型的约束,所以可定义元素是容器类型的容器.

考虑如下代码:

//use "> >" not ">>"
vector< vector<string> > lines; //vector of vector

注意:必须使用空格隔开两个相邻的>符号,以示这是两个分开的符号,否则系统会认为>>是单个符号,为右移操作符,导致编译时错误.

习题

• 定义一个list对象来存储deque对象,该deque对象存放int型元素.
  list<deque<int>> listDeque;
• 为什么我们不能使用容器来存储iostream对象?
  因为IO库类型不支持复制和赋值操作.
• 假设有一个名为Foo的类,该类没有定义默认构造函数,但提供了一个需要int型参数的构造函数,定义一个存放Foo的list对象,该对象有十个元素.
  list<Foo> listFoo(10,0);

迭代器和迭代器范围

容器是否为const类型决定了迭代器是否为const类型.

每种容器类型都提供若干不共同工作的迭代器类型.
与容器类型一样,所有迭代器具有相同的接口:如果某种迭代器支持某种操作,那么支持这种操作的其他迭代器也会以相同的方式支持这种操作.

例如:所有的迭代器都支持以解引用运算从容器中读入一个元素.类似的,容器都提供自增自减操作符来支持从一个元素草下一个元素的访问.

标准库容器类型所提供的运算

操作	含义
*iter	返回迭代器iter所指向的元素的引用
iter->mem	对iter解引用,获取指定元素中名为mem的成员.等效于(*item).mem
++iter / iter++	给iter加1,使其指向容器里的下一元素
–iter / iter–	给iter减1,使其指向容器里的前一个元素
iter1=iter2 iter1!=iter2	比较两个迭代器是否相等(不等).当两个迭代器指向同一个元素,或者他们都指向同一个容器超出末端的下一位置时,两个迭代器相等

vector和deque容器的迭代器提供额外的运算

C++定义的容器中,只有vector和deque容器提供下面两种重要的运算集合:

• 迭代器算数运算
• 可以使用除了!=和==之外的运算符里比较两个迭代器(!=和==这两种关系运算符适用于所有容器).

vector和deque类型迭代器支持的操作(如表)

操作	含义
iter+n iter-n	在迭代器上加(减)整数值n,将产生指向容器前面(后面)第n个元素的迭代器
iter+=iter2 iter-=iter2	迭代器加减法的复合赋值运算:将iter1加上或减去iter2的运算结果复制给iter1
iter1-iter2	两个迭代器的减法,其运算结果加上右边的迭代器即得到左边的迭代器. 这两个迭代器必须指向同一个容器中的元素或超出容器末端的下一位置. 只适用于vector或deque容器
>,>=,<,<=	迭代器的关系运算符 当一个迭代器指向元素在容器中位于另一个迭代器指向的元素之前,则前一个迭代器小于后一个迭代器. 关系操作符的两个迭代器必须指向同一个容器中的元素或超出容器末端的下一位置. 只适用于vector或deque容器

注意:**关系操作符只适用于vector或deque容器,因为只有这两种容器为其元素提供快速和随机的访问.他们确保可以根据元素位置直接有效地访问指定的容器元素**.这两种容器都支持通过元素位置实现的随机访问,因此他们的迭代器可以有效地实现算数和关系运算.

例如,计算vector对象的中点位置:

vector<int>::iterator iter=vec.begin()+vec.size()/2;	//OK
//error version
list<int> listint(vec.begin(),vec.end());
listint.begin()+listint.size()/2;	//list容器的迭代器不支持加法运算

list容器的迭代器既不支持算数运算(加法或减法),也不支持关系运算(<=,<,>=,>),它只提供前置和后置的自增和自减以及相等(不等)运算

习题

1.下面的程序错在哪里?如何改正.

list<int> lst1;
list<int>::iterator iter1 = list1.begin(),
					iter2 = list1.end();
while(iter1 < iter2)/*...*/

答案:list容器不支持关系运算,可以把while循环修改为while(iter1 != iter2)
2.假设vec_iter绑定到vector对象的一个元素,该vector对象存放string类型的元素,请问下面的语句实现什么功能?

if(vec_iter->empty)/*...*/

答案:若vec_iter为空则返回true进入if语句,否则返回false不能进入if语句.
3.编写一个循环将list容器的元素逆序输出.

int one_ten[10]={0,1,2,3,4,5,6,7,8,9};
list<int> listInt(one_ten,one_ten+10);
list<int>::iterator beg=listInt.begin(),
					end=listInt.end();
while(end!=beg)
	cout<<*--end<<endl;

4.下列迭代器的用法哪些(如果有的话)是错误的?

const vector<int> ivec(10);
vector<string>	  sevc(10);
list<int>		  ilist(10);

(a)vector<int>::iterator 	it=ivec.begin();
//容器ivec为const,迭代器也应为const,因为非const可以通过迭代器修改其值
(b)list<int>iterator 	 	it=ilist.begin()+2;
//list容器迭代器不支持算数运算
(c)vector<string>::iterator it=&sevc[0];//OK
(d)for(vector<string>::iterator it = sevc.begin();it != 0;++it)/*...*/
迭代器为指针,永远不会等于0,应改成it != sevc.end().

迭代器范围

C++语言使用一对迭代器标记迭代器范围(iterator range),这两个迭代器分别指向同一个容器中的两个元素或超出末端的下一位置(end).通常将他们命名为first和last,或beg和end,用于标记容器中一段元素的范围.

注意:**第二个迭代器last(end)从来不是指向元素范围的最后一个元素,而是指向最后一个元素的下一位置.该范围内的元素包括迭代器first(beg)指向的元素,以及从frist开始一直到last(end)指向位置之前的所有元素.
**如果first(beg)和last(end)相等,则迭代器范围为空.
此类元素范围称作左闭合区间(left-inclusive interval),其标准表示方式为:$[first,last)$,表示范围从first开始到last结束,但不包括last.
迭代器lst可以等于first(容器为空),或者指向first标记元素后面的某个元素(容器非空),但绝对不能指向first标记的前面的元素.

对形成迭代器范围的迭代器的要求

迭代器first和last如果满足以下条件,则可形成一个迭代器范围:

• 他们指向同一个容器中的元素或超出末端的下一位置
• 如果这两个迭代器不相等,则对first反复做自增运算必须能够到达last.(在容器中.last绝对不能位于first之前)

编译器自己不能保证上述要求,编译器无法知道迭代器所关联的是哪个容器,也不知道容器内有多少个元素.若不能满足上述要求,将导致运行时未定义的行为.

使用做闭合区间的编程意义

左闭合区间有两个方便使用的性质,所以标准库使用此类区间.
假设first和last标记了一个有效的迭代器范围,则:

• 当first与last相等时,迭代器范围为空
• 当first与last不相等时,迭代器范围内至少有一个元素,而且first指向该区间的第一个元素.通过若干次自增运算可以使first的值不断增大,直到first==last为止.
  根据以上两个性质意味着我们可以安全地编写如下循环:

while(first != last){
	//safe to use *first because we know there is at least one element
	++first;
}

习题

1.要标记处有效的迭代器范围,迭代器需要满足什么约束?
(a)指向同一个容器的元素或超出末端的下一位置
(b)两个迭代器不相等时,first通过反复自增能够到达last
2.编写一个函数,其形参是一对迭代器和一个int型数据,实现在迭代器标记范围内寻找给int型数值的功能,并返回一个bool结果,以指明是否找到指定数据.

bool find_int(vector<int>::const_iterator first,
			  vector<int>::const_iterator last,int find_num){
	while(first != last){
		if(*first == find_num)
			return true;
		else
            first++;
	}
}

3.重写程序,查找元素的值,并返回找到的元素的迭代器.确保程序在寻找的元素不存在时也能正常的工作.

#include <iostream>
#include <vector>
using namespace std;
vector<int>::const_iterator find_int(vector<int>::const_iterator first,
									 vector<int>::const_iterator last,
									 int find_num){
	while(first != last){
		if(*first == find_num)
			return first;
		else
            first++;
	}
	if(first == last)
        return last;
}
int main(void){
int one_ten[10]={0,1,2,3,4,5,6,7,8,9};
vector<int> vecInt(one_ten,one_ten+10);
if(find_int(vecInt.begin(),vecInt.end(),9)!=vecInt.end())
    cout<<"Yes"<<endl;
else
    cout<<"No"<<endl;
return 0;
}

4.使用迭代器编写程序,从标准输入设备读取若干string对象,并将他们存储在一个vector对象中,然后输出该vector对象中的所有元素。

关联容器

关联容器和顺序容器的本质差别在于：

• 关联容器通过**键(key)**存储和读取元素。
• 顺序容器通过元素在容器中的位置顺序存储和访
  问元素。

关联容器大部分行为和顺序容器相同，但其独善之处在于支持键的使用

关联容器(associative container)支持通过键来高效地查找和读取元素。

两个基本的关联容器类型是map和set：

• map的元素以键-值(key-value)的形式组织：键用作元素在map中的索引。
• set仅包含一个键，并有效地支持关于某个键是否存在的查询。

适用范围：

• map:需要存储（乃至修改）每个键所关联值得情况。
• set:有效存储不同值得集合。

关联容器类型	作用
map	关联数组，元素通过键来存储和读取
set	大小可变的集合，通过键实现的快速读取
multimap	支持同一个键多次出现的map类型
multiset	支持同一个键多次出现的set类型
set和map类型的对象所包含的元素都具有不同的键，不允许为同一个键添加第二个元素。
注意：如果一个键必须对应多个实例，则需要使用multinap和multiset类型。

引言·pair类型

与关联容器相关的简单的标准库类型——pair类型，该类型在utility头文件中定义。

pair类型	提供的操作
pair<T1,T2> p1	创建一个空的pair类型，它的两个元素分别是T1和T2类型,采用值初始化
pair<T1,T2> p1(v1,v2)	创建一个空的pair类型，它的两个元素分别是T1和T2类型,其中first成员初始 化为v1,second成员被初始化为v2
make_pair(v1,v2)	以v1和v2值创建一个新的pair对象，其元素类型分别是v1和v2的类型
p1 < p2	两个pair对象之间的小于运算，其定义遵循字典次序:如果p1.first<p2.first或者!(p2.first<p1.first)&&p1.second<p2.second，则返回true
p1 = p2	如果两个pair对象的first和second成员依次相等，则这两个对象相等，该运算使用其元素的==操作符
p.first	返回p中名为first的（公有）数据成员
p.second	返回p中名为second的（公有）数据成员

pair的创建和初始化

pair包含两个数据值。与容器一样，pair也是一种模板类型。
在创建pair对象时，必须提供两个类型名：pair对象所包含的两个数据成员各自对应的类型名字，这两个类型不必相同

//first is string,second is int.
pair<string,int> strint;
//first and second is int.
par<int,int> twoint;
//first is string.second is vector<int>
pair<string,vector<int>> line;

注意：如果在创建pair对象时不提供初始化式，则调用默认构造函数对其成员采用值初始化。
也可以在定义时为每个成员提供初始化式：

//将twostr.first初始化为vision,two.second初始化为smile.
pair<string,string> twoste("vision","smile");

pair类型的使用相当繁琐，如果需要定义多个相同的pair对象，可以用typedef简化其声明:

typedef pair<string,string> twostr；
twostr VS("vision","smile");
twostr HelloWorld("Hello","World")

生成新的pair对象

除了构造函数，标准库还定义了一个make_pair函数，由传递给它的两个实参生成一个新的pair对象。

例.创建一个新的pair对象并赋值给一个已存在的pair对象：

//创建一个pair对象
pair<string,string> next_twostr;
//创建两个string对象用于输入（make_pair的参数）
string first,second;
//读入两个string对象，并使用make_pair创建一个新的pair对象然后赋值给next_twostr.
while(cin>>first>>second)
	next_twostr=make_pair(first,second);

因为pair的数据是公有的，所以可以直接地读取输入。

pair<string,string> next_twostr;
cin>>next_twostr.first>>nexttwostr.second);

习题

10.1编写程序读入一系列string对象和int型数据，将每一组存储在一个pair对象中，然后将这些pair对象存储在vector对象中。

#include <iostream>
#include <vector>
#include <string>
#include <utility>
using namespace std;
int main(void)
{
	pair<string,int> strint;
	vector< pair<string,int> > vectwostr;
	while(cin>>strint.first>>strint.second){
	    vectwostr.push_back(strint);
	    if(strint.second==0)
            break;
	}
	cout<<"Output:"<<endl;
	for(vector< pair<string,int> >::iterator begin=vectwostr.begin();
	begin!=vectwostr.end();begin++){
		//(*begin).first,对迭代器使用点操作符之前要对该指针(迭代器)进行解引用操作
		//因为点操作符优先级高于解引用，所有要用括号，或者begin->first，使用箭头操作符也可。
		cout<<(*begin).first<<" "<<(*begin).second<<endl;
	}
	return 0;
}
}

10.2 在前一题中，至少可使用三种方法创建pair对象，编写三个版本的程序，分别采用不同的方法创建pair对象。你认为哪种方法更容易编写和理解，为什么？

string teststr = "Hello";
int testint = 11;
pair<string,int> one;
pair<string,int> two(teststr,testint);
pair<string.int> three = make_pair(tststr,testint);

答：我觉得第三种pair<string.int> three = make_pair(tststr,testint);这种方式更容易编写和理解，因为调用了make_pair函数，明确生成了一个pair对象。

关联容器

关联容器共享大部分——但并非全部顺序容器操作。

关联容器不提供font、push_font、pop_font、back、push_back和pop_back操作。

根据键排列元素

对于顺序容器也提供的相同操作，关联容器也重新定义了这些操作的含义和返回类型，其中的差别在于关联容器使用了键。

容器元素根据键的次序排列:在迭代遍历关容器时，我们可以确保按键的顺序访问元素，而与元素在容器中存放的位置完全无关。

习题

10.2 在前一题中，至少可使用三种方法创建pair对象，编写三个版本的程序，分别采用不同的方法创建pair对象。你认为哪种方法更容易编写和理解，为什么？

string teststr = "Hello";
int testint = 11;
pair<string,int> one;
pair<string,int> two(teststr,testint);
pair<string.int> three = make_pair(tststr,testint);

答：我觉得第三种pair<string.int> three = make_pair(tststr,testint);这种方式更容易编写和理解，因为调用了make_pair函数，明确生成了一个pair对象。

10.3 描述 关联容器和顺序容器的差别

答：关联容器和顺序容器的本质差别在于：关联容器使用键(key)存储和读取元素，儿顺序容器通过元素在容器中的位置顺序存储和读取元素。

10.4 举例说明list、vector、deque、map以及set类型分别适用的情况。

• list适用于需要在任何位置都能快速高效地插入和删除元素(不需要移动其他任何元素)，但不使用随机访问的情况(访问某个元素需要从头遍历)
• vector适用于不需要随机插入/删除但需要快速随机访问(下标)的情况。
• deque适用于在队列两端快速插入/删除的操作，但和vector一样不需要随机插入/删除，且支持对所有元素的随机访问的情况。
• map适用于需要关联的数据，比如人名和电话号码。
• set适用于键集合的情况，比如黑名单等。

map容器

map是键-值的一对组合。
map类型通常可以理解为关联数组：可使用键作为下标获取一个值，正如内置数组类型一样。
关联的本质在于元素的值与某个特定的键相关联，而并非通过元素在数组中的位置来获取。

map对象的定义

要使用map对象，必须包含map头文件。

在定义map对象时，必须分别指明键和值得类型。

//定义一个名为strint的map对象，由string类型类型的键索引，关联的值为int
map<string,int> strint;

键类型的约束

在使用关联容器时，它的键不但有一个类型，而且还有一个相关的比较函数。默认情况下，标准库使用键类型定义的<操作符来实现键的比较。
我们将在面向对象编程·句柄的使用节来介绍如何重写默认的操作符，并提供自定义的操作符函数。

注意：所用的比较函数必须在键类型上定义**严格弱排序(strict weak ordering)**。
严格弱排序理解为：键类型数据上的“小于”关系。但也可以选择将比较函数设计的更复杂。

• 当一个键与自身比较时，肯定会导致false结果。
• 在比较两个键时，不能出现相互小于的情况。
  如果k1<k2,k2<k3，则k1必然小于k3
• 对于两个键，如果它们相互之间都不存在小于关系，则容器将之视为相同的键。

用做map对象的键时，可使用任意一个键值来访问它。

注意
键类型必须定义<操作符，而且该操作符能“正确的工作”。
对于键类型，唯一的约束就是必须支持<运算符，至于是否支持其他的关系或相等运算，则不作要求。