set和map

set

set的普通迭代器和const迭代器都不支持修改。(这点可以根据源代码看出来，都是对const iterator进行了typedef)

insert

函数原型，value_type一般是T的typedef

单独插入一个值

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

insert后打印出来的值 会自动排序+去重。

set一般不使用在pos位置进行插入，因为可能这样会破坏搜索树的结构。

insert会不会有迭代器失效的问题？
不会，因为迭代器和链表一样，每个结点都是独立的。所以不会失效。

但是erase会失效。

find

返回迭代器

iterator find (const value_type& val) const;

set的find和头文件算法中的find的区别。

set的find是logn，因为用了搜索树的特性。

find的查找是O(N).是一个暴力查找。

erase

erase删除返回的被删除数据的个数。为了和冗余版本的erase对接。

count

count还可以判断元素在不在set中。

比find好用。

lower_bound

功能：返回要大于或等于要找元素的迭代器。(闭区间)

假如是找一个不存在的值。会返回一个比这个值大于的值迭代器。
总结：他会返回>=val位置的迭代器。

upper_bound

返回大于x的迭代器。
开区间。
不管要找的那个值存在不存在，则返回比它大的那个值的迭代器。

这样设计的原因，是要配合迭代器使用的。
假如要删除 x<= n <=y的值，但你不知道x和y存在不存在，这时候就要用uper_bound.

auto leftIt = s.lower_bound;
auto rightIt = s.upper_bound;

multiset

唯一和set不同的就是允许冗余，其他接口和set一样。

find和count的返回值和set的也契合。
find会返回中序遍历的第一个数。也就是按照左子树 根 右子树的顺序遍历。

count返回某个元素的个数。

set的应用

set有集合的意思，所以在集合的方面有用。
比如百度网盘备份功能。就是数据同步算法，找差集和交集。

比如找交集，最常用的方法就是：
1.相比较，小的++
2.相等的就是交集，然后同时++

差集：
1.相比较，小的就是差集，小的++
2.相等同时++

map

map里面存的是value_type
value_type就是pair，也就是存的是一对数据，是一个结构。

pair<string, string>(“sort”, “排序”)是一个构造函数。
<string,string>传递的是模板类型
pair是类名。

pair

insert的value_type就是pair

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

pair是什么？

template <class T1, class T2> struct pair;

pair的第一个参数是first，第二个参数是second。

insert

有三种写法

1.最常用的是匿名对象写法
2.先用pair生成一个对象，然后再调用insert
3.使用make_pair，它是一个函数模板，可以自动推导类型。

4.C++11也有一种写法，以后再说。

map<string , string> dict;
//匿名对象写法
dict.insert(pair<string, string>("sort", "排序"));
//先生成对象的写法
pair<string,string> kv("我"，“me”);
dict.insert(kv);
//make_pair
dict.insert(make_pair("left","左边"));

insert的pair

为了重载[ ]需要先了解insert的返回值。因为他要返回两个值，iterator和bool

insert的返回值的pair 和 库里面结构的pair不一样，这个要区分开来。

返回的pair的first是一个迭代器iterator，要么是新插入的元素，要么是没插入成功(防止冗余)，返回的是与之相等的元素的位置。second返回一个bool值，来看是否插入成功或者失败。

代码例子

   map<string, int> countMap;for (auto& str : arr){//pair<map<string, int>::iterator, bool> ret = countMap.insert(make_pair(str, 1));auto ret = countMap.insert(make_pair(str, 1));if (ret.second == false){ret.first->second++;}}

map的遍历

map的遍历就比较难。
it是pair这个结构。所以要用it->k和*(it).k

auto it = dict.begin();

map对[ ]的重载(重点)

[ ]这个运算符在map中可以用来进行插入，修改，和查找的功能。

函数原型
mapped_type是第二个模板参数T，key_type是第一个模板参数key

意思就是通过key来获得T，也就是value

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

源码如下

情况一，假如k在map的对象中，插入失败，这里充当查找k对应的v，修改k对应的v

情况二，假如不在，插入成功，这里充当插入和修改的功能。

mapped_type& operator[] (const key_type& K)
{pair<iterator, bool> ret = insert(make_pair(K, mapped_type()));
return ret.first->second;
}

最简单的统计次数的方法。用的次数最多。

map<string, int> countMap;for (auto& str : arr){countMap[str]++;}for (const auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}

multimap

和map最大的区别是支持冗余。

不支持operator[]
insert返回值不是返回pair。