STL泛型编程原创入门教程

1、STL泛型编程原创入门教程 集训会教案在讲STL之前 先普及下c+ 1：就是c的加强版，对我们算法竞赛而言，基本的提交语言都是c+的，因为 c+完全兼容c。 文件的拓展后缀是 .cpp 。2：头文件是 #include <xxxxxxx> 注意没有 .h 如果想用c的头文件就 是c stdio 不用.h3：定义命名空间，每个程序都要在头文件下写上 using namespace std；是为了防止重名4：基本输入输出是 iotream 用法是 cin >> a; cout <<a; 你们看看箭头就明白，前者是加入后者是抽出。5：其余语法一模一样，还能使用ST

2、L的函数库，STL全称是Standard template library 简单的说，就是一堆库函数，各种奇妙的功能，带你装比带你飞。别人要用5行来实现的排序，你一句sort轻松ok，要正排正排，要逆序逆序。多种数据结构，别人写几十行实现代码，你轻松敲下 find 实现查找，push入栈，pop出栈。STL使用c+编程。主要为13个头文件Algorithm 算法库 deque 双端队列 Functional函数式编程 iterator迭代器Vector 不定长数组 list 列表Map 映射 memory 内存方面Numeric 基础性的数值算法 queue 队列Set 集合 stack 栈U

3、tility 程序包 以上内容中，在acm中能用到的，是除了utulity 和memory 以外的，都是重点。 因为字符串也经常使用到，string 字符串容器我们也一样讲。今天我们不可能把stl都讲完，所以我就 主要是来讲讲他的 一些最常用案例的使用。之后呢建议个位，把每一个头文件都重新学习一遍，不需要背下来，只要在关键时刻能想起来有这个，然后查查资料就ko了。数据结构部分数据结构，按理而言是要计科的孩纸学一年，物联网的孩纸学半年的。不过，咱们也不需要那么细致的学习，其实太多的知识是能用就行的，现在让我们用一节课来ko基础的数据结构。数据结构是是什么呢，简单的理解就是数据如何的存储结构。我们

4、之前学习过链表，那么实际上大多数的数据结构都是由链表来加以改装来实现，首先是list 双向链表，这个熟悉吧！一定要注意其实容器都是类似的，学好一个后面的就刷刷会了。头文件是 #include <list> 定义是 list <int> l1; 构造一个int 类型的 l1的空链表 list <int> l1（3）; 有三个元素，值都为0 list <int> l1（3，1），; 有三个元素，值都为1 我们可以对比的来上手，和数组对比，其实是一样的 Int a100;这是在定义数组，同样是指定类型就可以了， 1：要找第一个元素怎么找呢：数组 直接

5、a【0】；List l1.front() ; /注意括号一定要有，其实这是一个函数返回值是他的首元素 2：找最后一个元素，数组 a【99】；List l1.back（）;3：访问中间元素，这个有点难度，要用指针，首先我们要定义指针：List<int>:iterator it ;这个形式记住就可以，容器<类型>：iterator it it = l1.begin(); 返回开始位置的指针it = l1.end(); 返回结束位置的下一个位置的指针如何添加和删除呢？Cin>>a;L1.push_front(a);添加一个a到链表头L1.push_back(a);

6、到尾L1.Pop_front(); 删除一个头，无参数L1.Pop_back(); 删除一个尾，无参数 L1.clear（）删除所有。 L1.erase（it ，it+5）；删除一个或者一个区域L1.Remove（4）删除链表中所有的4L1.Remove_if(某函数) 删除满足条件的数， L1.Size（）返回元素个数 L1.Empty（）判断是否空，空为真为true，否则为假false。 L1.Reverse（）反转链表 L1.Sort（） 正排序 L1.Sort（greater<int>）逆排序拿个题目练下，求次大值。和次小值。求全部的和。求长度。要求30行内实现。#incl

7、ude<iostream>#include<list>#include<numeric>using namespace std;int main() list<int>l1; list<int>:iterator it, it1; int a,i,j=5; while(j-) cin>>a; l1.push_front(a); i = accumulate(l1.begin(),l1.end(),0); l1.sort(); l1.pop_back(); l1.pop_front(); it = l1.begin(); i

