【c++】——map和set（csdn）————程序.pdf

C++中的`map`和`set`是STL（Standard Template Library）中两种重要的关联容器。它们都基于红黑树数据结构，提供了高效的数据插入、查找和删除操作。以下是关于`set`和`map`的详细说明： **set** 1. **底层结构**：`set`的底层实现为红黑树，这是一种自平衡的二叉搜索树，保证了在最坏情况下插入、查找和删除的时间复杂度为O(logn)。 2. **唯一性**：`set`中的元素都是唯一的，不允许有重复的键值(key)。一旦尝试插入重复的键值，插入操作将失败。 3. **插入操作**：`insert`接口用于插入元素。当插入的元素不存在时，返回的pair中，第一个元素是一个指向新插入节点的迭代器，第二个元素为`true`。若元素已经存在，返回的迭代器指向已存在的元素，第二个元素为`false`。 4. **遍历**：`set`支持通过迭代器或范围for循环进行遍历，遍历顺序是按照红黑树的中序遍历，即键值从小到大。 5. **查找操作**：`find`方法用于查找键值，如果找到则返回对应元素的迭代器，否则返回`end()`。 6. **const属性**：`set`中的键值是const的，不可修改，因为修改键值可能会破坏容器的排序和唯一性。 **multiset** `multiset`与`set`非常相似，唯一的区别在于`multiset`允许键值重复。在`multiset`中，查找操作同样按中序遍历，但可以找到多个相同的键值。 **map** 1. **键值对**：`map`是关联容器，它存储键值对(key-value)，其中键key用于唯一标识元素，值value则与键相关联。键和值可以有不同的类型。 2. **比较器**：默认情况下，键值之间按照小于关系进行比较。对于自定义类型，用户可能需要提供比较规则，通常通过函数指针或仿函数传递。 3. **插入操作**：插入键值对到`map`中，需要先将键值对存储到`pair`中，然后插入。`insert`接口与`set`的插入类似，但`map`中键值对的比较是基于键key，而非整个pair。 4. **下标操作`[]`**：`map`提供了下标操作符`[]`，如果键k不存在，它会自动插入一个键值对(k, mapped_type())，并返回引用到新插入的值。如果键k已存在，返回的是对应键的值的引用。 5. **pair模板**：`pair`是一个模板类，可以存储两个不同类型的值，分别称为`first`和`second`。`make_pair`是`pair`的一个静态成员函数，用于快速创建匿名`pair`对象。 6. **修改值**：在`map`中，键key是const的，不能修改，但对应的值(value)是可以改变的。 `set`和`map`是C++中用于存储和管理有序数据的重要工具，它们基于红黑树保证了高效的操作性能。在实际编程中，根据数据的需求和特性选择合适的容器是非常关键的。