【C++】set 类 和 map 类

小小小汐- 2024-08-05 11:05:06 阅读 87

1. 关联式容器

关联式容器也是用来存储数据的,与序列式容器不同的是,其里面存储的是<key, value>结构的

键值对,在数据检索时比序列式容器效率更高

2. 键值对

用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量keyvaluekey

表键值,value表示与key对应的信息

代码

<code>template <class T1, class T2>

struct pair

{

typedef T1 first_type;

typedef T2 second_type;

T1 first;

T2 second;

pair(): first(T1()), second(T2())

{}

pair(const T1& a, const T2& b): first(a), second(b)

{}

};

3. 树形结构的关联式容器

根据应用场景的不桶,STL总共实现了两种不同结构的管理式容器:树型结构与哈希结构

树型结构的关联式容器主要有四种:map、set、multimap、multiset

这四种容器的共同点是:使用平衡搜索树(即红黑树)作为其底层结果,容器中的元素是一个有序的序列

4. 标准库里面的 set类 和 map类

set 类的介绍:

set 类的实现底层就是红黑树,该容器可以进行双向迭代,且它是有序的与哈希不同,它 和 map 都是树形结构

a. set 类的使用

set 类的模板参数

    2. set 类的构造

     3.  set 类的修改

函数声明

pair<iterator,bool> insert

( const value_type& x )

功能介绍

set中插入元素x,实际插入的是<x, x>构成的

键值对,如果插入成功,返回<该元素在set中的

位置,true>,如果插入失败,说明xset中已经

存在,返回<x在set中的位置,false>

注意:

返回类型

是一个键值对

iterator代表新插入元素的位置,bool代表释放插入成功

函数声明

void erase ( iterator position )

void erase ( const value_type& x )

功能介绍

删除set中position位置上的元素

删除set中元素 x

函数声明                                                                                   

iterator find                                                                   

( const key_type& x ) const

功能介绍

返回set中值为x的元素的位置

函数声明

void erase

( iterator first, iterator last )

功能介绍

删除set中[ first, last ) 位置上的元素

set 类的容量

函数声明

bool empty ( ) const

功能介绍

检查 set 是否为空

函数声明

size_type size() const

功能介绍

返回set中有效元素的个数

b. map 类的使用

map 的构造

map()map(InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator())

map 的修改

函数声明

pair<iterator,bool> insert

( const value_type& x )

功能介绍

在map中插入键值对x,注意x是一个键值

,返回值也是键值对:iterator代表新插入

元素的位置,bool代表释放插入成功

代码举例

<code>#include<iostream>

using namespace std;

#include<map>

int main()

{

map<int, int> s;

s.insert(make_pair(10, 2)); //make_pair 是模板函数

// s.insert(pair<int,int>(10,2)) 也是对的

auto it = s.begin(); //it 是迭代器

while (it != s.end())

{

cout << it->first << ":" << (*it).second << endl; //*it 是键值对

++it;

}

}

真正写法是 it->->first (省略了一个->,这里用法提过一次,具体看底层实现)

函数声明

size_type erase ( const key_type& x )

void erase ( iterator position )

void erase ( iterator first, iterator last )

功能介绍

删除键值为x的元素

删除position位置上的元素

删除[first, last)区间中的元素

map 的容量和访问

这里明显用了运算符重载了[] , 传的参数是key_vaule 模型里面的 key ,返回得到的是 vaule 本身(既可被访问也可被修改)

代码举例

<code>#include<iostream>

using namespace std;

#include<map>

int main()

{

string arr[] = { "苹果", "香蕉" ,"苹果" ,"梨" ,"葡萄" };

map<string, int> s;

for (auto i : arr)

{

s[i]++;

}

auto it = s.begin();

while (it != s.end())

{

cout << it->first << ":" << it->second << endl;

++it;

}

}

运行结果:

实现原理

不看后置++,单看[] , 实际上里层是调用了 insert 函数 , 返回

这个类型的,再用 .first(iterator 类型) ,返回 它的 ->second (就是 value 了)

c. multiset类 的使用

与 set 类的不同的是:multiset 类 不会去重

d. multimap类 的使用

与 map 类的不同的是:multimap类 不会去重



声明

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