跳到主要内容 初学者从 C 转 C++ 指南 | 极客日志
C++ 算法
初学者从 C 转 C++ 指南 本文面向 C 语言初学者,介绍转向 C++ 的基础知识与常用技巧。内容包括 C++ 输入输出、string 类处理、sort 排序、数组去重、二分查找等基础操作,以及 STL 容器如 queue、stack、map、set 的使用方法。此外还涉及 IO 加速、lambda 表达式、优先队列自定义排序及 stringstream 流处理等进阶内容,旨在帮助读者快速掌握 C++ 核心特性并应用于算法竞赛或开发中。
为什么要转 C++
首先,对于 C 语言,它初见虽然简单,但是深入后确实非常的难并且不方便的。
例如 C 语言使用排序 qsort 必须要写排序函数,但是用 C++ 的 std::sort 就很方便,而且对于一些常见的数据结构 C++ 也有相对应的 STL 容器如:queue,stack,vector。最重要的还是 C++ 在 C++11 之前和 C 语言相差不大,如果仅仅是打算法竞赛那么 C++=C + STL,转起语言来几乎完全没有压力。
C++ 语言基础
对于初学者而言,我们只需要记住如下代码:
#include <bits/stdc++.h>
using namespace std;
int main (void ) {
return 0 ;
}
初看这个和 C 语言极为相似除了 using namespace std; 和 #include <bits/stdc++.h>。
对于 using namespace std; 我们只需要记住不需要了解,如果有人想了解的话可以去搜下 C++ 的命名空间。
然后对于 #include <bits/stdc++.h> 是 C++ 的万能头 (竞赛专用,你下的 gcc 里面是没有这个的,需要额外配置),后续内容中如果学习 C++ 只为了打算法竞赛,那么后续所有头文件都不需要记忆。
C++ 如何输入输出
#include <iostream>
#include <string>
using namespace std;
int main (void ) {
int n;
string s;
cin >> n;
cin >> s;
cout << n << "\n" << s << endl;
}
上述头文件的 iostream 就相当于 C 的 stdio.h,而 string 是 C++ 特有的字符串对象。
其中 C 输入为 scanf 而且还需要记住类似于 %d,%s 之类的格式化符号,而 C++ 之间 cin 就可以了,输出的话直接 cout。
C++string 相关
对于 C 语言我们处理字符串很痛苦 (虽然 C++ 也很痛苦),但 C++ 处理字符串却比 C 语言简单多了。
以下列举一些本人常用的字符串处理方法。
去除前导空格
#include <iostream>
#include <string>
std;
{
string s;
( (cin, s)) {
pos = s. ( );
s. ( , pos);
std::cout << s << ;
}
std::cout << ;
}
微信扫一扫,关注极客日志 微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
Markdown 转 HTML 将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML 转 Markdown 互为补充。 在线工具,Markdown 转 HTML在线工具,online
HTML 转 Markdown 将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML 转 Markdown在线工具,online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online
using
namespace
int main (void )
while
getline
int
find_first_not_of
" "
erase
0
"\n"
"hello , world"
提示:C++ 的 cin 会自动去除掉前导空格。
如果是去除前导 0 的话直接把 " " 换成 "0" 就可以了。
提取和拼接子串 #include <iostream>
#include <string>
using namespace std;
int main (void ) {
string s = "hello , world" ;
string s1 = s.substr (0 , 5 );
string s2 = s.substr (6 );
string s3 = s1 + s2;
cout << s1 << s2 << "\n" ;
cout << s3;
}
string 截取子串的成员函数为 substr 相关解释已经在注释当中。
一些常用的 C++ 操作
C++sort(排序函数的用法) #include <algorithm>
#include <iostream>
#include <string>
using namespace std;
bool comp (int & a, int & b) {
return a > b;
}
int main (void ) {
int a[1000 ] = {0 , 1 , 1 , 4 , 5 , 1 , 4 };
sort (a + 1 , a + 1 + 6 );
for (int i = 1 ; i <= 6 ; i++) cout << a[i];
std::cout << "\n" ;
sort (a + 1 , a + 1 + 6 , comp);
for (int i = 1 ; i <= 6 ; i++) cout << a[i];
}
C++ 的 sort 排序的时间复杂度是 O(nlogn) 比大家常用的冒泡排序快速多了,所有如果要有排序的话推荐一直用这个,至于 comp 函数,我这里使用了 & 也就是引用,这样可以避免复制数值,但是大家在平时使用时不添加引用符也可以正常运行。
数组去重 #include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main (void ) {
int a[1000 ] = {0 , 1 , 1 , 4 , 5 , 1 , 4 };
sort (a + 1 , a + 1 + 6 );
int * pos = unique (a + 1 , a + 1 + 6 );
int new_count = pos - (a + 1 );
for (int i = 1 ; i <= new_count; i++) std::cout << a[i] << " " ;
}
#include <algorithm>
#include <iostream>
#include <vector>
int main (void ) {
std::vector<int > arr = {0 , 1 , 1 , 4 , 5 , 1 , 4 };
std::sort (arr.begin () + 1 , arr.begin () + 1 + 6 );
auto pos = unique (arr.begin () + 1 , arr.begin () + 1 + 6 );
arr.erase (pos, arr.end ());
return 0 ;
}
unique 函数返回的是检查范围的数据,如果有相同的则移到传入的末尾,之后直接计算剩余元素数量后使用去重过后的数组就行了,详细操作见上述代码。
二分查找 #include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
using namespace std;
int main (void ) {
int a[105 ];
for (int i = 1 ; i <= 100 ; i++) a[i] = i;
int * lb1 = std::lower_bound (a + 1 , a + 101 , 25 );
int index1 = lb1 - a;
std::cout << "elem is" << *(lb1) << "index is" << index1 << endl;
int * lb2 = std::upper_bound (a + 1 , a + 101 , 25 );
int index2 = lb2 - a;
std::cout << "elem is" << *(lb2) << "index is" << index2 << endl;
int * result = std::lower_bound (a + 1 , a + 101 , 101 );
if (result == a + 101 ) {
std::cout << "lower_bound(101) return a+101\n" ;
}
return 0 ;
}
STL 容器相关
常见的 STL 容器使用 这部分设计数据结构,例如:栈,队列,红黑树,二叉搜索树。
常见队列 #include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
int main (void ) {
std::queue<int > q;
for (int i = 0 ; i < 10 ; i++) q.push (i);
while (!q.empty ()) {
std::cout << q.front () << " " << q.back () << "\n" ;
q.pop ();
}
std::deque<int > qu;
for (int i = 0 ; i < 10 ; i++) {
qu.push_back (i);
}
while (!qu.empty ()) {
std::cout << qu.front () << " " << qu.back () << "\n" ;
qu.pop_back ();
qu.pop_front ();
}
}
C++ 的队列使用和声明极为简单,其中内部实现为一个数组,是根据先进先出 (FIFO) 思想设计的,所有上述操作时间复杂度都为 O(1)。
如果使用了 using namespace std;,那么上述的的 "std::" 可以去掉。
栈 #include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
int main (void ) {
stack<int > s;
for (int i = 0 ; i < 10 ; i++) s.push (i);
while (!s.empty ()) {
std::cout << s.top () << " " ;
s.pop ();
}
}
栈和队列的使用方式差不多,最具有分辨力的区别是:栈是根据先进后出 (FILO) 的思想设计的。
map(键值对) 键值对又称字典,是一个相互进行映射 (一个键对应一个值) 的 STL 容器,内部实现为红黑树或 (二叉搜索树),其插入的时间复杂度为 O(logn) 是一个在算法竞赛中很实用的 STL 容器。
#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
using namespace std;
int main (void ) {
std::map<int , int > mp;
int temp = 114514 ;
for (int i = 0 ; i < 10 ; i++) {
if (i < 4 ) mp[i] = temp * (10 - i);
else mp.insert ({i, temp * (10 - i)});
}
for (auto & [key, value]: mp) {
std::cout << "mp[" << key << "] = " << value << "\n" ;
}
if (mp.find (2 ) != mp.end ()) std::cout << "Yes" ;
if (mp.find (10 ) == mp.end ()) std::cout << "No" ;
std::cout << "\n" ;
int idx = 0 ;
while (1 ) {
mp.erase (idx);
idx++;
if (mp.empty ()) {
std::cout << "已弹出所有元素" ;
break ;
}
}
return 0 ;
}
我们这里只讲 map 的插入,删除和遍历以及查找这种基础内容。
还有一种 map 是 unordered_map,其结构和 map 很像,这里不再介绍。
unordered_map 和 map 的区别是,map 是红黑树,而它的实现为哈希表,查找,插入的速度为 O(1),并且 unordered_map 是无序的。
set(集合) set 和 map 极为相似,你可以把 set 理解为只有一个 value 的的 map(一般 map 有键和值),其中时间复杂度和 map 基本一致,这里不再介绍。
#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
using namespace std;
int main (void ) {
set<int > s;
for (int i = 0 ; i < 100 ; i++) s.insert (0 );
s.insert (5 );
s.insert (3 );
s.insert (114514 );
for (auto i : s) cout << i << " " ;
cout << "\n" ;
if (s.find (3 ) != s.end ()) cout << "Yes" << " " ;
if (s.find (6 ) == s.end ()) cout << "No" << " " ;
cout << "\n" ;
cout << s.size () << "\n" ;
for (auto i : s) s.erase (i);
cout << s.size () << "\n" ;
return 0 ;
}
C++ 进阶相关
标准输入输出加快 ios::sync_with_stdio (false );
cin.tie (nullptr );
cout.tie (nullptr );
lambda 表达式 (无名函数) std::vector<int > arr = {1 , 1 , 4 , 5 , 1 , 4 };
std::sort (arr.begin (), arr.end (), [](int & a, int & b) {
return a > b;
});
优先队列自定义排序 struct Node {
int x, y;
bool operator <(Node &a) const {
return x < a.x;
};
};
int main (void ) {
std::priority_queue<Node> q;
}
对于我们自定义的结构体它是无法直接比较大小的,那么直接使用 operator 进行重载,可以使它们在一个陌生的结构体有明确的大小顺序。
由于作者赖的写了,这里简单的介绍下优先队列。优先队列就是我们所说的堆,其中内部是二叉搜索树,插入和弹出都是 logn 的复杂度,堆顶元素默认是最大 (最小) 元素。
stringstream 流 #include <vector>
#include <string>
#include <sstream>
#include <iostream>
using namespace std;
int main (void ) {
std::string s = "1 2 3 4 5 6" ;
std::vector<int > arr;
stringstream stream (s) ;
int num;
while (stream >> num) {
arr.push_back (num);
}
for (auto i : arr) cout << i << " " ;
cout << "\n" ;
string data = "apple,banana,orange,grape" ;
stringstream ss (data) ;
string fruit;
while (getline (ss, fruit, ',' )) cout << fruit << endl;
return 0 ;
}
结语 以上内容属于 C++ 基础内容,如果以后有从事 C++ 相关行业的话属于基础中的基础,相反则需要掌握一些 C++ 基础内容,虽然文章中分为了基础和进阶,但即便是只打算打一些简单的算法比赛,以上编码技巧也只属于基础内容。