本文主要是介绍[C++]（STL和泛型编程），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

• 认识headers
• STL各组件应用实例
• • STL体系结构基础介绍
  • 容器之分类与各种测试
  • 分配器之测试
• STL容器源码分析
• • STL设计模式:OOP和GP
  • 运算符重载与模板特化
  • 分配器
  • 容器
  • • list
    • vector

认识headers

C++ 标准库（STL大部分属于C++标准库） —STL和标准库的关系

STL各组件应用实例

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的行为也是一种容器。这就是一种配接器。除此之外，还有迭代器配接器和仿函数配接器。

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的个数

容器规定：“前闭后开”区间（涵盖第一个不涵盖最后一个） [)

引用代表其自身

容器之分类与各种测试

容器种类：
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

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

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

使用list

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

使用forward_list

使用deque

tips1:一段叫做一个buffer，指针走到一段buffer末尾，++操作符重载自动走到下一段，所以deque是分段连续
tips2:list每次扩充一个节点，效率最高，但是查找很慢；vector每次扩充两倍；deque扩充一个buffer

tips3:deque没有自己的sort，只能用全局sort
tips4:关联式容器的查找都非常快

使用stack,queue

tips1:stack和queue底层是通过deque实现的,从设计模式上来说,这两种容器本质上是deque的适配器.
tips2:这两个容器的元素进出是有严格顺序的,因此stack和queue不支持有关迭代器的操作.比如stack,防止iterator改变其先进后出的独特特性

**使用multiset **

tips1：multiset自带的find函数比全局find要快，但是insert要慢一点

使用multimap

tips:因为multimap支持重复的key,因此不能使用重载的[]运算符进行插入

**使用unordered_multiset/map **

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

使用set /map

tips1:map可以用[],因为key不会重复

使用unordered_set /map

分配器之测试

容器的背后需要分配器支持其对内存的使用

STL容器默认的分配器是std::allocator,除此之外gcc额外定义了几个分配器,其头文件均在目录ext下.

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里面）.

2.GP的目的是将数据和方法分离开来,例如对std::vector容器进行排序要调用std::sort方法.

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

运算符重载与模板特化

实现STL的两大基础就是运算符重载和模板特化.




特化又叫做全特化，即完整的特化，相对应的是局部的特化。偏特化：有两个模板参数，只指定其中一个，这是数量上的偏特化，还有范围上的偏特化

分配器

VC6.0的默认分配器std::allocator定义如下,可以看到VC6.0的分配器只是对::operator new和::operator delete的简单封装

allocator()创建一个临时对象



gcc2.9中的分配器std::allocator与VC6.0的实现类似,但std::allocator并非gcc2.9的默认分配器,观察容器源码,可以看到,gcc2.9的默认分配器为std::alloc.

做法是减少malloc的使用，因为malloc带有额外的开销，malloc每次分配的内存有大有小，所以需要cookie去记录，但容器里面元素的大小是一样的，所以似乎不需要吧每个元素的大小都记录。

std::alloc内部维护一个链表数组,数组中的每个链表保存某个尺寸的对象（以8的倍数增长）,减少了调用malloc的次数,从而减小了malloc带来的额外开销.每个容器元素的大小都被调整为8的倍数（比如50->56）

在gcc4.9以后,默认分配器变为std::allocator,变回了对::operator new和::operator delete的简单封装.gcc2.9中的std::alloc更名为__gnu_cxx::__pool_alloc.

容器

list

1.在32位电脑上，一个指针4个字节
2.因为链表是一个非连续空间，所以iterator不能够是一个指针，但要模拟指针的操作（除了vector和array之外，所有容器的iterator必须是一个class，才能够完成足够聪明的动作）
3.为实现前闭后开的特性,在环形链表末尾加入一个用以占位的空节点,并将迭代器list::end()指向该节点.

iterator要模拟指针，即箭头符号，，++，–甚至+=，-=操作符。迭代器__list_iterator重载了指针的,->,++,–等运算符,并定义了iterator_category、value_type、difference_type、pointer和pointer5个关联类型(associated types),这些特征将被STL算法使用.

为了模仿整数i++不能连续做两次即（i++）++,所以i++的返回值是self。而++i是返回引用&



————————————————————————————————————————————————————————————————————————
iterator需要遵循的原则

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

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

有时候呼叫的是一个指针，而不是泛化的指针iterator，但指针不能回答关联的问题，所以需要traits

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

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

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

// 针对一般的迭代器类型,直接取迭代器内定义的关联类型
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和泛型编程）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！