C++面试八股文:知道std::unordered_set/std::unordered_map吗?

这篇具有很好参考价值的文章主要介绍了C++面试八股文:知道std::unordered_set/std::unordered_map吗?。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

某日二师兄参加XXX科技公司的C++工程师开发岗位第27面:

面试官:知道std::unordered_set/std::unordered_map吗?

二师兄:知道。两者都是C++11引入的新容器,和std::setstd::map功能类似,key唯一,unordered_mapvalue可变。

二师兄:不同于set/mapunordered_set/unordered_map都是无序容器。

面试官:那你知道它们底层怎么实现的吗?

二师兄:两者底层使用哈希表实现,因此插入、删除和查找操作的平均时间复杂度为常数时间O(1)

面试官:既然平均复杂度是O(1),那么是不是可以取代setmap了?

二师兄:这里是平均的时间复杂度。哈希表插入、删除和查找操作的最差时间复杂度是O(n),要比set/mapO(log n)大。

面试官:那你觉得哪些场景适合set/map,哪些场景适合unordered_set/unordered_map

二师兄:set/map适用于需要有序存储和快速查找的场景,而unordered_set/unordered_map适用于需要快速插入和查找的场景。

面试官:unordered_set/unordered_map对于key的类型有什么要求吗?

二师兄:因为unordered_set/unordered_map底层采用哈希表,所以在使用自定义类型作为key的时候,需要告诉编译器如何计算此类型的hash值,同时还要告诉编译器如何判断两个自定义类型的对象是否相等。以下代码无法通过编译:

#include <iostream>
#include <unordered_set>
struct Foo
{
    std::string str;
    int val;
};
int main(int argc, char const *argv[])
{
    std::unordered_set<Foo> uset;
    uset.insert({"42",42});
    uset.insert({"1024",1024});
    return 0;
}

二师兄:此时需要为Foo类型实现bool operator==(const Foo& o) const函数和size_t operator()(const Foo& f) const仿函数,才能通过编译:

#include <iostream>
#include <unordered_set>
struct Foo
{
    std::string str;
    int val;
    bool operator==(const Foo& o) const
    {
        return str == o.str && val == o.val;
    }
};
struct Hash
{
    size_t operator()(const Foo& f) const
    {
        return std::hash<std::string>()(f.str) ^ std::hash<int>()(f.val);
    }
};
int main(int argc, char const *argv[])
{
    std::unordered_set<Foo,Hash> uset;
    uset.insert({"42",42});
    uset.insert({"1024",1024});
    return 0;
}

二师兄:当然我们也可以使用std::function或者lambda来代替仿函数,目的都是为了使得编译器知道如何计算自定义类型的哈希值。

面试官:用过unordered_multiset/unordered_multimap吗?

二师兄:没用过。但是应该和multiset/multimap类似,只是底层也采用hash表实现。

面试官:好的,今天的面试就结束了,请回去等消息吧。

对于今天面试官的表现,小伙伴们能给几分呢?不是面试官要放水,面完set/map之后再面unordered_set/unordered_map,真的没有那么多好问题,因为两者太像了。。。

好了,今天的面试到这里就结束了,让我们期待明天面试官的表现吧~

关注我,带你21天“精通”C++!(狗头)文章来源地址https://www.toymoban.com/news/detail-506044.html

