根据应用场景的不桶， STL 总共实现了两种不同结构的管理式容器：树型结构与哈希结构。 树型结构的关联式 容器主要有四种： map 、 set 、 multimap 、 multiset 。这四种容器的共同点是：使用平衡搜索树 ( 即红黑树 ) 作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一个容器 3.1 set 3.1.1 set 的介绍 翻译： 1. set 是按照一定次序存储元素的容器 2. 在 set 中，元素的 value 也标识它 (value 就是 key ，类型为 T) ，并且每个 value 必须是唯一的。 set 中的元素 不能在容器中修改( 元素总是 const) ，但是可以从容器中插入或删除它们。 3. 在内部， set 中的元素总是按照其内部比较对象 ( 类型比较 ) 所指示的特定严格弱排序准则进行排序。 4. set 容器通过 key 访问单个元素的速度通常比 unordered_set 容器慢，但它们允许根据顺序对子集进行直接迭代。 5. set 在底层是用二叉搜索树 ( 红黑树 ) 实现的。 注意： 1. 与 map/multimap 不同， map/multimap 中存储的是真正的键值对template3. 树形结构的关联式容器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) {} };
3. set的迭代器
4. set的容量
5. set 修改操作| 函数声明 | 功能介绍 |
|
pair |
在
set
中插入元素
x
，实际插入的是
|
| void erase ( iterator position ) | 删除 set 中 position 位置上的元素 |
| size_type erase ( const key_type& x ) | 删除 set 中值为 x 的元素，返回删除的元素的个数 |
| void erase ( iterator fifirst, iterator last ) | 删除 set 中 [fifirst, last) 区间中的元素 |
|
void swap (
set | 交换 set 中的元素 |
| void clear ( ) | 将 set 中的元素清空 |
| iterator fifind ( const key_type& x ) const | 返回 set 中值为 x 的元素的位置 |
| size_type count ( const key_type& x ) const | 返回 set 中值为 x 的元素的个数 |
删除一个元素可以通过迭代器删除，也可以通过值删除。但是通过值删除可以得到删除元素的个数，通过迭代器删除如果元素不存在会报错，所以一般我用迭代器删除的时候一般要判断要删除的元素是否存在
7.multiset 可以看出multiset可以插入相同的元素，删除元素可以删除多个 3.2 map 3.2.1 map的介绍 1. map 是关联容器，它按照特定的次序 ( 按照 key 来比较 ) 存储由键值 key 和值 value 组合而成的元素。 2. 在 map 中，键值 key 通常用于排序和惟一地标识元素，而值 value 中存储与此键值 key 关联的内容。键值 key 和值 value 的类型可能不同，并且在 map 的内部， key 与 value 通过成员类型 value_type 绑定在一起， 为其取别名称为 pair: typedef pair value_type; 3. 在内部， map 中的元素总是按照键值 key 进行比较排序的。 4. map 中通过键值访问单个元素的速度通常比 unordered_map 容器慢，但 map 允许根据顺序对元素进行 直接迭代 ( 即对 map 中的元素进行迭代时，可以得到一个有序的序列 ) 。 5. map 支持下标访问符，即在 [] 中放入 key ，就可以找到与 key 对应的 value 。 6. map 通常被实现为二叉搜索树 ( 更准确的说：平衡二叉搜索树 ( 红黑树 ))。 1. map 是关联容器，它按照特定的次序 ( 按照 key 来比较 ) 存储由键值 key 和值 value 组合而成的元素。 2. 在 map 中，键值 key 通常用于排序和惟一地标识元素，而值 value 中存储与此键值 key 关联的内容。键值 key 和值 value 的类型可能不同，并且在 map 的内部， key 与 value 通过成员类型 value_type 绑定在一起， 为其取别名称为 pair: typedef pair value_type; 3. 在内部， map 中的元素总是按照键值 key 进行比较排序的。 4. map 中通过键值访问单个元素的速度通常比 unordered_map 容器慢，但 map 允许根据顺序对元素进行 直接迭代 ( 即对 map 中的元素进行迭代时，可以得到一个有序的序列 ) 。 5. map 支持下标访问符，即在 [] 中放入 key ，就可以找到与 key 对应的 value 。 6. map 通常被实现为二叉搜索树 ( 更准确的说：平衡二叉搜索树 ( 红黑树 )) 。 3.2.2 map的使用 1. map 的模板参数说明 key: 键值对中 key 的类型 T ： 键值对中 value 的类型 Compare: 比较器的类型， map 中的元素是按照 key 来比较的，缺省情况下按照小于来比较，一般情况 下 ( 内置类型元素 ) 该参数不需要传递，如果无法比较时 ( 自定义类型 ) ，需要用户自己显式传递比较规则 ( 一般情况下按照函数指针或者仿函数来传递 ) Alloc ：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器 注意：在使用 map 时，需要包含头文件。 2.map的构造 3. map的迭代器 我们先看一段代码void MapTest1()
{
string array[] = { "苹果","香蕉","橘子","苹果","香蕉","橘子","樱桃" };
map mp;
for (const auto& e : array)
{
auto it = mp.find(e);
if (it == mp.end()) //说明该水果没有插入
{
mp.insert(make_pair(e, 1));
}
else
{
++it->second;
}
}
for (const auto& e : mp)
{
cout << e.first << ":" << e.second << endl;
}
}
int main()
{
//SetTest();
//MultisetTest();
//MapTest();
MapTest1();
}
这段代码时统计水果的出现的次数
第二种方法：
void MapTest1()
{
string array[] = { "苹果","香蕉","橘子","苹果","香蕉","橘子","樱桃" };
map mp;
for (const auto& e : array)
{
auto kv = mp.insert(make_pair(e, 1));
if (kv.second == false)
++kv.first->second;
}
for (const auto& e : mp)
{
cout << e.first << ":" << e.second << endl;
}
}
int main()
{
//SetTest();
//MultisetTest();
//MapTest();
MapTest1();
}
可以看出insert插入之后会返回一个pair，如果插入成功就返回插入之后的迭代器，返回true，插入失败就返回false，所以我们可以根据 第二个参数得到是否插入成功，失败就说明该水果存在我们就让value加1；
第三种方法：
for (const auto& e : array)
{
mp[e]++;
}
for (const auto& e : mp)
{
cout << e.first << ":" << e.second << endl;
}
}
int main()
{
//SetTest();
//MultisetTest();
//MapTest();
MapTest1();
}
mapped_type& operator[] (const key_type& k)
{
return (*((this->insert(make_pair(k,mapped_type()))).first)).second
}
//我们可以简化一下
mapped_type& operator[] (const key_type& k)
{
auto kv = insert(make_pair(k,mapped_type());
return kv.first->second;
}
【总结】
1. map
中的的元素是键值对
2. map
中的
key
是唯一的，并且不能修改
3.
默认按照小于的方式对
key
进行比较
4. map
中的元素如果用迭代器去遍历，可以得到一个有序的序列
5. map
的底层为平衡搜索树
(
红黑树
)
，查找效率比较高
6.
支持
[]
操作符，
operator[]
中实际进行插入查找。
1. 本公司现在要给公司员工发波福利，在员工工作时间会提供大量的水果供员工补充营养。由于水果种类 比较多，但是却又不知道哪种水果比较受欢迎，然后公司就让每个员工报告了自己最爱吃的k种水果,并且告知已经将所有员工喜欢吃的水果存储于一个数组中。然后让我们统计出所有水果出现的次数，并 且求出大家最喜欢吃的前k种水果。
void
GetFavoriteFruit
(
const
vector
&
fruits
，
size_t k
)
{
}
struct ComCol
{
bool operator()(pair& r, pair& l)
{
return r.first > l.first;
}
};
struct ComColIt
{
bool operator()(multimap::iterator& rt, multimap::iterator& lt)
{
return rt->first > lt->first;
}
};
void GetFavoriteFruit(const vector & fruits, size_t k)
{
map mp;
for (const auto& e : fruits)
{
mp[e]++;
}
multimap mmp;
for (const auto& e : mp)
{
mmp.insert(make_pair(e.second, e.first));
}
//以为mp是双向迭代器，所以不支持sort所以需要把mp中数据放入vector中
//方法一：将数据放入vector中
//方法二:将迭代器放入vector中
vector::iterator> v;
auto it = mmp.begin();
while (it != mmp.end())
{
v.push_back(it);
++it;
}
sort(v.begin(), v.end(), ComColIt());
for (int i = 0; i < k; ++i)
{
cout << v[i]->first << " : " << v[i]->second << endl;
}
//方法三：
priority_queue::iterator, vector::iterator>,
ComColIt> q;
auto it = mp.begin();
while (it != mp.end())
{
q.push(it);
++it;
}
while (k--)
{
cout << q.top()->first << " : " << q.top()->second << endl;
q.pop();
}
}
int main()
{
//SetTest();
//MultisetTest();
//MapTest();
//MapTest1();
vector v{ "苹果","橘子", "樱桃" ,"苹果", "樱桃", "橘子" ,"哈密瓜" ,"西瓜", "香蕉", "香蕉" ,"哈密瓜", "苹果" ,"苹果", "橘子", "苹果" };
GetFavoriteFruit(v, 3);
}
692. 前K个高频单词
class Solution {
public:
struct ComCoV
{
bool operator()(map::iterator &l,map::iterator &r)
{
if(l->second < r->second)
return true;
else if(l->second == r->second && l->first > r->first)
return true;
else
return false;
}
};
vector topKFrequent(vector& words, int k) {
vector v;
mapmp;
for(const auto & e: words)
{
++mp[e]; //统计次数
}
priority_queue::iterator,vector::iterator>,ComCoV> q;
auto it = mp.begin();
while(it != mp.end())
{
q.push(it);
++it;
}
while(k--)
{
v.push_back(q.top()->first);
q.pop();
}
return v;
}
};
