写在前面: 为了能够使后续的代码具有高效简洁的特点,在这里讲一下STL,就不用自己写堆,写队列,但是做为ACMer不用学的很全面,我认为够用就好,我只写我用的比较多的。
容器(Container): 是一种数据结构,如list,vector,和deques ,以模板类的方法提供。为了访问容器中的数据,可以使用由容器类输出的迭代器; 迭代器(Iterator): 提供了访问容器中对象的方法。例如,可以使用一对迭代器指定list或vector中的一定范围的对象。迭代器就如同一个指针。事实上,C++的指针也是一种迭代器。但是,迭代器也可以是那些定了operator*()以及其他类似于指针的操作符地方法的类对象; 算法(Algorithm): 是用来操作容器中的数据的模板函数。例如,STL用sort()来对一个vector中的数据进行排序,用find()来搜索一个list中的对象,函数本身与他们操作的数据的结构和类型无关,因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用; 仿函数(Functor) 适配器(Adaptor) 分配器(allocator) 仿函数、适配器、与分配器用的比较少,甚至没用过!在这里不做说明,有兴趣可以自己学习一下,那个东西C++软件工程可能用的比较多。
如果有不理解的容器知识可以先去看看容器
(可以去看看C++primer学学别的,但是我认为太多了没必要) 1.count: 利用等于操作符,把标志范围内的元素与输入值比较,返回相等元素个数。
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[14]={0,1,2,3,4,5,6,7,7,7,7,7,7,8};
cout<<count(a,a+14,7)<<endl;
vector<int> demo;
for(int i=0;i<10;i++)
demo.push_back(i);
demo.push_back(1);
cout<<count(demo.begin(),demo.end(),1)<<endl;
}
//运行结果 6 2;
2.count_if: 利用输入的操作符,对标志范围内的元素进行操作,返回结果为true的个数。
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int a)
{
return (a>1);
}
int main()
{
int a[14]={0,1,2,3,4,5,6,7,7,7,7,7,7,8};
int po=count_if(a,a+14,cmp);
cout<<po<<endl;
vector<int> demo;
for(int i=0;i<10;i++)
demo.push_back(i);
demo.push_back(1);
int poi=count_if(demo.begin(),demo.end(),cmp);
cout<<poi<<endl;
}// 运行结果 8 12
//看到网上大佬的代码写的比较深奥,特地去查了查书,我这样用没毛病的。
补充:捕获值列表,是允许我们在Lambda表达式的函数体中直接使用这些值,捕获值列表能捕获的值是所有在此作用域可以访问的值,包括这个作用域里面的临时变量,类的可访问成员,全局变量。捕获值的方式分两种,一种是按值捕获,一种是按引用捕获。顾名思义,按值捕获是不改变原有变量的值,按引用捕获是可以在Lambda表达式中改变原有变量的值。 [捕获值列表]: 1、空。没有使用任何函数对象参数。 2、=。函数体内可以使用Lambda所在作用范围内所有可见的局部变量(包括Lambda所在类的this),并且是值传递方式(相当于编译器自动为我们按值传递了所有局部变量)。 3、&。函数体内可以使用Lambda所在作用范围内所有可见的局部变量(包括Lambda所在类的this),并且是引用传递方式(相当于编译器自动为我们按引用传递了所有局部变量)。 4、this。函数体内可以使用Lambda所在类中的成员变量。 5、a。将a按值进行传递。按值进行传递时,函数体内不能修改传递进来的a的拷贝,因为默认情况下函数是const的。要修改传递进来的a的拷贝,可以添加mutable修饰符。 6、&a。将a按引用进行传递。 7、a, &b。将a按值进行传递,b按引用进行传递。 8、=,&a,&b。除a和b按引用进行传递外,其他参数都按值进行传递。 9、&, a, b。除a和b按值进行传递外,其他参数都按引用进行传递。
3.equal_range: 功能类似equal,返回一对iterator,第一个表示lower_bound,第二个表示upper_bound。
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int a)
{
return (a>1);
}
int main()
{
// int a[14]= {0,1,2,3,4,5,6,7,7,7,7,7,7,8};
//equal_range(a,a+14,auto po);
vector<int> demo;
for(int i=0; i<10; i++) demo.push_back(i);
demo.push_back(1);
cout<<*equal_range(demo.begin(),demo.end(),7).first<<endl;
cout<<*equal_range(demo.begin(),demo.end(),7).second<<endl;
cout<<equal_range(demo.begin(),demo.end(),7).first-demo.begin()<<endl;
cout<<equal_range(demo.begin(),demo.end(),7).second-equal_range(demo.begin(),demo.end(),7).first<<endl;
}
//也可以加cmp函数,同样适用于数组,在下文中不再举出数组的例子
4.find: 利用底层元素的等于操作符,对指定范围内的元素与输入值进行比较。当匹配时,结束搜索,返回该元素的一个InputIterator。
补充 InputIterator是用于输入的Iterator OutputIterator是用于输出的Iterator ForwardIterator是InputIterator,同时可以保证++运算不会使之失效 RandomIterator是ForwardIterator,同时具有+,-,+=,-=等运算及各种比较操作
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[14]= {0,1,2,3,4,5,6,7,7,7,7,7,7,8};
vector<int> demo;
for(int i=0; i<14; i++) demo.push_back(a[i]);
demo.push_back(1);
cout<<find(demo.begin(),demo.end(),8)-demo.begin()<<endl;
} //可以直接取地址获取值。
5.find_end: 在指定范围内查找"由输入的另外一对iterator标志的第二个序列"的最后一次出现。找到则返回最后一对的第一个ForwardIterator,否则返回输入的"另外一对"的第一个ForwardIterator。重载版本使用用户输入的操作符代替等于操作。
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[14]= {0,1,2,3,4,5,6,7,7,7,7,7,7,8};
vector<int> demo;
for(int i=0; i<14; i++) demo.push_back(a[i]);
demo.push_back(1);
cout<<find_end(demo.begin(),demo.end(),a+2,a+3)-demo.begin()<<endl;
}
6.find_first_of: 在指定范围内查找"由输入的另外一对iterator标志的第二个序列"中任意一个元素的第一次出现。重载版本中使用了用户自定义操作符。
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[14]= {0,1,2,3,4,5,6,7,7,7,7,7,7,8};
vector<int> demo;
for(int i=0; i<14; i++) demo.push_back(a[i]);
demo.push_back(1);
cout<<find_first_of(demo.begin(),demo.end(),a+2,a+3)-demo.begin()<<endl;
}
7.find_if: 使用输入的函数代替等于操作符执行find。返回的是迭代器,为了是大家更明白的理解,减去第一个元素的位置,就相当于得到了下标;
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int w) {
return w>5;
}
int main()
{
int a[14]= {0,1,2,3,4,5,6,7,7,7,7,7,7,8};
vector<int> demo;
for(int i=0; i<14; i++) demo.push_back(a[i]);
cout<< find_if(demo.begin(),demo.end(),cmp)-demo.begin();
}
8.lower_bound: 返回一个ForwardIterator,指向在有序序列范围内的可以插入指定值而不破坏容器顺序的第一个位置。重载函 数使用自定义比较操作。 在一个有序的范围内时间复杂度为log2n,普遍适用于二分算法。 跟3.equal_range的用法一样不过这个返回的是first 9.upper_bound: 返回一个ForwardIterator,指向在有序序列范围内插入value而不破坏容器顺序的最后一个位置,该位置标志 一个大于value的值。重载函数使用自定义比较操作。跟3.equal_range的用法一样不过这个返回的是second;
将指定范围内元素移到容器末尾,由middle指向的元素成为容器第一个元素。
以深搜的形式实现:
构造一个有序序列,该序列取两个序列的对称差集(并集-交集)。