C++ STL标准库与泛型编程（一）概述

阅读量：4079 次

发布时间：2019-05-25

本文共 4413 字，大约阅读时间需要 14 分钟。

泛型编程，就是使用模板为主要工具来编写程序。其中没有太多的面向对象的观念，不涉及虚函数的使用。

使用C++标准库

C++标准库：以代码形式给出，放于各种头文件( header files )内，经过编译后才能使用。

所有新式的 headers 内的组件封装于 namespace “std” 。

一、STL体系结构

STL标准库约占C++标准库的85%，其中含有六大部件。容器、算法、迭代器、仿函数、配接器、配置器。以及一些小的部分。

allocator 一般有默认值，显示化时，其参数类型要与容器类型匹配，否则编译出错。

count_if 算法计数给定条件下的元素个数。

not1 函数适配器表示条件反转，括号内的小于40语意变成大于等于40。

bind2nd 函数适配器绑定第2参数，表示通过算法 less 将容器内所有元素与常量40绑定比较。

less 函数对象比较小于40。

前闭后开区间 [ )，例如对象都有c.begin() 和 c.end()连个函数， c.end()指向最后一个元素地址的下一个地址。 *c.end() ×

for（begin：end）基于范围的 for 循环

auto 省略类型定义，可由编译器自动判断类型

容器 — 结构与分类

1.Sequence Containers 序列式容器

Array 数组类 —— 连续的固定大小的空间，不能自动扩充

Vector 数组 —— 可由尾端扩充，由容器分配器自动完成

Deque 双队列 —— 双向扩充

List —— 双向链表 Forward List —— 单链表

2.Association Containers 关联式容器 —— 有 key 和 value ，适合做查找

Set / Multiset 集合 —— 底层内存由红黑树（高度平衡二分树）实现，key 值就是 value

Map / Multimap 图 —— 有 key 与 value，Multi 表示 key 值可重复

3.Unordered Containers —— C++11不定序容器之前也归于关联式容器

基于 哈希表散列链表 （Hash Table Separate Chaining）实现

Unordered Set / Multiset 无序集合 Unordered Map / Multimap 无序图

容器的测试—限制与效率

无需将所有的 include 操作放在所有程序的最前面，以 namespace 将每段程序分隔开，每段测试用例所需的头文件会更明了。而且 include 头文件重复时有保护机制，所以不用担心。

变量的声明可不用全部写在程序开始处，放在使用出利用凸排一目了然。

1.测试 array

array提供的操作函数：

size() 返回数组大小 front() 返回第一个元素值

back() 返回数组尾元素值 data() 返回数组存放的首地址

其他：

clock() 记录当前系统时间，返回毫秒数 ms clock() - timeStart 可得到运行时间

qsort() 快速排序法参数为起始地址，元素个数，元素占用空间大小，元素比较函数

bsearch() 二分查找法，查找前数组必须有序，存放于cstdlib

2.测试 vector

Vector 提供的操作函数：

push_back() 元素放入Vector 尾端 vector容量增长的本质：每次空间不够时，容器适配器会在另一个内存空间将待用空间多次的两倍扩张（1.2.4.8........），安排好扩张内存后将所有值复制过去。

size() 目前容器中真正元素的个数 capacity() 扩充后真正的容器容量 2的n次幂

::find() STL模板函数（全局函数）循序查找，返回值为迭代器 ::sort() STL模板函数（全局函数）排序

在全随机排列的情况下，sort 加 bsearch 的查找方法所耗费的时间不如直接 find 循序查找快，虽然二分查找本身效率较高。

3.测试 List 、Forward_list

.sort() List容器的类方法，当容器自己提供了 .sort() 函数时，其运行效率一定比全局 ::sort() 要快。

forward_list只有 push_front() ,没有 .back()取表尾与 .size() 取表长函数。

4.测试 Deque

push_front() pop_front() push_back() pop_back()

内存中是分段连续的buffer，每次扩充时，扩充一个固定的 buffer 大小。

在队列前后入队出队时，会自动修正++与--所指向的地址，以保证表面上看是连续的。

没有 sort() 类方法，直接使用 ::sort() STL模板函数

queue 和 stack 都是基于 deque 实现，技术上本质为容器适配器，因为只能先进先出或者先进后出，所以不提供迭代器。

关联式容器的查找速度非常快（结构为红黑树），快于所有的序列式容器。

5.测试 Multiset / Set

在set 中 insert 相同数据时，不会报错，不会有异常返回。所以插入次数可能比元素个数少。

初始化后会自动排序，set 所具有的 insert 方法插入位置由排序自动决定。

6.测试 Multimap / Map

multimap
   
     c;c.insert(pair
    
     (i,buf));

定义时要指定两个参数 key 和 value。insert 时要将数据组合（pair）放入。

Multimap 不可使用 [ ] 做 insertion，map 可以 : c[ i ] = string (buf)，i 默认为key，string 为 value。

取 value 时用 (*pItem).second

7.使用 Unordered Set / Multiset

.bucket_count() 篮子的个数，即哈希表的大小。可能有的 bucket 存放多个元素，有的 bucket 不存放元素。

bucket 个数一定多余元素个数，实现时如果元素个数大于等于篮子个数时，bucket 就会以大约两倍扩充，散列表会重新打散放置。

8.分配器 — 使用

Windows中 Dev-C++ 、Code::Block 等集成开发环境下使用 GCC 编译器编译。

这些 allocator 后存放在 <ext\...> 中作为 GCC 扩展库，并非 C++ 标准规定的，存放在__gnu_cxx::命名空间中。

一般通过 allocator 调用容器的类方法来管理内存，一般没有必要使用 allocate() 和 deallocate() 方法直接申请与销毁内存(需指出所指定的内存大小)。

二、OOP (面向对象编程) vs. GP (泛型编程）

1.GP 的思想是将 datas 与 methods 分开来

采用 GP Containers 和 Algorithms 可以只关注自身的设计，期间以 Iterators 沟通即可。Algorithms 通过 Iterators 确定操作范围，并通过 Iterators 取用 Containers 元素。

template
   
    inline const T& min(const T& a,const T& b){    return b < a ? b : a;}template
    
     inline const T& min(const T& a,const T& b,Compare comp)   //提供自定义比较大小函数的重载方案{    return comp(b,a) ? b : a;}

min 函数只关心实现的求最小值的功能，不关心具体参数的类。

2.为什么 list 有自己的 .sort() 函数，而不能用全局的 ::sort() 函数？

全局 ::sort() 算法源码中，有 "first + ( last - first) / 2" 样的操作，只有随机访问迭代器才能做这样的操作。

list 所提供的迭代器不能做随机访问，其指向链表结点的指针，只能前进一个或者指向下一个，不能有类似+5操作。

三、操作符重载与模板

1.作为全局函数、类成员函数、一个参数的函数、双目运算符函数重载举例

例如：_list_iterator 双向链表迭代器

其本质为一个类，功能上可以等同为一个广义指针，是因为其定义的类方法重载了 operator*()、operator->()、operator++() 等指针使用时的操作符。

2.模板

Class Template 类模板

template 
   
    class  complex{public:    complex (T r = 0, T i = 0) : re (r), im (i) {};    complex& operator += (const complex&);    T real () const { return re };    T imag () const { return im };private:T re, im;        friend complex& __doapl (complex*, const complex&);}{    complex
    
      c1(2.5, 1.5);    complex
     
       c2(2, 6);}