来自新世界:标准模板库

什么是STL?

STL可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分

 

引入:模板类vector

vector<int> ratings(2);

这里建立了一个类型为int,名字是rating的vector类,这个rating里面有两个int元素(其实就是数组)

但是这个vector类对外有接口,比如begin()方法返一个指向容器中第一个元素的迭代器,迭代器是什么?它可以是指针,可对其执行类似指针的操作(解除引用,递增),它存在的意义就是让STL能够为各种各样不同的容器类提供统一的接口。迭代器的类型是一个名字为iterator的typedef,作用域为整个类。

int main(){
  vector<int>::iterator pd;
  vector<double> scores;
  pd = scores.begin();
  *pd = 55;
  pd++;

  auto pd = scores.begin();  //也可以通过auto直接声明使用
}

还有其他用法:

  vector<double> scores;
  double temp;
  while(cin >> temp){
    scores.push_back(temp);
  }
  cout << scores.size() << endl;
  scores.erase(scores.begin(), scores.begin() + 2);//删除第一个到第二个的元素
  scores.erase(scores.begin(), scores.end())       //end()返回末尾元素的后一个位置
  scores<int> new;
  scores.insert(scores.begin(), new.begin(), new.begin() + 5);

下面就来讲讲喜闻乐见的sort()函数,以前特别讨厌去写排序,一直想着去用sort去解决问题,那时都是用sort去对一个int/double数组进行排序,然鹅怎么对对象进行排序呢?

就是重载<,或者重新定义一个函数然后把函数当成参数传进sort()里面去

  bool operator<(const A &a1,const A &a2){
    if(a1.data > a2.data){
      return true;
    }
    else
      return false;
  }

  sort(book.begin(), book.end());

  bool Another(const A &a1,const A &a2){
    if(a1.data < a2.data){
      return true;
    }
    else
    {
      return false;
    }

    sort(book.begin(), book.end(), Another);

泛型编程

1.迭代器:连接容器和算法的一种重要桥梁,迭代器(iterator)是一种对象,它能够用来遍历标准模板库容器中的部分或全部元素,每个迭代器对象代表容器中的确定的地址。迭代器修改了常规指针的接口,所谓迭代器是一种概念上的抽象:那些行为上像迭代器的东西都可以叫做迭代器。然而迭代器有很多不同的能力,它可以把抽象容器和通用算法有机的统一起来。

迭代器可以分为一下5种:

  • 输入迭代器:仅仅读。支持++、==、!=
  • 输出迭代器:仅仅写,支持++
  • 前向迭代器:读写,支持++、==、!=
  • 双向迭代器:读写,支持++、–
  • 随机訪问迭代器:读写,支持++、–、[n]、-n、<、<=、>、>=

 

前文提到像begin()方法,find()方法它也会返回一个迭代器,我们来看一下它的函数原型:

template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T &value);

 

 

这里声明了find方法要传进一个输入迭代器,

我们可以看出,find是一种算法,vector是一种容器里面可以塞任何东西,当需要把算法应用于容器时,我们为了控制,才使用迭代器这个东西,可以看出不同的迭代器有着不同的权限,这也要求我们要根据算法的需求来选择迭代器。比如查找算法只需要定义++运算符和读取数据(假如查找算法可以修改数据将会变得很蛋疼)

 

sort算法使用双向迭代器对vector里面的数据进行修改与排序

 

 

事实上,迭代器是广义上的指针,指向int的常规指针是一个随机访问迭代器模型。

  ostream_iterator<int, char> out_iter(cout, "\n");  //第一个参数是输出方式,第二个是分隔符
  int x[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  vector<int> dice(10);  
  copy(x, x + 10, dice.begin());   //复制函数
  copy(dice.begin(), dice.end(), out_iter);    //将dice容器中的内容复制到输入流中
  exit(5);

再来讲讲其他有用的迭代器

1.反向类迭代器,vector里面有一个rbegin和rend方法,返回的值分别和end与begin方法返回的值相同,但是前两者返回的迭代器的类型是reverse_iterator而不是iterator

2.插入迭代器(预定义的),在通过copy来把数据插到容器中时,很有可能会覆盖掉前面的数据,那么这时就要把特殊的迭代器传进容器中了

copy(dice.begin(), dice.end(), back_insert_iterator< vector<int> > (words)); //将dice里面的内容从后面复制到words中

 

顺带一提copy可以:

  1. 将信息从一个容器复制到另外一个容器中
  2. 把数据从容器中复制到输出流
  3. 把信息从一个容器中插入到另外一个容器中

我们再来回顾一下前面的那一张图,我们可以发现,copy作为一种独立的算法,通过传给它不同的迭代器,可以实现对不同种类的容器的不同操作(输出,复制,插入)。

 

2.容器

list vector 什么的,还有关联容器set map pair,看的脑子疼就不计下来了

那个map和pair可以搭配使用

// multmap.cpp -- use a multimap
#include <iostream>
#include <string>
#include <map>
#include <algorithm>

typedef int KeyType;
typedef std::pair<const KeyType, std::string> Pair;
typedef std::multimap<KeyType, std::string> MapCode;

int main()
{
    using namespace std;
    MapCode codes;

    codes.insert(Pair(415, "San Francisco"));
    codes.insert(Pair(510, "Oakland"));
    codes.insert(Pair(718, "Brooklyn"));
    codes.insert(Pair(718, "Staten Island"));
    codes.insert(Pair(415, "San Rafael"));
    codes.insert(Pair(510, "Berkeley"));

    cout << "Number of cities with area code 415: "
         << codes.count(415) << endl;
    cout << "Number of cities with area code 718: "
         << codes.count(718) << endl;
    cout << "Number of cities with area code 510: "
         << codes.count(510) << endl;
    cout << "Area Code   City\n";
    MapCode::iterator it;
    for (it = codes.begin(); it != codes.end(); ++it)
        cout << "    " << (*it).first << "     "
            << (*it).second    << endl;

    pair<MapCode::iterator, MapCode::iterator> 
		auto range
         = codes.equal_range(718);
    cout << "Cities with area code 718:\n";
    for (it = range.first; it != range.second; ++it)
        cout <<  (*it).second    << endl;
    // cin.get();
    return 0; 
}

我感觉有点用的核心语句:

//利用map可以像数组那样子通过[]来访问数据来统计单词
map<string, int> wordmap;
set<string>::iterator si;
for (si = word.begin(); si != word.end();si++)  //si指向单词
     wordmap[*si] = cout(word.begin(), word.end(), *si);

 

函数对象

函数对象是可以以函数方式与()结合使用的任意对象,包括:

1)函数名;

