STL容器的使用与练习（上）

OVERVIEW

• STL容器的使用与练习（上）
• • • string类
    • 1.vector动态数组：
    • • （1）vector动态一维数组：
      • （2）vector动态二维数组：
    • 2.deque双端队列：
    • 3.stack栈：
    • 4.queue队列：
    • • （1）队列的基本使用：
      • （2）队列自定义类型：
    • 5.priority_queue优先队列
    • • （1）大顶堆：
      • （2）小顶堆：
      • （3）队列自定义类型：运算符重载
      • （4）队列自定义类型：仿函数
    • 6.set集合：
    • • （1）set的基本使用：
      • （2）set自定义类型：
    • 7.map键值对：
    • • （1）map的基本使用：
      • （2）unordered_map:

STL六大组件：

1. 容器
2. 适配器
3. 空间分配器：malloc
4. 迭代器：高级指针
5. 算法库：sort
6. 仿函数：一个类重载一个括号

string类

注意：find()返回值为第一个目标出现的下标值，若没有找到将返回string::npos(-1)

#include 
#include 
using namespace std;int main(){string str = "ABCDEF";//1.输出字符串长度cout << str.size() << endl;//2.查找字符串DE的位置cout << str.find("DE") << endl;//3.输出没有查找到的结果cout << (int)str.find("DE", 5) << endl;//4.字符串截取cout << str.substr(3, 2) << endl;//5.字符串插入str.insert(1, "abc");cout << str << endl;//6.字符串替换str.replace(2, 5, "000");cout << str << endl;//7.一次性读入一行包含空格的字符串string str1;getline(cin, str1);cout << str1 << endl;return 0;
}

1.vector动态数组：

（1）vector动态一维数组：

#include
#include
using namespace std;int main(){//初始化一个10个元素都为88的一维数组vector v(10, 88);v.push_back(99);v.push_back(8);v.push_back(56);for(int i = 0; i < v.size(); ++i){cout << v[i] << "\n";}return 0;
}

（2）vector动态二维数组：

#include
#include
#include
using namespace std;int main(){//初始化一位10*10元素都为9的二维数组vector > v(10, vector(10, 9));//(1)外层循环次数:v.sizefor(int i = 0; i < v.size(); ++i){//(2)内层循环次数:v[i].sizefor(int j = 0; j < v[i].size(); ++j){cout << v[i][j] << " ";}cout << endl;}return 0;
}

2.deque双端队列：

#include
#include
using namespace std;int main(){deque que;que.push_back(3);que.push_back(4);que.push_back(5);que.push_front(6);que.push_front(7);while(!que.empty()){cout << que.front() << " " << que.back() << endl;que.pop_back();}return 0;
}

3.stack栈：

#include
#include
using namespace std;int main(){stack sta;sta.push("1234567890");sta.push("abc");sta.push("909090");sta.push("T");cout << sta.size() << endl;cout << sta.top() << endl;while(!sta.empty()){cout << sta.top() << endl;sta.pop();}return 0;
}

stack栈本质上不是容器属于适配器，是由双端队列进行二次封装得到

4.queue队列：

（1）队列的基本使用：

#include
#include
using namespace std;int main(){queue que;que.push(6);que.push(7);que.push(1);cout << que.size() << endl;while(!que.empty()){cout << que.front() << " " << que.back() << endl;que.pop();}return 0;
}

queue队列本质上不是容器属于适配器，大部分情况下是由双端队列进行二次封装得到

（2）队列自定义类型：

#include
#include
using namespace std;struct node{int num, cnt;
};int main(){queue que;que.push((node){5, 6});que.push((node){1, 10});que.push((node){6, -1});cout << que.size() << endl;while(!que.empty()){cout << que.front().num << " " << que.front().cnt << endl;que.pop();}return 0;
}

5.priority_queue优先队列

priority_queue底层实现为堆，且建立后默认为大顶堆

