设为首页 收藏本站
查看: 626|回复: 1

[经验分享] C++面试八股文:用过std::set/std::map吗

[复制链接]
累计签到:34 天
连续签到:2 天
发表于 2025-1-22 14:46:49 | 显示全部楼层 |阅读模式
本帖最后由 jinchanchanwaji 于 2025-1-22 14:48 编辑

某日二师兄参加XXX科技公司的C++工程师开发岗位第27面:
面试官:用过std::set/std::map吗?
二师兄:用过。
面试官:能介绍一下二者吗?
二师兄:std::set是一个有序的集合,其中的元素是唯一的,即每个元素只能出现一次。一般用于去重和自动排序。
二师兄:std::map同样是有序组合,只不过它不止有key,每个key还对用一个value。其中key是唯一,不可重复,但是value却没有限制。key/value也被称为键值对。
面试官:知道他们底层使用什么数据结构存储数据的吗?
二师兄:两者都是使用红黑树作为底层的数据结构。红黑树是一种自动平衡的二叉树,它确保插入、删除和查找操作的时间复杂度都是O(log n)。
面试官:set/map对于key的类型有什么要求吗?
二师兄:因为set/map被称为有序容器,所以对插入进去的key有排序的要求。一般需要为类型实现<比较方法,以下代码无法通过编译:

[C++] 纯文本查看 复制代码
#include <iostream>
#include <set>
struct Foo
{
    Foo(int v):val(v){}
    int val;
};
int main(int argc, char const *argv[])
{
    std::set<Foo> iset;
    iset.insert(Foo(1024));
    iset.insert(Foo(42));
    for(auto it = iset.begin(); it != iset.end(); ++it)
    {
        std::cout << it->val << std::endl;
    }
    return 0;
}
二师兄:此时需要为Foo类型实现bool operator<(const T&, const T&)函数,才能通过编译:
bool operator<(const Foo& lhs,const Foo& rhs) {return lhs.val < rhs.val;}
面试官:按照你的方法,可以实现从小到大的排序。如何实现从大到小的排序?
二师兄:set/map类模板的第二个模板参数可以传入比较类型,默认比较类型是std::less<_Key>,我们可以传入std::greater<T>,此时需要实现bool operator>(const T&, const T&)函数。
二师兄:还有一种方法是手写一个仿函数,重载bool operator()(const T, const T) const函数用于比较两者的大小:

[C++] 纯文本查看 复制代码
struct Comp
{
    bool operator()(const Foo& lhs, const Foo& rhs) const
    {
        return lhs.val > rhs.val;
    }
};
std::set<Foo,Comp> iset;
面试官:可以修改map中的key吗?二师兄:不可以。因为map中的key是const的。强制修改(取地址,const_cast转非const指针,解引用赋值)会造未知的错误。
面试官:当map中不存在某个key时,对map使用map[key]操作会有什么后果?
二师兄:会在map中增加一个键值对,键名为key,值是传入的value类型的默认值。
面试官:如果不希望删除重复的key,有什么办法?
二师兄:STL中提供了std::multiset和std::multimap两个容器,可以存入key相同的多个元素。
面试官:在std::multimap中如何通过key查找value?
二师兄:multimap提供了equal_range方法,此方法返回一个pair,分别对应2个迭代器。通过循环迭代器来获取key对应的所有value。
#include <iostream>

[C++] 纯文本查看 复制代码
#include <map>
int main() {
    std::multimap<int, std::string> mmap;
    mmap.insert(std::make_pair(1, "1"));
    mmap.insert(std::make_pair(2, "2"));
    mmap.insert(std::make_pair(3, "3"));
    mmap.insert(std::make_pair(1, "1"));
    auto range = mmap.equal_range(1);
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << std::endl;
    }
    return 0;
}
面试官:最后一个问题,你觉得单纯的查询而言,是vector快还是map快?
二师兄:当然是map快,因为vector的查询的时间复杂度是O(n),而map是O(logn)。
面试官:好的,今天面试结束了,回去等通知吧。

让我们看看最后一个问题:
单纯的查询而言,是vector快还是map快?

