mapset
map&set
1 序列式容器和关联式容器
1.1 序列式容器
1）底层为线性结构；
2）存储的是元素本身；
3）可以任意插入数据位置。
比如之前所学习的：vector,list,deque,forward等。
1.2 关联式容器
1）存储的是<key,value>结构是键值对；
2）效率比序列式容器高；
3）数据与数据之间有较强的联系；
4）插入的数据有固定的位置。
比如，我们将要学习的map和set就是一种树形结构的关联式容器。
2 set
1）set的key是不允许修改的。
2）multiset与set的区别在于：其不去重，可以有相同的值。但是接口与set是相同的。
其中，对于multiset，find找的是中序中的第一个出现的。
2.1 Insert&iterator&end
void test1()
{
set<int> s;
s.insert(3);
s.insert(1);
s.insert(2);
s.insert(4);
s.insert(5);
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
it++;
}
}
int main()
{
test1();
}
使用set进行插入，并打印。为什么得到的结果是有序的？
因为其底层是二叉搜索树，并且是进行中序打印的。
更严格的来说，其实现的是去重+排序。
2.2 find
2.3 erase
而此处的size_type返回的是如果删除成功则是1，不成功则是0；这里的size_type是为了multiset设计的，删除了重复的，可能返回1,2,3等。
方式(1)：必须要找到有效的迭代器, 才能进行删除。否则报错。
也可以通过(2)的方式进行删除。此时，有这个值就删，没有这个值就不会进行删除。不会报错。
2.4 lower_bound&upper_bound
2.5 count
统计出现的次数。
3 map
3.1 概念
map相当于一个kv模型的平衡二叉树或者红黑树。
map相当于kv模型，而set相当于k模型。而这俩个模型中的key都是不能修改的，因为其是用来搜索的。而map中的value是可以修改的，因为就比如之前写过的通过二叉搜索树记录苹果个数的例子。如增加一个苹果，首先找树中是否有这个苹果，即找key,如果有，则苹果个数增加1，即value增加1.此时key的值不能改变，而value的值是可以改变的。再如C++中定义的：
C++库中，将key和value都放在pair中。
3.2 insert
map<string, string> dict;
//方式1:匿名对象
dict.insert(pair<string,string>("apple","苹果"));
//方式2:有名对象
pair<string, string> kv("string","字符串");
dict.insert(kv);
//方式3：C++11 隐式类型转换(构造函数)
dict.insert({"sort","排序"});
//方式4: make_pair
dict.insert(make_pair("abandon","放弃"));make_pair是一个函数模板，返回值是pair匿名对象。
此时我们可以对插入后的节点进行遍历：
为什么？
因为*it，访问的就是树中的节点中的数据，即pair。而这个pair并没有重载"«";所有访问不了数据。
此时，我们就可以了解，为什么pair里面为什么要存在key 和value,这样我们就可以解决上面的报错问题。为了更为方便，我们也可以使用范围for.
3.3 问题1
key相同,value不同，会出现什么样的问题？
从显示结果可以看出，key相同,value不同，并不会进行插入新的节点或者更新value的值。
3.4 multimap
multimap与map在接口上没有什么大的区别，那么如果key相同,value不同，会有什么样的结果？
从上面的图中可以看出，一个key可以对应不同的value,multimap是不去重的。
此时我们还可以像之前学习二叉搜索树时一样，写一个统计水果出现次数的游戏：
但是我们是否有其他的方法来快速统计水果出现的次数？
那么可以使用下面学习的operator[]来解决。
3.5 operator[]
Insert中的返回值的bool具有一种判断的功能，如果创建了一个新的节点，那么bool值为1，能拿到所对应节点的指针。如果没有创建，那么bool值为0，但是也会找到与key值相同的节点的指针。
mapped_typed& operator[](const key_typed& k)
{
return (*((this->insert(make_pair(k, mapped_type()))).first)).second;
}
operator[](const k& key)
{
pair<iterator, bool> ret = insert(key);
return ret.first->second;
}
还是上面的统计水果个数的问题：参考operator[]的版本
void test6()
{
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };
map<string, int> countfruit;
for (auto& e:arr)
{
pair<map<string, int>::iterator, bool> ret;
ret = countfruit.insert(make_pair(e, 1));//如果bool值为1，则已经完成插入
if (ret.second == false)
{
//bool值为0的情况
//已经存在,只需将value++即可
ret.first->second++;
}
}
for (auto& e : countfruit)
{
cout << e.first << " " << e.second << endl;
}
}使用operator[]:
void test6()
{
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };
map<string, int> countfruit;
for (auto& e : arr)
{
countfruit[e]++;
}
for (auto& e : countfruit)
{
cout << e.first << " " << e.second << endl;
}
}总结： operator[] 可以先进行查找，再进行插入和修改的功能。
map<string, string> dict;
dict.insert(make_pair("abandon", "放弃"));
dict.insert(make_pair("string", "字符串"));
dict.insert(make_pair("abandon", "真放弃？"));
dict["left"];//插入
cout << dict["abandon"] << endl;//查找
dict["string"] = "xxx";//修改
dict["right"] = "右边";//插入+修改