map和set的区别和底层实现是什么?map取值的 find,[],at方法的区别
目录
一、map 和 set 的区别
1. 基本定义
2. 底层实现
3. 存储内容
4. 常用操作
5. 有序性
二、map 的取值方法:find(),[],和 at()
1. find()
2. operator[]([] 操作符)
3. at()
一、map
和 set
的区别
1. 基本定义
map
:一种关联容器,存储的是键值对(key-value pairs),每个键对应唯一的值。键是唯一的,不允许重复。常见的用法是std::map<Key, Value>
.set
:一种集合容器,存储的是唯一的键(key),不存储值。元素是唯一的,且不可重复。常见的用法是std::set<Key>
.
2. 底层实现
map
和set
:底层通常使用**红黑树(Red-Black Tree)**实现,红黑树是一种自平衡的二叉查找树,能够保证增删查改操作的时间复杂度为 O(log n)。- 在
map
中,红黑树的节点存储键值对,按键排序。 - 在
set
中,红黑树的节点只存储键,按键排序。
- 在
unordered_map
和unordered_set
:底层使用**哈希表(Hash Table)**实现,通过哈希函数将键映射到不同的桶,增删查改操作的平均时间复杂度为 O(1),最坏情况下为 O(n)。
3. 存储内容
map
:存储键值对,键唯一,值可以重复或不同。- 例如:
map<int, string> m; m[1] = "one"; m[2] = "two";
- 例如:
set
:只存储唯一的键,不存储值。- 例如:
set<int> s; s.insert(1); s.insert(2);
- 例如:
4. 常用操作
map
:可以通过键来查找值(例如m[key]
),插入或删除键值对。set
:可以插入、删除和查找键(例如s.insert(key)
,s.find(key)
)。
5. 有序性
map
和set
:两者都按照键进行排序(使用比较函数,如<
)。unordered_map
和unordered_set
:无序,元素排列顺序由哈希函数决定。
二、map
的取值方法:find()
,[]
,和 at()
在 map
中,可以使用多种方法来访问存储的值,每种方法的行为略有不同。
1. find()
- 功能:用于查找指定键是否存在。如果存在,返回指向该元素的迭代器;如果不存在,返回
map.end()
。 - 用法:
std::map<int, std::string> m = {{1, "one"}, {2, "two"}};
auto it = m.find(1); // 返回指向键为1的迭代器
if (it != m.end()) {
std::cout << it->second << std::endl; // 输出 "one"
}
- 特点:
- 不会插入新元素,如果键不存在,仅返回
end()
。 - 时间复杂度为 O(log n)。
- 不会插入新元素,如果键不存在,仅返回
2. operator[]
([]
操作符)
- 功能:通过键来访问值。如果键存在,返回对应的值;如果键不存在,会创建一个新的键值对,并初始化值(通常为值类型的默认构造值,如 0、空字符串等)。
- 用法:
std::map<int, std::string> m;
m[1] = "one"; // 插入键1的元素,并赋值为"one"
std::cout << m[2]; // 键2不存在,插入键2,值初始化为空字符串
- 特点:
- 如果键不存在,会创建新元素并初始化,这种行为可能导致意外的元素插入。
- 适合用于需要修改或赋值的场景。
- 时间复杂度为 O(log n)。
3. at()
- 功能:通过键来访问值。如果键存在,返回对应的值;如果键不存在,抛出
std::out_of_range
异常。 - 用法:
std::map<int, std::string> m = {{1, "one"}};
std::cout << m.at(1); // 输出 "one"
std::cout << m.at(2); // 抛出 std::out_of_range 异常
特点:
- 不会插入新元素,仅在键存在时返回值。
- 适合用于确定键一定存在的场景,否则需要异常处理。
- 时间复杂度为 O(log n)。