【C++】set与map

一、预备知识：

1、关联式容器：

2、键值对：

3、树形结构的关联式容器：

二、set：

1、set的介绍：

2、使用：

1、set的构造：

2、set的各种功能：

3、multiset

三、map：

1、map的介绍：

2、使用：

1、map的构造：

2、map的各种功能：

3、map的operator[ ]

3、multimap:

一、预备知识：

1、关联式容器：

在以前阶段，已经接触过STL中的部分容器，比如：vector、list、deque等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。

那什么是关联式容器？它与序列式容器有什么区别？

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，<key,value> 结构就是根据键值key以某种特定的方式来存放的，而value则是通过寻找key所在的位置，就可以找到value了。

比如在下面中，就是一个<key, value>结构，可以通过中文（key）来找到每一个对应的英文（value），也可以说这些value是通过每个对应的key找到的。

2、键值对：

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。

如上所示：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。

在标准库中提供了类似下面pair这种结构体来进行操作：

pair作用是将两个普通元素first和second（可以是 C++ 基本数据类型、结构体、类自定的类型）创建成一个新元素<first, second>。

#include<iostream>
using namespace std;
namespace ppr
{//SGI 版 STL 中的实现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){}};
}
int main()
{pair<string, int> p1("hehe", 888);ppr::pair<int, string> p2(999, "hehe");cout << "p1:" << p1.first << " " << p1.second << endl;cout << "p2:" << p2.first << " " << p2.second << endl;return 0;
}

pair中的first表示键值，second则表示实值，在给关联式容器中插入数据时，可以构建pair对象，毕竟存在模版参数，所以自己来控制pair的两个类型，就可以通过first来找到second。

比如上面就构建了一个键值key为string，实值value为int的键值对p1和键值key为int，实值value为string的键值对p2，其中pair中的first是key，second是value。

除了以上这种方法，在库中设了一个函数模版make_pair，可以自主传参，从而去构建对象

make_pair在库中的实现如下：

template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
{return ( pair<T1,T2>(x,y) );
}

编译器会将这个函数转化成内联函数，这样话就节省了很多时间，但也不会造成过多的空间消耗。

3、树形结构的关联式容器：

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

树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。

C++ 11 还新增了4种哈希容器：unordered_map，unordered_multimap，unordered_set，unordered_multiset。但是哈希容器底层采用的是哈希表，而不是红黑树。

不同的是哈希结构的关联式容器比给予树形结构的关联式容器，提高添加和删除元素的速度以及提高查找算法的效率。

二、set：

1、set的介绍：

set是按照一定次序存储元素的容器，它是key结构的，只包含一个键值，如上的官方文档中，T就是set的键值类型，Compare是根据后面参数判断是升序还是降序，Alloc是空间配置器。

理解：

set中的元素不可以重复(因此可以使用set进行去重)，使用set的迭代器遍历set中的元素，可以得到有序序列。

2、使用：

1、set的构造：

int main()
{set<int> s1;cout << "构造空的set：s1" << endl;set<int>::iterator it1 = s1.begin();while (it1 != s1.end()){cout << *it1 << " ";it1++;}cout << endl;int arr[] = { 5,2,2,1,5,6,3,2,7,8 };set<int> s2(arr, arr + sizeof(arr)/sizeof(arr[0]));cout << "用区间元素构造set：s2" << endl;set<int>::iterator it2 = s2.begin();while (it2 != s2.end()){cout << *it2 << " ";it2++;}cout << endl;cout << "set的拷贝构造：s3" << endl;set<int> s3(s2);set<int>::iterator it3 = s3.begin();while (it3 != s3.end()){cout << *it3 << " ";it3++;}cout << endl;return 0;
}

通过以上代码可以看到，set构造后通过迭代器遍历会去重和排序，去重实质上是如果在set中存在就不会insert进去。

2、set的各种功能：

功能样例：

