跳至主要内容

【转】学习STL map, STL set之数据结构基础

作者： winter

摘要：本文列出几个基本的STL map和STL set的问题，通过解答这些问题讲解了STL关联容器内部的数据结构，最后提出了关于UNIX/LINUX自带平衡二叉树库函数和map, set选择问题，并分析了map, set的优势之处。对于希望深入学习STL和希望了解STL map等关联容器底层数据结构的朋友来说，有一定的参考价值。

STL map和set的使用虽不复杂，但也有一些不易理解的地方，如：

  • 为何map和set的插入删除效率比用其他序列容器高？
  • 为何每次insert之后，以前保存的iterator不会失效？
  • 为何map和set不能像vector一样有个reserve函数来预分配数据？
  • 当数据元素增多时（10000到20000个比较），map和set的插入和搜索速度变化如何？

    • 或许有得人能回答出来大概原因，但要彻底明白，还需要了解STL的底层数据结构。

    C++ STL 之所以得到广泛的赞誉，也被很多人使用，不只是提供了像vector, string, list等方便的容器，更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组，list封装了链表，map和set封装了二叉树等，在封装这些数据结构的时候，STL按照程序员的使用习惯，以成员函数方式提供的常用操作，如：插入、排序、删除、查找等。让用户在STL使用过程中，并不会感到陌生。

    C++ STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树：红黑树，也成为RB树(Red-Black Tree)。RB树的统计性能要好于一般的平衡二叉树(有些书籍根据作者姓名，Adelson-Velskii和Landis，将其称为AVL-树)，所以被STL选择作为了关联容器的内部结构。本文并不会介绍详细AVL树和RB树的实现以及他们的优劣，关于RB树的详细实现参看红黑树: 理论与实现(理论篇)。本文针对开始提出的几个问题的回答，来向大家简单介绍map和set的底层数据结构。

    为何map和set的插入删除效率比用其他序列容器高？

    大部分人说，很简单，因为对于关联容器来说，不需要做内存拷贝和内存移动。说对了，确实如此。map和set容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点。结构图可能如下：

                A
               / \
              B   C
             / \ / \
            D  E F  G

    因此插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点就OK了。这里的一切操作就是指针换来换去，和内存移动没有关系。

    为何每次insert之后，以前保存的iterator不会失效？

    看见了上面答案的解释，你应该已经可以很容易解释这个问题。iterator这里就相当于指向节点的指针，内存没有变，指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。相对于vector来说，每一次删除和插入，指针都有可能失效，调用push_back在尾部插入也是如此。因为为了保证内部数据的连续存放，iterator指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时push_back的时候，容器内部空间可能不够，需要一块新的更大的内存，只有把以前的内存释放，申请新的更大的内存，复制已有的数据元素到新的内存，最后把需要插入的元素放到最后，那么以前的内存指针自然就不可用了。特别时在和find等算法在一起使用的时候，牢记这个原则：不要使用过期的iterator。

    为何map和set不能像vector一样有个reserve函数来预分配数据？

    我以前也这么问，究其原理来说时，引起它的原因在于在map和set内部存储的已经不是元素本身了，而是包含元素的节点。也就是说map内部使用的Alloc并不是map<Key, Data, Compare, Alloc>声明的时候从参数中传入的Alloc。例如：

    map<int, int, less<int>, Alloc<int> > intmap;

    这时候在intmap中使用的allocator并不是Alloc<int>, 而是通过了转换的Alloc，具体转换的方法时在内部通过Alloc<int>::rebind重新定义了新的节点分配器，详细的实现参看彻底学习STL中的Allocator。其实你就记住一点，在map和set内面的分配器已经发生了变化，reserve方法你就不要奢望了。

    当数据元素增多时（10000和20000个比较），map和set的插入和搜索速度变化如何？

    如果你知道log2的关系你应该就彻底了解这个答案。在map和set中查找是使用二分查找，也就是说，如果有16个元素，最多需要比较4次就能找到结果，有32个元素，最多比较5次。那么有10000个呢？最多比较的次数为log10000，最多为14次，如果是20000个元素呢？最多不过15次。看见了吧，当数据量增大一倍的时候，搜索次数只不过多了1次，多了1/14的搜索时间而已。你明白这个道理后，就可以安心往里面放入元素了。

    最后，对于map和set Winter还要提的就是它们和一个c语言包装库的效率比较。在许多unix和linux平台下，都有一个库叫isc，里面就提供类似于以下声明的函数:

    void tree_init(void **tree);
    void *tree_srch(void **tree, int (*compare)(), void *data);
    void tree_add(void **tree, int (*compare)(), void *data, void (*del_uar)());
    int tree_delete(void **tree, int (*compare)(), void *data,void (*del_uar)());
    int tree_trav(void **tree, int (*trav_uar)());
    void tree_mung(void **tree, void (*del_uar)());

    许多人认为直接使用这些函数会比STL map速度快，因为STL map中使用了许多模板什么的。其实不然，它们的区别并不在于算法，而在于内存碎片。如果直接使用这些函数，你需要自己去new一些节点，当节点特别多，而且进行频繁的删除和插入的时候，内存碎片就会存在，而STL采用自己的Allocator分配内存，以内存池的方式来管理这些内存，会大大减少内存碎片，从而会提升系统的整体性能。Winter在自己的系统中做过测试，把以前所有直接用isc函数的代码替换成map，程序速度基本一致。当时间运行很长时间后（例如后台服务程序），map的优势就会体现出来。从另外一个方面讲，使用map会大大降低你的编码难度，同时增加程序的可读性。何乐而不为？

    | 引用

    评论

    发表评论

    此博客中的热门博文

    【转】AMBA、AHB、APB总线简介

    AMBA 简介 随着深亚微米工艺技术日益成熟，集成电路芯片的规模越来越大。数字IC从基于时序驱动的设计方法，发展到基于IP复用的设计方法，并在SOC设计中得到了广泛应用。在基于IP复用的SoC设计中，片上总线设计是最关键的问题。为此，业界出现了很多片上总线标准。其中，由ARM公司推出的AMBA片上总线受到了广大IP开发商和SoC系统集成者的青睐，已成为一种流行的工业标准片上结构。AMBA规范主要包括了AHB(Advanced High performance Bus)系统总线和APB(Advanced Peripheral Bus)外围总线。   AMBA 片上总线        AMBA 2.0 规范包括四个部分：AHB、ASB、APB和Test Methodology。AHB的相互连接采用了传统的带有主模块和从模块的共享总线，接口与互连功能分离，这对芯片上模块之间的互连具有重要意义。AMBA已不仅是一种总线，更是一种带有接口模块的互连体系。下面将简要介绍比较重要的AHB和APB总线。 基于 AMBA 的片上系统        一个典型的基于AMBA总线的系统框图如图３所示。        大多数挂在总线上的模块(包括处理器)只是单一属性的功能模块：主模块或者从模块。主模块是向从模块发出读写操作的模块，如CPU，DSP等；从模块是接受命令并做出反应的模块，如片上的RAM，AHB／APB 桥等。另外，还有一些模块同时具有两种属性，例如直接存储器存取(DMA)在被编程时是从模块，但在系统读传输数据时必须是主模块。如果总线上存在多个主模块，就需要仲裁器来决定如何控制各种主模块对总线的访问。虽然仲裁规范是AMBA总线规范中的一部分，但具体使用的算法由RTL设计工程师决定，其中两个最常用的算法是固定优先级算法和循环制算法。AHB总线上最多可以有16个主模块和任意多个从模块，如果主模块数目大于16，则需再加一层结构(具体参阅ARM公司推出的Multi-layer AHB规范)。APB 桥既是APB总线上唯一的主模块，也是AHB系统总线上的从模块。其主要功能是锁存来自AHB系统总...
    发表评论
    阅读全文

    【转】VxWorks套接口

    int m_socket;   // Open a socket        m_socket = socket(AF_INET, SOCK_STREAM, 0);   第一个参数 domain 说明我们网络程序所在的主机采用的通讯协族 (AF_UNIX 和 AF_INET 等 ). AF_UNIX 只能够用于单一的 Unix 系统进程间通信 , 而 AF_INET 是针对 Internet 的 , 因而可以允许在远程主机之间通信 . VxWorks 套接字仅支持 Internet 域地址族 , 不支持 UNIX 域地址族 . 因此在需要 domain 参数的函数中 , 使用 AF_INET 作为函数参数值 . 第二个参数 type 说明我们网络程序所采用的通讯协议 ( SOCK_STREAM , SOCK_DGRAM 等 ). SOCK_STREAM 表明我们用的是 TCP 协议 , 这样会提供按顺序的 , 可靠 , 双向 , 面向连接的比特流 . SOCK_DGRAM  表明我们用的是 UDP 协议 , 这样只会提供定长的 , 不可靠 , 无连接的通信 . 此外，还有 SOCK_RAW 代表是原始协议套接字 . 第三个参数 protocol, 由于我们指定了 type, 所以这个地方我们一般只要用 0 来代替就可以了 . socket 为网络通讯做基本的准备 , 成功打开则返回一个套接字描述符 , 如果失败则返回 ERROR. 套接字描述符是一个标准的 I/O 系统文件描述符 (fd, file descriptor), 可以被 close(), read(), write() 和 ioctl() 函数使用 .   // Make the socket sending alive messages when connected int flag = 1; setsockopt(m_socket, SOL_SOCKET, SO_KEEPALIVE, (char*)&flag, sizeof(flag));   // increase receive buffer siz...
    发表评论
    阅读全文

    【转】C++/CLI程序进程之间的通讯

    　现在，把大型软件项目分解为一些相交互的小程序似乎变得越来越普遍，程序各部分之间的通讯可使用某种类型的通讯协议，这些程序可能运行在不同的机器上、不同的操作系统中、以不同的语言编写，但也有可能只在同一台机器上，实际上，这些程序可看成是同一程序中的不同线程。而本文主要讨论C++/CLI程序间的通讯，当然，在此是讨论进程间通讯，而不是网络通讯。 　　 简介 　　试想一个包含数据库查询功能的应用，通常有一个被称为服务端的程序，等待另一个被称为客户端程序发送请求，当接收到请求时，服务端执行相应功能，并把结果（或者错误信息）返回给客户端。在许多情况中，有着多个客户端，所有的请求都会在同一时间发送到同一服务端，这就要求服务端程序要更加高级、完善。 　　在某些针对此任务的环境中，服务端程序可能只是众多程序中的一个程序，其他可能也是服务端或者客户端程序，实际上，如果我们的数据库服务端需要访问不存在于本机的文件，那么它就可能成为其他某个文件服务器的一个客户端。一个程序中可能会有一个服务线程及一个或多个客户线程，因此，我们需小心使用客户端及服务端这个术语，虽然它们表达了近似的抽象含义，但在具体实现上却大不相同。从一般的观点来看，客户端即为服务端所提供服务的"消费者"，而服务端也能成为其他某些服务的客户端。 　　 服务端套接字 　　让我们从一个具体有代表性的服务端程序开始（请看例1）,此程序等待客户端发送一对整数，把它们相加之后返回结果给客户端。 　　例1： using namespace System; using namespace System::IO; using namespace System::Net; using namespace System::Net::Sockets; int main(array<String^>^ argv) { if (argv->Length != 1) { Console::WriteLine("Usage: Server port"); Environment::Exit(1); } int port = 0; try { port = Int32::Parse(argv[0]); } catch (FormatException^ e) { Console::Wri...
    1 条评论
    阅读全文