前言

有了前面搜索二叉树的基础，那么这篇博客对于map和set两个容器就很好理解使用，让我们来看看map和set到底有什么特性吧

💓 个人主页：小张同学zkf

⏩ 文章专栏：C++

若有问题 评论区见📝

🎉欢迎大家点赞👍收藏⭐文章

目录

1.序列式容器和关联式容器 

2.set系列的使用

2.1set和multiset参考文档

2.2set类的介绍

2.3set的构造和迭代器

2.4set的增删查

 2.5multiset和set的差异

3.map系列的使用

3.1map和multimap参考文档

3.2map类的介绍

3.3pair类型介绍

3.4map的构造

3.5map的增删查

3.6map的数据修改

3.7multimap和map的差异

---

1.序列式容器和关联式容器 

---

2.2set类的介绍

template < class T , // set::key_type/value_type

class Compare = less<T>, // set::key_compare/value_compare

class Alloc = allocator<T> // set::allocator_type

> class set;

---

2.3set的构造和迭代器

// empty (1) ⽆参默认构造

explicit set ( const key_compare& comp = key_compare(),

const allocator_type& alloc = allocator_type());

// range (2) 迭代器区间构造

template < class InputIterator >

set (InputIterator first, InputIterator last,

const key_compare& comp = key_compare (),

const allocator_type& = allocator_type ());

// copy (3) 拷⻉构造

set ( const set& x);

// initializer list (5) initializer 列表构造

set (initializer_list<value_type> il,

const key_compare& comp = key_compare (),

const allocator_type& alloc = allocator_type ());

// 迭代器是⼀个双向迭代器

iterator -> a bidirectional iterator to const value_type

// 正向迭代器

iterator begin ();

iterator end ();

// 反向迭代器

reverse_iterator rbegin ();

reverse_iterator rend ();

---

2.4set的增删查

Member types

key_type -> The first template parameter (T)

value_type -> The first template parameter (T)

// 单个数据插⼊，如果已经存在则插⼊失败

pair<iterator, bool > insert ( const value_type& val);

// 列表插⼊，已经在容器中存在的值不会插⼊

void insert (initializer_list<value_type> il);

// 迭代器区间插⼊，已经在容器中存在的值不会插⼊

template < class InputIterator >

void insert (InputIterator first, InputIterator last);

// 查找 val ，返回 val 所在的迭代器，没有找到返回 end()

iterator find ( const value_type& val);

// 查找 val ，返回 Val 的个数

size_type count ( const value_type& val) const ;

// 删除⼀个迭代器位置的值

iterator erase (const_iterator position);

// 删除 val ， val 不存在返回 0 ，存在返回 1

size_type erase ( const value_type& val);

// 删除⼀段迭代器区间的值

iterator erase (const_iterator first, const_iterator last);

// 返回⼤于等 val 位置的迭代器

iterator lower_bound ( const value_type& val) const ;

// 返回⼤于 val 位置的迭代器

iterator upper_bound ( const value_type& val) const ;

---

 2.5multiset和set的差异

# include <iostream>

# include <set>

using namespace std;

int main ()

{

// 相⽐ set 不同的是， multiset 是排序，但是不去重

multiset< int > s = { 4 , 2 , 7 , 2 , 4 , 8 , 4 , 5 , 4 , 9 };

auto it = s. begin ();

while (it != s. end ())

{

cout << *it << " " ;

++it;

}

cout << endl;

// 相⽐ set 不同的是， x 可能会存在多个， find 查找中序的第⼀个

int x;

cin >> x;

auto pos = s. find (x);

while (pos != s. end () && *pos == x)

{

cout << *pos << " " ;

++pos;

}

cout << endl;

// 相⽐ set 不同的是， count 会返回 x 的实际个数

cout << s. count (x) << endl;

// 相⽐ set 不同的是， erase 给值时会删除所有的 x

s. erase (x);

for ( auto e : s)

{

cout << e << " " ;

}

cout << endl;

return 0 ;

}

---

3.map系列的使用

3.1map和multimap参考文档

链接：https://legacy.cplusplus.com/reference/map/ 

---

3.2map类的介绍

template < class Key , // map::key_type

class T , // map::mapped_type

class Compare = less<Key>, // map::key_compare

class Alloc = allocator<pair< const Key,T> > //

map::allocator_type

> class map;

---

3.3pair类型介绍

map底层的红⿊树节点中的数据，使⽤pair<Key, T>存储键值对数据。

typedef pair< const Key, T> value_type;

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)

{}

template < class U, class V>

pair ( const pair<U,V>& pr): first(pr.first), second(pr.second)

{}

};

template < class T1 , class T2 >

inline pair<T1,T2> make_pair (T1 x, T2 y)

