[C++](STL和泛型编程)

文章目录


认识headers

[C++](STL和泛型编程)
[C++](STL和泛型编程)
C++ 标准库(STL大部分属于C++标准库) —STL和标准库的关系

STL各组件应用实例

STL体系结构基础介绍

[C++](STL和泛型编程)
1.容器帮助我们吧内存的问题解决,需要一个分配器来支持容器,容器是一个模板类,有一些操作是自己做,更多的是独立出来成为算法。算法和容器之间的桥梁是迭代器,迭代器是一种泛化的指针

STL分为六大组件:

容器(container):常用数据结构,大致分为两类,序列容器,如vector,list,deque,关联容器,如set,map。在实现上,是类模板(class template)
迭代器(iterator):一套访问容器的接口,行为类似于指针。它为不同算法提供的相对统一的容器访问方式,使得设计算法时无需关注过多关注数据。(“算法”指广义的算法,操作数据的逻辑代码都可认为是算法)
算法(algorithm):提供一套常用的算法,如sort,search,copy,erase … 在实现上,可以认为是一种函数模板(function template)。
配置器(allocator):为容器提供空间配置和释放,对象构造和析构的服务,也是一个class template。
仿函数(functor):作为函数使用的对象,用于泛化算法中的操作。
配接器(adapter):将一种容器修饰为功能不同的另一种容器,如以容器vector为基础,在其上实现stack,stack的行为也是一种容器。这就是一种配接器。除此之外,还有迭代器配接器和仿函数配接器。
[C++](STL和泛型编程)

STL 六大组件的交互关系
Container 通过 Allocator 取得数据储存空间
Algorithm 通过 Iterator 存取 Container 内容
Functor 可以协助 Algorithm 完成不同的策略变化
Adapter 可以修饰或套接 Functor、Iterator。

vector<> 尖括号说明是一个模板

//一个例子说明六大部件
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;

int main()
{
	int ia[6] = {27, 210, 12, 47, 109, 83};
	vector<int, allocator<int>> vi(va,ia + 6);//<>符号表示模板,allocator<int>是一个分配器模板,一般vector都会自动默认使用分配器
	
	cout << count_if(vi.begin(), vi.end(),
			not1(bind2nd(less<int>(), 40)));
	return 0;
}
//vector是一个容器containers
//count_if是一个算法algorithm,计算vi里面的个数
//vi.begin(), vi.end()是一个迭代器iterator
//less<int>是一个仿函数function
//bind2nd是一个适配器function adapter,绑定第二个参数为40
//notl是一个适配器function adapter,表示否定
//整个表达,vi大于等于40的个数

[C++](STL和泛型编程)
容器规定:“前闭后开”区间(涵盖第一个不涵盖最后一个) [)

[C++](STL和泛型编程)
引用代表其自身

容器之分类与各种测试

[C++](STL和泛型编程)

容器种类:
1.顺序容器Sequence Containers

Array(固定元素个数)C++11
Vector(尾部个数可以扩充)
Deque(头尾个数可以扩充)
List(双向链表)
Forward-List(单向链表)C++11

2.关联容器Associative Containers:元素有key和value,适合做快速的查找
底层实现是红黑树,可以自动左右平衡

Set/Multiset(key=value)
Map/Multimap(key对应value;multimap允许重复元素,map不允许有重复)

不定序容器Unordered Containers(属于关联容器)
HashTable Separate chaining(不定序容器使用hashtable):同放一个内存,内存放这几个数据的链表

使用array
[C++](STL和泛型编程)

tips1: array.data()返回数组在内存中起点的地址
tips2: 二分查找的数组肯定是已经经过排序的,否则无法使用二分查找

[C++](STL和泛型编程)

[C++](STL和泛型编程)
[C++](STL和泛型编程)

tips1: try和catch是在抓取异常的发生,如果发生异常一定要abort退出程序
tips2: ::find表明是全局函数,如果不加的话程序最后也会去全局找
tips3:vector扩充是在别的地方找到一块内存,然后把原来的搬过去,找到的那一块必须是两倍大

使用list
[C++](STL和泛型编程)

tips1:动态内存
tips2:标准库提供全局sort,list容器自己也有sort,容器自己的sort一定是比较快(197行)

使用forward_list

[C++](STL和泛型编程)
[C++](STL和泛型编程)

使用deque

[C++](STL和泛型编程)
tips1:一段叫做一个buffer,指针走到一段buffer末尾,++操作符重载自动走到下一段,所以deque是分段连续
tips2:list每次扩充一个节点,效率最高,但是查找很慢;vector每次扩充两倍;deque扩充一个buffer