2)指向函数的指针;

3)重载了()操作符的类对象(即定义了函数operator()的类)

那又何必有所谓的仿函数呢?原因在于函数指针毕竟不能满足STL对抽象性的要求,也不能满足软件积木的要求——函数指针无法和STL其他组件(如配接器adapter)搭配,产生更灵活的变化。同时,函数指针无法保存信息,而仿函数可以。

 

。。。

 

看不懂,可能是直接用函数对象比较方便吧,比如:
template <class T,class S>   
  void fun(T &a,S &b){
    cout << a << ' ' << b << endl;
  }
//template void fun<int, double>(int &a, double &b);
int main(){
  
  int a = 1;
  double b = 2.5;
  string c = "hello";

  fun(a, b);
  void (*p1)(int &a, string &c) = fun;    //函数指针版本
  p1(a, c);

}
void show(const int a){
  cout << a << endl;
}
int main(){
  ostream_iterator<int, char> out_iter(cout, "\n");  //第一个参数是输出方式,第二个是分隔符
  int x[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  vector<int> dice(10);  
  copy(x, x + 10, dice.begin());   //复制函数
  for_each(dice.begin(), dice.end(), show);    //直接传函数版本
}
template <class T>
class show{
  public:
    show(){}
    void operator()(T &i) { cout << i << endl; }
};
int main(){
  ostream_iterator<int, char> out_iter(cout, "\n");  //第一个参数是输出方式,第二个是分隔符
  int x[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  vector<int> dice(10);  
  copy(x, x + 10, dice.begin());   //复制函数
  for_each(dice.begin(), dice.end(), show<int>());  //使用函数对象
}

 

这里可以发现,要用函数指针,先要这样子写一大串东西,然后才能传进去,但是用类的话会方便一点,直接实例化A<int>/<double>/<string>就完事了,然后还可以保存信息什么的,扩展性很高,但是占用内存更大和效率会比函数指针要慢得多。

 

其他库

1.vector,valarray,array

2.模板initializer_list:就是可以使用初始化列表语法来初始化STL容器,因为容器类现在包含将initializer_list<T>作为参数的构造函数。例如vector<double>包含一个将initializer_list<double>

作为参数的构造函数。

vector<int> x {1, 2, 3, 4, 5};

数据可以进行有必要的转化但不能隐式的窄化转化

 

总结

STL是一个容器类模板,迭代器模板,函数对象模板和算法模板的集合,他们的设计都是基于泛编程原则的。

  • 诸如vector和set等容器类是容器的概念(容器,序列,关联容器)的模型
  • 有一些算法被表示为容器的类方法,但是大量算法都被表示为通用的,非成员函数的,这是通过将迭代器作为容器和算法之间的接口得以实现的(把迭代器(这个类)给传进去,比如要把数据复制到输出流就传一个ostream_iterator,这样就把数据复制到输出流中。比如只是单纯的复制的话就传一个输入迭代器就成)。还有一个优点就是,我们只需要一个诸如copy(),for_each()这样的函数就可以了而不需要为每一个容器提供不同的版本。另外一个优点就是STL算法可以用于非STL容器,如常规数组,string对象。
  • 上面可以看到,算法对容器是有要求的,容器必须支持算法所需的迭代器,不然就要提供一个专门的方法。
  • STL还提供了函数对象,函数对象是重载了()运算符的类,可以用函数的表示方法来调用这种类的对象,同时可以携带更多的信息。

发布者

我乃堂堂SCUT的一条咸鱼!

发表评论

电子邮件地址不会被公开。 必填项已用*标注