面向自由编程

结构

G2.9源码结构

在低版本下list的结构比较简单，就是一个list模板类和一个node模板类。总体的数据结构事宜个环形双向链表。
begin()指向头结点，end()指向尾节点。

stack

G2.9版本

底层结构：hashtable

unordered set/map底层是以hashtable为数据结构，任何对象/类都可以折射成一个数值（类对象都是由数据构成，对数据进行一些操作然后hash就可以转化成一个数值）.

为什么set/map底层用红黑树而不用AVL树？

红黑树与AVL比较：

1. AVL是严格平衡的，频繁的插入和删除，会引起频繁的rebalance，导致效率降低；红黑树是弱平衡的，算是一种折中，插入最多旋转2次，删除最多旋转3次。

2. 红黑树在查找、插入删除的复杂度都是O(logn)，且性能稳定，所以STL里面很多结构包括map底层都是使用的红黑树。

VC6 malloc

• 想要搞清malloc是怎么运作的，就必须直到malloc首次分配内存进行了哪些操作，进行了哪些初始化。

• 很多人认为我们执行一个cpp文件是从main函数开始，但是实际上系统还会为我们进行一系列的环境准备，这些动作通常包含了环境变量的获取、堆的初始化等等一系列操作，在不同环境下可能略有不同。在cpp文件执行之后也存在很多善后操作，这个会在c++前世今生详细介绍。

• 下面来看一下vc环境下会有哪些动作.

  Read more »

allocate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

template<typename _Tp>
class bitmap_allocator: private free_list{
    pointer 
    allocate(size_type __n)
    {
        if (__n > this->max_size())
            std::__throw_bad_alloc();

        if (__builtin_expect(__n == 1, true))//如果数量为1个,则调用_M_allocate_single_object()
            return this->_M_allocate_single_object();
        else	//如果申请的数量大于1个,则直接调用operator new
        { 
            const size_type __b = __n * sizeof(value_type);
            return reinterpret_cast<pointer>(::operator new(__b));
        }
    }
}

单例模式

参考github
这个网站也非常生动。

VC6/BC5/G2.9(std::allocator)