std::map std::set

std::map和std::set是常用的关联式容器，它们都是ADT（抽象数据类型）。它们的接口不仅规定了操作的功能，还规定了操作的复杂度。例如，std::map的insert函数在通常情况下的复杂度是O(logN)，其中N是元素的数量。但是如果插入的元素已经按照键值排序，那么复杂度将会是O(1)。\[1\]

在实现中，为了节约std::map和std::set对象的大小，STL使用了空基类优化。具体做法是将rb_tree作为成员变量，而rb_tree又以rb_tree_impl为成员变量，rb_tree_impl继承自allocator。如果allocator是空类，那么rb_tree_impl的大小就和没有基类时一样。其他STL容器也使用了相同的优化措施，因此std::vector对象占用3个字长，std::list对象占用2个字长。boost的compressed_pair也使用了相同的优化。\[2\]

对于传递参数的方式，根据《Effective C++》的建议，我们应该尽量使用const引用来传递对象。但是对于内置类型、STL迭代器和STL仿函数，传值也是可以的，一般不会有性能损失。\[3\]
#### 引用[.reference_title]
- *1* *2* *3* [关于 std::set/std::map 的几个为什么](https://blog.csdn.net/Solstice/article/details/8521946)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^koosearch_v1,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]