标准模板库--STL

标准模板库STL


1、泛型程序设计

C++ 语言的核心优势之一就是便于软件的重用

C++中有两个方面体现重用:

  1.面向对象的思想继承和多态,标准类库

  2.泛型程序设计(generic programming) 的思想: 模板机制,以及标准模板库STL

简单地说就是使用模板的程序设计法。

将一些常用的数据结构比如链表,数组,二叉树)和算法比如排序,查找)写成模板,以后则不论数据结构里放的是什么对象,算法针对什么样的对象,则都不必重新实现数据结构,重新编写算法。标准模板库 (Standard Template Library) 就是一些常用数据结构和算法的模板的集合。

有了STL,不必再写大多的标准数据结构和算法,并且可获得非常高的性能。


2、STL中的基本概念

容  器: 可容纳各种数据类型的通用数据结构,是类模板

迭代器:可用于依次存取容器中元素,类似于指针

算  法:用来操作容器中的元素函数模板

      ·sort()来对一个vector中的数据进行排序

      ·find()来搜索一个list中的对象

算法本身与他们操作的数据的类型无关,因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。比如:

  int array[100];

  该数组就是容器,而 int * 类型的指针变量就可以作为迭代器,sort算法可以作用于该容器上,对其进行排序:

个元素排序


3、容器

可以用于存放各种类型的数据基本类型的变量,对象等)的数据结构,都是类模版,分为三种:

1)顺序容器

  vector ,deque ,list

2)关联容器

  set ,multiset ,map ,multimap

3)容器适配器

  stack ,queue ,priority_queue

对象被插入容器中时,被插入的是对象的一个复制品。许多算法,比如排序,查找,要求对容器中的元素进行比较,有的容器本身就是排序的,所以,放入容器的对象所属的类,往往还应该重载 == 和 < 运算符。

详细解析:

1)顺序容器

容器并非排序的,元素的插入位置同元素的值无关,有vector,deque,list 三种

A、vector   头文件 <vector>

  动态数组。元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能(大部分情况下是常数时间)。

B、deque  头文件 <deque>

  双向队列。元素在内存连续存放。随机存取任何元素都能在常数时间完成(但次于vector)。在两端增删元素具有较佳的性能(大部分情况下是常数时间)。

C、list   头文件 <list>

  双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。

2)关联容器

元素是排序的

插入任何元素,都按相应的排序规则来确定其位置

查找时具有非常好的性能

通常以平衡二叉树方式实现,插入和检索的时间都是 O(log(N))

set/multiset  头文件 <set>

  set 即集合。set中不允许相同元素,multiset中允许存在相同的元素

map/multimap  头文件 <map>

  map与set的不同在于map中存放的元素有且仅有两个成员变量,一个名为first,另一个名为second, map根据first值对元素进行从小到大排序,并可快速地根据first来检索元素。

  map同multimap的不同在于是否允许相同first值的元素。

3)容器适配器

stack  头文件 <stack>

  栈。是项的有限序列,并满足序列中被删除、检索和修改的项只能是最近插入序列的项(栈顶的项)。后进先出

queue  头文件 <queue>

  队列。插入只可以在尾部进行,删除、检索和修改只允许从头部进行。先进先出

priority_queue  头文件 <queue>

  优先级队列最高优先级元素总是第一个出列。


注:

<1>顺序容器的常用成员函数

  front :           返回容器中第一个元素的引用

  back :          返回容器中最后一个元素的引用

  push_back :    在容器末尾增加新元素

  pop_back :        删除容器末尾的元素

  erase  :         删除迭代器指向的元素(可能会使该迭代器失效),或删除一个区间,返回被删除元素后面的那个元素的迭代器

<2>顺序和关联容器中都有的成员函数

  begin    返回指向容器中第一个元素的迭代器

  end       返回指向容器中最后一个元素后面的位置的迭代器

  rbegin   返回指向容器中最后一个元素的迭代器

  rend     返回指向容器中第一个元素前面的位置的迭代器

  erase    从容器中删除一个或几个元素

  clear         从容器中删除所有元素


4、迭代器

用于指向顺序容器和关联容器中的元素

迭代器用法和指针类似

const 和非 const两种

通过迭代器可以读取它指向的元素

通过非const迭代器还能修改其指向的元素

定义一个容器类的迭代器的方法可以是:

  容器类名::iterator  变量名;

或:

  容器类名::const_iterator 变量名;

访问一个迭代器指向的元素:

  * 迭代器变量名

注:迭代器上可以执行 ++ 操作, 以使其指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面,此时再使用它,就会出错,类似于使用NULL或未初始化的指针一样。

<1>双向迭代器

若p和p1都是双向迭代器,则可对p、p1可进行以下操作:

  ++p, p++    使p指向容器中下一个元素

  --p, p--      使p指向容器中上一个元素

  * p         取p指向的元素

  p = p1      赋值

  p == p1 , p!= p1  判断是否相等、不等

<2>随机访问迭代器

若p和p1都是随机访问迭代器,则可对p、p1可进行以下操作:

  双向迭代器的所有操作

  p += i    将p向后移动i个元素

  p -= i     将p向向前移动i个元素

  p + i  值为:   指向 p 后面的第i个元素的迭代器

  p - i  值为:   指向 p 前面的第i个元素的迭代器

  p[i]  值为:   p后面的第i个元素的引用

  p < p1, p <= p1, p > p1, p>= p1