这里二师兄的是标准答案,实际上当数据量特别大的时候,的确map是更好的选择。
但当数据量没那么大的时候(少于1000条记录),vector要比map查询速度快。原因我们在之前的面试文章中讲过,vector内存连续,缓存更友好。map底层是红黑树,内存并不连续。
当数据量小的时候,算法的优势没有抵消缓存的劣势,所以vector在数据量小的时候更胜一筹。
“纸上得来终觉浅,绝知此事要躬行”。小伙伴们,一起努力吧!

运维网声明 1、欢迎大家加入本站运维交流群:群②:261659950 群⑤:202807635 群⑦870801961 群⑧679858003
2、本站所有主题由该帖子作者发表,该帖子作者与运维网享有帖子相关版权
3、所有作品的著作权均归原作者享有,请您和我们一样尊重他人的著作权等合法权益。如果您对作品感到满意,请购买正版
4、禁止制作、复制、发布和传播具有反动、淫秽、色情、暴力、凶杀等内容的信息,一经发现立即删除。若您因此触犯法律,一切后果自负,我们对此不承担任何责任
5、所有资源均系网友上传或者通过网络收集,我们仅提供一个展示、介绍、观摩学习的平台,我们不对其内容的准确性、可靠性、正当性、安全性、合法性等负责,亦不承担任何法律责任
6、所有作品仅供您个人学习、研究或欣赏,不得用于商业或者其他用途,否则,一切后果均由您自己承担,我们对此不承担任何法律责任
7、如涉及侵犯版权等问题,请您及时通知我们,我们将立即采取措施予以解决
8、联系人Email:admin@iyunv.com 网址:www.yunweiku.com

所有资源均系网友上传或者通过网络收集,我们仅提供一个展示、介绍、观摩学习的平台,我们不对其承担任何法律责任,如涉及侵犯版权等问题,请您及时通知我们,我们将立即处理,联系人Email:kefu@iyunv.com,QQ:1061981298 本贴地址:https://www.yunweiku.com/thread-1005675-1-1.html 上篇帖子: C++面试八股文:std::deque用过吗? 下篇帖子: C++面试八股文:知道std::unordered_set/std::unordered_map吗?
累计签到:34 天
连续签到:2 天
 楼主| 发表于 2025-1-22 14:48:59 | 显示全部楼层
<顺便吆喝一句,技术大厂年前捞人,前后端测试都有→https://jsj.top/f/o38ijj,感兴趣试试~>

运维网声明 1、欢迎大家加入本站运维交流群:群②:261659950 群⑤:202807635 群⑦870801961 群⑧679858003
2、本站所有主题由该帖子作者发表,该帖子作者与运维网享有帖子相关版权
3、所有作品的著作权均归原作者享有,请您和我们一样尊重他人的著作权等合法权益。如果您对作品感到满意,请购买正版
4、禁止制作、复制、发布和传播具有反动、淫秽、色情、暴力、凶杀等内容的信息,一经发现立即删除。若您因此触犯法律,一切后果自负,我们对此不承担任何责任
5、所有资源均系网友上传或者通过网络收集,我们仅提供一个展示、介绍、观摩学习的平台,我们不对其内容的准确性、可靠性、正当性、安全性、合法性等负责,亦不承担任何法律责任
6、所有作品仅供您个人学习、研究或欣赏,不得用于商业或者其他用途,否则,一切后果均由您自己承担,我们对此不承担任何法律责任
7、如涉及侵犯版权等问题,请您及时通知我们,我们将立即采取措施予以解决
8、联系人Email:admin@iyunv.com 网址:www.yunweiku.com

回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

扫码加入运维网微信交流群X

扫码加入运维网微信交流群

扫描二维码加入运维网微信交流群,最新一手资源尽在官方微信交流群!快快加入我们吧...

扫描微信二维码查看详情

客服E-mail:kefu@iyunv.com 客服QQ:1061981298


QQ群⑦:运维网交流群⑦ QQ群⑧:运维网交流群⑧ k8s群:运维网kubernetes交流群


提醒:禁止发布任何违反国家法律、法规的言论与图片等内容;本站内容均来自个人观点与网络等信息,非本站认同之观点.


本站大部分资源是网友从网上搜集分享而来,其版权均归原作者及其网站所有,我们尊重他人的合法权益,如有内容侵犯您的合法权益,请及时与我们联系进行核实删除!



合作伙伴: 青云cloud

快速回复 返回顶部 返回列表