1、algorithm(算法)、container(容器)和iterator(迭代器),并包括一些工具类如auto_ptr。几乎所有的代码都采用了模板类和模板函数的方式,这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。下面就由为大家介绍一下C+STL笔试题的文章,欢迎阅读。 C+STL笔试题篇1 1C+ STL 之所以得到广泛的赞誉,也被很多人使用,不只是提供了像vector, string, list等方便的容器,更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组,list封装了链表,map和set封装了二叉树等 2标准关联容器set, mul
2、tiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树:红黑树,也成为RB树(Red-BlackTree)。RB树的统计性能要好于一般的平衡二叉树 3STL map和set的使用虽不复杂,但也有一些不易理解的地方,如: map: type pair,很多不同的const Key对应的T对象的一个集合,所有的记录集中只要const Key 不一样就可以,T无关! set: type const Key 只存单一的对const Key,没有map 的T对像!可以看成map的一个特例 (1)为何map和set的插入删除效率比用其他序列容器高?,树 答:因为对于关联容器来说
3、,不需要做内存拷贝和内存移动。说对了,确实如此。map和set容器内所有元素都是以节点的方式来存储,其节点结构和链表差不多,指向父节点和子节点 (2)为何每次insert之后,以前保存的iterator不会失效?iterator这里就相当于指向节点的指针,内存没有变,指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。相对于vector来说,每一次删除和插入,指针都有可能失效,调用push_back在尾部插入也是如此。因为为了保证内部数据的连续存放,iterator指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时push_back的时候,容器内部空间可能不够,需要一块新的更大的内存,只有把以前的内存释放,申请新的更大的内存,复制已有的数据元素到新的内存,最后把需要插入的元素放到最后,那么以前的内存指针自然就不可用了。特别时在和find等算法在一起使用的时候,牢记这个原则:不要使用过期的iterator。