- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
因网络上 STL 教程大多零散且缺乏严谨性,本文对算法竞赛所需 C++ Standard Library 做了一个较为全面的总结.
全文主要参考以下文档:
如有能力,阅读原文可获得更深入的了解.
均在 #include<algorithm> 定义.
std::sort(first,last,cmp) 。
排序为不降序列.
接受随机访问迭代器。可自定义比较函数.
平均时间复杂度 O ( n log n ) ,C++11 后严格 O ( n log n ) .
std::stable_sort(first,last,cmp) 。
排序为不降序列,且保持相等元素的顺序.
std::lower_bound(first,last,val,cmp) 。
返回指向首个不小于 val 的元素的迭代器,如无,返回 last .
要求小于 val 的值和大于等于 val 的值分居区间两侧.
可自定义比较函数。若迭代器支持随机访问,对数时间复杂度,否则为线性.
std::upper_bound(first,last,val,cmp) 。
返回指向首个大于 val 的元素的迭代器,如无,返回 last .
std::unique(first,last,cmp) 。
保留区间中所有连续等值区间的首个元素组成新序列,返回处理后序列的尾迭代器.
接受前向迭代器,可自定义判断相等的函数.
线性时间复杂度.
注:C++11 新引入的容器,大部分头文件名与容器名一致.
pair
#include<utility>
:元素对。 tuple
(C++11) :元组。 bitset
#include<bitset>
:定长压缩 01 串,可在
string
#include<string>
:字符串。 operator=
:重载了赋值运算符用于拷贝。 first
/ second
:访问第一项或第二项。 std::make_pair(a,b)
:新建元素对,自动检测类型。 operator<=>
:重载了各种比较运算符,按第一关键字、第二关键字顺序比较。 operator=
:重载了赋值运算符用于拷贝。 std::get<i>(tp)
:获取元组的第 i 项。 std::get<T>(tp)
:获取元组中类型为 T 的项。 std::make_tuple(a,b,c,...)
:新建元组,自动检测类型。 operator<=>
:重载比较运算符,同样是顺序关键字比较。 … 与 vector 类似。其余重要特性如下:
c_str()
:生成一个 C 风格字符串(尾部置 0)并返回其头部指针。 length()
: size()
的同义函数。 append(str)
:后方追加字符串,返回 *this
。 append(first, last)
:区间插入版本。 operator+
:连接两个字符串。 compare(str)
:字典序比较。返回一个 int
,用 <0
/ ==0
/ >0
判断该字符串小于 / 等于 / 大于参数字符串。 operator<=>
:字典序比较的运算符重载。 substr(pos=0, count)
:返回 [pos, min(pos+count, size()))
的子串。时间复杂度与 count
成线性。 pop_back()
(C++11) find(str)
/ rfind(str)
/ find_first_of(c)
/ find_first_not_of(c)
/ find_last_of(c)
/ find_last_not_of(c)
:找字符串或字符,返回位置。若无,返回 npos=-1
。 无时间复杂度保证 ,不建议使用。 bitset<N> bs(val / str) :声明一个长度为 N 的 bitset 并设定初值.
& / ! / ^ / ~ / >> / <<
:支持 AND / OR / XOR / NOT / 右移 / 左移等位运算系列。 operator==
:判断两个 bitset
是否相同。 test(idx) / operator[idx]
:前者会做越界检查,抛出异常。 size()
count()
:返回 1 的个数。 all()
(C++11) :检查是否全为 1。 any() / none()
:检查是否存在 1 / 没有 1。 set() / reset()
:所有位赋 1 / 0。 flip()
:翻转 0 / 1。 以下部分均为 STL 容器相关内容.
声明:形如 vector<int>::iterator iter = xxx.begin() 。C++11 后可用 auto 代替类型声明.
*iter 取值, iter++ 后继.
双向迭代器可 iter-- ,随机访问迭代器支持加减、比较运算.
begin()
, end()
:返回迭代器。 end()
常作为 NULL 使用。 cbegin()
, cend()
(C++11) :部分容器支持,返回只读迭代器。 rbegin()
, rend()
:部分容器支持,返回反向迭代器。 crbegin()
, crend()
:部分容器支持,返回只读反向迭代器。 operator=
:重载了赋值运算符用于拷贝。 empty()
:返回容器是否为空,即 v.begin() == v.end()
。 size()
:返回容器内元素个数。 clear()
:清空容器。 序列式容器:
array
(C++11) :定长顺序表,常数随机访问。 vector
#include<vector>
:顺序表,常数后段插入,常数随机访问。 deque
#include<deque>
:顺序表,常数双端插入, 常数随机访问 。 list
#include<list>
:链表,常数插入删除,双向迭代器。
forward_list
(C++11) :单向版本。 容器适配器(均不支持迭代器):
queue
#include<queue>
:队列(FIFO)。适配双向变长序列式容器,即 deque
(默认)或 list
。 stack
#include<stack>
:栈(LIFO)。适配变长序列式容器,即 deque
(默认)、 vector
或 list
。 priority_queue
#include<queue>
:大根堆。适配随机访问变长序列式容器,即 vector
(默认)或 deque
。 Find
crbegin()
at(idx)
/ operator[idx]
:前者会做越界检查,抛出异常。 front()
, back()
:返回首尾元素引用。 Modify
push_back(x)
/ pop_back()
:均摊常数复杂度。 insert(iter, val)
:于迭代器 iter
处插入,返回指向被插入元素的迭代器。 insert(iter, first, last)
:左闭右开区间插入,返回指向首个被插入元素的迭代器。 注意,此操作 非常数时间复杂度 。 erase(iter)
:于迭代器 iter
处删除,返回指向被删除元素的后一个元素的迭代器。 erase(first, last)
:左闭右开区间删除,返回指向被删除元素的后一个元素的迭代器。 注意,此操作 非常数时间复杂度 。 Size
resize(n)
:改变长度,可指定补充元素默认值。 shrink_to_fit()
:调整为恰好长度。 vector<bool> 被特殊定义,使用方式较为复杂, 不建议使用 .
push_front(x)
, pop_front()
其余与 vector 类似.
top()
push(x)
pop()
front()
push(x)
pop()
std::priority_queue<TypeName, Container, Compare> :类型名,底层容器,比较类型.
大根堆,默认用 < 比较大小,即 Compare 传入 std::less<T> 。亦可选择传入 std::greater<T> 使用 > 作为比较符号,进而构造出小根堆.
函数同 queue ,但 push() / pop() 为对数时间复杂度.
参照 std::less<T> 的实现,自定义比较方式,需传入一个重载了 operator() 的结构体.
insert(iter, val)
/ erase(iter)
:插入与删除变为常数时间复杂度,参见 vector
。 sort(cmp)
:为链表特殊设计的
其余与 deque 类似.
不支持随机访问,双向迭代器,大部分操作为对数时间复杂度,红黑树实现.
set
/ multiset
#include<set>
:元素有序。后者支持同值多元素。 map
/ multimap
#include<map>
:键有序。后者支持同键值多元素。 set<Key, Compare> :类似 priority_queue ,可自定义比较方式.
Find:
crbegin()
count(x)
:返回值为 x
的元素数量。 lower_bound(x)
/ upper_bound(x)
:为 set
特殊定制的对数时间复杂度 lower_bound
和 upper_bound
。 没有 nth_element() ,对数时间复杂度查询第 k 大需手写或使用 pbds 库.
Modify
insert(x)
:插入元素 x。返回 pair<iterator, bool>
,表示插入元素的迭代器与插入是否成功。 对于 multiset
,由于插入不会失败, insert
只返回迭代器。 erase(x)
:删除所有值为 x 的元素,返回删除元素的个数。 erase(iter)
:删除迭代器指向的元素,(C++11) 返回指向被删除元素的后一个元素的迭代器。 erase(first, last)
:左闭右开区间删除,(C++11) 返回指向被删除元素的后一个元素的迭代器。 删除单个值为 x 的元素,可按如下方法进行:
auto it = s . find ( x );
s . erase ( it );
map<Key, T, Compare> :可自定义比较方式.
pair<Key, T>
。 insert(pair<Key, T>)
at[key]
/ operator[key]
:前者会做越界检查,抛出异常。 其余与 set 类似.
单向迭代器,平均常数时间复杂度,Hash 实现.
若不支持 c++11,使用时需引入 TR1 扩展。例如,使用 unordered_map 需引入 #include<tr1/unordered_map> 头文件,使用时需写为 std::tr1::unordered_map .
unordered_set
/ unordered_multiset
#include<unordered_set>
:元素无序。 unorderep_map
/ unordered_multimap
#include<unordered_map>
:键无序。 只有单向迭代器,其余特性与有序版本类似.
此外,可按如下方法自定义相等判定方式和 Hash 函数.
unordered_set<Key, Hash, KeyEqual>
unordered_map<Key, T, Hash, KeyEqual>
如上,可自定义 Hash 函数.
最后此篇关于算法竞赛向C++StandardLibrary使用速查的文章就讲到这里了,如果你想了解更多关于算法竞赛向C++StandardLibrary使用速查的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
#include using namespace std; class C{ private: int value; public: C(){ value = 0;
这个问题已经有答案了: What is the difference between char a[] = ?string?; and char *p = ?string?;? (8 个回答) 已关闭
关闭。此题需要details or clarity 。目前不接受答案。 想要改进这个问题吗?通过 editing this post 添加详细信息并澄清问题. 已关闭 7 年前。 此帖子已于 8 个月
除了调试之外,是否有任何针对 c、c++ 或 c# 的测试工具,其工作原理类似于将独立函数复制粘贴到某个文本框,然后在其他文本框中输入参数? 最佳答案 也许您会考虑单元测试。我推荐你谷歌测试和谷歌模拟
我想在第二台显示器中移动一个窗口 (HWND)。问题是我尝试了很多方法,例如将分辨率加倍或输入负值,但它永远无法将窗口放在我的第二台显示器上。 关于如何在 C/C++/c# 中执行此操作的任何线索 最
我正在寻找 C/C++/C## 中不同类型 DES 的现有实现。我的运行平台是Windows XP/Vista/7。 我正在尝试编写一个 C# 程序,它将使用 DES 算法进行加密和解密。我需要一些实
很难说出这里要问什么。这个问题模棱两可、含糊不清、不完整、过于宽泛或夸夸其谈,无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开,visit the help center . 关闭 1
有没有办法强制将另一个 窗口置于顶部? 不是应用程序的窗口,而是另一个已经在系统上运行的窗口。 (Windows, C/C++/C#) 最佳答案 SetWindowPos(that_window_ha
假设您可以在 C/C++ 或 Csharp 之间做出选择,并且您打算在 Windows 和 Linux 服务器上运行同一服务器的多个实例,那么构建套接字服务器应用程序的最明智选择是什么? 最佳答案 如
你们能告诉我它们之间的区别吗? 顺便问一下,有什么叫C++库或C库的吗? 最佳答案 C++ 标准库 和 C 标准库 是 C++ 和 C 标准定义的库,提供给 C++ 和 C 程序使用。那是那些词的共同
下面的测试代码,我将输出信息放在注释中。我使用的是 gcc 4.8.5 和 Centos 7.2。 #include #include class C { public:
很难说出这里问的是什么。这个问题是含糊的、模糊的、不完整的、过于宽泛的或修辞性的,无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开它,visit the help center 。 已关
我的客户将使用名为 annoucement 的结构/类与客户通信。我想我会用 C++ 编写服务器。会有很多不同的类继承annoucement。我的问题是通过网络将这些类发送给客户端 我想也许我应该使用
我在 C# 中有以下函数: public Matrix ConcatDescriptors(IList> descriptors) { int cols = descriptors[0].Co
我有一个项目要编写一个函数来对某些数据执行某些操作。我可以用 C/C++ 编写代码,但我不想与雇主共享该函数的代码。相反,我只想让他有权在他自己的代码中调用该函数。是否可以?我想到了这两种方法 - 在
我使用的是编写糟糕的第 3 方 (C/C++) Api。我从托管代码(C++/CLI)中使用它。有时会出现“访问冲突错误”。这使整个应用程序崩溃。我知道我无法处理这些错误[如果指针访问非法内存位置等,
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 我们不允许提问寻求书籍、工具、软件库等的推荐。您可以编辑问题,以便用事实和引用来回答。 关闭 7 年前。
已关闭。此问题不符合Stack Overflow guidelines 。目前不接受答案。 要求我们推荐或查找工具、库或最喜欢的场外资源的问题对于 Stack Overflow 来说是偏离主题的,因为
我有一些 C 代码,将使用 P/Invoke 从 C# 调用。我正在尝试为这个 C 函数定义一个 C# 等效项。 SomeData* DoSomething(); struct SomeData {
这个问题已经有答案了: Why are these constructs using pre and post-increment undefined behavior? (14 个回答) 已关闭 6
我是一名优秀的程序员,十分优秀!