8、t1 = -l1.end(); cout<<*it<<" "<<*it1<<" "<<l1.size()<<” ”<<i<<endl; list<int>l1; int a,j=5; while(j-) cin>>a; l1.push_front(a); l1.sort(); cout<<*+l1.begin()<<" "<<*(-(-l1.end()<<"

9、"<<l1.size()<<endl;cout<<accumulate(l1.begin(),l1.end(),0)<<endl;总结一下。链表除了不能随机访问以外，都是优点。链表功能非常强大。因为在增填数据和删除数据的时候，不像数组那样要移动大量数据。现在我们能懂一种结构了，那么我们快速的讲讲剩下的几种结构。主要由链表来解决的问题一般是一些大规模的数据，因为数组无法存放就可以使用，不过，STL里有一个不定长数组，也可以替代功能，希望大家多多看看这个链表的介绍，因为其他的结构其实运用的函数是一样的。在我的博客里也有一个文章上面是list

10、的测试代码，可以直接拷贝来测试各个功能模块数据结构之栈和队列栈这个比较常见，主要用于解决括号配对ps南阳题2。走迷宫，这类运用栈的记忆能力的题目，在实际运用中，电子设备的状态一般都是使用栈来保存的，经常电脑出故障的时候会说什么堆栈溢出，就是这类问题。 队列也常见，比方说，我们去食堂吃饭。就一个个排队，先进先出的结构。他的作业就是能公平的逐个操作一遍。Ps：1197: 鸡蛋队列那么如何使用这样的结构呢。 注意他们本身其实就是链表，不过对数字的操作受到限制。 栈队列头文件stack queue定义stack<int> s1;Queue<int>q1;判断是否空S1.empt

11、y()Q1.empty()求元素个数S1.size()Q1.size();删除首元素S1.pop（）Q1.pop（）获得首元素值S1.top（）；Q1.front（）加入新元素S1.push（）Q1.push（）返回尾元素值无Q1.back（）；队列嘛用的略少，所以我们来主要解析一下，括号匹配的代码int main() char b10005; stack<char> a; scanf("%s",b); int l=strlen(b)， p=0; if(b0=')'|b0=''|b0='') printf(&quo

12、t;Non"); else for(int i=0;i<l;i+) if(bi='('|bi=''|bi='') a.push(bi); else if(!a.empty()&&(a.top()+1=bi|a.top()+2=bi) cout<<" "<<a.top()+1<<" "<<a.top()+2<<endl;a.pop(); else p=1;/a.top+1 +2 这个因为（）【】的asc码差别是1 2.

13、 if(a.empty()&&p=0) printf("Yesn"); else printf("Non"); return 0;Map和set 这两个比较少用到，所以我只是描述一下他的性质，有同学在未来要用刀的话可以去我的博客里查看，有专题说明。Map 就是映射，代表一种一一对应的关系，比方学号和个人。比较类似我们用结构体来实现功能一样。特点是又自动排序的过程。 Set 就是集合，任何数据只存在一个，无重复，并且有序。在加入元素的过程中就开始排序了。所以在对时间和内存要求高的题目就可以使用他们。vector 这个叫向量，也是不定长数组，

14、用法和数组一样。Vector<int> v;V100 = “0”;主要是用于弥补数组无法确定是开多大的情况下。和list互补，主要优点是可以快速随机访问。string 字符串之所以抛弃char*的字符串而选用C+标准程序库中的string类，是因为他和前者比较起来，不必担心内存是否足够、字符串长度等等，而且作为一个类出现，他集成的操作函数足以完成我们大多数情况下(甚至是100%)的需要。我们可以用 = 进行赋值操作，= 进行比较，+ 做串联（是不是很简单?）。我们尽可以把它看成是C+的基本数据类型。   好了，进入正题首先，为了在我们的程序中使用string类型

15、，我们必须包含头文件 。如下：   #include <string>/注意这里不是string.h string.h是C字符串头文件1声明一个C+字符串声明一个字符串变量很简单：   string Str;这样我们就声明了一个字符串变量，但既然是一个类，就有构造函数和析构函数。上面的声明没有传入参数，所以就直接使用了string的默认的构造函数，这个函数所作的就是把Str初始化为一个空字符串。String类的构造函数和析构函数如下：a)    string s; /生成一个空字符串sb)  

16、  string s(str) /拷贝构造函数 生成str的复制品c)    string s(str,stridx) /将字符串str内“始于位置stridx”的部分当作字符串的初值d)    string s(str,stridx,strlen) /将字符串str内“始于stridx且长度顶多strlen”的部分作为字符串的初值e)    string s(cstr) /将C字符串作为s的初值f)    string s(chars,chars_len) /将C

