首页 > 编程语言 >C++面试八股文:用过std::set/std::map吗?

C++面试八股文:用过std::set/std::map吗?

时间:2023-06-27 23:31:40浏览次数:38  
标签:std map 面试官 set const key 师兄

某日二师兄参加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有排序的要求。一般需要为类型实现<比较方法,以下代码无法通过编译:

#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函数用于比较两者的大小:

struct Comp
{
    bool operator()(const Foo& lhs, const Foo& rhs) const
    {
        return lhs.val > rhs.val;
    }
};
std::set<Foo,Comp> iset;

面试官:可以修改map中的key吗?

二师兄:不可以。因为map中的keyconst的。强制修改(取地址,const_cast转非const指针,解引用赋值)会造未知的错误。

面试官:当map中不存在某个key时,对map使用map[key]操作会有什么后果?

二师兄:会在map中增加一个键值对,键名为key,值是传入的value类型的默认值。

面试官:如果不希望删除重复的key,有什么办法?

二师兄:STL中提供了std::multisetstd::multimap两个容器,可以存入key相同的多个元素。

面试官:在std::multimap中如何通过key查找value

二师兄:multimap提供了equal_range方法,此方法返回一个pair,分别对应2个迭代器。通过循环迭代器来获取key对应的所有value

#include <iostream>
#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在数据量小的时候更胜一筹。

“纸上得来终觉浅,绝知此事要躬行”。小伙伴们,一起努力吧!

关注我,带你21天“精通”C++!(狗头)

标签:std,map,面试官,set,const,key,师兄
From: https://blog.51cto.com/binarch/6568064

相关文章

  • 【Java】讲讲StreamAPI
     预设场景:从Mybatis调用Mapper得到的用户集合List<UserDTO>userList=newArrayList<>(); 常用的几种API用法示例:Map方法,转换为某一个字段的集合:List<Integer>userIdList=userList.stream()/*map转换成某个类型来处理,比如这个场景是为了快速......
  • C++输入输出,设置精度setprecision、域宽setw、填充setfill
    本文的三个函数均需要引入头文件:#include<iomanip>设置输出精度setprecision(intn)参考:C语言中文网:c++setprecision用法详解//写法1cout<<setprecision(10)<<a<<endl;//写法2:a、b、c都将以10位有效位输出cout<<setprecision(10);cout<<a<<endl;cout......
  • HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Secureboot
    regaddHKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Secureboot/vAvailableUpdates/tREG_DWORD/d0x10/f命令是用于在注册表中添加一个名为"AvailableUpdates"的DWORD值,并将其设置为十六进制值"0x10"。此操作需要管理员权限才能执行。这个命令的作用是向......
  • ConcurrentHashMap并不是绝对线程安全的
    ConcurrentHashMap是线程安全的概念已经深入人心,让我们在使用的时候有些大意了,我也懒得动脑子,直接使用,结果碰到钉子了. 这个问题让我很郁闷,程序逻辑全是对的,但是问题却明明摆在那边,最后怀疑是HashMap的问题。 1.package2.3.import4.import5.import6.7.impor......
  • mapper.xml
    <?xmlversion="1.0"encoding="UTF-8"?><!DOCTYPEmapperPUBLIC"-//mybatis.org//DTDMapper3.0//EN""http://mybatis.org/dtd/mybatis-3-mapper.dtd"><mappernamespace="com.framework.twm.mapper.St......
  • 基于vue+elementUI使用vue-amap高德地图
    首先,需要去高德地图进行注册一个https://lbs.amap.com/?ref=https://console.amap.com/dev/index,得到一个key然后安装依赖npminstallvue-amap—save在main.js中加入importVueAMapfrom'vue-amap’;Vue.use(VueAMap);VueAMap.initAMapApiLoader({key:'YOUR_KEY’......
  • mac 下使用 brew 安装包报错 error: Cannot install under Rosetta 2 in ARM default
    mac下使用brew安装包报错error:CannotinstallunderRosetta2inARMdefaultprefix(/opt/homebrew)!TorerununderARMuse:arch-arm64brewinstall...Toinstallunderx86_64,installHomebrewinto/usr/local. 解决:arch-arm64brewinstallxxx ......
  • 跨平台开源远程连接工具rustdesk
    rustdeskhttps://github.com/rustdesk/rustdeskhttps://gitee.com/mirrors/rustdesk......
  • vue2中$set用法详细讲解
    1、为什么要用set?在vue中,并不是任何时候数据都是双向绑定的。在官方文档中,有这样一段话,如下: 从文档得知,当数据没有被双向绑定的时候,我们就需要使用set了2、set用法解决数据没有被双向绑定我们可以使用vm.$set实例方法,该方法是全局方法Vue.set的一个别名。this.$set(原......
  • go:数组和切片、可变长参数、maps、字符串、指针、结构体、方法、接口
    目录数组和切片数组切片可变长参数maps字符串指针结构体方法接口数组和切片数组#1定义,初始化,使用#2数组是值类型数字,字符串,布尔,数组,都是值类型,真正直接存数据切片,map,指针引用类型,是个地址,指向了具体的值#3数组长度#4循环打印数组#5多纬数组#......