`

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

阅读更多

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

摘要:本文列出几个基本的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会大大降低你的编码难度,同时增加程序的可读性。何乐而不为?

 

转自 : http://blog.sina.com.cn/s/blog_5d2b79d20100bg61.html

分享到:
评论

相关推荐

    学习STL MAP, STL SET之数据结构基础

    本文将深入探讨这两个容器的数据结构基础,以及它们在插入、删除和迭代器有效性方面的特性。 首先,`map`和`set`在STL中的高效性主要来源于它们内部采用的平衡检索二叉树——红黑树(Red-Black Tree,简称RB树)。...

    学习STL+MAP%2C+STL+SET之数据结构基础.

    STL中的`map`和`set`是两种关联容器,它们在C++编程中被广泛使用,主要得益于它们高效的数据结构——红黑树(Red-Black Tree)。红黑树是一种自平衡的二叉查找树,它确保了在最坏情况下的时间复杂度为O(log n),从而...

    STL中map、set的数据结构及底层实现.docx

    在这个文档中,主要讨论了STL中两种关联容器——map和set的数据结构及其底层实现。 首先,map是一个键值对的集合,它将唯一的键映射到相应的值。在STL中,map通常使用红黑树(Red-Black Tree)作为其底层数据结构。...

    windbg导出stl map和set的插件

    这两个容器都基于红黑树数据结构,这使得它们能快速进行查找、插入和删除操作。 在没有这个插件的情况下,分析内存中的STL容器通常需要深入理解底层内存布局和容器的实现细节。这不仅复杂,而且容易出错。stlkit....

    STL中map、set的数据结构及底层实现.pdf

    STL中的map和set是两种关联容器,它们都基于一种高效的数据结构——红黑树(Red-Black Tree)进行实现。这种数据结构是一种自平衡的二叉查找树,能够保证在最坏情况下的搜索、插入和删除操作的时间复杂度为O(log n)...

    使用STL学习数据结构

    标题"使用STL学习数据结构"意味着本书将深入讲解如何利用STL来实现和理解各种数据结构。STL包括容器(如vector、list、set、map等)、迭代器、函数对象(functors)以及算法库。通过STL,开发者可以轻松地操作和管理...

    数据结构与(STL)(collins)

    数据结构与STL是计算机科学中的重要组成部分,特别是在软件开发和算法设计中起着核心作用。数据结构是指在计算机中组织和存储数据的方式,而STL(Standard Template Library,标准模板库)是C++编程语言中的一组通用...

    STL基础栈链表map set

    STL(Standard Template Library,标准模板库)是C++中的一个重要组成部分,提供了丰富的数据结构和算法,极大地简化了程序开发工作。在本篇内容中,我们将详细介绍STL中的几个基本概念:栈(Stack)、链表(List)...

    C语言版的STL,包含set,list,map等基本数据结构和算法.zip

    STL是C++的一个重要组成部分,它提供了一组高效的数据结构(如set、list、map)和算法,使得开发者可以更方便地处理数据。在C语言中,我们通常需要自己实现这些数据结构和算法,这既耗时又容易出错。而C语言版的STL...

    C++ STL--数据结构与算法实现(余文溪)示例程序代码.rar

    1. 容器(Containers):这是STL的基础,它们是存储数据的对象,如`vector`(动态数组)、`list`(双向链表)、`set`(红黑树实现的集合)、`map`(关联数组)等。每个容器都有其特定的内存管理和访问特性,开发者可以根据...

    在STL的map或set容器中使用类作为key

    ### 在STL的map或set容器中使用类作为key #### 概述 在C++标准模板库(STL)中,`map` 和 `set` 容器是两种非常重要的容器类型,它们提供了高效的键值对管理和有序集合的管理方式。在实际应用中,我们常常需要使用...

    数据结构各种结构的stl实现

    学习这些STL数据结构和算法,对于理解和编写高效的C++代码至关重要。通过实践和深入理解,你将能够更好地应对各种编程挑战,并为未来的编程生涯打下坚实基础。在实习过程中,熟练运用STL不仅能提高工作效率,还能...

    数据结构(STL框架)PPT

    在STL框架下学习数据结构,你将深入理解如何使用这些组件来优化代码的性能和可读性。例如,通过合理选择容器类型,可以提高程序运行效率;利用迭代器和算法,可以实现复杂的数据操作而不必关心底层实现细节。此外,...

    STL 中的常用的Vector Map Set Sort用法

    本篇文章将详细探讨STL中的四个常用组件:`vector`、`map`、`set`以及排序算法`sort`的用法。 1. `vector`: `vector`是STL中最基本的动态数组,它允许在运行时动态增加或减少元素。`vector`提供了许多便利的方法...

    数据结构C++语言描述——应用标准模板库(STL)

    在《数据结构C++语言描述——应用标准模板库(STL)》这本书中,你将深入学习如何利用STL来实现常见的数据结构,如堆、队列、栈等。作者可能通过实例演示了如何使用STL容器、算法和函数对象来解决实际问题,同时也...

    数据结构与STL源代码

    数据结构与STL(Standard Template Library)源代码是学习C++编程中不可或缺的一部分,特别是对于提升算法和程序设计能力至关重要的领域。STL是C++标准库的核心部分,它提供了高效且灵活的容器、迭代器、算法和函数...

Global site tag (gtag.js) - Google Analytics