C++教学总目录

1、set

1.1、set简介

如图：set是类模板，参数T表示存储的数据类型，类似上篇的key。Compare是仿函数，因为set插入值时需要进行比较大小，这里给模板参数我们就可以自己控制。Alloc是空间配置器。set包含于头文件<set>
map和set的底层都是红黑树，红黑树是一种二叉平衡搜索树，这个我们后面会模拟实现。

key_type就是T，key_type就是T的重命名。这里还有一个value_type这个现在还无法解释，得后面模拟实现map和set了解底层才能解释，这里先知道即可。
在上篇我们说了key版本的二叉搜索树是不能修改值的，因为修改了key会破坏二叉搜索树的结构，那么set这里如何控制迭代器无法修改呢？

可以看到，这里的普通迭代器实际上就是const迭代器。因此无论是普通迭代器还是const迭代器都无法修改key值。

---

1.2、set接口简介

构造函数有三个分别是：无参的默认构造函数、使用迭代器区间构造、拷贝构造。

迭代器这边基本上和vector、list一样了，会使用其中一个容器的迭代器，其他的也都会使用。这里不再赘述。

这里面比较重要的函数就三个，分别是插入、删除和查找函数。其他的用的不多，可以了解一下。

---

insert函数有三个：分别是插入一个值、在某个位置插入一个值、插入一段迭代器区间。
这里的value_type实际上就是T。

erase函数也有三个：分别是删除某个迭代器位置的数据、删除某个值、删除一段迭代器区间。

find函数就是传入key进行查找，找到就返回对应位置的迭代器，找不到返回end()。

---

1.3、set的使用

基于二叉搜索树的性质，我们知道二叉搜索树可以排序和快速的搜索，因为中序遍历二叉搜索树就是从小到大获取数据。
下面演示使用set去重+排序：

set<int> s;
s.insert(1);
s.insert(3);
s.insert(2);
s.insert(5);
s.insert(3);
s.insert(4);set<int>::iterator it = s.begin();
while (it != s.end())
{cout << *it << " ";++it;
}
cout << endl;for (auto e : s)
{cout << e << " ";
}
cout << endl;

运行结果如图所示，set插入的时候类似二叉搜索树，只不过底层是红黑树需要维持高度平衡，所以多了旋转的步骤。如果树中已存在数据就不插入。使用迭代器遍历set实际上就是中序遍历。因此set可以用来排序+去重。

---

另外如果我们要删除数据可以这样使用：

s.erase(3);

还可以这样使用：

set<int>::iterator pos = s.find(3);
if (pos != s.end())s.erase(pos);

找不到会返回end()，所以使用find进行删除需要多一步判断。
注意：这里的find函数的时间复杂度为O(logN)，如果使用算法库的find函数，时间复杂度为O(N)，所以一定要使用set自带的find函数。

---

1.4、set其他接口的使用

这里我们再介绍这四个函数的使用，但是并不常用，有些主要是为了multiset设计的。

---

count函数返回树中元素的个数，由于set不能存储重复的数据，所以返回值只有1/0，因此有点鸡肋(也可以使用find)。

set<int> s;
s.insert(1);
s.insert(3);
s.insert(2);
s.insert(5);
s.insert(4);auto pos = s.find(3);
if (pos != s.end())
{cout << "找到了" << endl;
}if (s.count(3))
{cout << "找到了" << endl;
}

---

这两个函数是配合着使用的，lower_bound返回>=val数据的迭代器，而upper_bound返回的是>val数据的迭代器。这样就形成了一个区间，我们可以删除这个区间中的值。使用如下：

set<int> myset;
set<int>::iterator itlow, itup;
for (int i = 1; i < 10; i++) myset.insert(i * 10); // 插入10->90
// [35, 60]
itlow = myset.lower_bound(35);   // >=35
itup = myset.upper_bound(60);    // >60std::pair<std::set<int>::const_iterator, std::set<int>::const_iterator> ret;
ret = myset.equal_range(30);
std::cout << "the lower bound points to: " << *ret.first << endl;
std::cout << "the upper bound points to: " << *ret.second << endl;// [itlow, itup)
cout << *itlow << endl;
cout << *itup << endl;
myset.erase(itlow, itup);for (auto e : myset)
{cout << e << " ";
}
cout << endl;

