哪些C++库对于竞技编程有用?

哪些C++库对于竞技编程有用?

C++是竞技编程中最受推荐的语言之一(请参考我们之前的文章原因)。

C++ STL 包含许多容器,这些容器对于不同的用途非常有用。在本文中,我们将着重介绍从竞技编程和面试准备的角度来看最重要的容器。

哪些C++库对于竞技编程有用?

vector :(#include<vector>)动态大小数组,允许插入和删除而不必考虑详细资料的大小,它还具有类似于普通数组的优点,例如随机访问和缓存友好。C++向量支持许多其他操作,例如erase(),push_front(),insert()等。

queue :(#include<queue>)用于希望按FIFO顺序排序项目的情况。示例问题是,使用给定数字生成数字,流中的第一个非重复字符,树的层序遍历及其变体,图的BFS及其变体。请参考队列实践问题以获取更多练习。

stack :(#include<stack>)用于希望具有LIFO顺序的情况。示例问题是平衡括号,股票跨度问题,下一个更大的元素和直方图中的最大区域。请参考堆栈实践问题以获取更多练习。

setmap :(#include<set>#include<map>)两者均实现了自平衡二叉搜索树(特别是红黑树)。在希望具有中等搜索、插入和删除查询时间(优于数组,劣于哈希)的情况下非常有用。示例问题是左侧最接近的大于或相同值,查找数组中每个元素的最接近值,等等。当想要存储仅键时,我们使用set,当想要存储键值对时,我们使用map。

unordered_setunordered_map :(#include< unordered_set>#include< unordered_map>)两者均使用哈希与链接来实现。当我们希望具有快速的搜索、插入和删除(这三个操作都是O(1))时非常有用。这是工业界中使用最多的数据结构之一,在学术界中最低估。有许多流行的问题,如不同的元素数、数组项的频率、0和2个无序数组的联合和交集算法。请参阅哈希实践问题以进行更多练习。

priority_queue :(#include<priority_queue>)默认情况下实现Max Heap。我们也可以创建Min Heap。每当我们希望高效地查找最小或最大元素时,它都会被使用。它被用于实现流行的算法,例如Prim算法、Dijkstra最短路径、Huffman编码、K个最大元素、合并K个排序数组、流的中位数。请参阅堆实践问题以进行更多练习。

deque :#include<deque> Dequeue支持在O(1)时在两端进行插入和删除。由于它使用数组实现,因此也允许随机访问。我们可以使用deque来实现队列和堆栈。Deque的示例问题包括访问所有加油站以及大小为k的所有子数组的最大值。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程