关于STL与泛型编程学习感想二（博览网）

体系结构与内核分析

本机使用了两个编译器

Visual C++ 6.0标准库位于：...\Program Files (x86)\Microsoft Visual Studio 14.0\VC\include

devcpp标准库位于：...\4.8.1\inlcude

面向对象编程（OOP)VS泛型编程(GP)

OOP:Object-Oriented programmingGP:Generic programming

OOP企图将datas和methods关联在一起

list不能使用全局的sort()排序，因为全局sort()需要的是随机访问迭代器，而list因为内存模型的原因，不是连续空间，在内存中它是由指针一个一个串起来,不能有iterator+5这种操作，所以它不能提供这种迭代器。

GP却是将datas和methods分开来,两者之间通过迭代器联系在一起。

分开的优点：

（1）Containers和Algorithms团队可各自独立开发，其间以Iterator沟通即可；做好接口就行

（2）Algorithms通过Iterators确定操作范围，并通过Iterators取用Container元素。

vector、deque等容器都提供RandomAccessIterator

template

class list{

...

void sort();

}

所有的algorithms，最终设计元素本身的操作，无非就是比大小。比如说重新定义max函数，根据字符长度来比大小，我们就必须重写一个比较函数。

所有algorithms，其内最终涉及元素本身的操作，无非就是比大小

bool strLonger(const string& s1,const string& s2) {return s1.size() < s2.size();}

cout<<"max of zoo and hello:"<

cout<<"longest of zoo and hello:"<

template

inline const T& max(const T& a,const T& b){

return a

}template

inline const T& max(const T& a,const T& b,Compare comp){

return comp(a,b)?b:a;

}

操作符重载 Operator Overloading

operator是C++的关键字，它和运算符一起使用，表示一个运算符函数，理解时应将operator=整体上视为一个函数名。

操作符重载实现为类成员函数

重载的操作符在类体中被声明，声明方式如同普通成员函数一样，只不过他的名字包含关键字operator，以及紧跟其后的一个c++预定义的操作符。

函数模板

（节选于前面课程笔记）

template

inline

constT&min(constT&a, constT&b)

