STL源码剖析——map、multimap

map/multimap以rb_tree为底层结构，根据元素的键值key自动排序，所有的元素都是pair，都具有实值value和键值key。pair<键值，实值>

template<class T1,calss T2>
struct pair{
    typedef T1 first_type;
    typedef T2 second_type;

    T1 first;    //注意，它是public
    T2 second;   //注意，它是public
    pair():first(T1()),second(T2())  {}
    pair(const T1& a,const T2& b):first(a),second(b){}
    };

• map不允许键值重复，插入操作采用的是底层RB-tree的insert_unique()

• multimap允许键值重复，插入操作采用的是底层RB-tree的insert_equal()

map不可以修改元素的键值，可以修改元素的实值，因为元素的键值关系到map元素的的排列顺序

map构造函数

map成员函数

begin()--返回指向第一个元素的迭代
end()--返回指向最后一个元素的迭代器
clear()--清除所有元素
size()--集合中元素的数目
max_size()--返回集合能容纳的元素的最大限值
empty()--如果集合为空，返回true
rbegin()--返回指向集合中最后一个元素的反向迭代器
rend()--返回指向集合中第一个元素的反向迭代器
swap()--交换两个集合变量
key_comp()--返回一个用于元素key值比较的函数
value_comp()--返回一个用于元素value值比较的函数
[] --由键值取得实值

insert()–在集合中插入元素
erase()–删除集合中的元素

//对关联式容器，使用其提供的find函数搜寻元素
//比STL算法find()函数有效率，因为STL算法只是循迹搜寻
find()--返回一个指向被查找到元素的迭代器
count()--返回某个值元素的个数
lower_bound()--返回指向大于（或等于）某值的第一个元素的迭代器
upper_bound()--返回指向小于（或等于）某值的第一个元素的迭代器
equal_range()--返回集合中与给定值相等的上下限的两个迭代器

测试程序

#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
	map<string,int>simap; 
    simap[string("jjhou")]= 1;
    simap[string("jerry")]= 2;
    simap[string("jason")]= 3;
    simap[string("jimmy")]= 4;
    
    pair<string,int>value(string("david"),5);
    simap.insert(value);
    
    map<string,int>::iterator simap_iter=simap.begin();
    for(;simap_iter!=simap.end();simap_iter++)
    {
    	cout<<simap_iter->first<<' '<<simap_iter->second<<endl;
	}
	
	int number=simap[string("jjhou")];
	cout<<number<<endl;
	
	map<string ,int>::iterator ite1;
	ite1=simap.find(string("machen"));
	if(ite1==simap.end())
	    cout<<"machen not found"<<endl;
    
    ite1=simap.find(string("jerry"));
    if(ite1!=simap.end())
        cout<<"jerry found"<<endl;
        
    ite1->second=9;
    int number2=simap[string("jerry")];
    cout<<number2<<endl;
}

• insert函数
  将工作转交给底层机制RB-tree的insert_unique()执行，其返回值是一个pair，由一个迭代器和一个bool值组成，后者表示插入成功，成功的话前者即指向被插入的那个元素。

• [ ]下标操作符
  用法由两种，左值运用（内容可被修改）和右值运用（内容不可修改）

map<string,int>simap;
simap[string("jjhou")]=1;//左值运用

int number=simap[string("jjhou")];//右值引用
//number=simap[string(""jimmy")];//接着加这句，运行不了，出错