更新网站内容,做网站如何排版,wordpress 插件和工具栏,网页设计与网站建设案例教程一、STL简介 STL提供六大组件#xff0c;彼此可以组合套用#xff1a;
容器 容器就是各种数据结构#xff0c;我就不多说#xff0c;看看下面这张图回忆一下就好了#xff0c;从实现角度看#xff0c;STL容器是一种class template。 算法 各种常见算法#xff0c;如sor… 一、STL简介 STL提供六大组件彼此可以组合套用
容器 容器就是各种数据结构我就不多说看看下面这张图回忆一下就好了从实现角度看STL容器是一种class template。 算法 各种常见算法如sortsearchcopyerase等我觉得其中比较值得学习的就是sortnext_permutationpartitionmerge sort从实现角度看STL算法是一种function template。迭代器 扮演容器与算法之间的胶合剂是所谓的“泛型指针”。共有五种类型从实现角度看迭代器是一种将operator*operator-operatoroperator--等指针相关操作予以重载的class template。所有STL容器都附带有自己专属的迭代器只有容器设计者才知道如何设计迭代器。原生指针也是一种迭代器。是设计模式的一种所以被问到了解的设计模式可以用来凑数。仿函数 行为类函数可作为算法的某种策略从实现角度看仿函数是一种重载了operator()的class或class template。一般函数指针可视为狭义的仿函数。配接器 一种用来修饰容器或者仿函数或迭代器接口的东西。比如queue和stack看着像容器其实就是deque包了一层皮。配置器 负责空间配置与管理。从实现角度看配置器是一个实现了动态空间配置、空间管理、空间释放额class template。 二、关于容器的一些问题 2.1 当vector的内存用完了它是如何动态扩展内存的它是怎么释放内存的用clear可以释放掉内存吗是不是线程安全的
vector内存用完了会以当前size大小重新申请2*size的内存然后把原来的元素复制过去把新元素插上然后释放原来的内存。一般我们释放vector里的元素使用clear其实它不能释放内存要想释放内存要使用swap这样 vectortype v;//.... 这里添加许多元素给v//.... 这里删除v中的许多元素vectortype(v).swap(v);//此时v的容量已经尽可能的符合其当前包含的元素数量//对于string则可能像下面这样string(s).swap(s); 引用《effective stl》的第十二条当涉及 STL容器和线程安全性时你可以指望一个 STL库允许多个线程同时读一个容器以及多个线程对不同的容器做写入操作。你不能指望 STL库会把你从手工同步控制中解脱出来而且你不能依赖于任何线程支持。必须自己去写多线程安全措施。 2.2 map是怎么实现的查找的复杂度是多少能不能边遍历边插入 红黑树和散列 O(logn) 不可以map不像vector它在对容器执行erase操作后不会返回后一个元素的迭代器所以不能遍历地往后删除。 2.3 写多读少应该用什么容器 私以为是链表链表的插入操作时常数时间复杂度访问操作是O(n)是最适合写多读少的容器。 2.4 vector每次insert或erase之后以前保存的iterator会不会失效 理论上会失效理论上每次insert或者erase之后所有的迭代器就重新计算的所以都可以看作会失效原则上是不能使用过期的内存 但是vector一般底层是用数组实现的我们仔细考虑数组的特性不难得出另一个结论 insert时假设insert位置在p分两种情况 a) 容器还有空余空间不重新分配内存那么p之前的迭代器都有效p之后的迭代器都失效 b) 容器重新分配了内存那么p之后的迭代器都无效咯 erase时假设erase位置在p则p之前的迭代器都有效并且p指向下一个元素位置如果之前p在尾巴上则p指向无效尾endp之后的迭代器都无效 2.5 hash_map和map的区别在哪里 hash_map底层是散列的所以理论上操作的平均复杂度是常数时间map底层是红黑树理论上平均复杂度是O(logn)下面是借鉴的网上的总结 这里总结一下选用map还是hash_map关键是看关键字查询操作次数以及你所需要保证的是查询总体时间还是单个查询的时间。如果是要很多次操作要求其整体效率那么使用hash_map平均处理时间短。如果是少数次的操作使用 hash_map可能造成不确定的O(N)那么使用平均处理时间相对较慢、单次处理时间恒定的map考虑整体稳定性应该要高于整体效率因为前提在操作次数较少。如果在一次流程中使用hash_map的少数操作产生一个最坏情况O(N)那么hash_map的优势也因此丧尽了。 2.6 为何map和set不能像vector一样有个reserve函数来预分配数据 map和set内部存储的已经不是元素本身了而是包含元素的节点。也就是说map内部使用的Alloc并不是map声明的时候从参数中传入的Alloc。例如 mapint, int, less, Alloc intmap; 这时候在intmap中使用的allocator并不是Alloc, 而是通过了转换的Alloc具体转换的方法时在内部通过 Alloc::rebind重新定义了新的节点分配器详细的实现参看彻底学习STL中的Allocator。 其实你就记住一点在map和set里面的分配器已经发生了变化reserve方法你就不要奢望了。 2.7 当数据元素增多时10000和20000个比较map和set的插入和搜索速度变化如何 算一下就知道了首先你得知道map和set的底层都是红黑树红黑树的搜索近似于二分查找二分查找呢平均时间复杂度是log2n,这里简写成logn, 狂按计算器 log(10000) 13.3 log(20000) 14.3 看到了不理论上平均就多了一次所以你懂的插起来。。。 2.8 auto_ptr可以做vector的元素呢为什么 不能。因为STL的标准容器规定它所容纳的元素必须是可以拷贝构造和可被转移赋值的。而auto_ptr不能可以用shared_ptr智能指针代替。 三、关于迭代器的一些问题 3.1 traits技术原理及应用 这个问题还真不知咋讲简单来说在STL算法中用到迭代器时肯定会用到会用到迭代器所指之物的型别假设算法中有必要声明一个变量以迭代器所指之物为型别但是C只支持sizeof()、并未 支持typeof()。即使typeid()也只能获得型别名称不能拿来声明变量所以这里就要用到作为”特性萃取机“的traits技术当然要让traits有效运作每个迭代器设计的时候的遵守约定自行以内嵌型别定义的方式定义出相应型别。 详情请看书或者移步Traits技术类型的if-else-then(STL核心技术之一) 四、关于算法的一些问题 4.1 快排算法的枢轴位置是怎么选择的 三点中值法取整个序列的头、尾、中央三个位置的元素以其中值作为枢轴。 4.2 简单说一下next_permutation和partition的实现 next_permutation下一个排列 首先从最尾端开始往前寻找两个相邻元素另第一个元素为i第二个元素为ii且满足iii。找到这样一组相邻元素后再从尾端开始往前检验找出第一个大于i的元素j将ij元素对调再将ii之后的所有元素颠倒排列。此即所求“下一个”排列组合。 partition 令头端迭代器first向尾部移动尾部迭代器last向头部移动。当first所指的值大于或等于枢轴时就停下来当last所指的值小于或等于枢轴时也停下来然后检验两个迭代器是否交错。如果first仍然在last左边就将连着元素互换然后各自调整一个位置向中央逼近再继续进行相同的行为。如果发现两个迭代器叫错了表示整个序列已经调整完毕。 五、关于内存配置的一些问题 5.1 stl对于小内存块请求与释放的处理 STL考虑到小型内存区块的碎片问题设计了双层级配置器第一级配置直接使用malloc()和free()第二级配置器则视情况采用不同的策略当配置区大于128bytes时直接调用第一级配置器当配置区块小于128bytes时便不借助第一级配置器而使用一个memory pool来实现。究竟是使用第一级配置器还是第二级配置器由一个宏定义来控制。SGI STL中默认使用第二级配置器。 二级配置器会将任何小额区块的内存需求量上调至8的倍数(例如需求是30bytes,则自动调整为32bytes)并且在它内部会维护16个free-list 各自管理大小分别为8 16 24…128bytes的小额区块这样当有小额内存配置需求时直接从对应的free list中拔出对应大小的内存(8的倍数)当客户端归还内存时将根据归还内存块的大小将需要归还的内存插入到对应free list的最顶端。 小结 STL中的内存分配器实际上是基于空闲列表(free list)的分配策略最主要的特点是通过组织16个空闲列表对小对象的分配做了优化。 1小对象的快速分配和释放。当一次性预先分配好一块固定大小的内存池后对小于128字节的小块内存分配和释放的操作只是一些基本的指针操作相比于直接调用malloc/free开销小。 2避免内存碎片的产生。零乱的内存碎片不仅会浪费内存空间而且会给OS的内存管理造成压力。 3尽可能最大化内存的利用率。当内存池尚有的空闲区域不足以分配所需的大小时分配算法会将其链入到对应的空闲列表中然后会尝试从空闲列表中寻找是否有合适大小的区域 但是这种内存分配器局限于STL容器中使用并不适合一个通用的内存分配。因为它要求在释放一个内存块时必须提供这个内存块的大小以便确定回收到哪个free list中而STL容器是知道它所需分配的对象大小的比如上述 stl::vector array; array是知道它需要分配的对象大小为sizeof(int)。一个通用的内存分配器是不需要知道待释放内存的大小的类似于free(p)。 详情请看书或移步STL源码剖析---空间配置器 六、关于线程安全的一些问题