17、字符串前chars_len个字符作为字符串s的初值。g)    string s(num,c) /生成一个字符串，包含num个c字符h)    string s(beg,end) /以区间beg;end(不包含end)内的字符作为字符串s的初值i)    s.string() /销毁所有字符，释放内存都很简单，我就不解释了。2字符串操作函数   这里是C+字符串的重点，我先把各种操作函数罗列出来，不喜欢把所有函数都看完的人可以在这里找自己喜欢的函数，再到后面看他的详细解释。a) =,a

18、ssign()   /赋以新值b) swap()   /交换两个字符串的内容c) +=,append(),push_back() /在尾部添加字符d) insert() /插入字符e) erase() /删除字符f) clear() /删除全部字符g) replace() /替换字符 EF BB BF 3C 3F 78 6D 6Ch) + /串联字符串i) =,!=,<,<=,>,>=,compare() /比较字符串j) size(),length() /返回字符数量k) max_size() /返回字符的可能最大个数l) em

19、pty() /判断字符串是否为空m) capacity() /返回重新分配之前的字符容量n) reserve() /保留一定量内存以容纳一定数量的字符o) , at() /存取单一字符p) >>,getline() /从stream读取某值q) << /将谋值写入streamr) copy() /将某值赋值为一个C_strings) c_str() /将内容以C_string返回t) data() /将内容以字符数组形式返回u) substr() /返回某个子字符串v)查找函数w)begin() end() /提供类似STL的迭代器支持x) rbegin() rend(

20、) /逆向迭代器y) get_allocator() /返回配置器STL算法部分 库为 Algorithm 算法库 Functional函数式编程Numeric 基础性的数值算法一一：find 查找类有13个函数，详情请百度。使用方法，s.find（“a”）；s就是一个数据类型，比方说set 集合，就是在一个集合中找到第一个和a一样的 字符，然后返回他的迭代器，迭代器可以大概理解为指针。用法是 queue<int> : : iterator it;因为大多数函数返回的都是it 类型的指针，所有必须认真掌握。二：排序和通用算法 Sort 排序类有 14个函数。详情请百度。Sort （

21、a，a+n） 这样直接在这个范围内正排。或者自己写cmp（比较）函数Sort（a，a+n，cmp）；关于cmp怎么写，这个比较麻烦，Reverse 对指定范围内元素重新反序排序，。1对一维数组排序超简单写法Bool cmp（int a，int b）return a>b；降序排序， 后面是完整写法如果是qsort的话得这样写 qsort(a,n,sizeof(a0),cmp);        int cmp(const void *a,const void *b)/ const 不可改变的 a所指向的值 void 是多态。 return *

22、(int *)a-*(int *)b;    /  由小到大 （int *）是强制类型转换为int的指针类型，int cmp(const void *a,const void *b) /前面的* 好取指针的值来减虽然麻烦， return *(int *)b-*(int *)a;    /  由大到小 不过是为了通用性而设计的，.特例排序double型（只能这样来写）： Double in 【1000】；int cmp(const void *a,const void *b)     return (*(d

23、ouble*)a)>(*(double*)b) ? 1:-1; /返回值的问题，cmp是int型的，避免double 返 回小数而被丢失，三：删除和替换类型算法十五个。Copy 复制序列Remove 删除指定范围内，等于指定元素的元素。Replace 替换 指定范围替换元素Swap 交换，存储在两个对象的值。Unique 清除指定范围内重复元素。四：排列组合算法 2个Next_permutatiom 将当前范围重新排序为全排列，获得的是下一个序列Prevp_ermutatiom同上，获得的是上一个序列next_permutation(a,a+m) 全排列的下一个样例是#include<iostream>#include<string