STL标准库介绍：

  • 介绍：STL是c++里面自带的标准库，里面自带了许多已经封装好的方法，通过合理的使用，我们可以应对很多情况，避免重复造轮子。
  • 这些容器包括了：vector(序列)，stack(栈)，queue(队列)，priority_queue(优先队列)，set(集合)，multiset(多重集合)，unordered_map(哈希表)。
  • 不同的STL容器可以应对不同的情况，犹如我们的瑞士军刀。
  • 刷题指南：牛客130系列 ，学完一些基本操作建议去刷一下这里面的题，熟悉一下应用。

方法模板汇总：

vector

特点

  • vector也被称为动态数组，特点是逻辑上连续且内存地址连续，可以自动扩容

方法：

  • 声明：vector<'type'> v;
  • 填入数据：v.push_back(value)，在容器末尾加入元素。
  • 获取长度：v.size();
  • 查找元素：auto it=find(v.begin,v.end(),x)，查找x的位置，返回x的迭代器
  • 删除元素：v.erase(it)，删除it迭代器对应的元素，配合一般find使用。
  • 删除末尾元素：v.pop_back()。
  • 函数传参：add(const vector< int > &v)。
  • 初始化：
    1. 全为0，vector< int >dp(10),十个元素全为0。
    2. 手动添加，vector< int >dp(10,0)。
  • 判断是否为空：v.empty()，为空则返回true。
  • 清空序列：v.clear()。
  • 排序：sort(v.begin(),v.end())。
  • 反转序列：v.reverse()。
  • 插入元素：
    1. 插入单个元素：v.insert(v.begin()+2,3)，在索引为2的地方插入3，这个元素，而原本这个位置的元素，以及后面的所有元素都会往后移1位。
    2. 插入多个元素：v.insert(v.begin()+2,other.begin(),other.end()) 这样可以将另一个容器插入到一个容器中。也可以指定插入v.insert(v.begin()+2,3,4) ,这样也是同理。
    3. 但我们要知道的是，我们在元素后，会使得插入点以及后续的所有迭代器都会失效。迭代器失效是什么意思呢？就是我们在插入元素后，内存空间会重新分配，原本指向某个位置的指针，在插入操作后，这个指针就失效了，我们要重新获取，获取方式:auto it=insert(v.being()+2,3) 获取3的指针，之后将it++ 即可得到，我们原本在索引2，这个位置的元素的指针，之后的元素指针也要重新在获取。
      数组能干的事情，序列也能干，但是序列是自动扩容，但要注意，当序列元素没有该索引是，我们不能访问这个索引，也就是不能在创建序列的时候通过索引来赋值。

stack

特点：

  • 栈只能在栈顶进行入栈和出栈操作，也就是先进后出，无法查看和访问栈内部的元素，只能看到栈顶的元素。

方法：

  • 声明：stack<type> s
  • 入栈：在栈顶加入，s.push(x)
  • 出栈：s.pop()
  • 查看栈顶元素：s.top()
  • 获取元素数量：s.size()
  • 判断栈是否为空：s.empty()

queue

特点：

  • 先进先出，队尾进入元素，队首出元素，不能随机访问。

方法：

  • 声明：queue< int > q
  • 入队：q.push(x)
  • 出队：q.pop()
  • 查看队首元素：q.front()
  • 查看队尾元素：q.back()
  • 查看是否为空：q.empty()
  • 查看长度：q.size()

set 与 multiset

特点：

  • set里面的元素不会有重复，也就是会自动去重，同时里面的数字是无序的，我们没办法用直接查找，但是有前驱和后驱的相应查找方法。
  • multiset与set的不同点就是，multiset里面允许有重复，且里面的元素会自动按照一定的规律排列，默认从小到大，我们也可以自己写一个比较函数，因此有时也用multiset来实现优先队列

方法：

  • 声明：set<type> s与multiset<type,比较函数> ms 比较函数不加默认为升序排列。
  • 插入元素：s.insert(x) 与ms.insert(x) 时间复杂度为O(log n)
  • 删除元素：s.erase(x) 删除x，ms.erase(x) 删除所有x，如果我们想要只删除一个元素，我们要先要用find找到这个元素的迭代器，在用这个迭代器来删元素。
  • 查找元素：s.find(x) 与ms.find(x) 找到对应元素的迭代器，没找到返回s.end()
  • 找前驱和后驱s.lower_bound(x) 返回第一个大于x的数的迭代器否则返回end()，s.upper_bound(x) 返回第一个大于等于x的数的迭代器，我们在将这个迭代器减一，就得到了x的前驱。
  • 统计数量：s.count(x) 与ms.count(x) 统计x出现的次数
  • 查找最大数量：ms.max_size() 返回不同元素的最大可能数量。

priority_queue

特点：

  • 优先队列有点类似于multiset，他是队列按照某种顺序排列组成的。

方法：

  • 大根堆声明：priority_queue<type> pq 按照从小到大的顺序排列
  • 小根堆声明：priority_queue<type,greater<type> > pq 按照从大到小排列
  • 由于是队列按照顺序排列的，因此队列有的方法优先队列都有。

map

特点：

  • map 也是一个储存键值对的容器，但是里面的key是有序的，会按照一定的顺序来存储，对于有序存储和快速查找方面有很大的优势

方法：

  • 声明：map< int ,int > m
  • 访问：有两种访问方法：m[i]，返回值，且m.at(i)，会进行边界检查，如果超出边界会抛出异常
  • 添加元素：m[i]=1
  • 例如：size，max_size，empty等常见方法，map也有
  • 删除元素：m.erase(i)用键来删除，m.erase(it) ，用迭代器删除

unordered_map

特点：

  • 哈希表最大的特点，就是查找元素速度极快，时间复杂度只要O(1)，在查找上具有巨大优势，因此当我们需要频繁查找时，哈希表使我们的不二之选。

方法：

  • 声明：unordered_map<key_type,value_type> hash ，哈希表里面分为键和值两部分，两部分的数据类型可不同，但是两种数据类型必须都是可哈希的，否则无法用哈希表。

  • 赋值：hash[key]=value 将key对应元素赋值为value，或创造一个新键值对，哈希表里面的键是不能重复的。

  • 判断是否存在：hash.count(x) 判断时候有key这个键.

  • 删除：hash.erase(key) 删除对应键值对。

  • 访问：hash[key] 如果存在该键值对，就返回值，不存在就创造一个key为键，默认数据的值，如0。

  • 遍历哈希表：for(auto& pair:hash),在循环里面pair.first为键,pair.second为值，也可以for(auto& [key,value]:hash)

  • 本节介绍了一些STL的基本方法，但更多的操作细节和灵活用法，还是要在题目中慢慢积累。