STL再回顾（非常见知识点）

目录

• 为人熟知的pair类型
• 再谈STL
  • 迭代器的使用
• 常用的STL容器
  • 顺序容器
    • vector(向量)
      • 构造方式
      • 拥有的常用的成员函数（java人称方法）
    • string
      • 构造方式
      • 成员函数
    • deque
    • list
  • 关联容器
    • set/multiset
      • 优点
      • 成员函数
      • 集合的交集，并集，差集
    • map/multimap
      • map/multimap的区别
      • 主要的成员函数
  • 适配器容器
    • 概述
    • stack
    • queue
    • priority_queue
• 关系函数对象
• 相关练习
  • 分隔单词

为人熟知的pair类型

注意：pair对于==, !=, <, >, <=, >=进行了重载，提供first第一关键字，second第二关键字的比较方法。

再谈STL

STL有三大件：

1. 容器
2. 算法
3. 迭代器

迭代器的使用

#include <vector> #include <iostream> using namespace std; int main() {     vector<int> myv;     myv.push_back(1);     myv.push_back(2);     myv.push_back(3);     vector<int>::iterator it;     for(it = myv.begin(); it != myv.end(); it++)     {         cout << *it << "  ";     }     puts("");     vector<int>::reverse_iterator rit;     for(rit = myv.rbegin(); rit != myv.rend(); rit++)     {         cout << *rit << "  ";     }     return 0; }  

常用的STL容器

顺序容器

有四个vector, string, deque, list

vector(向量)

优点：

• 可以在末尾快速插入以及删除
• 支持随机访问

缺点：

• 在中间插入或者删除像 数组 一样，移动大量元素
• 当大小不够时，按照两倍大小重新分配，并且移动。

构造方式

#include <vector> #include <iostream> using namespace std; #define V v4  //更改这里可以查看不同效果！ vector<int> v1; vector<int> v2(20);//指定了初始的size为20，再执行push_back是从21开始！！前面的20个元素的值是0 vector<int> v3(20, 2);//指定了初始的size为20，再执行push_back是从21开始！！前面的20个元素的值是2 int a[] = {1, 2, 3, 4}; vector<int> v4(a, a+4);//从数组中获取 int main() {     for(int i = 1; i <= 100; i++)     {         V.push_back(i);         printf("%dsize:%d, cap:%dn",i,  V.size(), V.capacity());     }     for(int i = 0; i < V.size(); i++)         cout << V[i] << "  ";     return 0; }  

拥有的常用的成员函数（java人称方法）

常用的仅仅列举 不说明！

empty()

size()

[]

reserve(n)分配n个元素的存储空间
注意：这一个仅仅是修改一开始的capacity，不影响size
使用可以直接给定一个空间，避免空间不够而进行频繁增加删除，当做更加优秀的数组使用

capacity

resize()调整size，比原来小时，删除多余的；比原来大时，补0

push_back()

insert(pos, elem)把某一个值插入到pos之前（注意这要耗费许多时间！）
pos是迭代器！

front()获取第一个值

back()获取最后一个值

erase()有重载：

1. 一个参数，迭代器，删除这一个位置元素
2. 两个迭代器，删除后这两个迭代器的区间中的元素。

clear()

begin(), end(), rbegin(), rend()

string

构造方式

string() string(char*) string(string) 

成员函数

empty()

size()

length()貌似除了类型与上面的有区别，其他的没有区别

[]

at()和上面一样

compare(const string &str)比较
如果自己大，返回1，形参大，返回-1，否则返回0

append(const string &str)在末尾增加字符串

insert(pos, elem)把某一个值插入到pos之前（注意这要耗费许多时间！）
pos可以是迭代器，也可以是数字！
但是elem一定是字符串！

find(字符或字符串， 位置)注意：如果找不到，返回值是一个迷，所以尽量不要用

replace()

例子：

string s1("abcdefg");     string s2(s1);     s1.replace(3, 3, "lll");//起始位置，长度，替换内容     cout << s1;     string::iterator it1 = s2.begin()+1;     string::iterator it2 = s2.end()-1;     s2.replace(it1, it2, "11");//[ , )     cout << s2 ; 

substr并不改变原来的值

 string s1("abcdefg");     cout << s1.substr(3) << "n";//defg     cout << s1.substr(3, 3);//def 

clear(), erase清空。

erase(idx);从idx（数字）处删除之后的内容

erase(idx, len)从idx（数字）处删除之后的长度为len内容

deque

deque与vector相比，他并不是由一个整体的内存存储的，而是由多个连续的内存块存储的，所以在头部以及尾部插入元素比较快，并且也支持随机访问。

构建方式：

#include <deque> #include <iostream> using namespace std; #define DQ dq3 int main() {     deque<int>dq1;     deque<int>dq2(2);     deque<int>dq3(2, 3);     deque<int>dq4(dq1);     deque<int>dq5(dq1.begin(), dq1.end());     deque<int>::iterator it;     DQ.push_back(8);     DQ.push_front(0);     for(it = DQ.begin(); it != DQ.end(); it++){         cout << *it;     }     return 0; } 

empty()

size()

front()

back()

push_front()

pop_front()

push_back()

pop_back()

erase()清除一个或者几个值

clear()全部清除

begin(), end(), rbegin(), rend()

list

可以快速插入以及删除元素，但是不支持随机访问。

empty()

size()

push_front()

pop_front()

push_back()

pop_back()

removeRemoves every element in the list equal to value.

