stl里map函数
声明:本文转自
C++ Maps(关联容器)
map类定义了一个关联容器,并且在容器中使用唯一的关键字(任何两个元素的键都不相同)来映射相应的值。从本质上来说,关键字就是值的名字。在map对象中存储了一个值之后,就可以通过关键字来获得它。map对象是一系列关键字/值的匹配对。 map的主要功能在于:只有你知道了一个值的关键字,就能够找到这个值。例如,定义一个map对象m,在该对象中使用人名作为关键字,并将每个人的电话号 码存储为值。那么可以使用m[“张三”]表示张三的电话号码。从前面的例子可以看出map类有一个非常优越的特点:关联数组。在普通的数组中,索引是一个 整数。而在关联数组中,索引是一个键,并且键可以是任意类型的,可以是String、double、int类型,甚至可以是一些用户定义的类。 map和set的插入删除效率比用其他序列容器高,因为对于关联容器来说,不需要做内存拷贝和内存移动。map和set容器内所有元素都是以节点的方式来存储,其节点结构和链表差不多,指向父节点和子节点。结构图可能如下:A
/ \ B C / \ / \ D E F G因此插入的时候只需要稍做变换,把节点的指针指向新的节点就可以了。删除的时候类似,稍做变换后把指向删除节点的指针指向其他节点就OK了。这里的一切操作就是指针换来换去,和内存移动没有关系。
每次insert之后,以前保存的iterator不会失效,因为iterator是指向节点的指针,内存没有变,指向内存的指针当然不会失效。函数列表如下:
begin() 返回指向map头部的迭代器 clear() 删除所有元素 count() 返回指定元素出现的次数 empty() 如果map为空则返回true end() 返回指向map末尾的迭代器 equal_range() 返回特殊条目的迭代器对 erase() 删除一个元素 find() 查找一个元素 get_allocator() 返回map的配置器 insert() 插入元素 key_comp() 返回比较元素key的函数 lower_bound() 返回键值>=给定元素的第一个位置 max_size() 返回可以容纳的最大元素个数 rbegin() 返回一个指向map尾部的逆向迭代器 rend() 返回一个指向map头部的逆向迭代器 size() 返回map中元素的个数 swap() 交换两个map upper_bound() 返回键值>给定元素的第一个位置 value_comp() 返回比较元素value的函数 constructors构造函数 explicit map(const Pred& comp = Pred(), const A& al = A()); map(const map& x); map(const value_type *first, const value_type *last, const Pred& comp = Pred(), const A& al = A());运算符[]
为了添加元素,可使用下标算符[]: map <string, string> addresses; addresses["Paul W."]=""; begin 语法: iterator begin(); begin()函数返回一个迭代器指向map的第一个元素。 clear 语法: void clear(); clear()函数删除map中的所有元素。 count 语法: size_type count( const KEY_TYPE &key ); count()函数返回map中键值等于key的元素的个数。用count函数来判定关键字是否出现,其缺点是无法定位数据出现位置,由于map的特性,一对一的映射关系,就决定了count函数的返回值只有两个,要么是0,要么是1.若key在map中存在,则返回1.empty
语法: bool empty(); empty()函数返回真(true)如果map为空,否则返回假(false)。 end 语法: iterator end(); end()函数返回一个迭代器指向map的尾部。 equal_range Syntax: pair equal_range( const KEY_TYPE &key ); equal_range()函数返回两个迭代器——一个指向第一个键值为key的元素,另一个指向最后一个键值为key的元素。 erase 语法: void erase( iterator pos ); void erase( iterator start, iterator end ); size_type erase( const KEY_TYPE &key ); erase()函数删除在pos位置的元素,或者删除在start和end之间的元素,或者删除那些值为key的所有元素。 find 语法: iterator find( const KEY_TYPE &key ); find()函数返回一个迭代器指向键值为key的元素,如果没找到就返回指向map尾部的迭代器。 get_allocator 语法: allocator_type get_allocator(); get_allocator()函数返回map的配置器。 insert 语法: iterator insert( iterator pos, const pair<KEY_TYPE,VALUE_TYPE> &val ); void insert( input_iterator start, input_iterator end ); pair<iterator, bool> insert( const pair<KEY_TYPE,VALUE_TYPE> &val ); 1.插入val到pos的后面,然后返回一个指向这个元素的迭代器。 2.插入start到end的元素到map中。 3.只有在val不存在时插入val。返回值是一个指向被插入元素的迭代器和一个描述是否插入的bool 因为map会排序,插入元素后,关键字将按升序排列,而与插入时的pos无关。 值。 示例: #include<iostream> #include <fstream> #include<map> #include<string> using namespace std; void main() { map<string,int> m,n; string key;int value; value=1;key="A12"; m[key]=value; value=5;key="A3"; m[key]=value; m["D5"]=4; m["A2"]=5; map<string,int>::iterator p=m.begin();//定义m对象的迭代器,并输出m中所有项 p++;p++; m.insert(p,pair<string,int>("A1",7)); m["B6"]=3; p=m.begin(); for (int i=0; i<m.size(); i++) { cout <<p->first <<" "<<p->second <<endl;//first指向关键字,second指向值 p++; } cout<<m.count("E")<<endl; } 输出结果: A1 7 A12 1 A2 5 A3 5 B6 3 D5 4 0 请看下面代码: #include <map> #include <string> #include <iostream> Using namespace std; void main() { Map<int, string> mapStudent; mapStudent.insert(pair<int, string>(1, "student_one")); mapStudent.insert(pair<int, string>(2,"student_two")); mapStudent.insert(pair<int, string>(3, "student_three")); } STL中默认是采用小于号来排序的,以上代码在排序上是不存在任何问题的,因为上面的关键字是int型,它本身支持小于号运算,在一些特殊情况,比如关键 字是一个结构体,涉及到排序就会出现问题,因为它没有小于号操作,insert等函数在编译的时候过不去,下面给出两个方法解决这个问题. 第一种:小于号重载. 示例: #include<iostream> #include <fstream> #include<map> #include<string> using namespace std; typedef struct tagStudentInfo { int nID; string strName; bool operator <(tagStudentInfo const& _A) const//升序排列 { //这个函数指定排序策略,按nID排序,如果nID相等的话,按strName排序 if(nID<_A.nID) return true; if(nID == _A.nID) return strName.compare(_A.strName) < 0; return false; } }StudentInfo,*PStudentInfo; //学生信息 void main() { map<StudentInfo,int>mapStudent;//关键字具有唯一性,不能两个内容相同的StudentInfo StudentInfo studentInfo; studentInfo.nID = 2; studentInfo.strName="student_one"; mapStudent.insert(pair<StudentInfo,int>(studentInfo, 90)); studentInfo.nID=1; studentInfo.strName="student_two"; mapStudent.insert(pair<StudentInfo,int>(studentInfo, 80)); map<StudentInfo,int>::iterator p=mapStudent.begin(); cout<<p->first.strName<<endl;p++; cout<<p->first.strName<<endl; } 输出结果: student_two student_one第二种:仿函数的应用,这个时候结构体中没有直接的小于号重载。
示例: #include<iostream> #include <fstream> #include<map> #include<string> using namespace std; typedef struct tagStudentInfo { int nID; string strName; }StudentInfo,*PStudentInfo; //学生信息 class sort { public: bool operator() (StudentInfo const &_A, StudentInfo const &_B) const { if(_A.nID < _B.nID) return true; if(_A.nID == _B.nID) return _A.strName.compare(_B.strName) < 0; return false; } }; void main() { map<StudentInfo,int,sort>mapStudent; StudentInfo studentInfo; studentInfo.nID = 2; studentInfo.strName="student_one"; mapStudent.insert(pair<StudentInfo,int>(studentInfo,90)); studentInfo.nID=1; studentInfo.strName="student_two"; mapStudent.insert(pair<StudentInfo,int>(studentInfo,80)); map<StudentInfo,int,sort>::iterator p=mapStudent.begin(); cout<<p->first.strName<<endl;p++; cout<<p->first.strName<<endl; }key_comp
语法: key_compare key_comp(); key_comp()函数返回一个比较key的函数。 先说key_compare类,它是一个函数对象类型,这种类型的对象的行为象一个函数指针,指向的函数必须是接受两个key类型的值并返回一个bool 类型的值。象这样:bool myCompare(const key_type& key1, const key_type& key2);然后你在定义map的时候,可以指定一个key_compare类型,在map的声明中第三个模板参数就是。如果你不指定,它有一个缺省的 less<>可用。这个函数对象被map用于插入一个新元素时确定它的位置,即map通过调用这个函数,把新元素中的key和map里面已有 元素的key进行比较,以找出新元素应该放在哪。lower_bound
语法: iterator lower_bound(const Key& key); const_iterator lower_bound(const Key& key) const; lower_bound()函数返回一个迭代器,指向map中键值<=key的第一个元素。If no such element exists, the function returns end(). 例如:map中已经插入了1,2,3,4的话,如果lower_bound(2)的话,返回的2,而upper-bound(2)的话,返回的就是3.max_size
语法: size_type max_size(); max_size()函数返回map能够保存的最大元素个数。 rbegin 语法: reverse_iterator rbegin(); rbegin()函数返回一个指向map尾部的逆向迭代器。 rend 语法: reverse_iterator rend(); rend()函数返回一个指向map头部的逆向迭代器。 size 语法: size_type size(); size()函数返回map中保存的元素个数。 swap 语法: void swap( map &obj ); swap()交换obj和现map中的元素。 upper_bound 语法: iterator upper_bound( const KEY_TYPE &key ); upper_bound()函数返回一个迭代器,指向map中键值>key的第一个元素。 value_comp 语法: value_compare value_comp(); value_comp()函数返回一个比较元素value的函数。 本文来自CSDN博客,转载请标明出处: