上一篇文章《STL系列》之vector原理及实现，介绍了vector的原理及实现，这篇文章介绍map的原理及实现。STL实现源码下载。
STL中map的实现是基于RBTree的，我在实现的时候没有采用RBTree，觉得这东西有点复杂，我的map采用的是排序数组（CSortVector）。map中的Key存在排序数据中，通过二分查找判断某个Key是否在map中，时间复杂度为O(logN)。在用一个CVector存Key和Value，为了方便拿到Key和Value,这里有点冗余，Key被存了两次。
现在先介绍我的CSortVector，先贴出完整的代码，如下：
CSortVector和CVector有点类似，只不过CSortVector中的数据在插入的时候需要排序，其他的接口比较相识。CSortVector的关键实现就是二分查找。新增和删除的时候都是通过二分查找，定位到指定的位置，在进行相关操作。这里有必要特意列出二分查找的实现，如下：
int indexOf(const T& t) { int begin=0; int end=size_-1; int index=-1; while (begin<=end) { index=begin+(end-begin)/2; if (buf[index]==t) { return index; }else if (buf[index]<t) { begin=index+1; }else{ end=index-1; } } return -1; }
CSortVector测试代码如下：
void csortvectorTest() { csortvector<int> l; l.add(2); l.add(4); l.add(9); l.add(3); l.add(7); l.add(1); l.add(5); l.add(8); l.add(0); l.add(6); cout<<"任意插入一组数据后，自动排序："<<endl; for (int i=0;i<l.size();i++) { cout<<l[i]<<" "; } cout<<endl<<endl; l.erase(l.begin()); l.erase(l.end()-1); cout<<"删除第一个和最后一个数："<<endl; for (int i=0;i<l.size();i++) { cout<<l[i]<<" "; } cout<<endl<<endl; cout<<"5的下标："<<l.indexOf(5)<<endl; cout<<"下标为3的数："<<l[3]<<endl; l.remove(5); cout<<"删除5以后，5的下标是"<<l.indexOf(5)<<endl<<endl; cout<<"最后还剩："<<endl; for (int i=0;i<l.size();i++) { cout<<l[i]<<" "; } }
运行结果如下：
注意：由于CSortVector中的元素要排序，所以其中的元素要实现运算符”<”。
介绍完CSortVector，接下来说说CMap。其实CSortVector已经解决CMap的大部分功能了，后者只需要在前者的基础之上简单的封装即可完事。CMap源码如下：
插入操作，CMap的插入操作分两种，一种是通过insert方法；另一种是通过操作符[]。
Insert方法是先找到Key在Keys中的位置，如果已经存在就返回，CMap不允许重复，如果不存在就通过二分查找找到对应的位置，插入Key,并在Values中对应的地方插入Value。
通过操作符[]插入：如m[1]=1;刚开始我也不知道这个是怎么实现的，后来突然明白，操作符[]返回的是一个引用，其实就是给我m[1]的返回值赋值，调用的也是返回值的operator=，CMap只用实现operator[]就行。
其他的方法都是一些简单的封装，这里就不在累赘，最后概述一下CMap的实现：
CMap是基于一个排序数组CSortVector实现的，将Key存入排序数据中，Value和Key通过Pair<Key,Value>存在CVector中，通过二分查找确定某个Key是否存在，不存在就将这个Key插入排序数据中，返回Key在数组中的索引，并将Pair<Key,Value>存在CVector中对应的位置。删除还是通过二分查找寻找，找到就将两个数组中对应的元素删除。
CMap测试代码运行如下：
本文转自啊汉博客园博客，原文链接：http://www.cnblogs.com/hlxs/p/3752988.html