总结:

  容器          容器上的迭代器类别

  vector          随机访问

  deque          随机访问

  list             双向  

  set/multiset           双向

  map/multimap         双向

  stack           不支持迭代器

  queue           不支持迭代器

  priority_queue      不支持迭代器


STL中的“大”和“小”的概念

关联容器内部的元素是从小到大排序

有些算法要求其操作的区间是从小到大排序的,称为“有序区间算法

例:binary_search

有些算法会对区间进行从小到大排序,称为“排序算法

例: sort

还有一些其他算法会用到“大”,“小”的概念

使用STL时,在缺省的情况下,以下三个说法等价:

  1) x比y小

  2) 表达式“x<y”为真

  3) y比x大


STL中的“相等”的概念

有时,“x和y相等”等价于“x==y为真”

  例:

  在未排序的区间上进行的算法,如顺序查找find

  ……

有时,“x和y相等”等价于“x小于y和y小于x同时为假”

  例:

  有序区间算法,如binary_search

  关联容器自身的成员函数find

  ……


5、算法

算法就是一个个函数模板 ,大多数在<algorithm> 中定义

STL中提供能在各种容器中通用的算法,比如查找,排序等

算法通过迭代器来操纵容器中的元素。许多算法可以对容器中的一个局部区间进行操作,因此需要两个参数,一个是起始元素的迭代器,一个是终止元素的后面一个元素的迭代器。比如,排序和查找

有的算法返回一个迭代器。比如 find() 算法,在容器中查找一个元素,并返回一个指向该元素的迭代器

算法可以处理容器,也可以处理普通数组

比如:

template<class InIt, class T>

InIt find(InIt first, InIt last, const T& val);

   first 和 last 这两个参数都是容器的迭代器,它们给出了容器中的查找区间起点和终点[first,last)。区间的起点是位于查找范围之中的,而终点不是。find在[first,last)查找等于val的元素

   用 == 运算符判断相等

   函数返回值是一个迭代器。如果找到,则该迭代器指向被找到的元素。如果找不到,则该迭代器等于last。


vector

可变长的动态数组

必须包含头文件 #include <vector>

支持 随机访问迭代器

  • 根据下标随机访问某个元素时间为常数

  • 在尾部添加速度很

  • 在中间插入慢

所有STL算法都能对vector操作

vector成员函数

构造函数初始化:

标准模板库--STL

其它常用函数:

标准模板库--STL

  v.end()      容器最后一个元素之后元素相应位置对应的迭代器

  v.begin()     首元素的迭代器

  v[i]          访问某个元素

  v.at(i)      访问某个元素

  v.insert(a,b)    在位置a处插入一个元素b

定义二维动态数组

  vector< vector<int> > v(3);

  //v有3个元素,

  //每个元素都是vector<int> 容器


list

双向链表 必须包含头文件 : #include <list>

标准模板库--STL

在任何位置插入/删除都是常数时间

标准模板库--STL

不支持根据下标随机存取元素

个成员函数:

标准模板库--STL

list容器之sort函数

  list容器的迭代器不支持完全随机访问

    不能用标准库中sort函数对它进行排序

  list自己的sort成员函数

    ·list<T> classname

    ·classname.sort(compare);  //compare函数可以自己定义

    ·classname.sort();  //无参数版本, 按<排序

  list容器只能使用双向迭代器

    不支持大于/小于比较运算符, []运算符和随机移动(即类似 “list的迭代器+2” 的操作)


deque 容器

双向队列 必须包含头文件 : #include <deque>

  所有适用于vector的操作都适用于deque

  deque还有

    push_front (将元素插入到容器的头部)

    pop_front (删除头部的元素) 操作


函数对象

若一个类重载了运算符 “()”,则该类的对象就成为函数对象

例如:

  class CMyAverage {  //函数对象类

  public:

  double operator() ( int a1, int a2, int a3 ) {

  return (double)(a1 + a2+a3) / 3;

  }

  };

  CMyAverage average;  //定义函数对象

  cout << average(3,2,3); // 相当于average.operator()(3,2,3)

  ·输出 2.66667

STL中的函数对象类模板

  以下模板可以用来生成函数对象。

    equal_to

    greater

    less

    …….

    头文件: <functional>

greater 函数对象类模板

  template<class T>

  struct greater : public binary_function<T, T, bool> {

  bool operator()(const T& x, const T& y) const {

  return x > y;

  }

  };

list 有两个sort成员函数

  void sort();

  将list中的元素按 “<” 规定的比较方法升序排列。

  template <class Compare>

  void sort (Compare op);

  将list中的元素按 op 规定的比较方法升序排列。即要比较x,y大小时,看 op(x,y)的返回值,为true则认为 x小于y。


在STL中使用自定义的“大”,“小”关系

关联容器和STL中许多算法,都是可以用函数或函数对象自定义比较器的。在自定义了比较器op的情况下,以下三种说法是等价的:

  1) x小于y

  2) op(x,y)返回值为true

  3) y大于x

上一篇:vs2015 工具栏添加控件


下一篇:java里的基本数据类型和引用数据类型