共计 2159 个字符，预计需要花费 6 分钟才能阅读完成。
某日二师兄加入 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中的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 在数据量小的时候更胜一筹。
“纸上得来终觉浅，绝知此事要躬行”。小伙伴们，一起致力吧！
关注我，带你 21 天“精通”C++！（狗头）