{  return b

函数模板是一种不说明某些参数的数据类型的函数。函数模板被调用时，编译器根据实际参数的类型确定模板参数T的类型，并自动生成一个对应的函数。定义函数模板时也可以使用多个类型参数，这时，每个类型参数前面都要加上关键字class 或typename，其间用逗号分隔。

成员模板（member template）

任意类（模板或非模板）可以拥有本身为类模板或函数模板的成员，这种成员称为成员函数模板。

template

struct pair{

typedef T1 first_type;

typedef T2 second_type;

T1 first;

T2 second;

pair()：first(T1()),second(T2()) {}

pair(const T1 &a,const T2 &b):first(a),second(b) {}

template     //成员模板

pair(const pait &p)//T1和T2类型确定了以后，U1和U2也能进行确定

:first(p.first),second(p.second) {}

}

这里一共有三个模板：类模板，函数模板，成员模板。关于区别

参考：http://blog.csdn.net/zhangyulin54321/article/details/7897246

模板特化 （specialization）

泛化[全泛化]（模板等）与特化是对立的，特化，就是将泛型的东东搞得具体化一些，从字面上来解释，就是为已有的模板参数进行一些使其特殊化的指定，使得以前不受任何约束的模板参数或受到特定的修饰或完全被指定了下来。

template

struct hash{ };    // 泛化

template<>

struct hash{

size_t operator() (char x) const {return x;}//  重载()

};                        //特化

特化与偏特化资料：http://www.jb51.net/article/56004.htm

模板偏特化（partial specialization）

偏特化就是模板中的模板参数没有被全部确定，需要编译器在编译时进行确定。

个数上的偏特化，范围上的偏特化

个数上的偏特化

template

class vector

{...};

template         //Alloc为分配器

class vector

{...};

范围上的偏特化

template   //泛化 任何类型均可

class C{...};

template   //特化 指定指针

class C

{...};

C obj1;

C obj2;

模板模板参数（template template parameter）

将一个模板作为另一个模板的参数。

templateclass container>

class XCls

{

private:

containerc;

public:

......

};

template

using Lst=list>;

XCls mylst2;

分配器

分配器（Allocator）是容器管理内存的工具，在容器申请内存空间上起作用。

分配器在底层实现上通过operator new()和operator delete()来完成内存分配和释放，而operator new()和operator delete()实际上是通过调用malloc()和free()函数来实现操作。

源代码可以看出，无论是VC、BC还是GNU的版本中分配器实际上是通过operator new和operator delete来调用malloc和free来管理内存（allocate()和deallocate(),没有什么特殊设计）。

但是在GNU2.9中，容器实际使用的并非是allocator，而是alloc。

//VC6使用allocator，分配512ints

int* p=allocator().allocate(512,(int*)0);

allocator().deallocate(p,512);

//BC5使用allocator，分配512ints

int* p=allocator().allocate(512);

allocator().deallocate(p,512);

//GNU2.9使用allocator，分配512bytes

void* p=alloc::allocate(512);  //也可以alloc().allocate(512);

alloc::deallocate(p,512);

alooc的最终实现内存管理也是通过malloc和free，但是可以避免其他额外开销，比如cookie（记录整块的大小）

配器查看链条有没有挂内存块，如果没有，向操作系统要内存，得到的内存块除了头尾有cookie，中间的每一小块内存都不带cookie；

实现过程示意图如下图所示：

容器的结构与分类

（部分节选自前面课程笔记）

序列式容器（排列有一定秩序），关联式容器（key适合做快速查找）、UNordered containers（不定序容器，前身是关联式容器 ）

序列式容器：数组array（连续空间，固定内存，不能再扩充）、Vector（向量，前面固定，后面还可以扩充）、Deque（双向队列，两端都可扩充）、链表List（不连续，用指针相连，双向环状链表）Forward-List（单向链表）

关联式容器：set/multiset（set中key不可重复，multiset可以|后面map相同） （key就是vault）二分树（高度平衡）map/multimap（有key和vault）在STL中关联容器使用红黑树来实现，因为不是顺序结构，因而不能使用上面提到的push和pop函数，使用insert和erase函数来实现元素的插入删除操作。关联容器支持通过键来高效地查找和读取元素，两个基本的关联容器类型是map和set。map的元素以键-值（key-value）对的形式组织：键用于元素在map中的索引，而值则表示所存储和读取的数据。set仅包含一个键，并有效地支持关于某个键是否存在的查询。map可理解为字典，set可理解为一类元素的集合。关联容器和顺序容器的本质差别在于：关联容器通过键（key）存储和读取元素，而顺序容器则通过元素在容器中的位置顺序存储和访问元素。set 和 map 类型的对象所包含的元素都具有不同的键，不允许为同一个键添加第二个元素。如果一个键必须对应多个实例，则需使用 multimap 或 multi set，这两种类型允许多个元素拥有相同的键。

不定序容器：  hashtable、separate chaining、UNordered set/multiset、UNordered map/multimap

每个单元独立（每段测试独立放一个namespace）

测试程序变量声明不放在最前面，用之前声明

设S表示一种容器类型（如：vector），s1、s2都是S类型的实例，容器都具有如下基本功能：

S s1  容器的默认构造函数，用于构造一个没有任何元素的空容器。

s1 op s2  对两容器之间的元素按字典序进行比较，op表示==、!=、<、<=、>、>=任何一个。

s1.begin()  返回指向s1第一个元素的迭代器。

s1.end()  返回指向s1最后一个元素的下一个位置的迭代器。

s1.empty()  表示s1容器是否为空，返回一个布尔值。

s1.size()  返回s1容器中元素的个数。

s1.swap(s2)  将s1容器和s2容器的内容交换。

下图以缩排形式表达“基层与衍生层”的关系。这里所谓衍生，并非继承而是复合。

在C++11中，slist名为forward_list,hash_set,hash_map名为unordered_set，unordered_map,hash_multiset,hash_multimap名为unordered_multiset,unordered_multimap;且新添array。

容器LIST

list 和vector是两个最常用的容器（序列式容器）。二者最显著的区别自然就是vector是连续线性空间，list则是不连续线性空间，相比于vector（动态数组），它的好处是每次插入和删除一个元素，只需配置或释放一个元素空间，对于任何位置的元素插入或元素移除，list永远是常数时间。

GNU2.9和4.9刻意在环状list尾端加一空白节点node，用以符合ST“前闭后开”区间。

GNU4.9相较于GNU2.9：

模板参数只有一个；

node结构有其parent；

node的成员的type较精确；

list 的迭代器

因为链表节点在储存空间中不一定是连续存在的，自然也就不能像vector一样用普通指针作为迭代器。list迭代器必须有能力指向list的节点，并有能力正确的递增。递减。取值、成员存取等操作。这是作为任何一个容器的迭代器必须具备的。对于非连续空间的递增，递减等操作自然是针对该容器的属性来的，就list而言，则是指向上一个节点，下一个节点，以及获取指定节点。

STL list是一个双向链表，迭代器必须具备前移，后移的能力，所以list提供的是bidirectional iterator （双向一个个移动）。

self operator++(int){self tem=*this ;++*this; return tmp;}(i++)

//1.记录原值2.进行操作调用了前++3.返回原值

self& operator++(){node =(link_type)((*node).next);return *this;} (++i)

Iterators的设计原则

Iterators必须有能力回答算法的五个问题，也就是说Iterators必须提供五种associated types。(category,value,pointer,reference,difference;reference和pointer用得很少)

为了分离class Iterators和non-class Iterators，就产生了Iterator traits，并且可以通过偏特化实现。

其他各式各样的traits

type traits                    <.../C++/type_traits>

iterator traits     <.../C++/bits/stl_iterator.h>

char traits     <.../C++/bits/char_traits.h>

allocator traits     <.../C++/bits/alloc_traits.h>

pointer traits             <.../C++/bits/ptr_traits.h>

array traits     <.../C++/bits/array>

容器vector深度探索

参考资料：http://blog.csdn.net/wenqian1991/article/details/19486317

vector是C++STL中一种线性容器，其分配元素在内存中是连续存储的，本质是一个可变数组，当申请的空间在需要的时候默认以倍增的形式扩充。

vector将其元素置于一个动态数组中加以管理，与 array 非常类似，两者的唯一差别在于空间运用的灵活性，array 是静态空间，一旦配置了就不能更改，当需要容纳更多的元素时(此时已越界)，需要重新手动配置更大的 array 空间，然后重新置入数据。而 vector 是动态空间，在同样的情况下，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。

vector同 array 一样可以很方便的通过索引值直接存取任何一个元素，在数组的尾端追加或移除元素均非常快速(当追加元素超出原有分配空间时，vector需要重新分配空间)，但在其中间或头部插入移除元素就比较费时，需要移动安插点之后的所有元素以保持原来的相对位置。

深度探索array

array是一个固定大小的顺序容器，不能动态改变大小，array内的元素在内存中以严格的线性顺序存储，与普通数组声明存储空间大小[]的方式是一样有效的，只是加入了一些成员函数和全局函数[get (array)、operators (array)]，以便当作标准容器使用。与list和vector的iterator类似，有一种iterator traits用以分类class Iterators和non-class Iterators。