31、map deque list的实现原理【中高频】
文章目录
list:双向链表,适用于频繁在中间 插入和删除操作。在链表中,每个元素都有 指向前后元素的指针,所以 在任何位置进行插入和删除都非常高效。
-
高效插入和删除:在链表中的插入和删除时间复杂度为 (O(1)),不需要像 vector 一样移动其他元素。
-
访问效率低:由于链表没有连续存储,不能通过索引直接访问某个元素。所以 必须从头或尾遍历,因此访问的效率低。
deque:双端队列,可以在头部和尾部 快速插入和删除,适合 在头尾 都需要频繁增删数据的场景
-
高效双端操作:无论是头部还是尾部插入/删除,时间复杂度均为 (O(1))。
-
支持随机访问:deque 支持通过索引 直接访问元素,但它的底层存储结构并非一个连续的内存块,而是一个存储指针的数组,里面的每个元素都是指针,指向了内存中的小块连续的内存空间。这个指针数组从中间位置开始存储指针,留下首尾两端,从而便于扩容。
#include <deque>
#include <iostream>
int main() {
std::deque<int> dq = {1, 2, 3};
dq.push_front(0); // 在头部添加元素 0
dq.push_back(4); // 在尾部添加元素 4
// 遍历并输出元素
for (int val : dq) {
std::cout << val << " ";
} // 输出 0 1 2 3 4
return 0;
}
map:键值对容器,类似于字典,它也是通过红黑树实现的,因此也是有序存储。适合需要快速查找键值对的场景,比如存储用户信息或用于配置文件读取等
-
有序存储:键值对按照键的顺序存储(所以map不能修改key的值,但可以修改value的值)
-
键唯一:每个键都是唯一的(如果想保存多个相同的键,可以用multimap)
-
查找高效:map 的查找、插入和删除操作的时间复杂度为 O(log n)。
#include <map>
#include <iostream>
int main() {
std::map<int, std::string> m = {{1, "one"}, {2, "two"}};
m[3] = "three"; // 插入键值对 (3, "three")
// 遍历并输出键值对
for (auto& [key, value] : m) {
std::cout << key << ": " << value << std::endl;
}
return 0;
}
原文地址:https://blog.csdn.net/2402_84438596/article/details/146266805
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/586024.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/586024.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!