Tips:
- Generic Programming 将算法和数据结构分开，让其可以独立设计。
- 所有算法最终就是在比大小。
- 操作符重载和模板在STL中占相当重要的位置。
- STL是主要是使用 Generic Programming 的方式实现的
1. Befor All
-
STL六大部件关系
-
“前闭后开”区间
STL中的容器均为此类空间。
2. 分配器 allocators
- 不建议直接使用，因为其使用方法很不友好。
- 作为容器的基础支持部分，其优劣十分重要，若质量太差会造成效率大幅降低。
- C++中所有申请内存都会调用
malloc()，而malloc()得到的内存会附带一定的 overhead ，当数据本身较小时，空间浪费较严重。 - allocator 最重要的两个函数：
allocate和deallocate。前者申请内存，后者释放内存。 - 多数实现的 allocator 以
::operator new()和::operator delete()完成allocate和deallocate，没有任何特殊设计。
实现(以VC6为例)
#ifndef _FARQ
#define _FARQ
#define _PDFT ptrdiff_t
#define _SIZT size_t
#endif
#define _POINTER_X(T,A) T_FARQ*
#define _REFERENCE_X(T,A) T_FARQ&
template<typename _Ty>
class allocator
{
public:
typedef _SIZT size_type;
typedef _PDFT difference_type;
typedef _Ty _FARQ *pointer;
typedef _Ty value_type;
pointer allocate(size_type _N, const void *)
{ return (_Allcoate(difference_type(_N), pointer(0))); }
void deallocate(void _FARQ *_P, size_type)
{ operator delete(_P); }
};
template<typename _Ty>
inline _Ty _FARQ *_Allocate(_PDFT _N, _Ty _FARQ *)
{
if (_N < 0)
_N = 0;
return (_Ty _FARQ *)operator new(_SIZT(_N) * sizeof(_Ty));
}
3. 容器之间的实现关系
4. 容器 list
5. 迭代器 iterator 和 Iterator Traits
- 五个必须的
typedef
A.iterator_category:记录 iterator 的分类
B.value_type:记录数据类型
C.pointer:记录数据指针
D.reference:记录数据引用
E.difference_type:记录指针距离的类型 - 重载++、--操作符时：用
operator++()、operator--()表示前置++、--；用operator++(int)、operator--(int)表示后置++、--。 - 指针被视为一种退化的 iterator 。算法想要提取 iterator 的特征时可以通过 iterator traits 来识别指针和 iterator ，进而由 iterator traits回答算法。
实现
6. 容器 vector