int main()
{vector<int> arr1 = { 1,2,3,4,6,7,8,9,0 };set<int> s1(arr1.begin(), arr1.end());cout << "迭代器遍历容器" << endl;set<int>::iterator it1 = s1.begin();while (it1 != s1.end()){cout << *it1 << " ";it1++;}cout << endl;cout << "insert 元素:" << endl;s1.insert(99);s1.insert(5);s1.insert(-1);for (const auto& e : s1)cout << e << " ";cout << endl;cout << "erase 元素:" << endl;s1.erase(5);s1.erase(7);s1.erase(-1);for (const auto& e : s1)cout << e << " ";cout << endl;vector<int> arr2 = { 11, 22, 88, 33, 55, 44, 99 };set<int> s2(arr2.begin(), arr2.end());cout << "s2遍历:" << endl;for (const auto& e : s2)cout << e << " ";cout << endl;cout << "s1 和 s2交换后:" << endl;s1.swap(s2);cout << "s1:" << endl;for (const auto& e : s1)cout << e << " ";cout << endl;cout << "s2:" << endl;for (const auto& e : s2)cout << e << " ";cout << endl;cout << "s1.find(44): " << endl;cout << (s1.find(44) != s1.end()) << endl;set<int> s3(s1.find(44), s1.end());//找到后返回当前位置的迭代器cout << "s3:" << endl;for (const auto& e : s3)cout << e << " ";cout << endl;cout << "s1.find(4): " ;cout << (s1.find(4) != s1.end()) << endl;cout << "s1的size:"  << s1.size() << endl;cout << "s2的size:"  << s2.size() << endl;cout << "s3的size:" << s3.size() << endl << endl;//count是计算容器中指定元素的个数的，但是set的元素不能有多个，所以count也就只能统计在不在vector<int> arr = {1,3,5,6,7,8,0};set<int> s5(arr.begin(), arr.end());for (int i  = 0;i<10;i++){if (s5.count(i))cout << i << " 在 s5 中" << endl;elsecout << i << " 不在 s5 中" << endl;}return 0;
}

在set中，默认是升序的，但是可以改变第二个模版参数Compare来进行控制升降序

int main()
{vector<int> arr3 = { 11,22,33,44,55,66,77,88,99,100 };set<int> s6(arr3.begin(), arr3.end());set<int, greater<int>> s7(arr3.begin(), arr3.end());cout << "s6:";for (const auto& e : s6)cout << e << " ";cout << endl;cout << "s7:";for (const auto& e : s7)cout << e << " ";cout << endl;return 0;
}

3、multiset

multiset 与 set 的区别：set支持唯一键值，每个元素值只能出现一次；而 multiset 中同一值可以出现多次。

其余操作基本是相同的。

vector<int> arr = { 1,2,2,2,2,3,3,3,4,5,6,7,8,9,9 };
multiset<int> ms(arr.begin(), arr.end());
for (auto e : ms)cout << e << " ";
cout << endl;

注意：

在查找后返回的是第一个的迭代器，并且count计数也在这用。

int main()
{vector<int> arr = { 1,2,2,2,2,3,3,3,4,5,6,7,8,9,9 };multiset<int> ms(arr.begin(), arr.end());for (auto e : ms)cout << e << " ";cout << endl;cout << "查找3，返回的是第一个出现的3的迭代器" << endl;multiset<int>::iterator it = ms.find(3);while (it != ms.end()){cout << *it << " ";it++;}cout << endl;cout << "count在这也很好用" << endl;cout << "计数2 : " << ms.count(2) << endl;cout << "计数3 : " << ms.count(3) << endl;return 0;
}

三、map：

1、map的介绍：

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

2、在map中，键值key通常用于排序惟一的标识元素，而值value中存储与此键值key关联的内容。

3、键值key和值value的类型可以不同，并且在map的内部，key与value通过成员类型 value_type绑定在一起，为其取别名称为pair。

比如：

在英汉对应的词典中就用到了这种KV模型

如上所示文档中，Key就是键值对中的键值，T则是键值对中的实值，在 map 中会用到前面提到过的pair结构，其中 first 表示键值，second 表示实值。

在访问map中的键值和实值时，需要通过pair对象指定访问，比如m.first

2、使用：

1、map的构造：

int main()
{map<int, int> m1;vector<pair<int, string>> arr = { make_pair(1,"one"),make_pair(2,"two"),make_pair(3,"three"),make_pair(4,"four"),make_pair(5,"five"),make_pair(6,"six") };map<int, string> m2(arr.begin(), arr.end());for (auto& e : m2){cout << e.first << " " << e.second << endl;}cout << endl;cout << "m3拷贝构造m2" << endl;map<int, string> m3(m2);for (auto& e : m3){cout << e.first << " " << e.second << endl;}cout << endl;return 0;
}

2、map的各种功能：

总的来说和set大差不差，主要是多了operator[ ]

功能样例：

