STL的一些知识点整理

标准模板库（STL）

• 常用数据结构和算法的模板的集合

• 有了STL，不必再从头写大多的标准数据结构和算法，并且可以获得非常高的性能，节省了大量的时间和精力。

泛型程序设计---使用模板的程序设计法

• 将一些常用的数据结构（如链表、数组、二叉树）和算法（如排序、查找）写成模板，以后则不论数据结构里放的是什么对象，算法针对什么样的对象，则都不必重新实现数据结构，重新编写算法。

模板分类：

• 函数模板

  • 是独立类型的函数

  • 可产生函数的特定版本

• 类模板

  • 跟类相关的模板--vector

  • 可产生类对特定类型的版本，如vector<int>

STL中的基本概念：

• 容器———可容纳各种数据类型的数据结构

• 迭代器————可依次存取容器中元素的智能指针（如int a[100]是个容器，而int* 类型的指针变量就可以作为迭代器，可以为 这个容器编写一个排序的算法）

• 算法algorithm

  • 用来操作容器中的元素的函数模板。sort()---对一个vector中的数据进行排序；find()---搜索一个list中的对象

  • 函数本身与他们操作的数据的结构和类型无关，在从简单数组到高复杂容器的任何数据结构上使用。

容器：可以用于存放各种类型的数据的数据结构

• 顺序容器（将单一类型元素聚集起来成为容器，然后根据位置来存储和访问这些元素）（元素的插入位置与元素的值无关）

  • vector：后部插入/删除，直接访问任何元素；动态数组，随机存取任何元素都能在常数时间完成，在尾端增删元素具有较佳的性能。

  • deque：前/后部插入/删除，直接访问，随机存取；性能次于vector；

  • list：     双向链表，任意位置插入、删除；在两端增删元素具有较佳的性能，不支持随机存取；双向不随机

• 关联容器（支持通过键来高效的查找和读取元素（map/set））（元素是排序的，插入任何元素都按相应的排序准则来确定其位置。特点：在查找时具有非常好的性能）

  • set：快速查找，无重复元素

  • map：一对一映射，无重复元素，基于关键字查找 

• 容器适配器

  • stack（后进先出）

  • queue（先进先出）

容器的共有成员函数：

1)所有标准库容器共有的成员函数：

• 相当于按词典顺序比较两个容器大小的运算符：  =, < , <= , >  , >=, == , !=

• empty : 判断容器中是否有元素

• max_size: 容器中最多能装多少元素

• size:   容器中元素个数

• swap: 交换两个容器的内容

    若两容器长度相同、所有元素相等，则两个容器就相等，否则为不等。

    若两容器长度不同，但较短容器中所有元素都等于较长容器中对应的元素，则较短容器小于另一个容器

    若两个容器均不是对方的子序列，则取决于所比较的第一个不等的元素

2)只在第一类容器中的函数

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

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

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

• clear    从容器中删除所有的元素

迭代器：

1.定义：

• 提供一种方法访问一个容器对象中各个元素，而又不需要暴露该对象的内部细节。

• 用于指向第一类容器的元素，有const和非const两种

2.用法与指针相似

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

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

3.定义一个容器类的迭代器的方法

• 容器类名::iterator  变量名

• 容器类名::const_iterator  变量名

#include <vector>
#include <iostream>
using namespace std;
int main()  {
  vector<int> v; //一个存放int元素的向量，一开始里面没有元素
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  v.push_back(4);
  vector<int>::const_iterator i;   //常量迭代器
  for( i = v.begin(); i != v.end(); i ++ )
  cout << * i << ",";
  cout << endl;
  vector<int>::reverse_iterator r;  //反向迭代器
  for( r = v.rbegin(); r != v.rend(); r++ )
  cout << * r << ",";
  cout << endl;
  vector<int>::iterator j;   //非常量迭代器
  for( j = v.begin();j != v.end();j ++ )
  * j =  100;
  for( i = v.begin();i != v.end();i++ )
  cout << * i << ",";
}

不同迭代器所能进行的操作（功能）

* 所有迭代器： ++p, p ++

* 输入迭代器： * p, p = p1, p == p1 , p!= p1

* 输出迭代器： * p, p = p1

* 正向迭代器： 上面全部

