为什么STL和linux都使用红黑树作为平衡树的实现

红黑树是平衡二叉树的一种，它有很好的性质，树中的结点都是有序的，而且因为它本身就是平衡的，所以查找也不会出现非常恶劣的情况，基于二叉树的 *** 作的时间复杂度是O(log(N))。Linux内核在管理vm_area_struct时就是采用了红黑树来维护内存块的....

STL是Standard Template Library的简称，也即标准模板库，是一个具有工业强度的，高效的C++程序库。有关使用库的好处自不必多说，这里大致的讲述一下STL的相关知识和如何在Linux下使用STL；下面首先给出这几篇文章，都是介绍STL入门的极佳导学文章－－C++ STL轻松导学STL简介A modest STL tutorial看了这篇文章之后，我想你一定对STL有了一个概括性质的了解，当然，如果你感觉自己了解的仍然不够充分，你可以去这里－－STL 中文站最优秀的STL使用学习网站C++ Standard Template Library Overview获取更为详细的信息；其实网上有关STL的东西太多了，鱼龙混杂，但绝不乏精品，所以，如果你感觉看某一篇有关STL的文章实在是看不下去了，就应该考虑是不是这篇文章质量有问题，再去网上搜取合适的吧。我想通览了以上有关STL的信息之后，我们可以得出这样一个结论，那就是在linux下，如果要使用STL库，可选的就是这两个：Boost和SGI；下面我们分别来作一下比较：这是C++ Boost 库的文档索引这是C++ SGI 库的文档索引经过比较，我们可以得出这样一个结论，Boost库的内容更为丰富一些；所以，如果你打算体验一下Linux下的基于STL的应用开发，可以准备从Boost的学习开始，而且Boost的网上文档也是非常丰富的，参与Boost的开发人员甚至达到了2000多人！下面在Linux下编写一个基于STL的程序，测试一下；对了，现在我们也知道了Linux下默认支持的STL是SGI库，此库在Linux下性能非常不错！这里先给出程序源代码：#include <iostream>#include <vector>using namespace stdint main(int argc, char *argv[]){ vector<int>int_vectorvector<double>double_vectorint_vector.push_back(99)int_vector.push_back(9999)double_vector.push_back(99.99)double_vector.push_back(9999.9999)int sizesize = int_vector.size()for (int i = 0i <sizei ++){ cout <<int_vector[i] <<endl} size = double_vector.size()for (int j = 0j <sizej ++){ cout <<double_vector[j] <<endl}}注意其中的这一句“using namespace std”，如果没有这一句，你会遇到很多莫名其妙的问题，导致你不知所措，没办法排除错误，而实际上解决问题的关键就是这么一句话！

---