（1）大顶堆：

#include
#include
using namespace std;int main(){priority_queue que;que.push(5);que.push(9);que.push(-1);que.push(999);que.push(72);cout << que.size() << endl;while(!que.empty()){cout << que.top() << endl;que.pop();}return 0;
}

（2）小顶堆：

#include
#include
using namespace std;int main(){/*priority_queue, greater > que;priority_queue<类型（装的是什么）, 容器（用什么装）, 比较规则（greater） > que;*/priority_queue, greater > que;que.push(5);que.push(9);que.push(-1);que.push(999);que.push(72);cout << que.size() << endl;while(!que.empty()){cout << que.top() << endl;que.pop();}return 0;
}

（3）队列自定义类型：运算符重载

#include
#include
using namespace std;/*容器存储自定义类型必须重载小于号：bool operator< (const node &b)const{return this->num < b.num;    } 
*/struct node{int num, cnt;bool operator< (const node &b)const{return this->num < b.num;    }
};int main(){priority_queue que;que.push((node){1, 2});que.push((node){4, -2});que.push((node){3, -9});cout << que.size() << endl;while(!que.empty()){cout << que.top().num << " " << que.top().cnt << endl;que.pop();}return 0;
}

总结：自定义类型自定义输出顺序规则为按照第一个数字从大到小输出

（4）队列自定义类型：仿函数

#include
#include
using namespace std;struct node{int num, cnt;
};/*
自定义仿函数：
struct func{bool operator() (const node &a, const node &b){return a.num < b.num;    }
};
*/struct func{bool operator() (const node &a, const node &b){return a.num < b.num;    }
};int main(){priority_queue, func> que;que.push((node){1, 2});que.push((node){4, -2});que.push((node){3, -9});cout << que.size() << endl;while(!que.empty()){cout << que.top().num << " " << que.top().cnt << endl;que.pop();}return 0;
}

6.set集合：

set集合特点：

1. 无重复元素
2. 元素是有序的
3. 插入、查找、删除操作的时间复杂度为log(N)

（1）set的基本使用：

#include
#include
using namespace std;int main(){set s;s.insert(7);s.insert(5);s.insert(99);s.insert(128);s.insert(-1);cout << s.size() << endl;if(s.count(128) == 1){cout << "YES" << endl;}else{cout << "NO" << endl;}s.erase(128);if(s.count(128) == 1){cout << "YES" << endl;}else{cout << "NO" << endl;}//迭代器遍历set集合中的元素for(auto it = s.begin(); it != s.end(); it++){cout << *it << endl; }return 0;
}

（2）set自定义类型：

#include
#include
using namespace std;struct node{int num,cnt;bool operator< (const node &b)const {return this->num < b.num;}
};int main(){set s;s.insert((node){8, 9});s.insert((node){-99, 128});s.insert((node){2, 73});for(auto it = s.begin(); it != s.end(); it++){cout << it->num << " " << it->cnt << endl;}return 0;
}

7.map键值对：

除了map中存储的为键值对，其他与set集合基本一致

（1）map的基本使用：

#include
#include

注意：在使用[]查询键值对时，若键值对不存在将自动创建，int类型将初始化值为0

（2）unordered_map:

#include
#include
#include
using namespace std;int main(){unordered_map m;m["1234567890"] = 67890;m["abcdefg"] = 12345;m["(+_+)"] = 666666;cout << m.size() << endl;for(auto it = m.begin(); it != m.end(); it++){cout << it->first << " " << it->second << endl;}return 0;
}

注：对于无序map/set其内部的结构是一个哈希表（利用哈希查找函数），

• 所以如果在unordered_map/set中使用自定义类型，就必须要自己手写哈希函数。
• 在容器选择时，如果需要容器有序时才使用map/set，若无序有序则使用unordered_map/set以尽可能提升运行速度。

unordered_set

unordered_map

unordered_multiset

unordered_multimap