用list来实现顺序map（不自动排序的map）
更新时间：2015-07-27 22:11:03浏览次数：1+次
（1）map的自动排序功能示例：
比如下面一个简单的程序：
#include <utility>
#include <map>
#include <string>
#include <iostream>
int main()
{
std::map<std::string, int> mapStudentNo;
mapStudentNo.insert(std::make_pair("zhangsan", 1));
mapStudentNo.insert(std::make_pair("lisi", 2));
mapStudentNo.insert(std::make_pair("wangwu", 3));
std::map<std::string, int>::iterator itStudentNo = mapStudentNo.begin();
for (; itStudentNo!=mapStudentNo.end(); ++itStudentNo)
{
std::cout << (*itStudentNo).first << "的学号是" << (*itStudentNo).second << std::endl;;
}
return 0;
}
我们插入的顺序是("zhangsan", 1)，("lisi", 2)，("wangwu", 3)，但是我们可以看到输出结果并不是：
zhangsan的学号是1
lisi的学号是2
wangwu的学号是3
而是：
lisi的学号是2
wangwu的学号是3
zhangsan的学号是1
（2）STL中的map存在的问题：
为什么会这样呢？因为map是有自动排序功能的，里面的元素顺序并不是按插入顺序的。这时你可能会问，STL有没有为我们提供这样一种功能，设置map的属性，可以让它不自动排序？想法是不错，可惜的是，STL并没有向我们提供这个功能。那么，我们如何自己实现一种map，可以不自动排序，里面的元素按我们插入的先后顺序排序呢（事实上，这个需求在实际的开发中经常会用到）？下面，我们就来一起学习，如何来用list实现不自动排序的“map”。
（3）自已动手实现自己的“map”：
① 首先呢，我们定义如下的一个list：
std::list< std::pair<std::string, int> > lstStudentNo;
可以看到，此list非彼list，它有两个键，一个string，一个int，所以可以像map一样，实现键-值之间的对应关系。
② 然后，我们利用list的成员函数push_back()来插入元素：
lstStudentNo.push_back(std::make_pair("zhangsan", 1));
lstStudentNo.push_back(std::make_pair("lisi", 2));
lstStudentNo.push_back(std::make_pair("wangwu", 3));
③ 最后，我们利用迭代器输出元素，一起来看看结果吧。
std::list< std::pair<std::string, int> >::iterator itStudentNo = lstStudentNo.begin();
for (; itStudentNo!=lstStudentNo.end(); ++itStudentNo)
{
std::cout << (*itStudentNo).first << "的学号是" << (*itStudentNo).second << std::endl;;
}
可以看到，输出结果是：
zhangsan的学号是1
lisi的学号是2
wangwu的学号是3
成功了！呵呵！怎么样？很有趣吧。快去自己上机试试吧。
附：
完整的用list来实现顺序map（不自动排序的map）代码：
#include <utility>
#include <string>
#include <iostream>
#include <list>
int main()
{
std::list< std::pair<std::string, int> > lstStudentNo;
lstStudentNo.push_back(std::make_pair("zhangsan", 1));
lstStudentNo.push_back(std::make_pair("lisi", 2));
lstStudentNo.push_back(std::make_pair("wangwu", 3));
std::list< std::pair<std::string, int> >::iterator itStudentNo = lstStudentNo.begin();
for (; itStudentNo!=lstStudentNo.end(); ++itStudentNo)
{
std::cout << (*itStudentNo).first << "的学号是" << (*itStudentNo).second << std::endl;;
}
return 0;
}