int main()
{vector<pair<int, string>> arr1 = { make_pair(1,"one"),make_pair(2,"two"),make_pair(3,"three"),make_pair(4,"four"),make_pair(5,"five"),make_pair(6,"six") };map<int, string> m1(arr1.begin(), arr1.end());cout << "迭代器遍历m1：" << endl;map<int, string>::iterator it1 = m1.begin();while (it1 != m1.end()){cout << it1->first << " " << it1->second << endl;it1++;}cout << endl;cout << "插入元素后" << endl;m1.insert({ 7,"seven" });for(auto& e : m1)cout << e.first << " " << e.second << endl;cout << "根据键值 删除元素后" << endl;m1.erase(1);m1.erase(7);for (auto& e : m1)cout << e.first << " " << e.second << endl;cout << endl;cout << "构造新的m2" << endl;vector<pair<int, string>> arr2 = { make_pair(11,"eleven"),make_pair(12,"twelve"),make_pair(13,"thirteen"),make_pair(14,"fourteen"),make_pair(15,"fifteen"),make_pair(16,"sixteen") };map<int, string> m2(arr2.begin(), arr2.end());for (auto& e : m2)cout << e.first << " " << e.second << endl;cout << "m1和m2交换后：" << endl;m1.swap(m2);cout << "m1:" << endl;for (auto& e : m1)cout << e.first << " " << e.second << endl;cout << "m2:" << endl;for (auto& e : m2)cout << e.first << " " << e.second << endl;cout << endl<< "根据键值查找元素：" << endl;cout << "m1.find(11): ";cout << (m1.find(11) != m1.end()) << endl << endl;cout << "m1的size:" << m1.size() << endl;cout << "m2的size:" << m2.size() << endl;cout << endl;map<int, int> m3;cout << "m1的empty:" << m1.empty() << endl;cout << "m3的empty:" << m3.empty() << endl;return 0;
}

3、map的operator[ ]

operator[]的原理是：

用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中

如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器

如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器

operator[]函数最后将insert返回值键值对中的value(实值)返回。

也就是说：

operator[ ]返回的是当前键值对应的实值，如果当前键值不存在，则会插入新的键值对，然后在返回新的键值对的实值。

int main()
{vector<pair<int, string>> arr1 = { make_pair(1,"one"),make_pair(2,"two"),make_pair(3,"three"),make_pair(4,"four"),make_pair(5,"five"),make_pair(6,"six") };map<int, string> m1(arr1.begin(), arr1.end());cout << m1[1] << endl;cout << m1[3] << endl;cout << m1[7] << endl;m1[7] = "seven";m1[8];m1[9] = "nine";for (auto& e : m1)cout << e.first << " " << e.second << endl;return 0;
}

应用（计数）

int main()
{vector<string> v1 = { "苹果","香蕉","西瓜","西瓜" ,"西瓜" ,"西瓜","香蕉","香蕉","苹果" };map<string, int> m1;for (auto& e : v1){map<string, int>::iterator ret = m1.find(e);if (ret == m1.end())m1.insert(make_pair(e, 1));elseret->second++;}for (auto& e : m1)cout << e.first << ":" << e.second << endl;return 0;
}

那么operator[]就可以优化上述的代码：

int main()
{vector<string> v1 = { "苹果","香蕉","西瓜","西瓜" ,"西瓜" ,"西瓜","香蕉","香蕉","苹果" };map<string, int> m1;for (auto& e : v1)m1[e]++;for (auto& e : m1)cout << e.first << ":" << e.second << endl;return 0;
}

3、multimap:

multimap和map的关系，和multiset和set的关系差不多。都是将容器中不能重复的值变为可以存在重复的值。

int main()
{vector<pair<int, string>> arr1 = { make_pair(1,"one"),make_pair(2,"two"),make_pair(3,"three"),make_pair(4,"four"),make_pair(5,"five"),make_pair(6,"six") };multimap<int, string> m1(arr1.begin(), arr1.end());map<int, string> m2(arr1.begin(), arr1.end());m1.insert(make_pair(2, "two"));m1.insert(make_pair(2, "two"));m1.insert(make_pair(2, "two"));m1.insert(make_pair(7, "seven"));cout << "multimap<int, string> m1(arr1.begin(), arr1.end());" << endl;for (auto& e : m1)cout << e.first << " " << e.second << endl;cout << endl;m2.insert(make_pair(2, "two"));m2.insert(make_pair(2, "two"));m2.insert(make_pair(2, "two"));m2.insert(make_pair(7, "seven"));cout << "map<int, string> m2(arr1.begin(), arr1.end());" << endl;for (auto& e : m2)cout << e.first << " " << e.second << endl;return 0;
}