map和multimap将key/value pair当做元素,进行管理。它们根据key的排序准则自动将元素排序。multimap允许重复元素,map不允许。
使用map和multimap之前,必须包含头文件<map>,map和multimap被定义为命名空间std内的class template:
1 2 3 4 5 6 7 8 9 |
namespace std { template<class Key, class T, class Compare = less<Key>, class Allocator = allocate<pair<const Key,T> > > class map; template<class Key, class T, class Compare = less<Key>, class Allocator = allocate<pair<const Key,T> > > class multimap; } |
第一个template参数被当做元素的key,第二个template参数被当做元素的value。map和multimap的元素类型Key和T,必须满足以下两个条件:
- key/value必须具备assignable和copyable性质。
- 对排序准则而言,key必须是comparable。
第三个template参数可有可无,用来定义排序准则。元素的次序由它们的key决定,和value无关。
1.map和multimap的能力
(1)和所有标准的关联式容器一样,map/multimap通常以平衡二叉树完成,如下图:
(2)典型情况下,set,multiset,map,multimap使用相同的内部数据结构。因此你可以把set和multiset分别视为特殊的map和multimap,只不过set元素的value和key是指向同一对象。因此map和multimap拥有set和multiset的所有能力和操作函数。
(3)当然某些细微差异还是有的:首先,它们的元素是key/value pair,其次map可作为关联式数组来运用。
(4)“自动排序”这一性质使得map和multimap身上有了一条重要的限制:你不可以直接改变元素的key,因为这会破坏正确次序。要修改元素的key,你必须先移除拥有该key的元素,然后插入新的key/value元素。
2.map和multimap的操作函数
(1)map和multimap的构造函数和析构函数
1 2 3 4 5 6 7 8 9 10 11 12 |
map 产生一个空的map/multimap,其中不含任何元素 map c(op) 以op为准则,产生一个空的map/multimap map c1(c2) 产生某个map/multimap的副本,所有元素均被复制 map c(beg,end) 以区间[beg,end)内的元素产生一个map/multimap map c(beg,end,op) 以op为排序准则,利用[beg,end)内的元素生成一个map/multimap c.~map() 销毁所有元素,释放内存 其中,map可为下列形式: map<Key, Elem> 一个map,以less<>(operator<)为排序准则 map<Key, Elem, Op> 一个map,以op为排序准则 multimap<Key, Elem> 一个multimap,以... multimap<Key, Elem, Op> ... |
(2)有两种方式可以定义排序准则:
- 以template参数定义:
std::map<float, std::string, std::greater<float> >cloo; - 以构造函数参数定义:
你可以有一个“排序准则类型”并为它指定不同的排序准则。如果执行期才获得排序准则,而且程序需要用到不同的排序准则,此一方法可派上用场。一个典型的例子是在执行期指定“key的类型为string”的排序准则,见稍后的例子。
如果没有提供特定的排序准则,就采用缺省准则——仿函数less<>。
(3)map和multimap的非变动性操作
1 2 3 4 5 6 7 8 9 |
c.size() 返回容器大小 c.empty() 判断容器大小是否为0 c.max_size()返回可容纳的最大元素数量 c1 ==c2 判断c1是否等于c2 c1 != c2 ... c1 < c2 ... c1 > c2 ... c1 <= c2 ... c1 >= c2 ... |
(4)特殊的搜寻动作
1)就像set和multiset一样,map和multimap也提供特殊的搜寻函数,以便用内部树状结构获取较好的性能。
2)成员函数find()用来搜寻有用某个key的第一个元素,并返回一个迭代器,指向该位置。如果没有找到这样的元素,就返回容器的end()。但不能用find()搜寻拥有某个特定value的元素,这是必须改用算法find_if(),或干脆写一个显式循环。
1 2 3 4 |
for (pos = coll.begin(); pos != coll.end(); ++pos) { if (pos->second == value) do_something(); } |
3)map和multimap特殊搜寻操作函数
1 2 3 4 5 |
count<key) 返回“键值等于key”的元素个数 find(key) 返回“键值等于key”的第一个元素,找不到返回end() lower_bound(key) 返回“键值为key”之元素的第一个可插入位置,也就是“键值>=key”的第一个元素位置 upper_bound(key) 返回“键值为key”之元素的最后一个可插入位置,也就是“键值>key”的第一个元素位置 equal_range(key) 返回“键值为key”之元素的第一个可插入位置和最后一个可插入位置,也就是“键值==key”的元素区间 |
(4)map和multimap的赋值操作
1 2 3 |
c1 == c2 将c2中所有元素赋值给c1 c1.swap(c2) 将c1和c2元素互换 swap(c1,c2) 同上,此为全局函数 |
(5)map和multimap的迭代器相关操作函数
1 2 3 4 |
c.begin() 返回一个双向迭代器(key被视为常数),指向第一个元素 c.end() 返回一个双向迭代器(key被视为常数),指向最后元素的下一位置 c.rbegin() 返回一个逆向迭代器,指向逆向遍历时的第一个元素 c.rend() 返回一个逆向迭代器,指向逆向遍历时的最后元素的下一位置 |
1)和其它所有关联式容器类似,这里的迭代器是双向迭代器。所以,对于只能用于随机存取迭代器的STL算法,map和multimap就无福消受了。
2)更重要的是,在map和multimap中,所有元素的key都被视为常数,因此元素的实质类型为pair<const key,T>。这个限制是为了确保你不会因为变更元素的key而破坏已排好的元素次序。
3)所以,你不能针对map或multimap调用任何变动性算法。例如,不能调用remove()。
(6)map和multimap所支持的元素插入和删除函数
1 2 3 4 5 6 7 |
c.insert(elem) 插入一个elem副本,返回新元素位置(不论成功与否——对map而言) c.insert(pos,elem) 插入一个elem副本,返回新元素位置(pos是个提示,指出插入操作的搜寻起点) c.insert(beg,end) 将区间[beg,end)内所有元素的副本插入到c(无返回值) c.erase(elem) 移除“实值value与elem相等”的所有元素,返回移除元素个数 c.erase(pos) 移除迭代器pos所指位置上的元素,无返回值 c.erase(beg,end) 移除区间[beg,end)内的所有元素,无返回值 c.clear() 移除全部元素,将整个容器清空 |
注:C++11新标准,规定erase(pos)和erase(beg,end)动作之后,返回最后一个被删除的元素的下一个位置。
插入一个key/value pair的时候,一定要记住,在map和multimap内部,key被视为常数。有三个不同的方法可将value传入map:
1)运用value_type
为了避免隐式类型转换,可以利用value_type明白传递正确类型:
std::map<std::string, float> coll;
…
coll.insert(std::map<std::string, float>::value_type(“otto”, 22.3);
2)运用pair<>
std::map<std::string, float> coll;
…
//use implict conversion:
coll.insert(std::pair<std::string, float>(“otto”, 22.3));
//use no implicit conversion:
coll.insert(std::pair<const std::string, float>(“otto”, 22.3));
上述第一个insert()语句内的类型并不正确,所以会被转换成真正的元素类型。
3)运用make_pair()
最方便的办法是运用make_pair()函数。这个函数根据传入的两个参数构造出一个pair对象:
std::map<std::string, float> coll;
…
coll.insert(std::make_pair(“otto”, 22.3));
3.将map视为关联式数组
(1)通常,关联式容器并不提供元素的直接存取,你必须依靠迭代器。不过map是个例外。Non-const map提供下标操作符,支持元素的直接存取。
(2)不过,小标操作符的索引值并非元素整数位置,而是元素的key。也就是说,索引可以是任意类型,而非局限为整数类型。这种接口正是我们所说的关联式数组。
1 |
m[key] 返回一个reference,指向键值为key的元素。如果该元素尚未存在,就插入该元素 |
(3)和一般数组之间的区别还不仅仅在于索引类型。其他区别还包括:你不可能用上一个错误索引。如果你使用某个key作为索引,而容器中尚未存在对于元素,那么就会自动插入该元素。新元素的value有default构造函数构造。(提醒,所有基本数据类型都提供有default构造寒素,以零为初值)
(4)关联式数组的行为方式可以说是各有利弊:
1)有点是你可以透过更方便的接口对着map插入新元素:
std::map<std::string, float> coll;
coll[“otto”] = 7.7;
其中第二条语句的处理如下:
- 如果存在键值为“otto”的元素,以上式子返回该元素的reference。
- 如果不存在键值“otto”,以上式子便会为map自动插入一个新元素,键值key为“otto”,实值value则以default构造函数完成,并返回一个reference指向新元素。
- 紧接着,将7.7赋值给上述刚刚诞生的新元素
2)缺点是你可能会不小心误置新元素:
std::cout << coll[“ottto”];
它会插入一个键值为”ottto”的新元素,然后打印其实值,缺省情况下是0。然而,按道理它应该产生一条错误信息,告诉你你把”otto”拼写错了。
4.异常处理
就异常处理而言,map和multimap的行为与set和multiset一样。
5.map和multimap运用实例
(1)map.cpp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <iostream> #include <map> #include <string> #include <algorithm> #include <iterator> using namespace std; int main() { typedef map<string,float> StringFloatMap; StringFloatMap stocks; stocks["BASF"] = 369.50; stocks["VW"] = 413.50; stocks["Daimler"] = 819.00; stocks["BMW"] = 834.00; stocks["Siemens"] = 842.20; StringFloatMap::iterator pos; for (pos = stocks.begin(); pos != stocks.end(); ++pos) { cout << "stock: " << pos->first << "\t" << "price: " << pos->second << endl; } cout << endl; for (pos = stocks.begin(); pos != stocks.end(); ++pos) { pos->second *= 2; } for (pos = stocks.begin(); pos != stocks.end(); ++pos) { cout << "stock: " << pos->first << "\t" << "price: " << pos->second << endl; } cout << endl; /*rename key from VM to Volkswagen, only provided by exchanging element */ stocks["Volkswagen"] = stocks["VW"]; stocks.erase("VW"); for (pos = stocks.begin(); pos != stocks.end(); ++pos) { cout << "stock: " << pos->first << "\t" << "price: " << pos->second << endl; } } |
输出:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
[root@VM_198_209_centos cppstl]# ./map stock: BASF price: 369.5 stock: BMW price: 834 stock: Daimler price: 819 stock: Siemens price: 842.2 stock: VW price: 413.5 stock: BASF price: 739 stock: BMW price: 1668 stock: Daimler price: 1638 stock: Siemens price: 1684.4 stock: VW price: 827 stock: BASF price: 739 stock: BMW price: 1668 stock: Daimler price: 1638 stock: Siemens price: 1684.4 stock: Volkswagen price: 827 |
(2)将multimap当做字典
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <iostream> #include <map> #include <string> #include <algorithm> #include <iterator> #include <iomanip> using namespace std; int main() { typedef multimap<string, string>StrStrMMap; StrStrMMap dict; dict.insert(make_pair("day","Tag")); dict.insert(make_pair("strange","fremd")); dict.insert(make_pair("car","Auto")); dict.insert(make_pair("smart","elegant")); dict.insert(make_pair("trait","Merkmal")); dict.insert(make_pair("strange","seltsam")); dict.insert(make_pair("smart","raffiniert")); dict.insert(make_pair("smart","klug")); dict.insert(make_pair("clever","raffiniert")); StrStrMMap::iterator pos; cout.setf(ios::left, ios::adjustfield); cout << ' ' << setw(10) << "english " << "german " << endl; cout << setfill('-') << setw(20) << " " << setfill(' ') << endl; for (pos = dict.begin(); pos!= dict.end(); ++pos){ cout << ' ' << setw(10) << pos->first.c_str() << pos->second << endl; } cout << endl; string word("smart"); cout << word << ": " << endl; for (pos = dict.lower_bound(word); pos != dict.end(); ++pos) { cout << " " << pos->second << endl; } word = ("raffiniert"); cout << word << ": " << endl; for (pos = dict.begin(); pos != dict.end(); ++pos){ if (pos->second == word) cout << " " << pos->first << endl; } } |
输出:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
[root@VM_198_209_centos cppstl]# ./multimap english german ------------------- car Auto clever raffiniert day Tag smart elegant smart raffiniert smart klug strange fremd strange seltsam trait Merkmal smart: elegant raffiniert klug fremd seltsam Merkmal raffiniert: clever smart |
其中,函数setw()和setfill包含在头文件<iomanip>中。