map容器

map所处理的数据与数据库表具有键值的记录很相似，在键值与映射数据之间，建立一个数学上的映射关系。map容器的数据结构仍然采用红黑树进行管理，插入的元素键值不允许重复，所使用的结点元素的比较函数只对元素的键值进行比较，元素的各项数据可以通过键值检索出来。对于键值和映射数据，可以通过pair封装成一个结构对象，map要做的就是将这个pair对象插入到红黑树中，同时也需要提供一个仅使用键值进行比较的函数对象，将它传递给红黑树。此时就可以利用红黑树的操作将map元素插入到二叉树的正确位置，并对其进行元素的删除和检索。map与set的区别主要在于，map处理的是带有键值的记录型元素数据的快速插入、删除和检索，而set是对单一数据的处理。二者都是泛型库对二叉树的一个泛化。

创建map对象

主要有以下几种方式。

(1)    map()

创建一个空的map对象，元素的键值类型为char，元素的映射数据类型为int，键值的比较函数对象为greater<char>

map<char,int,grater<char>> m;

(2)    map(const key_compare&cmp)

struct strLess{

bool operator()(const char* s1,const char*s2)const

{

           return strcmp(s1,s2)<0;

}

};

map<const char*,int> m(strLess());

(3)    map(const map&)

拷贝构造函数。

map<int,char*> m1;

map<int,char*> m2(m1);

(4)    map(InputIteratorfirst,InputIterator last)

pair<const int,char> p1(1,'a');

pair<const int,char> p2(2,'b');

pair<const int,char> p3(3,'c');

pair<const int,char> p4(4,'d');

pair<const int,char> array[]={p1,p2,p3,p4};

map<const int,char> m(array,array+4);

(5)    map(InputIteratorfirst,InputIterator last, const key_compare&cmp)

map<const int,char,greater<const int>>m(array,array+4,greater<const int>());

元素的插入

元素的插入主要利用insert函数，利用数组操作也可以显式地为map赋值，但是不能检测是否插入成功。

#include<iostream>
#include<map>
using namespace std;
int main()
{
	map<const char*,float> m;
	m["apple"]=1.5f;
	m["orange"]=2.0f;
	m["banana"]=1.1f;
	cout<<"苹果价格:"<<m["apple"]<<"元/斤"<<endl;
	cout<<"橘子价格:"<<m["orange"]<<"元/斤"<<endl;
	cout<<"香蕉价格:"<<m["banana"]<<"元/斤"<<endl;
	return 0;
}

元素的删除

与set集合容器一样，map容器可以删除某个迭代器位置上的元素，等于某个键值的元素，一个迭代器区间上的元素和容器中的所有元素，erase函数和clear函数。

元素的遍历

map元素的遍历除了利用键值的数组方式来访问元素，还可以使用迭代器的方式进行访问。

#include<iostream>
#include<map>
using namespace std;
struct stuInfo{
	char *name;
	int age;
};
struct stuRecord{
	int id;
	stuInfo sf;
};
int main()
{
	stuRecord sArray[]={{1,"li",20},{10,"shi",18},{3,"wang",21}};
	map<int,stuInfo> m;
	for(int i=0;i<3;i++)
	{
		m[sArray[i].id]=sArray[i].sf;
	}
	map<int,stuInfo>::iterator begin,end;
	end=m.end();
	cout<<"学号	"<<"姓名	"<<"年龄	"<<endl;
	for(begin=m.begin();begin!=end;begin++)
	{
		cout<<(*begin).first<<"	"
		<<(*begin).second.name<<"	"
		<<(*begin).second.age<<"	"
		<<endl;
	}
	
	return 0;
}

 

从结果可以看出，虽然是无序插入的，但是遍历出的结果是有序的。

元素的搜索

利用find函数可以搜索出具有某一键值的元素。

#include<iostream>
#include<map>
using namespace std;
struct stuRecord{
	struct stuInfo{
		char *name;
	    int age;
	};
	stuRecord(int id_,char *name_,int age_)
	{
		id=id_;
		sf.name=name_;
		sf.age=age_;
	}
	int id;
	stuInfo sf;
};

int main()
{
	typedef map<int,stuRecord::stuInfo> stuMap;
	stuMap m;
	pair<stuMap::iterator,bool> p;
	//插入第一条学生记录 
	stuRecord stu1=stuRecord(5,"li",22);
	pair<int,stuRecord::stuInfo> pairStu1(stu1.id,stu1.sf);
	p=m.insert(pairStu1);
	if(!p.second)
		cout<<"插入学生记录失败\n";
	//插入第二条学生记录
	stuRecord stu2=stuRecord(1,"shi",20);
	pair<int,stuRecord::stuInfo> pairStu2(stu2.id,stu2.sf);
	p=m.insert(pairStu2);
	if(!p.second)
		cout<<"插入学生记录失败\n";
	//插入第三条学生记录
	stuRecord stu3=stuRecord(10,"zhang",21);
	pair<int,stuRecord::stuInfo> pairStu3(stu3.id,stu3.sf);
	p=m.insert(pairStu3);
	if(!p.second)
		cout<<"插入学生记录失败\n"; 
	
	//搜索
	stuMap::iterator i=m.find(5);
	cout<<"搜索学号为5的记录：\n"
	<<(*i).first<<'	'
	<<(*i).second.name<<'	'
	<<(*i).second.age<<'	'<<endl;
	 
	return 0;
}

 

