当前位置：首页 > news >正文

关联容器笔记

news 2025/6/20 0:26:05

关联容器总结

有序关联容器

键值的顺序自动排序，键值必须支持 < 操作符

底层数据结构

使用平衡树，比如（红黑树）
增删查的平均时间复杂度接近 O(log⁡n)

种类

std::set：集合，包含唯一的键元素。
std::multiset：多重集合，允许键重复。
std::map：映射，键值对（键唯一，值可以重复）。
std::multimap：多重映射，允许键重复的键值对。

无序关联容器

底层数据结构

链式哈希
增删查的平均时间复杂度接近O(1)

种类

std::unordered_set：无序集合，包含唯一的键元素。
std::unordered_multiset：无序多重集合，允许键重复。
std::unordered_map：无序映射，键唯一。
std::unordered_multimap：无序多重映射，允许键重复。

方法

插入操作
- insert()：在容器中插入元素，返回一个迭代器和一个布尔值（表示插入是否成功）。对于无序容器，可以传入 hint 迭代器提升效率。
- emplace()：在容器中原地构造元素，避免不必要的复制或移动操作。
删除操作
- erase()：根据键或迭代器删除元素。返回已删除元素的数量。
查找操作
- find()：返回一个指向指定键的迭代器，若键不存在则返回 end()。

#include <iostream>
#include <map>
#include <unordered_set>int main() {// std::map 示例std::map<int, std::string> m;// 插入元素m.insert(std::make_pair(1, "one"));m.emplace(2, "two");m[3] = "three";  // 使用下标操作符插入或更新元素// 查找元素auto it = m.find(1);if (it != m.end()) {std::cout << "Key 1 found with value: " << it->second << std::endl;  // 输出 "one"}else {std::cout << "Key 1 not found" << std::endl;}// 删除元素m.erase(2);  // 删除键为 2 的元素std::cout << "After erase, size of map: " << m.size() << std::endl;// 遍历元素std::cout << "Elements in map:" << std::endl;for (const auto& kv : m) {std::cout << kv.first << " => " << kv.second << std::endl;}// std::unordered_set 示例std::unordered_set<int> uset = { 1, 2, 3 };// 插入元素uset.insert(4);// 查找元素if (uset.find(3) != uset.end()) {std::cout << "Found 3 in unordered_set" << std::endl;}else {std::cout << "3 not found in unordered_set" << std::endl;}// 删除元素uset.erase(1);  // 删除元素 1std::cout << "After erase, size of unordered_set: " << uset.size() << std::endl;// 遍历元素std::cout << "Elements in unordered_set:" << std::endl;for (const auto& elem : uset) {std::cout << elem << " ";}std::cout << std::endl;return 0;
}