stl对于小内存块请求与释放的处理 STL考虑到小型内存区块的碎片问题，设计了双层级配置器，第一级配置直接使用malloc()和free()；第二级配置器则视情况采用不同的策略，当配置区大于128bytes时，直接调用第一级配置器；当配置区块小于128bytes时，便不借助第一级配置器，而使用一个memory pool来实现。究竟是使用第一级配置器还是第二级配置器，由一个宏定义来控制。SGI STL中默认使用第二级配置器。二级配置器会将任何小额区块的内存需求量上调至8的倍数，(例如需求是30bytes,则自动调整为32bytes)，并且在它内部会维护16个free-list， 各自管理大小分别...

set：所有元素根据键值自动被排列。而且不允许有相同的值 set的迭代器是不允许修改set元素值，会严重破坏set组织。iterator 是一种 constant iterators。删除和新增，不会使原来的迭代器失效（是因为，树以节点的形式存着，树的样子虽然在变，但是也是指针指向内容在变） 对于关联容器，应该使用容器提供的find，因为STL算法里的find，是按照顺序的。 map:也会根据元素的键值自动被排序。map不能修改键值，但是能修改value. 俩者不能重复，实现的机制是，RB-tree里的insert_unique;首先先查找，是否有对应的值，有的话就不插入了。真正插入的函数是_...

Copy算法 STL中通过使用copy函数以提供一种方便的方式来输出容器中的元素。函数copy作为泛型算法的一部分，任何容器类型都可以使用。 copy算法利用函数重载，对char 和wchar_t 的操作直接memmove，利用模版特化对于有trivial operator=的操作memmove，对于RandomAccessIterator通过头尾间隔来确定循环次数，对于InputIterator通过不断累加是否到达last来确定循环次数。 它允许我们复制元素从一个地方到另一个地方。例如输出vector的元素或复制vector的元素到另一个vector，我们可以使用copy函数。函数原型是:...

Heap堆是常用的数据结构,但STL中并没有提供Heap容器，只是提供了关于Heap操作的算法。只要支持RandomAccessIterator的容器都可以作为Heap容器。 Heap分为max heap和min heap，max heap中每次取出的结点时heap结构中值最大的结点，min heap中每次取出的结点时heap结构中值最小的结点。也就是不允许遍历节点,因此heap没有迭代器. 在STL中,heap是作为priority queue(优先队列)的助手出现的. push_heap算法方法是层层上挪，直到正确的位置. template inline void push_heap(R...

1.迭代器的定义 迭代器是一种抽象的设计概念，迭代器是一种数据结构，提供统一方法（如遍历，获取元素）对容器内部的元素进行操作，而又无需暴露容器元素的内部表达方式。 举个例子，指针可以看做是数组的迭代器（尽管不太符合STL规范），但是指针有很多种，我们可以提供一个封装来解决这个问题 template<tyname PtrType> class Proxy { PtrType* ProxyPtr; //…… } 通过模板，我们用Proxy这个类统一了指针 Proxy<int>就是int指针Proxy<string>就是string指针. 它提供...

令人会产生疑问的语法形式 __STL_NULL_TMPL_ARGS 这个组态往往用在 class template 的 friend 函数声明中. 例如 stack 源码中: template > class stack { friend bool operator== __STL_NULL_TMPL_ARGS (const stack&,const stack&); friend bool operator< __STL_NULL_TMPL_ARGS (const stack&,const stack&); } ...

title: 模拟STL顺序容器list 相对于vector的连续线性空间,list每次插入或删除一个元素就会分配或者释放一块空间.因此,list对空间的运用十分精准. 重点说一下list的插入和移除操作: 插入一个节点作为尾节点,思路是申请一块内存,将原list节点最后一个节点的 next 指向这个内存,并将该节点的next 设置为NULL. 当需要在中间插入一个节点时,先遍历找到需要插入节点的前一个节点node1,然后将node1的next指向该节点 并将该节点的next指向node1原来的下一个节点node2. 移除操作当需要移除一个尾节点node1时,将前...

Vector源码 准备工作: C++标准库「memory」,用它的Allocator类来作配置器 allocate(std::size_t n, const void * hint) 参数: size_t n - 为其分配存储空间的对象数量 const void* hint - 指向附近内存位置的指针 返回指向适当对齐的内存块的第一个字节的指针，并且足以容纳一个n类型的对象数组T std :: uninitialized_fill( ForwardIt first, ForwardIt last, const T& value) 参数: F...