set和map的使用

目录

1.关联式容器

2.键值对

3.set

3.1set的模版参数列表

3.2对set的修改

 3.2.1insert

3.2.2 erase

3.2.3clear

3.2.4swap

3.2.5 find

3.3set的迭代器

3.4set的容量

4.map

4.1对map的修改

4.1.1insert

 4.1.2erase

 4.1.3swap

4.1.4clear

4.2map的迭代器

 4.3operator[ ] 

4.4map容量查询 

4.5利用map统计个数的三种方法 

4.5.1方法一

4.5.2方法二

4.5.3方法三

5.multiset和multimap 

---

1.关联式容器

我们之前学的string，vector，deque，list等，其底层都是线性序列的数据结构，统称为序列式容器，里面存储的是元素本身。而set和map的底层是平衡搜索树，平衡搜索树中存储的是<key,val>结构的键值对，通过key才可找寻到存储的val，属于关联式容器。

相比序列式容器，关联式容器在数据检索时速度更快

2.键值对

键值对是一一对应的一种结构，里面存储着两个变量key和val，key代表键值，val表示的是key对应的信息

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)
{}
};

通过阅读pair的源码我们发现，在pair中key被命名为first，val被命名为second。

3.set

set就类似我们之前学到的k型的搜索树，只存储val，但是其底层实际上也是存储着键值对，不过是<val,val>类型。

3.1set的模版参数列表

第一个参数代表着val的类型；compare：set中的元素默认按照小于来比较 ；alloc：set中元素的空间管理方式，采用的STL提供的空间进行管理

3.2对set的修改

 3.2.1insert

set<int> s;
s.insert(5);
pair<set<int>::iterator, bool> p = s.insert(10);
cout << p.second << endl; //输出1（true）
cout << *p.first;//输出iterator指向的10

3.2.2 erase

3.2.3clear

将set中的元素全部清空 

3.2.4swap

将两个set交换，实际上就是交换头节点。

void set_text2()
{set<int> s;s.insert(9);s.insert(8);s.insert(3);s.insert(2);set<int> s1;s1.insert(8);s1.insert(7);s1.insert(5);s1.insert(4);s1.insert(0);s1.swap(s);
}

3.2.5 find

根据要找的val值，如果有则返回其对应的迭代器，如果没有则返回迭代器end();与algorithm中的find的区别是，时间复杂度的区别。因为是二叉搜索树，所以这里的find时间复杂度是O（logN）

3.3set的迭代器

set也支持迭代器遍历和范围for遍历

set<int> s;
s.insert(9);
s.insert(8);
s.insert(3);
s.insert(2);
set<int>::iterator it = s.begin();
while (it != s.end())
{cout << *it << " ";++it;
}
cout << endl;
for (auto& x : s)
{cout << x << " ";
}

值得注意的是，它的遍历都是走的中序遍历，因此排出的是有序的，且能去重。因此set的一个功能就是排列和去重。

3.4set的容量

 值得注意的是，set中不允许修改它的val值，因为这可能会使二叉搜索树被破坏掉。

4.map

map的底层是KV模型，但是其节点是打包成pair键值对来进行存储的，pair中的first成员存储的就是key，pair成员的second存储的就是val值。我们是通过pair中的key来进行排序，查找的

4.1对map的修改

4.1.1insert

如图可以看见insert插入的其实是pair键值对，返回的也是一个pair键值对。如果插入成功那么返回的pair键值对的first存储的是成功插入位置pair的迭代器，second是bool值的1；如果插入失败，那么返回的pair健值对的first存储的是map中已经存储的相同key值的pair的迭代器，second是bool值的0。

map<int, int> m;
m.insert(pair<int, int>(1, 1));
m.insert(make_pair(2, 2));

上述的第一个插入实际上是一个匿名构造了一个pair，但过于复杂。我们通常用第二个make_pair模版函数进行构造,实际效果相同。

 4.1.2erase

 4.1.3swap

交换两个map的数据

4.1.4clear

清空一个map的所有数据

4.2map的迭代器

map支持迭代器就意味着它也支持范围for，迭代器中存储的实际上是pair键值对的指针

map<int, int> m;
m.insert(make_pair(1, 1));
m.insert(make_pair(2, 2));
m.insert(make_pair(3, 3));
m.insert(make_pair(4, 4));
m.insert(make_pair(5, 5));
m.insert(make_pair(8, 8));
m.insert(make_pair(10, 10));
map<int, int>::iterator it = m.begin();
while (it != m.end())
{cout << it->first << " " << it->second << endl;;++it;
}
cout << endl;
for (auto& x : m)
{cout << x.first << " " << x.second << endl;
}
cout << endl;

 4.3operator[ ] 

map中重载了operator[]，如果传入的key值map中存在，则返回val的引用；如果传入的key不存在，则先insert，在返回默认的val。

其底层实现如下

   

operator[]的作用有插入，查找，修改val 

4.4map容量查询 

4.5利用map统计个数的三种方法 

例如一个string数组中存储了许多水果，统计不同水果重复出现的次数

4.5.1方法一

利用find查找判断是否在m内，如果不再则插入，在则++其second值

string s[] = { "苹果","香蕉","苹果","哈密瓜","凤梨","哈密瓜","苹果" };
map<string, int> m;
//方法一，利用find查找判断是否在m内，如果不再则插入，在则++其second值
for (auto& x : s)
{map<string, int>::iterator it = m.find(x);if (it == m.end()){m.insert(make_pair(x, 1));}else{it->second++;}
}

4.5.2方法二

利用insert的返回值进行操作

	string s[] = { "苹果","香蕉","苹果","哈密瓜","凤梨","哈密瓜","苹果" };map<string, int> m;for (auto& x : s){pair<map<string,int>::iterator,bool> p = m.insert(make_pair(x, 1));if (p.second == false){p.first->second++;}}

4.5.3方法三

利用operator[]

string s[] = { "苹果","香蕉","苹果","哈密瓜","凤梨","哈密瓜","苹果" };
map<string, int> m;
for (auto& x : s)
{m[x]++;//如果x在m中，就++其val值；如果x不再m中，先创建一个默认val值的pair，插入，然后++其val
}
for (auto& x : m)
{cout << x.first << " " << x.second << " ";
}

map中的key值是唯一的，不可修改。但是其val值并不是唯一的，且可修改

5.multiset和multimap 

set和map中的key值都是唯一的，而multiset和multimap中的key可以有重复的，但是mulitmap中没有重载operator[]，因为可能有重复的key，那么就不知道该返回哪个val的引用