STL——map和set

一、set的介绍

1、set是按照一定次序存储元素的容器；

2、在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的，set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们；

3、set在底层是用二叉搜索树(红黑树)实现的；

4、set中的元素默认按照小于来比较；

5、set中查找某个元素，时间复杂度为：O(log2N)；

set的一些接口函数可自行查看文档来使用 set - C++ Reference (cplusplus.com)

这里需要了解一下insert()函数：

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

1、key已经在树里面，返回pair<树里面key所在节点的iterator， false>；

2、key不在树里面，返回pair<新插入树中key所在节点的iterator， true>；

pair是一个类模板：

我们删除set节点的时候，可以传一段迭代器区间，可以用以下三个函数来找迭代器区间的范围。

1、lower_bound（找左边界）

找大于等于val的第一个值；

2、upper_bound（找右边界）

找大于val的第一个值；

因为erase()传的是一个左闭右开的区间，举个例子：

int main ()
{set<int> myset;set<int>::iterator itlow,itup;for (int i=1; i<10; i++) myset.insert(i*10); // 10 20 30 40 50 60 70 80 90//要删除[30， 60]的值itlow=myset.lower_bound (30);itup=myset.upper_bound (60);//[30, 70)myset.erase(itlow,itup);//左闭右开            // 10 20 70 80 90return 0;
}

3、equal_range

void setTest2()
{multiset<int> s;s.insert(1);s.insert(2);s.insert(4);s.insert(2);s.insert(2);s.insert(3);s.insert(2);s.insert(5);for (auto e : s){cout << e << " ";}cout << endl;auto ret = s.equal_range(2);auto itlow = ret.first;auto itup = ret.second;cout << *itlow << endl;cout << *itup << endl;s.erase(itlow, itup);for (auto e : s){cout << e << " ";}cout << endl;
}

运行结果：

二、map的介绍

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

2、在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:typedef pair<const key, T> value_type;

我们已经在上面介绍了pair

3、map支持下标访问符，即在[]中放入key，就可以找到与key对应的value；
4、map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

map的一些接口函数可自行查看文档来使用 map - C++ Reference (cplusplus.com)

map和set大致上是一样的，都是红黑树，但是map节点存的是键值对，即一个key和其对应的信息，map中重点要理解 [] 的使用。

operator[]里面调用了insert函数，而insert函数上面已经介绍了；

更容易理解的来说，调用operator[]就是传过去一个key，返回这个key对应的value的引用。

例如：之前统计水果出现的次数和实现类似字典的程序都可以使用operator[]

void map_test2()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };map<string, int> countmap;//方法一：/*for (auto s : arr){map<string, int>::iterator it = countmap.find(s);if (it == countmap.end()){countmap.insert(make_pair(s, 1));}else{it->second++;}}*///方法二：for (auto s : arr){countmap[s]++;}map<string, int>::iterator it = countmap.begin();while (it != countmap.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;
}

void map_test3()
{map<string, string> dict;dict.insert(make_pair("car", "汽车"));dict.insert(make_pair("football", "足球"));dict.insert(make_pair("red", "红色"));cout << dict["car"] << endl;//查找，显示dict["black"];//插入dict["football"] = "kkk";//修改dict["green"] = "绿色";//插入+修改cout << dict["black"] << endl;cout << dict["football"] << endl;}

总结：

1、map中的的元素是键值对；
2、map中的key是唯一的，并且不能修改；
3、默认按照小于的方式对key进行比较；
4、map中的元素如果用迭代器去遍历，可以得到一个有序的序列；
5、map的底层为平衡搜索树(红黑树)，查找效率比较高O(log2 N)；
6、支持[]操作符，operator[]中实际进行插入查找。