C++——STL入门-阿里云开发者社区

开发者社区> 开发与运维> 正文
登录阅读全文

C++——STL入门

简介: C++——STL入门

c++标准库包含STL,STL包含六大部件


STL

standard template library 标准模板库

C++的含义:C语言+类+模板

STL有6大组件:

容器、算法、迭代器、适配器、分配器、仿函数

容器(container)

  1. 系统封装好的数据结构
  2. 泛型编程思想,每种数据结构都能装任意类型
  3. 主要是对数据结构增删改查的操作

算法(algorithm)

  1. 系统封装好的算法(如sort排序算法)
  2. 一个算法适用多种容器(泛型编程思想)

迭代器(Iterator)

迭代器相当于指针

迭代器告诉算法要执行的范围(在容器中)

分配器(allocator)

对容器的内存进行管理分配(例如vector容器的自动扩充,自动缩容等)

仿函数(functor)

仿函数:结构体或类要实现函数的功能,就要重载function call 操作符 ()

#include <iostream>

using namespace std;

class Stu{

public:

    //重载()操作符

   //只有函数返回true时,a的优先级才大于b

    bool operator () (int a,int b){

        

        return a>b; //此时当a>b时返回true,那么数值越大优先级越高

        

       //return a<b; 此时当a<b时返回true,那么数值越小优先级越高

    }

};

int main()

{

     Stu s;

     cout << s(1,2) << endl;//0

     cout << s(2,1) << endl;//1

    return 0;

}

容器(container)

容器类自动申请和释放内存,无需new和delete操作


结构及分类

Sequence Containers

序列式容器:按照放入元素的顺序进行排列

Array:定长数组

Vector:不定长数组

Deque:双端队列

List:双向链表

Forward-List:单向链表

Associative Containers

关联式容器:元素是以键值对的形式存在(key/value),通过key可以快速查找,因此这种容器适合大量查找

关联式容器又分为Ordered Container和Unordered Container,即定序容器和不定序容器

定序容器:元素在容器内的位置是亘古不变的

不定序容器:元素在容器内的位置会随着时间的推移而发生变化

Ordered Container

定序容器:底部是红黑树,一种高度平衡的二分树,避免最差情况的发生(例如退化成链表)

Set:key不可以重复(set的key就是value,value就是key)

Multset:key可以重复

Map:key不可以重复

Multmap:元素可以重复

Unordered Container

不定序容器:底部是HashTable(HashTable中的链表不宜过长,避免查找忒慢)

Unordered Set

Unordered Multset

Unordered Map

Unordered Multmap

所有容器共有的操作

  1. 赋值(=):数组之间不可以赋值,相同类型容器之间可以
  2. begin():返回指向开头元素的迭代器
    end():返回指向末尾的下一个元素的迭代器
  3. size():返回容器内元素的个数
  4. empty():空返回true,不空返回false
  5. clear():清空容器(可以用来初始化)

vector(动态数组)

#include<vector>

构造函数

vector();

explicit vector(size_type count);

vector(size_type count, const Type& value);

template <class InputIterator>

vector(InputIterator first, InputIterator last);

vector<int> memo;//无参构造啥都不加

memo=vector<int>(n+1,-1); //初始化n+1个元素,即[0,n]都为-1

vector<string> board(n,string(n,'.'));//初始化n个元素,即[0,n-1]都为n个'.'的字符串

vector<int> v(10);//初始size为10,是动态数组,容量可以改变;int a[10]容量则不可以改变

访问元素

  1. 下标
  2. back():返回末尾元素的引用
  3. front():返回首元素的引用

增删改查

push_back():在末尾插入一个元素

pop_back():删除末尾元素

insert():某个迭代器位置插入元素

erase():删除某个迭代器或者区间的元素,返回最后被删除的迭代器

队列

#include<queue> //包含queue,deque,priority_queue

queue<int> q;

双端队列deque

既可以头出队,也可以尾出队

既可以头入队,也可以尾入队

优先队列

priority_queue<int> q;//默认大的元素先出队

