每天写1000字linux c/c++杂谈每周500字

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. 怎么判断该用什么容器

上一篇下一篇

猜你喜欢

热点阅读