摸鱼利器

有啥不会的,就去看手册

STL(Standard Template Library)内置了多种数据结构和算法,并且通过泛型编程的方法完成。

所以有了STL,不必再写大多的标准数据结构和算法,同时可以获得非常高的性能。

基本概念

  • 容器

    类似于类模板

  • 迭代器

    类似于指针,用于依次存取容器中的元素

  • 算法

    就是一些函数模板,自带的有

    • sort():玄学优化好的排序
    • find():二分查找

使用前,需要重载<或者写自定义函数

举个例子:

  • sort

    int a[100];
    sort(a, a+80);    //这里a和a+80就是迭代器

容器

可以用于存放各种类型的数据

概述

  1. 顺序容器

    vector, deque, list

  2. 关联容器

    set,multiset,map,multimap

  3. 容器适配器

    stack,queue,priority_queue

对象被插入容器时,被插入的是一个复制品!

并且,对于排序和查找,或者自带排序功能的容器,要求对象已经重载==<运算符

顺序容器

  • vector的随机速度快于deque的速度,后端和vector同速,前端快很多

    deque维护方法比较奇怪,导致deque速度慢
  • list不支持随机读取,因为内存不连续存放

关联容器

  1. 元素是排列的
  2. 插入任何元素,需要按照排序规则来确定位置
  3. 查找性能好
  4. 一般是用平衡二叉树实现的

容器适配器

就是套娃,但啥也不支持

常用的成员函数

顺序容器和关联容器都有的

  • begin:第一个元素的迭代器
  • end:返回最后一个元素后面位置的迭代器
  • rbegin:返回最后一个元素的迭代器
  • rend:返回第一个元素前面的迭代器
  • erase:删除一个或多个元素
  • clear:全部清空

顺序容器特有

  1. front:返回第一个元素的引用
  2. back:返回最后一个元素的引用
  3. push_back:在容器末尾添加新元素
  4. pop_back:删除容器末尾的元素
  5. erase:删除迭代器指向的元素,或区间,

    返回删除元素后面那个元素的迭代器

迭代器

概念

  1. 用于指向顺序容器和关联容器中的元素
  2. 迭代器的用法和指针类似

    毕竟是拿指针实现的
  3. const和非const两种
  4. 可以通过迭代器读取,或(非const)修改其元素

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

迭代器类名::iterator 变量名;
//或者
迭代器类名::const_iterator 变量名

访问,和指针一样

*it;

支持++操作

it++;

看一段代码

int main() {
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);

    vector<int>::const_iterator cit;
    vector<int>::iterator it;

    for(cit = v.begin();cit!=v.end();++cit)
        cout << *cit << ",";
    cout << endl;
    
    for(it = v.begin();it!=v.end();++it)
        ++(*it);

    for(int i : v)
        cout << i << ",";

输出

1,2,3,4
4,3,2,1

也有个反向迭代器reverse_iteraotr表示方向的迭代器,++操作,相当于得到上一个元素,看代码

int main() {
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);

    vector<int>::reverse_iterator cit;

    for(cit = v.rbegin();cit!=v.rend();++cit)
        cout << *cit << ",";
    cout << endl;
}
容器适配器类型不支持迭代器!

双向迭代器

如果pp1都是双向迭代器,那么可以进行如下操作

++p, p++;
--p, p--;
*p;
p = p1;
p == p1;
p != p1;

和指针类似

被如下的容器支持:

  • list
  • set/multiset
  • map/multimap

随机访问迭代器

  1. 双向迭代器都可以
  2. 其他

    p += i;
    p -= i;
    p + i;
    p - i;
    p[i];
    p < p1, p<=p1, p>p1, p>=p1;

    和指针完全一致

被如下的容器支持:

  • vector
  • deque

算法要求

  1. sortbinary_search需要通过随机访问迭代器来访问元素,所以不支持随机访问迭代器的统统不能调用该函数。
  2. 如果容器/算法没有指定排序方法,则需要保证小于号和双等号正常工作

算法

由于算法过多,此处只涉及非常常用的,

其余算法在另一篇文章

algorithm头文件中定义

算法通过迭代器来操纵容器中的元素,许多算法可以对容器中的一个局部区间进行操作,因此需要两个参数,一个是起始,一个是终止。

有的算法会返回一个迭代器,比如说find()算法

算法可以处理容器,同时也可以处理普通数组

迭代器可以拿指针初始化

find()

在左闭右开的区间寻找,通过用==判断相等,返回被找到的迭代器,如果没有找到,则返回区间右端点

算法复杂度是O(n)

用法

find(a, a+50, 30);
//起始,终止,查找的值

binary_search

二分查找

binary_search(a,a+90,342);

sort()

玄学优化排序

sort(a,a+90,[](){return true;})

容器的具体使用

如果非常长,可以用typedef来解决问题!比如