list<int> l1({1, 2, 3, 4, 4, 4});     l1.remove(4);     list<int>::iterator it;     for(it = l1.begin(); it != l1.end(); it++)     {         cout << *it << "  ";//1  2  3     } 

remove_if()

#include <list> #include <iostream> using namespace std; #define DQ dq3 bool judge(int val) {     return val&1; } int main() {     list<int> l1({1, 2, 3, 4, 5, 6});     l1.remove_if(judge);     list<int>::iterator it;     for(it = l1.begin(); it != l1.end(); it++)     {         cout << *it << "  ";//2  4  6       }     return 0; } 

erase()删除一个或者几个元素

clear()清除所有的元素

insert(pos, n, elem), insert(pos, elem)注意：这一个插入是瞬间完成的。

insert(pos, 迭代器开始, 迭代器结束)

由于STL中的某些算法处理的是顺序容器的，所以在list中额外提供了一些功能。

#include <list> #include <iostream> using namespace std; list<int>::iterator it; int main() {     list<int> l1({1, 3, 5, 7,  9, 11});     list<int> l2({2, 4, 6, 8, 10, 11});     l1.merge(l2);//************************************     for(it = l1.begin(); it != l1.end(); it++)     {         cout << *it << "  ";     }     puts("");     l1.reverse();//************************************     for(it = l1.begin(); it != l1.end(); it++)     {         cout << *it << "  ";     }     puts("");     l1.sort();//************************************     for(it = l1.begin(); it != l1.end(); it++)     {         cout << *it << "  ";     }     puts("");     l1.unique();//************************************     for(it = l1.begin(); it != l1.end(); it++)     {         cout << *it << "  ";     }     puts("");     return 0; } 

关联容器

set/multiset

set：集合容器

multiset：多重集合容器

元素值就是关键字

优点

1. 默认进行了排序。
2. 可以快速插入，删除，查询（全部是logN）。
3. 支持集合的交，差，并

成员函数

empty()

size()

insert()

erase()查找元素并且删除（返回值为删除了的元素的个数（在multiset中可能大于1））

clear()

count返回关键字出现的次数

find()如果存在，返回迭代器，否则返回end()

upper_bound()第一个大于num的数字

lower_bound()第一个大于或等于num的数字

begin(), end(), rbegin(), rend()

集合的交集，并集，差集

#include <list> #include <iostream> #include <set> #include <algorithm> using namespace std;  list<int>::iterator it; int main() {     set<int> s1({1, 2, 3, 4, 5, 6, 7, 8});     set<int> s2({5, 6, 7, 8, 9, 10});     vector<int> ret;      //一定要设置大小！     ret.resize(max(s1.size(), s2.size()));     vector<int>::iterator tmp = set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), ret.begin());     ret.resize(tmp - ret.begin());     //重新设置大小     for(vector<int>::iterator it = ret.begin(); it != ret.end(); it++)     {         cout << *it << "  ";     }     return 0; } 

set_intersection              //求两个容器的交集  set_union                        //求两个容器的并集  set_difference                //求两个容器的差集 

map/multimap

注意：map/multimap中的元素是以pair<>进行存储的。

map/multimap的区别

map的key不允许重复，可以使用[]

multimap的key允许重复，不可以使用[]

主要的成员函数

empty()

size()

XX[key]

• 如果存在key，那么就可以进行引用以及赋值；
• 但是如果不存在key，那么就会新创建一个key然后插入。

insert(make_pair() 或者 {__, __})

erase()

multimap<int, int> mp;     mp.insert({1, 2});     mp.insert({1, 3});     mp.insert({1, 4});     int ret = mp.erase(1);     cout << ret; 

当然里面也可以是迭代器！

clear()

count()返回指定关键字的数量

find()查找关键字（如果是Multimap,那么就会返回第一个关键字）

tip:利用find和count就可以找到multimap中的所有的key值元素

哈希容器：
unorder_map/multimap、unorder_set/multiset

基本的使用与上面的是相同的

• 但是就是没有排序也不能进行集合的运算。
• 会占用较大的空间
• 访问的速度也将大大提升

适配器容器

概述

一般情况下，

stack：deque（常规），list，vector

queue：deque（常规），list

priority_queue：vector（常规），deque

手动指定：

stack<int, deque<int> >s;//默认 stack<int, list<int> >s; stack<int, vector<int> >s;  queue<int, deque<int> >q;//默认 queue<int, list<int> >q;  priority_queue<int, vector<int> >q;//默认 priority_queue<int, deque<int> >q; 

stack

具有

empty()

size()

push

pop

top

queue

具有

empty()

size()

push

pop

front

back

priority_queue

empty()

size()

push

pop

top

---

关系函数对象

头文件：#include<functional>

greater<>

less<>

相关练习

分隔单词

输入一堆单词，分割单词（没有标点符号）

#include <bits/stdc++.h> using namespace std; void Divide(const string &str, vector<string> &vec) {     int i, j;     i = 0;     j = str.find(" ");     while(j != -1)     {         vec.push_back(str.substr(i, j-i));         i = j+1;         j = str.find(" ", i);     }     if(i < str.length())     {         vec.push_back(str.substr(i));     } } int main() {     char buf[100];     fgets(buf, 100, stdin);     string str = string(buf);     str.erase(str.find("n"));     vector<string> vec;     Divide(str, vec);     for(int i = 0; i < vec.size(); i++)         cout << vec[i] << "n";     return 0; }