multimap的相关原理-——(映照容器)
一、multimap的相关原理multimap与map一样,都是使用红黑树对记录型的元素数据按元素键值的比较关系,进行快速的插入、删除和检索操作,所不同的是multimap允许将具有重复键值的元素插入容器。在multimap容器中,元素的键值与元素的映照数据的映照关系,是多对多的,因此,multimap称为多重映照容器。multimap与map之间的多重特性差异,类似于multiset...
一、multimap的相关原理
multimap与map一样,都是使用红黑树对记录型的元素数据按元素键值的比较关系,进行快速的插入、删除和检索操作,所不同的是multimap允许将具有重复键值的元素插入容器。在multimap容器中,元素的键值与元素的映照数据的映照关系,是多对多的,因此,multimap称为多重映照容器。multimap 与 map 之间的多重特性差异,类似于 multiset 与 set 的多重特性差异。
是由于元素键值允许重复,使得数组操作符“[]”利用键值来访问元素失去意义,因此,multimap并没有定义数组方式的“[]”操作运算。
二、multimap的应用
1、创建
(1)multimap()
利用默认 less函数对象和内存分配器,创建一个没有任何元素的 multimap 对象。如下一行代码创建了一个空的multimap对象mm,元素的键值类型为char,元素的映照数据类型为int,键值的比较函数对象greater。
multimap > mm;
(2)multimap(const key_compare& comp)
指定一个比较函数对象comp来创建multimap对象,内存分配器为默认值。例如,下面代码使用自定义的函数对象strLess,创建一个multimap容器对象mm。该容器的键值类型为const char*,映照数据类型为int。
//定义字符串比较函数对象strLess
struct strLess{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) < 0;
}
}; //创建multimap容器对象mm
multimap mm(strLess());
(3)multimap(const map&)
拷贝构造函数。用一个 multimap 容器的元素和比较函数,拷贝生成另一个 multimap 容器对象。例如,下面代码利用multimap 容器对象mm1,创建另一个容器对象 mm2。
//multimapmm1; multimapmm2(mm1); // 使用默认的键值比较函数 less
(4)multimap(InputIterator first, InputIterator last)
用迭代器区间[first,last)所指的数据,作为multimap容器的元素(包括键值和映照数据),创建一个 multimap 容器对象。例如,下面代码使用数组pairArray的5个pair对象,创建multimap容器对象mm。
pair p1(1,'a');
pair p1(2,'b');
pair p1(3,'c');
pair p1(4,'d');
pair p1(5,'e');
pair pairArray[]={p1,p2,p3,p4,p5};
map m(pairArray,pairArray+5)
//创建multimap容器对象mm
multimap mm(pairArray, pairArray + 5);
(5)multimap(InputIterator first, InputIterator last, const key_compare& comp)
用迭代器区间[first, last)所指的数据和comp函数对象,创建一个multimap对象。例如,下面代码使用greater函数对象,取替默认的less,创建multimap对象mm。
multimap > mm(pairArray, pairArray+5,greater());
2、插入
(1)pair insert(const value_type& v)
将元素v(包括键值和映照数据)插入multimap容器,允许v的键值与容器中的某元素键值重复,下同。返回一个pair配对对象,提供所插入元素的迭代器位置和true/false插入成功标志。
(2)iterator insert(iterator position, const value_type& v)
将元素v(包括键值和映照数据)插入multimap容器,参数position只是提示可在position位置之前插入v,所返回的插入位置视实际情况而定,不一定能在position位置前插入。
(3)void insert(InputIterator first, InputIterator last)
将迭代器区间[first, last)所指的数据作为元素(包括键值和映照数据),插入到multimap容器中。
multimap mm;
mm.insert(pair)(3.0f,"apple"));
mm.insert(pair)(3.0f,"pear"));
mm.insert(pair)(2.6f,"orange"));
mm.insert(pair)(1.8f,"banana"));
3、删除
multimap容器删除函数原型与map容器的一样,可删除某个迭代器位置上的元素、等于某键值的所有元素、一个迭代器区间上的元素和容器中的所有元素。
(1)void erase(iterator position)
删除position所指的元素。
(2)size_type erase(const key_type& k)
删除键值为k的元素,返回删除的元素个数。
(3)void erase(iterator first, iterator last)
删除multimap迭代器区间[first, last)上的所有元素。
(4)void clear()
删除multimap容器的所有元素。
4、遍历访问
不同于map容器,multimap容器只能采用迭代器的方式,而不能用数组方式,遍历容器的元素。迭代器方式的元素访问,一般要用 begin 和 end 函数找出遍历开始的首元素和结束元素,然后通过迭代器的“++”和“*”操作取出元素。以下是multimap容器的begin和end函数原型,分别返回指向首尾元素的迭代器位置。
(1)iterator begin()
(2)iterator end()
利用multimap容器定义的反向迭代器reverse_iterator和const_reverse_iterator,及获取反向首尾元素的rbegin和rend函数,可反向遍历multimap容器的元素。
(1)reverse_iterator rbegin()
(2)reverse_iterator rend()
5、元素的搜索
由于键值允许重复插入,在multimap容器中具有同一个键值的元素有可能不只一个。因此,multimap容器的find函数将返回第一个搜索到的元素位置,如果元素不存在,则返回end结束元素位置。equal_range函数则返回一个可指示相等元素范围区间的pair对象。
(1)iterator find(const key_type& k) const
返回第一个搜索到的元素迭代器位置,空则返回end()结束位置。
(2)pair equal_range(const key_type& k) const
返回一个pair对象,它的first变量值为lower_bound(k),second变量值为upper_bound(k),分别指向大于等于k的第一个元素位置(x≥k)和大于k的第一个元素位置(x>k)。由此可确定出键值为k的元素位置范围是[lower_bound(k), upper_bound(k))。
#include "map"
#include "string"
#include "iostream"
using namespace std;
class CourseRecord{
public:
struct CourseInfo{
char* course;
int period;
char* required;
};
char* teacher;
CourseInfo cf;
CourseRecord(char* teacher_,char* course_,int period_,char* required_){
teacher=teacher_;
cf.course=course_;
cf.period=period_;
cf.required=required_;
}
};
int main()
{
typedef multimap coursemap;
coursemap mm;
CourseRecord course1=CourseRecord("wq","OS",60,"BX");
pair pairCourse1(course1.teacher,course1.cf);
mm.insert(pairCourse1);
CourseRecord course2=CourseRecord("LW","BYX",30,"BX");
pair pairCourse2(course2.teacher,course2.cf);
mm.insert(pairCourse2);
CourseRecord course3=CourseRecord("LW","DS",20,"BX");
pair pairCourse3(course3.teacher,course3.cf);
mm.insert(pairCourse3);
CourseRecord course4=CourseRecord("LW","Java",28,"XX");
pair pairCourse4(course4.teacher,course4.cf);
mm.insert(pairCourse4);
cout<<"LW 老师的课: ";
pair p=mm.equal_range("LW");
coursemap::iterator i;
for(i=p.first;i!=p.second;i++)
cout<<(*i).first<<" "
<<(*i).second.course<<" "
<<(*i).second.period<<"学时 "
<<(*i).second.required<<" "
<
return 1;
}
6、其它操作,如
empty() const,)size_type size(),//容器的元素个数
const,iterator lower_bound(const key_type& k) const,//小于等于k的第一个元素位置
iterator upper_bound(const key_type& k) const//大于k的第一个元素位置
可以见前面部分
http://blog.163.com/zhoumhan_0351/blog/static/39954227201022644534780
7、size_type count(const key_type& k) const//键值等于k的元素个数
更多推荐
所有评论(0)