[C++](STL和泛型编程)
tips3:deque没有自己的sort,只能用全局sort
tips4:关联式容器的查找都非常快

使用stack,queue
[C++](STL和泛型编程)
[C++](STL和泛型编程)

tips1:stack和queue底层是通过deque实现的,从设计模式上来说,这两种容器本质上是deque的适配器.
tips2:这两个容器的元素进出是有严格顺序的,因此stack和queue不支持有关迭代器的操作.比如stack,防止iterator改变其先进后出的独特特性
[C++](STL和泛型编程)
**使用multiset **
[C++](STL和泛型编程)
tips1:multiset自带的find函数比全局find要快,但是insert要慢一点

使用multimap
[C++](STL和泛型编程)
tips:因为multimap支持重复的key,因此不能使用重载的[]运算符进行插入

**使用unordered_multiset/map **
[C++](STL和泛型编程)
[C++](STL和泛型编程)
[C++](STL和泛型编程)

tips1:unordered_multiset和unordered_multimap底层是使用hash+链表实现的.
tips2:unordered_multiset和unordered_multimap的元素个数小于篮子数目,若元素数目达到篮子个数,则容器扩容,将篮子数组扩充约一倍.

使用set /map

[C++](STL和泛型编程)
[C++](STL和泛型编程)
tips1:map可以用[],因为key不会重复

使用unordered_set /map

[C++](STL和泛型编程)
[C++](STL和泛型编程)
[C++](STL和泛型编程)

分配器之测试

容器的背后需要分配器支持其对内存的使用
[C++](STL和泛型编程)
STL容器默认的分配器是std::allocator,除此之外gcc额外定义了几个分配器,其头文件均在目录ext下.
[C++](STL和泛型编程)
gcc额外定义的分配器均位于__gnu_cxx命名空间下.分配器一般用于构建容器,不会直接使用.因为分配器想要直接使用也不好用(使用free关键字时不需要指定回收内存的大小,而分配器的deallocate函数需要指定回收内存大小).

STL容器源码分析

STL设计模式:OOP和GP

整个C++标准库并不是用面向对象实现的,而是泛型编程

OOP(Object-Oriented Programming)和GP(Generic Programming)是STL容器设计中使用的两种设计模式.

1.OOP的目的是将数据和方法绑定在一起,例如对std::list容器进行排序要调用std::list::sort方法(sort放到list里面).
[C++](STL和泛型编程)

2.GP的目的是将数据和方法分离开来,例如对std::vector容器进行排序要调用std::sort方法.
[C++](STL和泛型编程)

[C++](STL和泛型编程)
为什么list不能像vector和deque一样去用全局的sort,这种不同是因为std::sort方法内部调用了iterator的-运算,如果要运用需要满足一定的条件,std::list的iterator没有实现-运算符,而std::vector的iterator实现了-运算符.
[C++](STL和泛型编程)
[C++](STL和泛型编程)

运算符重载与模板特化

实现STL的两大基础就是运算符重载和模板特化.
[C++](STL和泛型编程)
[C++](STL和泛型编程)
[C++](STL和泛型编程)
[C++](STL和泛型编程)
特化又叫做全特化,即完整的特化,相对应的是局部的特化。偏特化:有两个模板参数,只指定其中一个,这是数量上的偏特化,还有范围上的偏特化

[C++](STL和泛型编程)

[C++](STL和泛型编程)

分配器

[C++](STL和泛型编程)
VC6.0的默认分配器std::allocator定义如下,可以看到VC6.0的分配器只是对::operator new和::operator delete的简单封装
[C++](STL和泛型编程)

[C++](STL和泛型编程)
allocator()创建一个临时对象
[C++](STL和泛型编程)
[C++](STL和泛型编程)
[C++](STL和泛型编程)
gcc2.9中的分配器std::allocator与VC6.0的实现类似,但std::allocator并非gcc2.9的默认分配器,观察容器源码,可以看到,gcc2.9的默认分配器为std::alloc.
[C++](STL和泛型编程)
做法是减少malloc的使用,因为malloc带有额外的开销,malloc每次分配的内存有大有小,所以需要cookie去记录,但容器里面元素的大小是一样的,所以似乎不需要吧每个元素的大小都记录。

