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

某日二师兄参加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，此时需要实现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中的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>
#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在数据量小的时候更胜一筹。