上面的代码我们使用lower_bound计算出大于等于35的值，所以获取40这个数据的迭代器。使用upper_bound计算出大于60的值，所以获取70这个数据的迭代器。紧接着我们通过erase删除这段区间的值，由于迭代器区间都是左闭右开，所以实际上删除的是[40，70)之间的值，因此70并没有被删除。

---

这个函数返回一个迭代器区间。第一个值还是大于等于val的，第二个大于val。

std::set<int> myset;
for (int i = 1; i <= 5; i++) myset.insert(i * 10);   // myset: 10 20 30 40 50std::pair<std::set<int>::const_iterator, std::set<int>::const_iterator> ret;
ret = myset.equal_range(30);std::cout << "the lower bound points to: " << *ret.first << '\n';
std::cout << "the upper bound points to: " << *ret.second << '\n';

然后调用erase传入这个区间就可以删除区间之间的值。

---

1.5、multiset

multiset基本上同set，使用方式也一样，只不过multiset支持插入重复的值。因此count和equal_range在multiset这里用处更大。包含于头文件<set>

multiset<int> s;
s.insert(3);
s.insert(5);
s.insert(8);
s.insert(7);
s.insert(7);
s.insert(9);
s.insert(7);
for (auto e : s)
{cout << e << " ";
}
cout << endl;// 返回中序第一个7
auto pos = s.find(7);
while (pos != s.end())
{//*pos = 10;cout << *pos << " ";++pos;
}
cout << endl;
cout << s.count(7) << endl;auto ret = s.equal_range(6);
auto itlow = ret.first;
auto itup = ret.second;
// [itlow, itup)
// [7,7)
cout << *itlow << endl;
cout << *itup << endl;
s.erase(itlow, itup);   
for (auto e : s)
{cout << e << " ";
}
cout << endl;

1、这里find找出的7是中序遍历的第一个7，通过该位置继续向后遍历可以获取所有7以及大于7的值。
2、并且可以利用count函数计算出树中存储了几个7。
3、使用equal_range函数算出的两个范围分别是7，但是由于区间是[7，7)所以什么也不删除。
其他的使用同set，这里不再赘述。

---

2、map

2.1、map简介

map是key/value结构的，所以模板参数有Key、T，仿函数用来比较。包含于头文件<map>

map的数据类型实际上是一个pair，pair里面又有key和T，所以实际上T就是value。
map是不能修改key的，因为修改了key就会破坏二叉搜索树的结构，但是是可以修改value的。这里是通过给pair的第一个参数加上const来控制的，这样就不能修改key了。

---

2.2、pair使用

pair是一个类模板，有两个模板参数T1、T2。包含于头文件<utility>
下面给出pair的类似实现方式：

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

因此pair可以存储两个类型，可以是同种类型，也可以是不同类型。
例如做算法题我们需要存储点的位置，可以使用下面的方式来存储：

typedef pair<int, int> PII;
const int N = 100010;
PII sec[N];
sec[0] = {1, 1};
//.....

另外上面的equal_range函数的返回值也是一个pair，是同种类型的迭代器，由于pair是通过struct定义出来的，所以可以直接在类外访问成员变量，即通过：pair.first和pair.second来访问。

---

2.3、map接口使用

构造函数分别为：无参的默认构造函数、使用迭代器区间构造、拷贝构造函数。

map同样有find、count、lower_bound、upper_bound、equal_range。而这六个函数在set我们已经介绍过了，这里不再赘述。

---

insert函数有三个：插入一个pair（这里的value_type就是pair）、在某个位置插入一个pair、插入一段迭代器区间。
下面来看insert的使用：

