STL的关联式容器总结
2018-08-01 本文已影响0人
cpp加油站
1. map
1.1 map的底层实现
map是红黑树(一种非严格意义上的平衡二叉树),置于红黑树的具体可以看算法和数据结构,这里不多说。
1.2 map的元素类型
map的key类型必须要重载"<"操作符,无法重载时用自定义仿函数代替map的第三个参数,因为map是有序的。
map第一个参数是key,第二个参数是value,第三个参数是compare函数,第四个参数是内存配置对象
insert(std::pair<key,value>(1,'gg'))
判断insert是否成功:
pair<map<int,string>iterator, bool> insert_pair;
insert_pair = map.insert(std::pair<key,value>(1,'gg'));
if ( insert_pair.second == true )
cout << "success" << endl;
else
cout << "failed" << endl;
1.3 map遍历删除
map<int,string>::iterator iter = m.begin();
for(; iter != m.end();)
{
if ( iter->first % 10 == 0 )
{
m.erase(iter++); //不能直接在for里面自加,因为erase以后iter会失效
}
}
2. set
2.1 set的底层原理
set类似于数学里面的集合,不过set的集合中不包含重复的元素,这是和vector的第一个区别,第二个区别是set内部用红黑树实现,便于元素查找。在set中查找是使用二分查找法,所以set在查询方面速度很快。在set中做插入和删除效率也是比较高的,因为不需要做内存拷贝和内存移动。
3. 怎么判断该用什么容器
- 如果需要高效的随机存取,不在乎插入和删除的效率,使用vector;
- 如果需要大量的插入和删除元素,不关心随机存取的效率,使用list;
- 如果需要随机存取,并且关心两端数据的插入和删除效率,使用deque;
- 如果打算存储数据字典,并且要求方便地根据key找到value,一对一的情况使用map,一对多的情况使用multimap;
- 如果打算查找一个元素是否存在于某集合中,唯一存在的情况使用set,不唯一存在的情况使用multiset。