typedef function<map<int,string>(map<int,string>,int,int)> fun1;
typedef vector<map<int,string>> myvt;

vector

看代码

template<typename T>
void printVector(T& v){
    for(auto i : v)
        cout << i << ", ";
    cout << endl;
}

int main() {
    int a[5] = {1,2,3,4,5};
    vector<int> v(a,a+5);
    printVector(v);

    cout << v.end()-v.begin()<< "\t" << v.size() << endl; //输出大小,5
    
    v.insert(v.begin()+2, 13); //多了个13
    printVector(v);
    
    v.erase(v.begin()+2); //少了个13
    printVector(v);
    

    vector<int> v2(4,100);  //有4个元素,都是100

    v2.insert(v2.begin(), v.begin()+1, v.begin()+3);    //插入2个元素
    printVector(v2);
    
    v.erase(v.begin()+1,v.begin()+3);
    printVector(v);
}

deque

多了个push_frontpop_front

性能比list好,比vector弱

list

除了常见的,还有

  • push_front
  • pop_front
  • sort,特殊的排序
  • remove,删除和值相等的所有元素
  • unique,删除和前一个元素相同的元素

    如果想要去重,需要先sort
  • merge,合并两个链表,并清空被合并的那个
  • reverse,颠倒链表

less和greater

先介绍一个东西,再来看map和set

看代码

template<T>
bool less(constT& a,const T& b) const{
    return a<b;
}
template<T>
bool greater(constT& a,const T& b) const{
    return a>b;
}

相当于把小于号和大于号封装了一下

set/multiset

支持:

  • find(const T& val)
  • lower_bound(const T& val):查找某个下界

    找到一个最大的位置it,使得[begin(), it)的元素都比val

  • upper_bound:查找某个上界

    找到一个最小的位置it,使得[it, end() )的元素都比val

  • equal_range(equal_range):同时查找上届和下届,返回一个pair<iterator, iterator>
  • count(const T& val):计算等于某个值的元素个数
  • insert(iterator first, iterator last):插入一个元素或区间

定义

template<class Key, class Pred = less<Key>, class A=allocator<Key>>
class multiset{
    
}

可以通过指定第二个参数来改变排序的方法。

默认调用小于号

map/multiset

template<class Key, class T, class Pred = less<Key>, class A = allocator<T> >
class multimap{
 
    typedef pair<const Key, T> value_type;
}

可以通过指定第3个参数来改变排序的方法。

默认调用小于号

注意:map根据first值来排序

map中相当于存储了若干个value_type

示例

map的insert函数会返回一个pair,first表示是否成功,second表示如果插入成功,返回插入的迭代器
 int main() {
    typedef multimap<int, double, less<int>> mmid;
    mmid pairs;
    cout << pairs.count(15) << endl;
    pairs.insert(mmid::value_type(15,2.7));
    pairs.insert(mmid::value_type(15,99.3));
    cout << pairs.count(15) << endl;
    pairs.insert(mmid::value_type(10,111.1));
    pairs.insert(mmid::value_type(10,22.22));
    pairs.insert(mmid::value_type(25,33.33));
    pairs.insert(make_pair(20,9.3));

    for(auto i = pairs.begin(); i!=pairs.end(); ++i)
        cout << i->first << '\t' << i->second << endl;
    
    return 0;
}

输出

0
2
10      111.1
10      22.22
15      2.7
15      99.3
20      9.3
25      33.33

map好玩的一点是支持[]函数

stack

  • pop:去堆顶
  • top:得到堆顶
  • push:压入堆顶
  • size:大小
  • empty:是否为空

queue

  • push:到队尾
  • pop:去对头
  • top:取对头
  • back:取队尾
  • size:大小
  • empty:是否为空

priority_queue

template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue{
    
}

默认大根堆,通过小于号实现,可以通过第三个参数指定排序方法

  • push,pop:O(logN)
  • top: O(1)
  • size:大小
  • empty:是否为空

补充:bitset

#include <bitset>

bitset<40> bst;

有如下成员函数:

  • &=按位与等(两个bitset要一样长)
  • |=按位与等
  • ^=按位异或等
  • <<=左移等
  • >>=右移等
  • set()全部变成1
  • set(pos, val)把pos改为val
  • reset()全部变成0
  • reset(pos) 某位置改为0
  • flip()全部反转(1变0,0变1)
  • flip(pos)反转某位
  • []随机访问
  • at()检查下标的随机访问
  • to_ulong()转整形
  • to_string()转字符串
  • count()计算1得个数
  • size()大小
  • ==!= 相等与不等
  • any()判断是否有一位是1
  • none()判断是否全0
注意一点,第0位在最右边!
Last modification:April 17th, 2020 at 01:03 pm
Compared with money, your comment could inspire me more.
相较于钱财,你的留言更能激发我创作的灵感