STL中map和set详解数据结构

在STL中有这两个容器set和map，它们的特性都是：所有元素都会根据元素的键值自动被排序。
下面来介绍一下这两个容器和与之相关的几个容器。
一、set和map
1.set和map的区别和联系：
联系：它们的底层实现都是红黑树。
区别：set是key形式的，set元素的键值(key)就是实值(value)，实值就是键值。而map是key/value形式的，map的所有元素都是pair,同时拥有实值和键值；它们两个的key值都是唯一的，不能有重复。
2.set的常见用法：
<1>元素的插入insert：insert当set中已经有所要插入的元素，则插入失败，若没有，则插入成功。（因为key值唯一）

void TestInsert() { set s1; set::iterator setIt; pair::iterator, bool> ret; //插入1:直接插入key s1.insert(1); s1.insert(10); s1.insert(5); s1.insert(7); ret = s1.insert(10); //已经存在，插入失败//插入二:利用迭代器插入 if (ret.second == false) setIt = ret.first; s1.insert(setIt, 6); //插入三:插入一个迭代器区间 list l1; l1.push_back(34); l1.push_back(33); l1.push_back(32); l1.push_back(31); list::iterator listIt = l1.begin(); s1.insert(listIt, l1.end()); //将list的迭代器区间插入//正向遍历 setIt = s1.begin(); while (setIt != s1.end()) { cout << *setIt << " "; ++setIt; } }

<2>元素的删除erase：

void TestErase() { set s1; set::iterator setIt; for (int i = 10; i > 0; --i) s1.insert(i); //删除一:利用迭代器删除(无返回值) setIt = s1.begin(); //setIt指向1 s1.erase(setIt); //删除二:根据key值删除（删除成功返回1，失败返回0） size_t ret1 = s1.erase(10); size_t ret3 = s1.erase(5); size_t ret2 = s1.erase(20); cout << "删除二返回值:"; cout << ret1 << " " << ret2 <<" " << ret3<< endl; //删除三：删除一段迭代器区间 setIt = s1.find(7); s1.erase(setIt, s1.end()); //遍历 cout << "遍历set:"; setIt = s1.begin(); while (setIt != s1.end()) { cout << *setIt << " "; ++setIt; } }

<3>查找元素find：参数为key值，找到则返回要查找结点的迭代器，找不到则返回end()

void TestFind() { set s1; set::iterator setIt; for (int i = 10; i > 0; --i) s1.insert(i); setIt = s1.find(8); //存在 cout << *setIt << endl; setIt = s1.find(20); //不存在 cout << (setIt == s1.end()) << endl; //打印1，说明返回值为end() }

3.map的常见用法：
<1>map的插入insert，删除erase，查找find都和set类似，这里说说操作的不同。
set是key形式的，map是key/value形式的。所以原来传入key的位置现在要传入一个pair结构体类型。
pair类型其实就是：

template struct pair { K first; V second; };

【STL中map和set详解】示例程序如下：

void TestInsert() { map wordCount; //示例插入方式之一，插入pair元素，其余与set类似 wordCount.insert(pair("hello", 1)); wordCount.insert(pair("world", 3)); wordCount.insert(pair("aaa", 7)); wordCount.insert(pair("bbb", 1)); PrintMap(wordCount); //遍历map的函数 }

<2>map的operator[ ] 方法：
operator[ ] 传入参数为key值，返回值为value的引用。它的内部实现嵌套了insert函数，当传入key值不存在时，就会插入该key。
通过返回value值的引用，可以修改元素的value值。
示例程序：统计出现次数最多的前K种水果。（利用operator[ ]统计水果出现的个数。）

//统计出现次数最多的前K种水果 void TopK(vector& fruits) { //统计水果出现的次数 map fruitCount; size_t size = fruits.size(); for (size_t i = 0; i < size; ++i) { fruitCount[fruits[i]]++; }//排序 vector v; //将数据保存在可以随机访问的容器里。 map::iterator it = fruitCount.begin(); while (it != fruitCount.end()) { v.push_back(it); ++it; }struct CMP { bool operator()(const map::iterator l, const map::iterator r) const { return (l->second > r->second); } }; sort(v.begin(), v.end(), CMP()); //输出排序结果 for (size_t i = 0; i < v.size(); ++i) { cout << v[i]->first << "-" << v[i]->second << endl; } } void TestFruitCount() { vector fruits; fruits.push_back("苹果"); fruits.push_back("梨"); fruits.push_back("苹果"); fruits.push_back("香蕉"); fruits.push_back("葡萄"); fruits.push_back("苹果"); fruits.push_back("苹果"); fruits.push_back("梨"); fruits.push_back("葡萄"); fruits.push_back("西瓜"); fruits.push_back("猕猴桃"); fruits.push_back("葡萄"); fruits.push_back("猕猴桃"); fruits.push_back("猕猴桃"); fruits.push_back("柠檬"); fruits.push_back("香蕉"); fruits.push_back("柚子"); fruits.push_back("香蕉"); TopK(fruits); }

注意：
不能通过迭代器来改变set和map内部的值，因为要保证key值的唯一和元素的顺序
*setIt = 20; //这样是错误的