set/multiset容器
set/multiset容器是以红黑树（平衡二叉树的一种）为底层实现机制，set不允许元素重复，multiset允许元素重复，树查找效率高
二叉树，二叉搜索树，平衡二叉树，
list不能支持随机访问
list采用动态分配，不会造成内存浪费和溢出
list执行插入操作十分方便，修改指针即可，不需要移动大量元素
list灵活，但是空间和时间额外耗费较大
链表和数组区别
1、数组必须事先定义固定长度（元素个数），不能适应数据动态的增减情况，当数据增加时，可能***原先定义的元素个数，当数据减少时，造成内存浪费
2、链表动态进行存储分配，可以适应动态的增减情况，且可以方便的插入，删除数据元素
set/multiset容器
1、set构造函数
set<T> st;//set默认构造函数；
multiset<T> mst;//multiset默认构造函数
set(const set &st);//拷贝构造
2、set赋值操作
set& opertator=(const set &st);//重载等号操作
swap(st);交换两个集合容器
3、set大小操作
size();
empty();
4、set插入和删除
insert(elem);//
clear();
erase(pos);删除pos迭代器所指的元素，返回下一个元素的迭代器
erase(beg,end);删除区间[beg,end)的所有元素，返回下一个元素的迭代器
erase(elem);删除容器中值为elem的元素
5、set查找操作
find(key);//查找键key是否存在，若存在，返回该键的元素的迭代器，若不存在，返回map.end();
lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器
upper_bound(keyElem)//返回第一个key>=keyElem元素的迭代器
equal_range(keyElem);//返回容器中key与keyElem相等的山下限的两个迭代器
6、pair的用法
7、multiset使用方法和set类似，只是可以有重复的元素而已
#include<iostream>
#include<set>
#include<functional> //预定义函数对象
using namespace std;
//init
void test01(){
set<int> myset;
set<int> myset2(myset);//capy构造
}
//使用迭代器
void printSet(set<int> myset){
for (set<int>::iterator it = myset.begin(); it != myset.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
//插入和删除
void test02(){
set<int> myset;//默认从小到大排序
myset.insert(4);
myset.insert(2);
myset.insert(3);
printSet(myset);
myset.erase(myset.begin());
myset.erase(2);
printSet(myset);
myset.erase(myset.begin(), myset.end());
cout << "size:" << myset.size() << endl;
}
//set容器查找
template<class T>
class mycompare03{
public:
bool operator()(int v1,int v2) const{
if (v1 > v2){
cout << v1 << endl;
return v2 > v1;
}
}
};
void test03(){
//set<int> myset//默认从小到大排序
//mycompare03 mycom;
//mycom(10);//函数对象，仿函数，可以当函数用
set<int, mycompare03<int>> myset;
myset.insert(4);
myset.insert(2);
myset.insert(3);
myset.insert(9);
/*set<int>::iterator pos=myset.find(20);//返回值为2的元素所在的位置
if (pos == myset.end()){
cout << "没有查找到" << endl;
}
else
{
cout << *pos << endl;
}*/
}
class Teacher{
public:
Teacher(int id, int age) :id(id), age(age){}
int id;
int age;
};
//排序方法
class mycompare04{
public:
bool operator()(Teacher t1, Teacher t2){
return t1.id > t2.id;
}
};
void test04(){
set<Teacher, mycompare04> myset;
Teacher t1(1, 2), t2(3, 4), t3(5, 6);
myset.insert(t1);
myset.insert(t2);
myset.insert(t3);
for (set<Teacher, mycompare04>::iterator it = myset.begin(); it != myset.end(); it++)
{
cout << it->age << it->id << endl;
}
cout << endl;
//查找
set<Teacher, mycompare04>::iterator pos = myset.find(t2);
if (pos == myset.end()){
cout << "没有查找到" << endl;
}
else
{
cout << "查找到" << pos->age << pos->id << endl;
}
//按照值查找，pos前面已经定义
pos = myset.find(Teacher(3, 4));
if (pos == myset.end()){
cout << "没有查找到" << endl;
}
else
{
cout << "查找到" << pos->age<<":" << pos->id << endl;
}
}
void test05()
{
set<int> myset;
myset.insert(4);
myset.insert(2);
myset.insert(3);
myset.insert(9);
set<int>::iterator pos=myset.lower_bound(9);//返回大于等于5迭代器
if (pos == myset.end()){
cout << "没有查找到" << endl;
}
else
{
cout << "lower_bound" << *pos << endl;
}
pos = myset.upper_bound(3);
if (pos == myset.end()){
cout << "没有查找到" << endl;
}
else
{
cout << "upper_bound" << *pos << endl;
}
pair<set<int>::iterator, set<int>::iterator> pos2 = myset.equal_range(3);
if (pos2.first== myset.end()){
cout << "no find" << endl;
}
else
{
cout << "find" << *(pos2.first) << endl;
}
if (pos2.second == myset.end()){
cout << "no find" << endl;
}
else
{
cout << "find" << *(pos2.second) << endl;
}
}
int main()
{
//test02();
//test04();
test05();
return EXIT_SUCCESS;
}
滴滴一面70人在聊