priority_queue<int,vector<int>,greater<int> > q;//这样子小的元素先出队

栈stack

#include<stack>

stack<int> s;

  1. push():将新元素进栈
  2. pop():弹出栈顶元素
  3. top():访问栈顶元素

集合set

不含重复元素,默认从小到大排序

#include<set>

增删改查

增删改查时间复杂度都为O(log n)

  1. insert():插入元素
  2. erase(x):删除元素
  3. count():返回元素数量
  4. find(x):在set内存在值为x的元素会返回该元素的迭代器,否则返回end()
  5. 遍历不能使用下标,要用迭代器

 set<int> s;

 s.insert(3);

 s.insert(2);

 set<int>::iterator it;

 for (it = s.begin(); it != s.end(); it++)

  cout << *it << endl;

映射map

#include<map>

map<string,int> m;

m["string"]=1;//下标为字符串

迭代器(iterator)

迭代器是泛化的指针,每个容器基本都有迭代器

算法通过迭代器知道要处理数据的范围(在容器中)

迭代器实现遍历

 int ia[6]={5,1,2,3,1,4};

 vector<int> vi(ia,ia+6);

 vector<int>::iterator it=vi.begin();

 for(;it!=vi.end();++it){

  cout << *it << endl;

 }

因为每种容器的迭代器实现是不同的,因此我们声明一个迭代器变量的时候需要指明是属于谁的迭代器

vector<int>::iterator it=vi.begin();//it是vector的迭代器

但是这种方式比较麻烦,我们可以使用auto关键字来自动识别迭代器种类

int main()

{

 int ia[6]={5,1,2,3,1,4};

 vector<int> vi(ia,ia+6);

 for(auto a : vi){

  cout << a << endl;

 }

 return 0;

}

谓词(predicate)

谓词就是一个判断,只能返回bool类型

5种谓词模式

1. 函数(function)谓词

/*Function Predicate*/

bool isLarger (const std::string &s1, const std::string &s2) {

 return s1.size() > s2.size();

}

......

std::stable_sort(sv.begin(), sv.end(), isLarger);

函数谓词使用时,只需要函数名,函数名代表函数地址,但函数名本质并不是函数地址

2. 函数对象(function object)谓词

函数对象谓词也叫仿函数(functor)谓词:在类或结构体中重载了函数调用符()

/*Function Object*/

class LargerString {

public:

 bool operator() (const std::string& a, const std::string& b) {

  return a.size() > b.size();

 }

};

......

std::stable_sort(sv.begin(), sv.end(), LargerString());

因为他们是仿函数(不是真的函数),因此仿函数谓词在使用时,需要 类名+() 或 结构体名+() 这种格式

3. 库定义的函数对象(library-defined function object)谓词

使用标准库定义的函数对象, 充当算法中的谓词, 包含在#include<functional>

std::stable_sort(sv.begin(), sv.end(), std::less<std::string>());

4. 函数指针(function pointer)谓词

5. Lambda表达式(lambda expression)谓词

常用的谓词是函数谓词,仿函数谓词(分为自定义的和标准库定义的)

一元谓词与二元谓词

  1. 如果operator()接收一个参数,叫一元谓词
  2. 如果operator()接收两个参数,叫二元谓词

//自己定义的一元函数谓词greater2

bool greater2(int a){

 return a>2;

}

int main()

{

 int ia[6]={5,1,2,3,1,4};

 vector<int> vi(ia,ia+6);

 cout << count_if(vi.begin(),vi.end(),greater2);//3

 return 0;

}

//使用标准库定义好的仿函数谓词greater<int>()

int main()

{

 int ia[6]={5,1,2,3,1,4};

 vector<int> vi(ia,ia+6);

 cout << count_if(vi.begin(),vi.end(),bind2nd(greater<int>(),2));//3

 return 0;

}

count_if函数第三个参数需要的是一元谓词,但是greater仿函数是二元谓词,所以我们可以通过function adapter(binder)来绑定第二个参数为2,那么greater<int>()只需要一个参数


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章
最新文章
相关文章