std::alloc内部维护一个链表数组,数组中的每个链表保存某个尺寸的对象(以8的倍数增长),减少了调用malloc的次数,从而减小了malloc带来的额外开销.每个容器元素的大小都被调整为8的倍数(比如50->56)
[C++](STL和泛型编程)
在gcc4.9以后,默认分配器变为std::allocator,变回了对::operator new和::operator delete的简单封装.gcc2.9中的std::alloc更名为__gnu_cxx::__pool_alloc.

容器

[C++](STL和泛型编程)

list

1.在32位电脑上,一个指针4个字节
2.因为链表是一个非连续空间,所以iterator不能够是一个指针,但要模拟指针的操作(除了vector和array之外,所有容器的iterator必须是一个class,才能够完成足够聪明的动作)
3.为实现前闭后开的特性,在环形链表末尾加入一个用以占位的空节点,并将迭代器list::end()指向该节点.
[C++](STL和泛型编程)
iterator要模拟指针,即箭头符号,,++,–甚至+=,-=操作符。迭代器__list_iterator重载了指针的,->,++,–等运算符,并定义了iterator_category、value_type、difference_type、pointer和pointer5个关联类型(associated types),这些特征将被STL算法使用.

[C++](STL和泛型编程)
为了模仿整数i++不能连续做两次即(i++)++,所以i++的返回值是self。而++i是返回引用&
[C++](STL和泛型编程)
[C++](STL和泛型编程)
[C++](STL和泛型编程)
————————————————————————————————————————————————————————————————————————
iterator需要遵循的原则

1.算法需要知道iterator有哪些性质,因为他要做动作
2.下面的rotate例子中,iterator_category指的是其移动性质,有的iterator可以++,有的可以–,有的可以跳着走
difference_type:两个iterator之间的距离应该用什么type去表现
value_type:iterator所指元素本身的类型,如string等
另外两种性质reference和pointer从来没有被使用过
[C++](STL和泛型编程)

STL的算法传入的参数的一般是迭代器或指针,在算法内部,需要根据传入的迭代器或指针推断出迭代器的关联类型(associated types).

[C++](STL和泛型编程)
有时候呼叫的是一个指针,而不是泛化的指针iterator,但指针不能回答关联的问题,所以需要traits

1.迭代器的5个关联类型在类中均有定义,但是指针类型的关联类型需要根据指针类别进行确定,为了使STL算法同时兼容迭代器和一般指针,就在迭代器(指针)和算法之间加一个中间层萃取器(traits).

2.迭代器萃取器iterator_traits能够兼容迭代器和一般指针,获取其5个关联类型:iterator_category、value_type、difference_type、pointer和pointer.

[C++](STL和泛型编程)
在实现上,iterator_traits类使用模板的偏特化,对于一般的迭代器类型,直接取迭代器内部定义的关联类型;对于指针和常量指针进行偏特化,指定关联类型的值.
[C++](STL和泛型编程)

// 针对一般的迭代器类型,直接取迭代器内定义的关联类型
template<class I>
struct iterator_traits {
    typedef typename I::iterator_category 	iterator_category;
    typedef typename I::value_type 			value_type;
    typedef typename I::difference_type 	difference_type;
    typedef typename I::pointer 			pointer;
    typedef typename I::reference 			reference;
};

// 针对指针类型进行特化,指定关联类型的值
template<class T>
struct iterator_traits<T *> {
    typedef random_access_iterator_tag 		iterator_category;
    typedef T 								value_type;
    typedef ptrdiff_t 						difference_type;
    typedef T*								pointer;
    typedef T&								reference;
};

// 针对指针常量类型进行特化,指定关联类型的值
template<class T>
struct iterator_traits<const T *> {
    typedef random_access_iterator_tag 		iterator_category;
    typedef T 								value_type;		// value_tye被用于创建变量,为灵活起见,取 T 而非 const T 作为 value_type
    typedef ptrdiff_t 						difference_type;
    typedef const T*						pointer;
    typedef const T&						reference;
};

想要在算法内获取关联类型的值,只需像下面这样写:

template<typename T>
void algorithm(...) {
    typename iterator_traits<I>::value_type v1;
}

vector

1.容器vector的迭代器start指向第一个元素,迭代器finish指向最后一个元素的下一个元素,这两个迭代器对应begin()和end()的返回值,维持了前闭后开的特性.

2.vector对使用者是连续的,因此重载了[]运算符.

3.vector的实现也是连续的,因此使用指针类型做迭代器(即迭代器vector::iterator的实际类型是原生指针T*).

[C++](STL和泛型编程)

上一篇:2021-1-25计算机快速入门,简单掌握各种技巧


下一篇:TermQuery打分过程