乐趣区

关于c++:C面试八股文用过stdsetstdmap吗

某日二师兄加入 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++!(狗头)

退出移动版