01. set/multiset容器
1.1set/multiset简介
- set是一个集合容器,其中所包含的元素是唯一的,集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入,所以不能指定插入位置。
- set采用红黑树变体的数据结构实现,红黑树属于平衡二叉树。在插入操作和删除操作上比vector快。
- set不可以直接存取元素。(不可以使用at.(pos)与[]操作符)。
- multiset与set的区别:set支持唯一键值,每个元素值只能出现一次;而multiset中同一值可以出现多次。
- 不可以直接修改set或multiset容器中的元素值,因为该类容器是自动排序的。如果希望修改一个元素值,必须先删除原有的元素,再插入新的元素。
#include <set>
![]()
1.2set/multiset构造器
set<int> setInt;
//一个存放int的set容器。set<float> setFloat;
//一个存放float的set容器。set<string> setString;
//一个存放string的set容器。multiset<int> mulsetInt;
//一个存放int的multi set容器。multiset<float> multisetFloat;
//一个存放float的multi set容器。multiset<string> multisetString;
//一个存放string的multi set容器。
#include <iostream>
#include <set>
#include <functional>
using namespace std;
int main()
{
set<int> seta; //默认是小于比较强less<int>的set
set<int, greater<int>> setb; //创建一个带大于比较器的set,需要包含头文件functional
int a[5] = { 1,2,3,4,5 };
set<int> setc(a, a + 5); //数组初始化一个set
set<int> setd(setc.begin(), setc.end()); //setc初始化一个set
set<int> sete(setd); //拷贝构造创建set
return 0;
}
1.3set/multiset容器常用操作
s.begin()
//返回set容器的第一个元素s.end()
//返回set容器的最后一个元素s.clear()
//删除set容器中的所有的元素s.empty()
//判断set容器是否为空s.insert()
//插入一个元素s.erase()
//删除一个元素s.size()
//返回当前set容器中的元素个数
1.4案例
1.4.1 insert插入
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> s;
s.insert(1);
s.insert(5);
s.insert(4);
s.insert(2);
cout << "Test 1" << endl;
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << " ";
}
cout << endl;
s.insert(2); //set只允许相同的值出现一次,要插入相同的值用multiset
cout << "Test 2" << endl;
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << " ";
}
cout << endl;
return 0;
}
Test 1
1 2 4 5
Test 2
1 2 4 5
1.4.2 erase和clear删除
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> s;
s.insert(1);
s.insert(5);
s.insert(4);
s.insert(2);
s.insert(3);
s.insert(9);
s.insert(8);
cout << "Test 1" << endl;
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << " ";
}
cout << endl;
s.erase(4); //根据元素删除
cout << "Test 2" << endl;
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << " ";
}
cout << endl;
set<int>::iterator ita = s.begin();
s.erase(ita); //删除迭代器指向位置的元素
cout << "Test 3" << endl;
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << " ";
}
cout << endl;
set<int>::iterator itb = s.begin();
ita = s.begin();
itb++;
s.erase(ita,itb);//删除区间[ita,itb)的元素
cout << "Test 4" << endl;
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << " ";
}
cout << endl;
s.clear(); //删除所有元素
cout << "Test 5" << endl;
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << " ";
}
cout << endl;
return 0;
}
Test 1
1 2 3 4 5 8 9
Test 2
1 2 3 5 8 9
Test 3
2 3 5 8 9
Test 4
3 5 8 9
Test 5
1.4.3 find查找
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> s;
s.insert(1);
s.insert(5);
s.insert(4);
s.insert(2);
if (s.find(2) != s.end())
{
cout << "2 is existent" << endl;
}
else
{
cout << "2 is non-existent" << endl;
}
if (s.find(3) != s.end())
{
cout << "3 is existent" << endl;
}
else
{
cout << "3 is non-existent" << endl;
}
return 0;
}
2 is existent
3 is non-existent
1.4.4 lower_bound()、upper_bound()、equal_range()
s.lower_bound()
返回第一个大于或等于给定关键值的元素s.upper_bound()
返回第一个大于给定关键值的元素s.equal_range()
返回一对定位器,分别表示 第一个大于或等于给定关键值的元素 和 第一个大于给定关键值 的元素,这个返回值是一个pair
类型,如果这一对定位器中哪个返回失败,就会等于 s.end()
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> s;
s.insert(1);
s.insert(5);
s.insert(4);
s.insert(2);
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << " ";
}
cout << endl;
cout << "lower_bound & upper_bound test:" << endl;
cout << "第一个大于或等于3的元素: " << *s.lower_bound(3) << endl;
cout << "第一个大于或等于2的元素: " << *s.lower_bound(2) << endl;
cout << "第一个大于2的元素: " << *s.upper_bound(2) << endl;
cout << "equal_range test:" << endl;
cout << "第一个大于或等于2的元素: " << *s.equal_range(2).first << endl;
cout << "第一个大于2的元素: " << *s.equal_range(2).second << endl;
return 0;
}
1 2 4 5
lower_bound & upper_bound test:
第一个大于或等于3的元素: 4
第一个大于或等于2的元素: 2
第一个大于2的元素: 4
equal_range test:
第一个大于或等于2的元素: 2
第一个大于2的元素: 4
1.4.5判断是否为空
#include <iostream>
#include <set>
#include <functional>
using namespace std;
int main()
{
set<int > s;
if (s.empty()) cout << "容器为空" << endl;
s.insert(1);
if (!s.empty()) cout << "容器不为空" << endl;
if (s.count(1)) cout << "1在容器中" << endl;
if (!s.count(2)) cout << "2不在容器中" << endl;
return 0;
}
容器为空
容器不为空
1在容器中
2不在容器中
1.4.6自定义函数,伪函数
- 尽管函数指针被广泛用于实现函数回调,但C++还提供了一个重要的实现回调函数的方法,那就是函数对象。
functor
,翻译成函数对象,伪函数,算符,是重载了“()”
操作符的普通类对象。从语法上讲,它与普通函数行为类似。greater<>
与less<>
就是函数对象。
#include <iostream>
#include <set>
#include <functional>
using namespace std;
struct cmp
{
bool operator () (const int& a, const int& b) const
{
return a > b;
}
};
set<int, cmp>s; //自定义排序函数构造set
void setprint(int cnt) {
cout << "Test output :" << cnt << ":" << endl;
for (set<int, cmp>::iterator it = s.begin(); it != s.end(); it++)
cout << *it << " ";
puts("");
return;
}
int main() {
s.insert(1);
s.insert(2);
s.insert(6);
setprint(1);
return 0;
}
Test output :
6 2 1
1.5本章小结
- 容器
set/multiset
的使用方法 - 红黑树的变体,查找效率高,插入不能指定位置,插入时自动排序。
functor
的使用方法;- 类似于函数的功能,可用来自定义一些规则,如元素比较规则。
unordered_set
和unordered_multiset
,为set
和multiset
的无序版,使用时要包含头文件#include<unordered_set>
02. map/multimap容器
2.1 map/multimap简介
- map是标准的关联式容器,一个map是一个键值对序列,即(key,value)对。它提供基于key的快速检索能力。
- map中key值是唯一的。集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入,所以不能指定插入位置。
- map的具体实现采用红黑树变体的平衡二叉树的数据结构。在插入操作和删除操作上比vector快。
map
可以直接存取key
所对应的value
,支持[]
操作符,如map[key]=value
。multimap
与map
的区别:map
支持唯一键值,每个键只能出现一次;而multimap
中相同键可以出现多次。multimap
不支持[]
操作符。#include <map>
![]()
2.2 map/multimap构造函数
map/multimap
采用模板类实现,对象的默认构造形式:map<T1,T2> mapTT;
multimap<T1,T2> multimapTT;
- 如:
map<int, char> mapA;
map<string,float> mapB;
- //其中T1,T2还可以用各种指针类型或自定义类型
2.3 map/multimap成员函数
begin()
返回指向map头部的迭代器clear()
删除所有元素count()
返回指定元素出现的次数empty()
如果map为空则返回trueend()
返回指向map末尾的迭代器equal_range()
返回特殊条目的迭代器对erase()
删除一个元素find()
查找一个元素get_allocator()
返回map的配置器insert()
插入元素key_comp()
返回比较元素key的函数lower_bound()
返回键值>=给定元素的第一个位置max_size()
返回可以容纳的最大元素个数rbegin()
返回一个指向map尾部的逆向迭代器rend()
返回一个指向map头部的逆向迭代器size()
返回map中元素的个数swap()
交换两个mapupper_bound()
返回键值>给定元素的第一个位置value_comp()
返回比较元素value的函数
2.4使用案例
2.4.1插入
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
map<int, string> mapStudent;
//使用insert和pair插入
mapStudent.insert(pair<int, string>(1, "student_one"));
cout << "Test one" << endl;
for (map<int, string>::iterator iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
{
cout << iter->first << ":"<< iter->second << " ";
}
cout << endl;
//使用insert函数插入value_type数据
mapStudent.insert(map<int, string>::value_type(2, "student_two"));
cout << "Test two" << endl;
for (map<int, string>::iterator iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
{
cout << iter->first << ":" << iter->second << " ";
}
cout << endl;
//使用数组方式插入
mapStudent[3] = "student_three";
cout << "Test three" << endl;
for (map<int, string>::iterator iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
{
cout << iter->first << ":" << iter->second << " ";
}
cout << endl;
return 0;
}
Test one
1:student_one
Test two
1:student_one 2:student_two
Test three
1:student_one 2:student_two 3:student_three
- 注意:当然了第一种和第二种在效果上是完成一样的,用
insert
函数插入数据,在数据的 插入上涉及到集合的唯一性这个概念,即当map
中有这个关键字时,insert
操作是插入数据不了的,但是用数组方式就不同了,它可以覆盖以前该关键字对应的值。 - 判断是否插入成功
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
map<int, string> mapStudent;
pair<map<int, string>::iterator, bool> Insert_Pair;
Insert_Pair = mapStudent.insert(pair<int, string>(1, "student_one"));
if (Insert_Pair.second == true)
{
cout << "Insert Successfully" << endl;
}
else
{
cout << "Insert Failure" << endl;
}
Insert_Pair = mapStudent.insert(pair<int, string>(1, "student_two"));
if (Insert_Pair.second == true)
{
cout << "Insert Successfully" << endl;
}
else
{
cout << "Insert Failure" << endl;
}
map<int, string>::iterator iter;
for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
{
cout << iter->first << ' ' << iter->second << endl;
}
return 0;
}
Insert Successfully
Insert Failure
1 student_one
2.4.2查找
count
函数来判定关键字是否出现,其缺点是无法定位数据出现位置,由于map
的特性,一对一的映射关系,就决定了count
函数的返回值只有两个,要么是0,要么是1,出现的情况,当然是返回1了。find
函数来定位数据出现位置,它返回的一个迭代器,当数据出现时,它返回数据所在位置的迭代器,如果map
中没有要查找的数据,它返回的迭代器等于end
函数返回的迭代器。
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, "student_one"));
mapStudent.insert(pair<int, string>(2, "student_two"));
mapStudent.insert(pair<int, string>(3, "student_three"));
map<int, string>::iterator iter;
iter = mapStudent.find(1);
if (iter != mapStudent.end())
{
cout << "Find, the value is " << iter->second << endl;
}
else
{
cout << "Do not Find" << endl;
}
return 0;
}
Find, the value is student_one
lower_bound、upper_bound、equal_range
函数用法Equal_range
函数返回一个pair
,pair
里面第一个变量是Lower_bound
返回的迭代器,pair
里面第二个迭代器是Upper_bound
返回的迭代器,如果这两个迭代器相等的话,则说明map
中不出现这个关键字
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
map<int, string> mapStudent;
mapStudent[1] = "student_one";
mapStudent[3] = "student_three";
mapStudent[5] = "student_five";
map<int, string>::iterator iter;
iter = mapStudent.lower_bound(1);
//返回的是下界1的迭代器
cout << iter->second << endl;
iter = mapStudent.lower_bound(2);
//返回的是下界3的迭代器
cout << iter->second << endl;
iter = mapStudent.lower_bound(3);
//返回的是下界3的迭代器
cout << iter->second << endl;
iter = mapStudent.upper_bound(2);
//返回的是上界3的迭代器
cout << iter->second << endl;
iter = mapStudent.upper_bound(3);
//返回的是上界5的迭代器
cout << iter->second << endl;
pair<map<int, string>::iterator, map<int, string>::iterator> mappair;
mappair = mapStudent.equal_range(2);
if (mappair.first == mappair.second)
{
cout << "Do not Find" << endl;
}
else
{
cout << "Find" << endl;
}
mappair = mapStudent.equal_range(3);
if (mappair.first == mappair.second)
{
cout << "Do not Find" << endl;
}
else
{
cout << "Find" << endl;
}
return 0;
}
student_one
student_three
student_three
student_three
student_five
Do not Find
Find
2.4.3删除元素
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
map<int, string> mapStudent;
mapStudent.insert(pair<int, string>(1, "student_one"));
mapStudent.insert(pair<int, string>(2, "student_two"));
mapStudent.insert(pair<int, string>(3, "student_three"));
mapStudent.insert(pair<int, string>(4, "student_four"));
cout << "Test one" << endl;
for (map<int, string>::iterator iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
{
cout << iter->first << ":" << iter->second << " ";
}
cout << endl;
//如果要删除1,用迭代器删除
map<int, string>::iterator iter;
iter = mapStudent.find(1);
mapStudent.erase(iter);
cout << "Test two" << endl;
for (map<int, string>::iterator iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
{
cout << iter->first << ":" << iter->second << " ";
}
cout << endl;
//如果要删除1,用关键字删除
int n = mapStudent.erase(2);//如果删除了会返回1,否则返回0
cout << "Test three" << endl;
for (map<int, string>::iterator iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
{
cout << iter->first << ":" << iter->second << " ";
}
cout << endl;
//用迭代器,成片的删除
//一下代码把整个map清空
mapStudent.erase(mapStudent.begin(), mapStudent.end());
cout << "Test four" << endl;
for (map<int, string>::iterator iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
{
cout << iter->first << ":" << iter->second << " ";
}
cout << endl;
//成片删除要注意的是,也是STL的特性,删除区间是一个前闭后开的集合
return 0;
}
Test one
1:student_one 2:student_two 3:student_three 4:student_four
Test two
2:student_two 3:student_three 4:student_four
Test three
3:student_three 4:student_four
Test four
2.4.4仿函数的应用
#include <iostream>
#include <map>
#include <string>
using namespace std;
typedef struct tagStudentinfo
{
int niD;
string strName;
}Studentinfo, * PStudentinfo; //学生信息
class sort
{
public:
bool operator() (Studentinfo const& _A, Studentinfo const& _B) const
{
if (_A.niD > _B.niD)
return true;
if (_A.niD == _B.niD)
return _A.strName.compare(_B.strName) < 0;
return false;
}
};
int main()
{ //用学生信息映射分数
map<Studentinfo, int, sort>mapStudent;
map<Studentinfo, int>::iterator iter;
Studentinfo studentinfo;
studentinfo.niD = 1;
studentinfo.strName = "student_one";
mapStudent.insert(pair<Studentinfo, int>(studentinfo, 90));
studentinfo.niD = 2;
studentinfo.strName = "student_two";
mapStudent.insert(pair<Studentinfo, int>(studentinfo, 80));
studentinfo.niD = 3;
studentinfo.strName = "student_three";
mapStudent.insert(pair<Studentinfo, int>(studentinfo, 70));
for (iter = mapStudent.begin(); iter != mapStudent.end(); iter++)
{
cout << iter->first.niD << ":" << iter->first.strName << ":" << iter->second << endl;;
}
}
3:student_three:70
2:student_two:80
1:student_one:90
2.5本章小结
- 容器
map/multimap
的使用方法 - 红黑树的变体,查找效率高,插入不能指定位置,插入时自动排序。
functor
的使用方法;- 类似于函数的功能,可用来自定义一些规则,如元素比较规则。
unordered_map
和unordered_multimap
,为map
和multimap
的无序版,使用时要包含头文件#include<unordered_map>
评论已关闭