* 双向迭代器： 上面全部，--p, p --,

* 随机访问迭代器： 上面全部以及：

    *   p+= i, p -= i,

    *   p + i： 返回指向 p 后面的第i个元素的迭代器

    *   p - i： 返回指向 p 前面的第i个元素的迭代器

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

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

&&stack、queue、priority_queue不支持迭代器

vector的迭代器是随机迭代器，故遍历vector可以有以下几种做法：

vector<int>v(100);
for(int i=0;i<v.size();i++)
    cout<<v[i];
vector<int>::const_iterator ii;
for(ii=v.begin;ii!=v.end();ii++)
    cout<<*ii;
ii=v.begin();
while(ii<v.end())
{
    cout<<*ii;
    ii=ii+2;//间隔一个输出
}

算法简介：

      STL中提供能在各种容器中通用的算法，如插入、删除、查找、排序等。

• 算法就是函数模板；

• 算法通过迭代器来操纵容器中的元素；许多算法需要两个参数，即其实元素的迭代器和终止元素的后面一个元素的迭代器。

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

• 算法可以处理容器，也可以处理C语言的数组。

算法分类：

• 变化序列算法

  • copy、remove、replace、random_shuffle、swap等

  • 会改变容器

• 非变化序列算法

  • equal、find、mismatch、count、search等

• 排序相关算法

  • 以上函数模板都在<algorithm>中定义

  • 此外还有其他算法，比如<numeric>中的算法

算法示例：find()

  template<class InIt, class T>

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

• first和last这两个参数都是容器的迭代器，他们给出了容器中的查找区间起点和终点；

• 区间左闭右开；

• val是要查找的元素的值；

• 函数返回值是一个迭代器。如果找到则该迭代器指向被找到的元素。否则，指向查找区间终点。

---

顺序容器：

   共同操作：

• front()：返回容器中第一个元素的引用；

• back()：返回容器中最后一个元素的引用；

• push_back()：在容器末尾增加新元素；

• pop_back()：删除容器末尾的元素；

vector示例：

• 支持随机访问迭代器，所有的STL算法都能对vector进行操作；

• 随机访问时间为常数。在尾部添加速度很快，在中间插入很慢。实际是动态数组。

--->copy (v.begin(),v.end(), output)： 导致v的内容在 cout上输出、

---

关于ostream_iterator, istream_iterator的例子：

istream_iterator<int>inputInt(cin);
int n1,n2;
n1=*inputInt;//读入n1；
inputInt++;
n2=*inputInt;//读入n2；
cout<<n1<<","<<n2<<endl;
ostream_iterator<int>outputInt(cout);
*outputInt=n1+n2;
cout<<endl;
int a[5]={1,2,3,4,5};
copy(a,a+5,outputInt);//输出整个数组

list容器：

    不支持随机存取，在任何位置插入删除都是常数时间，除了具有所有顺序容器都有的成员函数外，还有：

• push_front：在前面插入

• pop_front：删除前面的元素

• sort：排序（list不支持STL的算法sort）

• remove：删除和指定值相等的所有元素

• unique：删除所有和前一个元素相同的元素

• merge：合并两个链表，并清空被合并的链表

• reverse：颠倒链表

• splice：在指定位置前插入另一个链表中的一个或多个元素，并在另一个链表中删除被插入的元素。

---

关联容器

* set, multiset, map, multimap

    *  内部元素有序排列，新元素插入的位置取决于它的值，查找速度快

    * map关联数组：元素通过键来存储和读取

    * set大小可变的集合，支持通过键实现的快速读取

    * multimap支持同一个键多次出现的map类型

    * multiset支持同一个键多次出现的set类型

* 与顺序容器的本质区别

    * 关联容器是通过键(key)存储和读取元素的

    * 而顺序容器则通过元素在容器中的位置顺序存储和访问元素。

    * 除了各容器都有的函数外，还支持以下成员函数：

    * 设m表容器，k表键值

•  m.find(k) ：如果容器中存在键为k的元素，则返回指向该元素的迭代器。如果不存在，则返回end()值。

• m.lower_bound(k)：返回一个迭代器，指向键不小于k的第一个元素

• m.upper_bound(k)：返回一个迭代器，指向键大于k的第一个元素

• m.count(k) ：返回m中k的出现次数