map<string, string> dict;
pair<string, string> kv1("insert", "插入");
dict.insert(kv1);

这样写会比较麻烦，还可以我们直接构造一个临时对象然后这个临时对象再去拷贝构造，编译器会优化成一个构造函数：

dict.insert(pair<string, string>("insert", "插入"));

但是这么写还是很麻烦，这里就需要使用一个函数了：make_pair

make_pair是pair类内提供的一个函数，这个函数直接返回一个临时对象，所以我们可以直接使用make_pair来构造，等价于上面的写法，只不过这样写更加简便：

dict.insert(make_pair("insert", "插入"));

但是这种写法还不是最简便的写法，C++11支持多参数的构造函数隐式类型转换，还可以这么写：

dict.insert({ "insert", "插入" });

而我们之前的一些写法是支持了单参数的构造函数隐式类型转换，如下：

string str = "hello";

上面的代码发生了隐式类型转换，先用字符串构造一个临时的string对象，再用这个临时的string对象去拷贝构造str，连续的构造+拷贝构造编译器优化成直接用字符串构造str对象。

向dict中插入几个pair对象并使用迭代器遍历：

map<string, string> dict;
dict.insert(make_pair("string", "字符串"));
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("insert", "插入"));auto it = dict.begin();
while (it != dict.end())
{cout << (*it).first << ":" << (*it).second << endl;++it;
}

迭代器解引用后获取的是pair对象，所以还需要.first和.second访问成员变量。另外还可以使用->来访问更简便：

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

这是因为迭代器重载了operator->，返回值是pair*的指针，所以正确写法应该是it->->first，只不过为了观赏性省略掉一个->。支持迭代器都可以使用范围for，这里不再演示。

---

erase函数支持删除迭代器位置的数据，传入key删除数据，删除迭代器区间。

---

我们注意到：map和set相比，多了operator[]这个函数：

前面讲了key_type就是key，mapped_type就是value。所以这个函数参数就是传入key，然后返回value的引用，因此使用这个函数可以修改value的值。

(*((this->insert(make_pair(k,mapped_type()))).first)).second

这个函数的实现调用了insert函数。
并且注意到insert的返回值是pair<iterator, bool>

在operator[]中调用insert函数的返回值：
1、key已经在树里面，返回pair<树里面key所在节点的iterator，false>
2、key不在树里面，返回pair<新插入key所在节点的iterator，true>
分析这行代码：

用map来统计次数：

string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
map<string, int> countMap;
for (auto e : arr)
{auto it = countMap.find(e);if (it == countMap.end()){countMap.insert(make_pair(e, 1));}else{it->second++;}
}
for (const auto& e : countMap)
{cout << e.first << ":" << e.second << endl;
}

重载了operator[]，我们还能这么写：

string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
map<string, int> countMap;
for (auto e : arr)
{countMap[e]++;
}
for (const auto& e : countMap)
{cout << e.first << ":" << e.second << endl;
}

如果水果没有在树里面，那就插入并返回value的引用，由于构造piar时使用的是默认构造，所以返回的value是0，然后对0进行++。
如果水果在树里面，那insert就插入失败返回，operator[]中返回value的引用，然后对value的值进行++。

operator[]中调用了insert，不管key在树中是否存在（不在就插入），都会将key位置的迭代器构造一个pair返回，通过pair.first可以获取到key位置的迭代器，通过pair.second的值true/false可以判断是否插入成功。

---

map<string, string> dict;
dict.insert(make_pair("string", "字符串"));
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("insert", "插入"));cout << dict["sort"] << endl; // 查找和读
dict["map"];                  // 插入
dict["map"] = "映射,地图";     // 修改
dict["insert"] = "xxx";       // 修改
dict["set"] = "集合";         // 插入+修改

最后一个先调用insert插入字符串"set"，然后返回值value的引用是空串，紧接将value修改为"集合"。

2.4、multimap

multimap支持插入重复key的pair键值对。使用方式类似set和multiset之间的区别。