{

return ( pair <T1,T2>(x,y) );

}

---

3.4map的构造

// empty (1) ⽆参默认构造

explicit map ( const key_compare& comp = key_compare(),

const allocator_type& alloc = allocator_type());

// range (2) 迭代器区间构造

template < class InputIterator >

map (InputIterator first, InputIterator last,

const key_compare& comp = key_compare (),

const allocator_type& = allocator_type ());

// copy (3) 拷⻉构造

map ( const map& x);

// initializer list (5) initializer 列表构造

map (initializer_list<value_type> il,

const key_compare& comp = key_compare (),

const allocator_type& alloc = allocator_type ());

// 迭代器是⼀个双向迭代器

iterator -> a bidirectional iterator to const value_type

// 正向迭代器

iterator begin ();

iterator end ();

// 反向迭代器

reverse_iterator rbegin ();

reverse_iterator rend ();

---

3.5map的增删查

Member types

key_type -> The first template parameter (Key)

mapped_type -> The second template parameter (T)

value_type -> pair < const key_type,mapped_type>

// 单个数据插⼊，如果已经 key 存在则插⼊失败 ,key 存在相等 value 不相等也会插⼊失败

pair<iterator, bool > insert ( const value_type& val);

// 列表插⼊，已经在容器中存在的值不会插⼊

void insert (initializer_list<value_type> il);

// 迭代器区间插⼊，已经在容器中存在的值不会插⼊

template < class InputIterator >

void insert (InputIterator first, InputIterator last);

// 查找 k ，返回 k 所在的迭代器，没有找到返回 end()

iterator find ( const key_type& k);

// 查找 k ，返回 k 的个数

size_type count ( const key_type& k) const ;

// 删除⼀个迭代器位置的值

iterator erase (const_iterator position);

// 删除 k ， k 存在返回 0 ，存在返回 1

size_type erase ( const key_type& k);

// 删除⼀段迭代器区间的值

iterator erase (const_iterator first, const_iterator last);

// 返回⼤于等 k 位置的迭代器

iterator lower_bound ( const key_type& k);

// 返回⼤于 k 位置的迭代器

const_iterator lower_bound ( const key_type& k) const ;

---

3.6map的数据修改

Member types

key_type -> The first template parameter (Key)

mapped_type -> The second template parameter (T)

value_type -> pair < const key_type,mapped_type>

// 查找 k ，返回 k 所在的迭代器，没有找到返回 end() ，如果找到了通过 iterator 可以修改 key 对应的

mapped_type 值

iterator find ( const key_type& k);

// ⽂档中对 insert 返回值的说明

// The single element versions (1) return a pair , with its member pair::first

set to an iterator pointing to either the newly inserted element or to the

element with an equivalent key in the map . The pair::second element in the pair

is set to true if a new element was inserted or false if an equivalent key

already existed.

// insert 插⼊⼀个 pair<key, T> 对象

// 1 、如果 key 已经在 map 中，插⼊失败，则返回⼀个 pair<iterator,bool> 对象，返回 pair 对象

first 是 key 所在结点的迭代器， second 是 false

// 2 、如果 key 不在在 map 中，插⼊成功，则返回⼀个 pair<iterator,bool> 对象，返回 pair 对象

first 是新插⼊ key 所在结点的迭代器， second 是 true

// 也就是说⽆论插⼊成功还是失败，返回 pair<iterator,bool> 对象的 first 都会指向 key 所在的迭

代器

// 那么也就意味着 insert 插⼊失败时充当了查找的功能，正是因为这⼀点， insert 可以⽤来实现

operator[]

// 需要注意的是这⾥有两个 pair ，不要混淆了，⼀个是 map 底层红⿊树节点中存的 pair<key, T> ，另

⼀个是 insert 返回值 pair<iterator,bool>

pair<iterator, bool > insert ( const value_type& val);

mapped_type& operator [] ( const key_type& k);

// operator 的内部实现

mapped_type& operator [] ( const key_type& k)

{

// 1 、如果 k 不在 map 中， insert 会插⼊ k 和 mapped_type 默认值，同时 [] 返回结点中存储

mapped_type 值的引⽤，那么我们可以通过引⽤修改返映射值。所以 [] 具备了插⼊ + 修改功能

// 2 、如果 k 在 map 中， insert 会插⼊失败，但是 insert 返回 pair 对象的 first 是指向 key 结点的

迭代器，返回值同时 [] 返回结点中存储 mapped_type 值的引⽤，所以 [] 具备了查找 + 修改的功能

pair<iterator, bool > ret = insert ({ k, mapped_type () });

iterator it = ret.first;

return it->second;

}

---

3.7multimap和map的差异