到了这里,关于C++面试八股文:知道std::unordered_set/std::unordered_map吗?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++面试八股文:std::string是如何实现的?

    某日二师兄参加XXX科技公司的C++工程师开发岗位第18面: 面试官: std::string 用过吧? 二师兄:当然用过(废话,C++程序员就没有没用过 std::string 的)。 面试官: std::string(\\\"hello\\\")+\\\"world\\\" 、 \\\"hello\\\"+std::string(\\\"world\\\") 和 std::string(\\\"hello\\\")+std::string(\\\"world\\\") 的结果是什么?为什么? 二师

    2024年02月09日
    浏览(40)
  • C++面试八股文:std::array如何实现编译器排序?

    某日二师兄参加XXX科技公司的C++工程师开发岗位第25面: 面试官: array 熟悉吗? 二师兄:你说的是原生数组还是 std::array ? 面试官:你觉得两者有什么区别? 二师兄:区别不是很大,原生数组(非动态数组)和std::array都在栈上开辟空间,初始化的时候需要提供数组长度,且

    2024年02月10日
    浏览(50)
  • C++面试八股文:在C++中,你知道哪些运算符?

    某日二师兄参加XXX科技公司的C++工程师开发岗位第11面: 面试官:在C++中,你都知道都哪些运算符? 二师兄:啥?运算符? +-*/= 这些算吗? 面试官:嗯,还有其他的吗? 二师兄:当然还有, +=,-=,*=,/=,== ,还有逻辑运算,位运算等。 面试官:好的。那你知道这些运算的优

    2024年02月08日
    浏览(38)
  • C++面试八股文:技术勘误

    不知不觉,《C++面试八股文》已经更新30篇了,这是我第一次写技术博客,由于个人能力有限,出现了不少纰漏,在此向各位读者小伙伴们致歉。 为了不误导更多的小伙伴,以后会不定期的出勘误文章,请各位小伙伴留意。 在《C++面试八股文:C++中,设计一个类要注意哪些东

    2024年02月11日
    浏览(50)
  • C++面试八股文:如何避免死锁?

    某日二师兄参加XXX科技公司的C++工程师开发岗位第31面: 面试官:什么是锁?有什么作用? 二师兄:在C++中,锁(Lock)是一种同步工具,用于保护共享资源,防止多个线程同时访问,从而避免数据竞争和不一致。 面试官:有哪些锁? 二师兄:从种类上分,可以分为普通锁、

    2024年02月12日
    浏览(50)
  • C++面试八股文:什么是智能指针?

    某日二师兄参加XXX科技公司的C++工程师开发岗位第19面: 面试官:什么是智能指针? 二师兄:智能指针是C++11引入的类模板,用于管理资源,行为类似于指针,但不需要手动申请、释放资源,所以称为智能指针。 面试官:C++11引入了哪些智能指针? 二师兄:三种,分别是 s

    2024年02月09日
    浏览(44)
  • C++面试八股文:了解位运算吗?

    某日二师兄参加XXX科技公司的C++工程师开发岗位第12面: 面试官:了解位运算吗? 二师兄:了解一些。(我很熟悉) 面试官:请列举以下有哪些位运算? 二师兄:按位与( )、按位或( | )、按位异或( ^ ),按位取反( ~ )、左移( )和右移( )。 面试官:好的。那你

    2024年02月08日
    浏览(41)
  • C++面试八股文:什么是构造函数?

    某日二师兄参加XXX科技公司的C++工程师开发岗位第29面: 面试官:什么是构造函数? 二师兄:构造函数是一种特殊的成员函数,用于创建和初始化类的对象。构造函数的名称与类的名称相同,并且没有返回类型。构造函数在对象被创建时自动调用。 面试官:什么是默认构造

    2024年02月11日
    浏览(47)
  • C++面试八股文:用过STL吗?

    某日二师兄参加XXX科技公司的C++工程师开发岗位第21面: 面试官:用过STL吗? 二师兄:(每天都用好吗。。)用过一些。 面试官:你知道STL是什么? 二师兄:STL是指标准模板库( Standard Template Library ),是C++区别于C语言的特征之一。 面试官:那你知道STL的六大部件是什么

    2024年02月09日
    浏览(48)
  • C++面试八股文:什么是RAII?

    某日二师兄参加XXX科技公司的C++工程师开发岗位第13面: 面试官:什么是 RAII ? 二师兄: RAII 是 Resource Acquisition Is Initialization 的缩写。翻译成中文是资源获取即初始化。 面试官: RAII 有什么特点和优势? 二师兄:主要的特点是,在对象初始化时获取资源,在对象析构时释放

    2024年02月08日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包