Learning

STL学习笔记-1.1~2.2

笔记

p45

出现了::operator new和::operator delete，这个地方比较难理解。首先，先把new和delete当作一个操作符，因此要重载它的时候需要加个operator。

1
::operator new

这个语句的意思是在全局命名空间下的new操作符。

重要概念

模版特化

函数模版特化

比如设置了一个带有模版的函数，但是我想对其中的某种类型参数的函数进行单独定义。如果不含有这个机制的话，编译器会将其匹配到原始的模版函数中。例如

1
2
3
4
5
template <class T>
T max(T a,T b)
{
    return a<b ? b:a;
}

如果我想使用这个模版函数来处理字符串

1
2
3
char* p1="hello";
char* p2="world";
char* p3=max(p1,p2);

这时候会单纯地比较p1和p2两个指针数值本身的大小，而非对应的字符串。所以我们需要特化。

1
2
3
4
5
template<>
char* max(char* a,char* b)
{
    returan (strcmp(a,b)<0)?b:a;
}

这样才能让程序正确地被编译出来。

类模版特化

1
2
3
4
template <class T>
class stack {};
template < >
class stack<bool> { //…// };

偏特化

偏特化的意思就是对某些参数给定类型的时候给出特化方案。

类模版特化

1
2
3
4
template <class T, class Allocator>
class vector { // … // };
template <class Allocator>
class vector<bool, Allocator> { //…//};

函数模版特化

严格的来说，函数模板并不支持偏特化，但由于可以对函数进行重载，所以可以达到类似于类模板偏特化的效果。

1
template <class T> void f(T);  (a)

根据重载规则，对（a）进行重载

1
template < class T> void f(T*);  (b)

如果将（a）称为基模板，那么（b）称为对基模板（a）的重载，而非对（a）的偏特化。C++的标准委员会仍在对下一个版本中是否允许函数模板的偏特化进行讨论。

memory

std::allocator

这个文件是旧式做法的配置器。不建议使用它，所有的SGI STL头文件都没有包含它。

SGI的std::allocator只是对::operator new和::operator delete做了一层薄薄的包装。

stl_alloc.h

  • 负责内存空间的配置与释放
  • 包含了一二级的配置器，彼此合作。
设计哲学
  • 向system heap要求空间
  • 考虑多线程（multi-threads)状态。
  • 考虑内存不足时的应变措施。
  • 考虑过多的“小型区块”可能造成的内存碎片（fragment）问题。

当需要的区块大于128 Bytes的时候，会使用一级配置器来分配内存，如果是小于的话，则利用二级配置器，从free list中获取。

SGI STL缺省使用的空间配置器并不是标准的allocator，而是alloc。它在所有的需要空间配置器的类中使用的都是alloc。

例如

1
2
template <class T,class Alloc=alloc>
class vector {...};

一级配置器:__malloc_alloc_template

二级配置器:__default_alloc_template

无论是一级还是二级配置器，SGI都为其包装了一层薄薄的借口，使之能够符合STL的标准:

1
2
3
4
5
6
7
8
9
10
11
12
13
template<class T, class Alloc>
class simple_alloc {

public:
    static T *allocate(size_t n)
                { return 0 == n? 0 : (T*) Alloc::allocate(n * sizeof (T)); }
    static T *allocate(void)
                { return (T*) Alloc::allocate(sizeof (T)); }
    static void deallocate(T *p, size_t n)
                { if (0 != n) Alloc::deallocate(p, n * sizeof (T)); }
    static void deallocate(T *p)
                { Alloc::deallocate(p, sizeof (T)); }
};
free list

这个结构存储这个多个区块，同时拥有一个节点的数据结构

1
2
3
4
union obj {
        union obj * free_list_link;
        char client_data[1];    /* The client sees this.        */
  };

这个结构的就只包含一个指针，在64位系统中，这个指针的大小位8个字节。因此在free list中，如果想要存储小于8个字节的区块时是会失败的。每个区块实际上都存着一个obj结构。这里的设计的妙处在于，我们通常都会用一个节点结构，这个节点结构后面再挂着实际区块。例如

1
2
3
4
struct obj{
    struct obj* next_obj;
    char* addr;
};
chunk_alloc()

这样我们就需要16个字节来表示一个区块，而且这16个字节还不是区块本身的字节。因此孰优孰劣，一目了然。

stl_construct.h

负责对象内容的构造与析构

其中的__type_traits<> 将在3.7节中有详细介绍。

分享到