map还提供其他的函数，empty、size、swap、lower_bound、upper_bound、equal_range等。

multimap多重映射容器

multimap容器也是用红黑树对记录型元素数据按照键值的比较关系进行快速的插入、删除、检索，元素的检索是对数级的时间复杂度，与map不同的是，multimap允许将具有重复键值的元素插入容器，元素的键值与元素的映射数据的映射关系是多对多的。

创建multimap对象

有以下几种方式。

(1)    multimap()

multimap<char,int,greater<char>>mm;

(2)    multimap(constkey_compare&cmp)

struct strLess{

bool operator()(const char *s1,const char*s2)const

{

           return strcmp(s1,s2)<0;

}

};

multimap<constchar*,int> mm(strLess());

(3)    multimap(const map&)

multimap<int,char*> mm1;

multimap<int,char*> mm2(mm1);

(4)    multimap(InputIteratorfirst,InputIterator last)

pair<constint,char> p1(1,'a');

pair<constint,char> p2(1,'e');

pair<constint,char> p3(2,'b');

pair<constint,char> p4(3,'c');

pair<constint,char> pairArray[]={p1,p2,p3,p4};

multimap<constint,char> mm(pairArray,pairArray+4);

(5)    multimap(InputIteratorfirst,InputIterator last, const key_compare&cmp)

multimap<constint,char,greater<const int>> mm(pairArray,pairArray+4,greater<constint>());

元素的插入

multimap容器只能使用insert函数插入元素到容器的红黑树中。

multimap<float,char *> mm;

mm.insert(pair<float,char*>(3.0f,"apple"));

mm.insert(pair<float,char*>(3.0f,"pear"));

mm.insert(pair<float,char*>(2.1f,"orange"));

mm.insert(pair<float,char*>(1.5f,"banana"));

 

元素的删除

与map集合容器一样，map容器可以删除某个迭代器位置上的元素，等于某个键值的元素，一个迭代器区间上的元素和容器中的所有元素，erase函数和clear函数。

 

元素的遍历

multimap容器的遍历，可以用迭代器来实现。

 

#include<iostream>
#include<map>
using namespace std;
int main()
{
	multimap<float,char *> mm;
    mm.insert(pair<float,char *>(3.0f,"apple"));
    mm.insert(pair<float,char *>(3.0f,"pear"));
    mm.insert(pair<float,char *>(2.1f,"orange"));
    mm.insert(pair<float,char *>(1.5f,"banana"));
    
    multimap<float,char *>::iterator begin,end;
    end=mm.end();
    for(begin=mm.begin();begin!=end;begin++)
    {
    	cout<<(*begin).second<<"	"<<(*begin).first<<"元/斤"<<endl;
    }
    cout<<endl;
	return 0;
}

反向遍历

利用反向迭代器可以实现逆向遍历。

#include<iostream>
#include<map>
using namespace std;
int main()
{
	multimap<float,char *> mm;
    mm.insert(pair<float,char *>(3.0f,"apple"));
    mm.insert(pair<float,char *>(3.0f,"pear"));
    mm.insert(pair<float,char *>(2.1f,"orange"));
    mm.insert(pair<float,char *>(1.5f,"banana"));
    
    multimap<float,char *>::reverse_iterator rbegin,rend;
    rend=mm.rend();
    for(rbegin=mm.rbegin();rbegin!=rend;rbegin++)
    {
    	cout<<(*rbegin).second<<" "<<(*rbegin).first<<"元/斤"<<endl;
    }
	return 0;
}

 

元素的搜索

multimap容器的find函数将返回第一个搜索到的元素的位置，如果元素不存在将返回end结束元素位置。

其他常用函数

 

其他常用函数有empty、size、count、lower_bound、upper_bound等。

 

 

#include<iostream>
#include<map>
using namespace std;
int main()
{
	multimap<int,char> mm;
	cout<<mm.size()<<endl;
	mm.insert(pair<int,char>(3,'a'));
	mm.insert(pair<int,char>(3,'c'));
	mm.insert(pair<int,char>(1,'b'));
	mm.insert(pair<int,char>(2,'d'));
	mm.insert(pair<int,char>(3,'e'));
	mm.insert(pair<int,char>(4,'g'));
	
	cout<<mm.count(3)<<endl;
	cout<<mm.size()<<endl;
	
	return 0;
}