std::(unordered_)map与set是否共享底层代码？用map替代set能否减小二进制体积？

问题1：用std::map<T, bool>替代std::set<T>能否减小二进制体积？ #

• 是的，如果你已经在代码中大量使用std::map，改用std::map<T, bool>替代std::set<T>大概率能降低二进制体积。核心原因是：主流标准库实现中，std::set的底层逻辑和std::map高度相似，但如果你的代码之前没用到std::set，引入它会触发新的模板实例化（包括std::set的迭代器、成员函数等封装层代码）；而std::map<T, bool>只是复用已存在的std::map模板，仅新增值类型为bool的实例化部分，这部分额外代码量远小于新增std::set的开销。
• 当然要接受一个小权衡：std::map<T, bool>的每个节点会多存储一个bool值（部分实现会用位优化减少开销，但仍有额外存储），内存效率略低于std::set<T>，但如果核心诉求是二进制体积，这个代价是可控的。

问题2：std::(unordered_)map与std::(unordered_)set底层是否共享代码？ #

C标准没有强制要求，但业界主流实现（GCC libstdc、Clang libc++、MSVC STL）都采用了代码复用的设计：

• 有序容器组（map/set）：二者共享红黑树的核心实现。std::set本质是只存储键的红黑树封装，std::map是存储键值对的红黑树封装，标准库通过模板参数的差异（比如是否携带值）来复用红黑树的插入、查找、平衡等核心逻辑，避免重复编写代码。
• 无序容器组（unordered_map/unordered_set）：二者共享哈希表的底层实现。std::unordered_set仅存储键，std::unordered_map存储键值对，同样通过模板特化或内部辅助类复用哈希表的核心操作逻辑。

需要注意的是，即使底层共享核心代码，std::set和std::unordered_set仍有自己的封装层代码（比如专属的迭代器、成员函数），如果之前没用到过这些容器，首次引入还是会增加二进制体积——这也是为什么用std::map<T, bool>替代更省体积的原因。

内容的提问来源于stack exchange，提问作者Paul