【C++】map和set

核动力C++选手 2024-07-16 15:05:02 阅读 58

目录

关联式容器

树形结构的关联式容器

set

set的使用

map

map的使用

multiset和multimap

multiset

multimap


关联式容器

在以前我们学到的vector/list/deque等容器,它们只是单纯存储数据,存储的数据和数据之间没什么关联,它们都属于序列式容器

这篇学习的map和set,叫做关联式容器,一般还可以用来查找数据,存储的数据和数据之间有很强的关联性,这样设计的目的是在数据检索时效率更高。

树形结构的关联式容器

根据应用场景的不桶,STL总共实现了两种不同结构的管理式容器:树型结构与哈希结构。树型结构的关联式容器主要有四种:map、set、multimap、multiset。这四种容器的共同点是:使用平衡搜索树(即红黑树)作为其底层结果,容器中的元素是一个有序的序列。

set

set的使用

1.set的模板参数列表

T:set存放参数的类型

Compare:set中元素默认按照小于来比较

2.set的构造

函数声明 功能介绍
set(const Compare& comp = Compare(),const Allocator& = Allocator()); 构造空的set
set(InputIterator first,InputIterator last,const Compare& comp = Compare(),const Allocator& = Allocator()); 用[first,last)区间中的元素构造set

3.set的迭代器

函数声明 功能介绍
iterator begin() 返回set中起始位置元素的迭代器
iterator end() 返回set中最后一个元素后面的迭代器

4.set的修改操作

函数声明 功能介绍
void erase(iterator position) 删除set中position位置上的元素
insert(const value_type& x) 在set中插入元素x

5.set的使用示例

<code>void test_set()

{

//排序+去重

set<int> s1;

s1.insert(9);

s1.insert(4);

s1.insert(2);

s1.insert(7);

s1.insert(4);

s1.insert(8);

s1.insert(6);

set<int>::iterator it = s1.begin();

while (it != s1.end())

{

cout << *it << endl;

++it;

}

vector<int> v = { 5,7,6,12,2,3,5,1,7 };

set<int> s2(v.begin(), v.end());

for (auto e : s2)

{

cout << e << " ";

}

cout << endl;

set<int> s3 = { 4,1,9,3,7,5,6 };

for (auto e : s3)

{

cout << e << " ";

}

cout << endl;

s3.erase(9);

for (auto e : s3)

{

cout << e << " ";

}

cout << endl;

auto pos = s3.find(10);

if (pos != s3.end())

{

cout << *pos << endl;

s3.erase(pos);

}

else

{

cout << "找不到" << endl;

}

}

除了set,还有multiset,但是multiset只有搜索和排序的功能,没有去重的功能。

void test_set()

{

//搜索 排序

multiset<int> s1;

s1.insert(9);

s1.insert(4);

s1.insert(1);

s1.insert(7);

s1.insert(4);

s1.insert(8);

s1.insert(6);

s1.insert(4);

s1.insert(1);

s1.insert(7);

s1.insert(4);

s1.insert(8);

multiset<int>::iterator it = s1.begin();

while (it != s1.end())

{

cout << *it << " ";

++it;

}

cout << endl;

}

那么,在multiset中,如果有相同值,find默认查找的是中序第一个,查找x,查找到x的节点后,这个节点的左子树没有x节点,他就是中序第一个x节点。

map

map的使用

1.map是关联式容器,它按照特定的次序(按照key来比较)存储由键值key和value组合而成的元素

2.在map中,键值key通常用于排序和唯一地标识元素,而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同,并且在map的内部,key与value通过成员类型value_type绑定在一起,为其取名为pair(typedef  pair<const key,T>  value_type)。

3.map支持下标访问符,即在[]中放入key,就可以找到与key对应的value。

4.map底层是平衡二叉搜索树(红黑树)。

1.map的模版参数说明

key:键值对中key的类型

T:键值对中value的类型

Comapre:比较器类型,缺省情况下按照小于比较,也可以自己显式传递比较规则

注意:在使用map时,需要包含头文件。

2.map的迭代器

函数声明 功能介绍
begin() 返回map中起始位置元素的迭代器
end() 返回map中最后一个元素后面的迭代器

3.map的容量与元素访问

函数声明 功能
bool empty() const 检测map中元素是否为空
size_type size() const 返回map中有效元素个数
mapped_type& operator[](const key_type& k) 返回key对应的val

问题:如果key不在map中,通过operator[]获取对应value时会发生什么?

我们先来看一下operator[]的文档说明:

operator[]的实现调用了insert函数,那再看一下insert的文档说明:

总结一下insert的返回值说明:

key存在,插入失败,返回->pair<存在的key所在节点的迭代器,false>

key不存在,插入成功,返回->pair<新插入key所在节点的迭代器,true>

了解了insert的返回值之后,我们来翻译一下上面operator[]中的调用:

我们再来结合operator[]的功能来进一步了解:

总结一下,operator[]给一个key,返回key对应value的引用,如果map之前已经有这个key了,那么返回这个key对应value的引用;如果map之前没有这个key,那么这个value相当于一个缺省值。

4.map中元素的修改

函数声明 功能
pair<iterator,bool> insert(const value_type& x) 在map中插入键值对x,注意x是一个键值对,返回值也是键值对,详见上面,不再赘述
void erase(iterator position) 删除position位置上的元素
iterator find(const key_type& x) 在map中插入key为x的元素,找到返回该元素位置的迭代器,否则返回end
size_type count(const key_type& x)const 返回key为x的键值在map中的个数,由于map中key是唯一的,因此该函数的返回值要么为0,要么为1,因此可以检测一个key是否在map中

上面的count函数为什么不返回bool值而返回个数呢?其实这个函数是和multimap结合的,multimap允许多个key为x的元素存在(允许key冗余)。

multiset和multimap

multiset

1.与set的区别是,multiset的元素可以重复,set中的value是唯一的

2.使用迭代器对multiset的元素进行遍历,可以得到有序的序列

3.multiset中的元素不能修改

multimap

1.multimap中的key是可以重复的

2.multimap中的元素默认将key按照小于来比较

3.multimap中没有重载operator[]操作,这是由于multimap中的key可以重复

4.使用时与map包含的头文件相同



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。