网站核验通知书,贵阳网站建站建设定制,.net 网站开发权限设计,祁阳seo1. STL常见容器及其内部实现的数据结构
序号 名称 描述 存储结构 常用方法和操作
1vector动态分配的数组顺序数组#xff08;array#xff09;v.push_back(), v.pop_back(), v.insert(), v.erase(), v.capacity(), v.size(), v.at(idx), v.front(), v.back()2list双向链表离…1. STL常见容器及其内部实现的数据结构
序号 名称 描述 存储结构 常用方法和操作
1vector动态分配的数组顺序数组arrayv.push_back(), v.pop_back(), v.insert(), v.erase(), v.capacity(), v.size(), v.at(idx), v.front(), v.back()2list双向链表离散lt.push_back(), lt.push_front(), lt.insert(), lt.erase(), lt.sort(), lt.merge(), lt.splice()3stack栈用 list 或 deque 实现push(), pop(), top()4queue队列用 list 或 deque 实现push(), pop(), front(), back()5deque双端队列分段连续多个 vector 连续d.push_back(), d.push_front(), d.pop_back(), d.pop_front(), d.insert(), d.erase()6priority_queue优先级队列vectorpush(), pop(), top()7set集合有序不重复红黑树弱平衡二叉搜索树insert(), erase(), find(), count(), clear()8multiset集合有序可重复红黑树insert(), erase(), find(), count(), clear()9unordered_set集合无序不重复哈希表insert(), erase(), find(), count(), clear()10map键值对有序不重复红黑树insert(), erase(), find(), count(), clear()11multimap键值对有序可重复红黑树insert(), erase(), find(), count(), clear()12unordered_map键值对无序不重复哈希表insert(), erase(), find(), count(), clear()13hash_map哈希表类似 map哈希表insert(), erase(), find(), count(), clear()
2. deque底层数据结构
deque 底层实现通常是分段连续的内存结构即由多个 vector 组成允许高效的从两端进行元素的插入和删除。
3. 红黑树
红黑树是一种非严格平衡的二叉查找树具有自动排序的功能。每个节点存储一个颜色红或黑并且通过调整树的结构保持特定的平衡条件从而保证最坏情况下的查找效率。
4. 常见排序算法
4.1 sort()
适用容器仅支持随机访问的容器如 vector、deque、array。功能快速排序。
bool func(int a, int b) {return a b; // 降序排列
}
sort(vec.begin(), vec.end(), func); // 对vector进行排序4.2 partial_sort()
功能对部分元素进行排序使用堆排序实现。参数排序范围默认排序前 n 个元素。
int n 4; // 需要排序的元素个数
partial_sort(vec.begin(), vec.begin() n, vec.end(), func); // 排序前4个元素4.3 is_sorted()
功能检查容器是否已排序。返回值布尔值true 表示已排序。
bool result is_sorted(vec.begin(), vec.end(), func);4.4 is_sorted_until()
功能返回第一个破坏排序规则的元素位置。
auto it is_sorted_until(vec.begin(), vec.end(), func);5. 查找操作
5.1 find()
功能查找指定元素。
vectorint vec{10, 20, 30, 40, 50};
auto it find(vec.begin(), vec.end(), 30); // 查找30
if (it ! vec.end()) {cout 查找成功 *it;
} else {cout 查找失败;
}5.2 find_if()
功能根据自定义谓词查找元素。
bool mycomp(int i) {return (i % 2) 1; // 查找奇数
}
vectorint myvector{4, 2, 3, 1, 5};
auto it find_if(myvector.begin(), myvector.end(), mycomp);6. 使用 vector 避免频繁的内存重新分配
vector 在扩容时通常会以 2 倍容量增长这会导致频繁的内存分配和元素拷贝。为了优化性能可以采取以下策略
6.1 预分配内存
在创建 vector 时可以使用 reserve() 方法预先分配内存以减少多次扩容。
6.2 合理选择初始容量
根据数据的预计大小选择合适的初始容量避免不必要的扩容操作。
6.3 优化算法
使用时间复杂度较低的算法避免在数据量增大时造成性能瓶颈。
7. vector 的 resize() 与 reserve()
7.1 resize()
功能调整容器的大小。效果如果 n 小于当前大小则删除尾部元素如果 n 大于当前大小新的元素会被默认构造并添加到尾部。
7.2 reserve()
功能调整容器的容量不会改变当前大小。效果用于减少扩容次数确保容器有足够的内存空间。
8. vector 扩容原理
扩容过程每次扩容时vector 会分配新的内存块并将现有元素复制到新内存中旧内存被释放。扩容系数通常情况下vector 容量每次会翻倍或增加 1.5 倍这可以减少频繁的扩容。
8.1 Linux中的内存管理
在Linux系统中内存区域以2的倍数扩容以便进行高效的内存分配。
8.2 Windows中的内存管理
在Windows系统中内存分配通常会增加1.5倍以便更好地利用已经释放的内存。
9. 迭代器
迭代器是STL中用于访问容器元素的一种抽象工具。通过迭代器容器元素的访问具有一致的接口并且可以实现多态。
注意迭代器只能前进不能回退。
10. 迭代器失效的情况
迭代器可能会因为容器结构的修改而失效。不同类型的容器失效的情况略有不同
数组型数据结构如 vectorinsert 和 erase 操作会使插入或删除点之后的所有迭代器失效。链表型数据结构如 listerase 操作只会使指向删除元素的迭代器失效其他迭代器不受影响。树型数据结构如 maperase 操作会使指向删除元素的迭代器失效其他迭代器不受影响。 insert 操作不会使任何迭代器失效。