• 插入元素用 insert（insert函数的返回值是一个pair对象，其first是被插入元素的迭代器，second代表是否成功插入了）

pair模板：

 pair模板类用来绑定两个对象为一个新的对象，该类型在<utility>头文件中定义。该模板类支持一下操作：

• pair<T1,T2>p1：创建一个空的pair对象，它的两个元素分别是T1和T2类型，采用值初始化；

• pair<T1,T2>p1<v1,v2>：创建一个pair对象，它的两个元素分别是T1和T2类型，first成员初始化为v1，second成员初始化为v2；

• make_pair(v1,v2)：以v1、v2值创建一个新的pair对象，其元素类型分别是v1和v2的类型。

• p.first  返回p中名为first的（公有）数据成员

• p.second   返回p中名为second的（公有）数据成员

• p1 < p2字典次序   如果p1.first<p2.first或者!(p2.first <p1.first)&& p1.second<p2.second，则返回true

• p1 == p2     如果两个pair对象的first和second成员依次相等，则这两个对象相等。

map

template<class Key, class T,
                  class Pred = less<Key>,    class A = allocator<T> >
class map {

  ….

  typedef pair<const Key, T> value_type;

  …….

};

* map 中的元素关键字各不相同。元素按照关键字升序排列，缺省情况下用 less 定义“小于”

* 可以用下标的形式访问map中的元素。

/*
 统计一篇英文文章中单词出现的频率（为简单起见，假定依次从键盘输入该文章）
*/
int main()
{
  map<string, int> wordCount;      //map
  string word;                     //string
  while ( cin >> word )
  ++wordCount[word];           //单词频率统计
  map<string, int>::iterator it ;
  for ( it= wordCount.begin();  it != wordCount.end();  ++it)
  cout<<"Word: "<<(*it).first    
  <<" \tCount:"<<(*it).second<<endl;
  return 0;
}

---

容器适配器：stack

  可用vector、list、deque来实现

• 缺省情况下用deque；

• 用vector和deque比用list实现性能好

template<class T, class Cont=deque<T>>

    class stack{  ...  };

   stack是先进后出的数据结构，只能插入、删除、访问栈顶元素的操作：

• push：插入元素

• pop：弹出元素

• top：返回栈顶元素的引用

 容器适配器：queue

    可以用list、deque实现，缺省情况下用deque；

template<class T, class Cont=deque<T>>

    class queue{   ...  };

   先进先出，也有push、pop、top函数，但push发生在队尾，另外俩在队头。

容器适配器：priority_queue

   和queue类似，可以用vector和deque实现，缺省情况下用vector实现。

    priority_queue通常用堆排序技术实现，保证最大的元素总在最前面。

    即执行pop操作，删除的是最大的元素；执行top操作时，返回的是最大元素的引用。默认的元素比较器是less<T>;

#include <queue>
#include <iostream>
using namespace std;
int main()  {
  priority_queue<double> priorities;
  priorities.push(3.2);
  priorities.push(9.8);
  priorities.push(5.4);
  while( !priorities.empty() ) {
  cout << priorities.top() << " ";    priorities.pop();
  }
     return 0;
}

//输出结果：9.8 5.4 3.2

---

排序和查找算法

/*sort*/
template<class RanIt>
  void sort( RanIt first,  RanIt last);

/*find*/
template<class InIt, class T>
InIt find(InIt first, InIt last, const T& val);

/*binary_search 折半查找，要求容器已经有序*/
template<class FwdIt, class T>
bool binary_search(FwdIt first, FwdIt last, const T& val);

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
  const int SIZE = 10;
  int a1[] = { 2,8,1,50,3,100,8,9,10,2 };
  vector<int> v(a1,a1+SIZE);
  ostream_iterator<int> output(cout," ");
  vector<int>::iterator location;
  location = find(v.begin(),v.end(),10);
  if( location != v.end())
      cout<< "1) " << location - v.begin() << endl ;
  sort(v.begin(),v.end());                           //sort()排序
  if( binary_search(v.begin(),v.end(),9))
      cout<< "2) " << "9 found" << endl ;
  else
      cout << "3) " << " 9 not found" << endl;      
  return 0;
}

参考老师课件嘻嘻嘻(*^▽^*)