C/C++基础整理（三）

本篇主要总结C++中的结构体、标准模板库(STL)、algorithm头文件下常用函数和C++11的部分新特性

结构体

定义

struct Stu
{
    int id;
    char gender;
    char name[20];
};
struct Stu stu1;	//	C语言定义时必须要声明struct
Stu stu2;			//  C++可以直接声明

针对链表节点

struct node
{
    node n;		/*** WRONG ***/   // 不能定义本身node类型
    Stu stu;	// Right
    node* next;		//  可以定义node*型指针变量
};

访问

struct Stu
{
    int id;
    char name[20];
    Stu* next;
} stu, *p;

// 访问普通结构体变量
stu.id;
stu.name;
stu.next;
// 访问结构体指针变量
(*p).id;
(*p).name;
(*p).next;

p->id;
p->name;
p->next;

初始化

stu.id = 1;
stu.gender = 'M';

scanf("%d %c",&stu.id, &stu.gender);

通过构造函数来进行初始化

不需要写返回类型，且函数名与结构体名相同，每个结构体都有个默认的构造函数，如果自己重新定义了构造函数，则不能不经初始化就定义结构体变量 ==> 同Java

#include<iostream>
using namespace std;
 struct Stu
 {
     int id;
     char gender;
     Stu(){}
     Stu(int _id, char _gender){
         id = _id;
         gender = _gender;
     }
 };

int main(void) {
	Stu stu1(1,'M');
	cout << stu1.id << " " << stu1.gender << endl;	 1 M	
	return 0;
}

标准模板库(STL)

string

string：字符串 ==> 头文件 #include<string>

定义string
```
string str;
string str = "abcd";
```

访问遍历

#include <iostream>
#include <string>
using namespace std;

int main(void) {
    string str1 = "abcdef";
    for (int i = 0; i < str1.length(); i++)
    {
      printf("%c",str1[i]);	// abcdef
    }
      // 迭代器访问 ==> 同vector
    for (string :: iterator it = str1.begin(); it != str1.end(); it++)
    {
      printf("%c", *it);		// abcdef
    }

    /* 读入和输出整个字符串，只能用cin和cout */
    string str2;
    cin >> str2;	
      getline(cin, str2); 		// 读取一行的字符串，包括空格
    cout << str2;

    /*将字符串转换成字符数组输出*/
    string str3 = "abcd";
    printf("%s\n", str3.c_str());
    return 0;  
}

常用函数

// + 	==>	字符串拼接
string str1 = "abc", str2 = "def";
string str3 = str1 + str2;	// "abcdef"
// == != < >  ==> 字符串比较(字典序)

// length()/size()
string str = "abcdef";
str.size();		// 6
str.length();	// 6

// clear()	==>	清空string中的数据
str.clear();

// substr()	==>	子串
string str = "abcdef";
string s2 = str.substr(4); 		//  ef  表示从下标4开始一直到结束
string s3 = str.substr(2, 3); 	// cde  表示从下标2开始，3个字符

//find()	==>	查找子串
int main(void) {
    string str = "Thank you for your smile.";
    string str1 = "you";
    string str2 = "me";
      /* str.find(str1),当str1是str的子串时，返回其在str中第一次出现的位置
         如果str1不是str的子串，则返回string::npos */
    if (str.find(str1) != string :: npos)
    {
      cout << str.find(str1) << endl;		// 6
    }
      /* str.find(str1, pos),从str的第pos号位开始匹配str1，返回值与上相同 */
    if (str.find(str1, 7) != string::npos)
    {
      cout << str.find(str1, 7) << endl;	// 14
    }
    if (str.find(str2) != string::npos)
    {
      cout << str.find(str2) << endl;
    }
    else
    {
      cout << "I know there is no position for me." << endl;
    }
    return 0;
}

// insert()		==>	字符串插入
string str = "abcdef";
string str2 = "123";
/* insert(pos,string) ==> 从pos号位置插入字符串string */
str.insert(3, str2);	// str的第3号位置插入字符串str2
cout << str;			// abc123def
/* insert(it,it2,it3) ==> it为原字符串要插入的位置，it2和it3为待插字符串首尾迭代器(左闭右开) */
str.insert(str.begin() + 3, str2.begin() + 1,str2.end());	
cout << str;			// abc23def

// replace()	==> 替换子串
string str = "Maybe you will turn around.";
string str1 = "will not";
string str2 = "surely";
/* str.replace(pos,len,str1) 将str从pos号位置开始、长度为len的子串替换为str1 */
str.replace(10, 4, str1);		//Maybe you will not turn around.
/* str.replace(it,it1,it2) 将str的迭代器[it1,it2)范围的子串替换为str2 */
str.replace(str.begin(), str.begin() + 5, str2);	//surely you will not turn around.

// erase()	==>	删除单个元素、删除一个区间内的所有元素
string str = "abcdef";
/* str.erase(it)删除单个元素 */
str.erase(str.begin() + 4);		// abcdf
/* str.erase(first,last) 删除区间元素[first,last) */
str.erase(str.begin() + 2,str.end() - 1);	//	abf
/* str.erase(pos,length) 删除pos号位开始length长度*/
str.erase(0,2);					// f

vector

vector：变长数组 ==> 头文件#include<vector>

vector<typename>

定义vector

// 直接定义长度为10的int数组，默认这10个元素值都为0
vector<int> v(10); 

// 先定义一个vector变量量v1，然后将长度resize为8，默认这8个元素都是0
vector<int> v1;
v1.resize(8); 

// 在定义的时候就可以对vector变量进行初始化 把100长度的数组中所有的值都初始化为9
vector<int> v3(100, 9);

访问遍历元素

// 通过下标访问
vector<int> vi(10);		//可一开始定义大小，也可不定义
int n = vi[index];		// index在 0 ~ vi.size() - 1

// 迭代器访问1 (迭代器可理解为指针)
// 迭代器 it 的类型就为 vector<int> ::iterator ,vi.begin()是取首元素地址
// 访问元素的值要对it 指针取值，要在前面加星号 所以是cout << *it;
vector<int> ::iterator it = vi.begin();
for (int i = 0; i < 10; i++){
	cout << *(it + i) << " ";	 // 这里可以看出vi[i]和*(it + i)是等价的
}
   
// 迭代器访问2
for (vector<int>::iterator it = vi.begin(); it != vi.end(); it++){
	cout << *it << " ";
}

常用函数

vector<int> vi;

// push_back()  ==>  vector后面追加元素x
for (int i = 0; i < 10; i++){
	vi.push_back(i);	// 0 1 2 3 4 5 6 7 8 9
}

// pop_back()   ==>  删除vector的伪元素
vi.pop_back();		// 删除vi尾元素3

// size()	==>  vector中元素个数
vi.size();		// 9

// begin()  ==>  vector中首元素地址
vi.begin();

// end()	==>  vector中*****最后一个元素的后一个地址*****

// clear()  ==>  清空vector中所有元素
vi.clear();		// vi清空

// insert()	==> 向vector的任意迭代器it处插入元素x，时间复杂度 O(N)
vector<int> vi;
for (int i = 0; i < 10; i++){
	vi.push_back(i);
}
vi.insert(vi.begin() + 2, -1);		// 将 -1 插入vi[2]的位置
for (int i = 0; i < vi.size(); i++){
	cout << vi[i] << " ";		// 0 1 -1 2 3 4 5 6 7 8 9
}

// erase()	==>  删除单个元素、删除一个区间(左闭右开)所有元素
vector<int> vi;
for (int i = 0; i < 10; i++){
	vi.push_back(i);
}
/* 删除单个元素 */
vi.erase(vi.begin() + 2);	// 删除vi[2]
for (int i = 0; i < vi.size(); i++){
	cout << vi[i] << " ";	// 0 1 3 4 5 6 7 8 9
}
/* 删除一个区间内元素 */
vi.erase(vi.begin() + 1, vi.begin() + 4);	// 删除 vi[1] vi[2] vi[3]
for (int i = 0; i < vi.size(); i++){
	cout << vi[i] << " ";	// 0 5 6 7 8 9
}

set

set为集合，自动内部有序且不含重复元素的容器(内部红黑树实现，元素本身有序) ==> 头文件 #include<set>

set<typename>

定义set

set <int> name;
set <double> name;
set <int> a[100];

访问遍历元素 ==> 只能通过迭代器来访问

#include <iostream>
#include <set>
using namespace std;

int main(void) {
    set<int> st;
    st.insert(1);
    st.insert(2);
    st.insert(3);	
    st.insert(4);
    st.insert(5);
    st.insert(5);	//	重复 ，不可插入
    for (set<int> ::iterator  it = st.begin(); it != st.end(); it++)
    {
      cout << *it;	// 1 2 3 4 5
    }
    return 0;
}

常用函数

set <int> st;

// insert(x)  ==>  将x插入set容器中，并自动递增排序和去重 O(logN) 其中N为set内元素个数
st.insert(1);
st.insert(2);
st.insert(3);
st.insert(5);
st.insert(4);	//	顺序不影响
st.insert(5);	//	重复，不可插入		==>  1 2 3 4 5

// find(value)	==>  返回set对应值为value的迭代器
set<int> ::iterator it = st.find(2);
cout << *it;	//	2

// size()	==>	 获得set内元素个数
st.size();	// 5

// clear()	==>  清空set中所有元素
st.clear();	//	清空set

// erase()	==>	 删除单个元素(两种方式)、删除一个区间内(左闭右开)所有元素
int main(void) {
    set<int> st;
    st.insert(1);
    st.insert(2);
    st.insert(3);
    st.insert(4);
    st.insert(5);
      /* 删除单个元素 */
    st.erase(st.find(1));	// 传入迭代器 时间复杂度O(1)
    st.erase(2);			// 传入value 时间复杂度O(logN)
    for (set<int> ::iterator  it = st.begin(); it != st.end(); it++)
    {
      cout << *it << " ";	// 3 4 5
    }
      /* 删除一个区间内所有元素 */
      set<int> ::iterator it = st.find(4);
    st.erase(it, st.end());	// 删除元素4至末尾的元素 
    for (it = st.begin(); it != st.end(); it++)
    {
      cout << *it << " ";	// 3
    }
    return 0;
}

map

map为映射，键值对(内部红黑树实现，元素本身有序) ==> 头文件 #include<map>

map<typename1, typename2> mp

定义map

map<string, int> mp1;		// 映射到字符串时，必须使用string而不使用char[]
map<set<int>, string> mp2;	// 键值也可以是STL容器

访问遍历map

#include <iostream>
#include <map>
using namespace std;

int main(void) {
    map<char, int> mp;
    mp['a'] = 1;
    mp['b'] = 2;
    mp['c'] = 3;
    // 访问map具体key对应的value
    cout << mp['c'] << endl;	// 3
    // 遍历map的key-value
    for (map<char, int> ::iterator it = mp.begin(); it != mp.end(); it++)
    {
      // map中的迭代器，it->first访问键，it->second访问值
      cout << it->first << " " << it->second << endl;	// a 1 b 2 c 3
    }
    return 0;
}

常用函数

map<char, int> mp;
mp['a'] = 1;
mp['b'] = 2;
mp['c'] = 3;
mp['d'] = 4;

// find(key)	==>	返回键为key映射的迭代器 O(logN)
map<char, int> :: iterator it = mp.find('a');
cout << it->first << " " << it->second << endl;	// a 1

// size()	==>	map中映射的个数
mp.size();	// 4

// clear()	==>	清空map中所有元素
mp.clear();

// erase()	==>	删除单个元素、删除一个区间内的所有元素
map<char, int> mp;
mp['a'] = 1;
mp['b'] = 2;
mp['c'] = 3;
mp['d'] = 4;
mp['e'] = 5;
/* mp.erase(it) 出入要删除键值对的迭代器 O(1) */
mp.erase(mp.find('a'));		// 删除 a 1
/* mp.erase(key) 删除键为key的键值对 O(logN) */
mp.erase('b');				// 删除 b 2
/* mp.erase(first, last) 删除[first, last) */
mp.erase(mp.find('d'), mp.end());
for (map<char, int> ::iterator it = mp.begin(); it != mp.end(); it++){
	cout << it->first << " " << it->second << endl;		// c 3
}

queue

queue队列 ==> 先进先出

queue<typename> name ==> 头文件 #include<queue>;

定义queue
```
queue<int> qu;
```

访问遍历 ==> 只能访问队首和队尾的元素

#include <iostream>
#include <queue>
using namespace std;

int main(void) {
    queue<int> qu;
    for (int i = 1; i <= 5; i++)
    {
      	qu.push(i);
    }
    cout << qu.front() << endl;		// 1
    cout << qu.back() << endl;		// 5
    return 0;
}

常用函数

// push(x)	==>	将x进入队列
queue<int> qu;
for (int i = 1; i <= 5; i++){
		qu.push(i);		// 1 2 3 4 5
}

// front()	==>	队首元素	back()	==>	队尾元素
cout << qu.front() << endl;		// 1
cout << qu.back() << endl;		// 5

// size()	==>	队列中元素个数
qu.size();	// 5

// empty()	==>	检测队列是否为空
qu.empty()	// 0(false) => 不空 1(true) => 空

// pop()	==>	队首元素出队
queue<int> qu;
for (int i = 1; i <= 5; i++)
{
		qu.push(i);
}
for (int i = 1; i <= 3; i++)
{
		qu.pop();
}
cout << qu.front() << endl;	// 4
cout << qu.back() << endl;	// 5

stack

stack 栈 ==> 先进后出

stack<typename> name ==> 声明头文件 #include<stack>

定义stack

#include<iostream>
#include<stack>
using namespace std;

int main(void){
    stack<int> st;
}

访问遍历 ==> 栈顶元素

#include<iostream>
#include<stack>
using namespace std;

int main(void) {
    stack<int> st;
    for (int i = 1; i <= 5; i++)
    {
      st.push(i);
    }
    cout << st.top() << endl;	// 5
    return 0;
}

常用函数

// push(x)	==> 将x入栈
stack<int> st;
for (int i = 1; i <= 5; i++)
{
		st.push(i);
}

//	top()	==>	取栈顶元素
cout << st.top() << endl;	// 5

// pop()	==>	弹出栈顶元素
st.pop();
st.pop();
cout << st.top() << endl;	// 3

// empty()	==>	检测栈是否为空
cout << st.empty();		// 0(false) =>不空 1(true) => 空

// size()	==> 栈内元素个数
cout << st.size();		// 3

algorithm

max()、min()、abs()

max(x,y)，min(x,y)分别返回x和y中最大值和最小值，参数必须是两个(可以是浮点数)

abs(x)返回x(必须是整型)的绝对值，浮点数绝对值用#include<math.h>头文件下fabs

#include<iostream>
#include<algorithm>
using namespace std;

int main(void){
    int x = 1;
    int y = -2;
    cout << max(x, y) << endl;	// 1
    cout << min(x, y) << endl;	// -2
    cout << abs(y) << endl;			// 2
}

sort()

sort(首元素地址(必填),尾元素地址下一个地址(必填),比较函数(非必填)) ==> 默认从小到大排序

主要是对一个数组进行排序( int arr[] 数组或者 vector 数组都⾏)， vector 是容器，要⽤ v.begin() 和 v.end() 表示头尾;而 int arr[] 用 arr 表示数组的首地址， arr+n 表示尾部

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(int a, int b) { 		// cmp函数返回的值是bool类型
		return a > b; 			// 从⼤到小排列
}

int main() {
    /* 容器的排序 */
    vector<int> v(10);
    for (int i = 0; i < 10; i++) { 
      cin >> v[i];
    }
    sort(v.begin(), v.end());// 因为这里没有传入参数cmp，所以按照默认，v从小到大排列
    int arr[10];
    for (int i = 0; i < 10; i++) {
      cin >> arr[i];
    }
    sort(arr, arr + 10, cmp); // arr从大到小排列，因为cmp函数排序规则设置了从大到⼩
    return 0;
}

注意: sort 函数的 cmp 必须按照规定来写，即必须只是 > 或者 < ，⽐比如: return a > b; 或者 return a < b; ⽽不能是 <= 或者 >= ，因为快速排序的思想中， cmp 函数是当结果为 false 的时候迭代器器指针暂停开始交换两个元素的位置，当 cmp 函数 return a <= b 时，若中间元素前面的元素都比它小，⽽而后⾯的元素都跟它相等或者⽐它⼩，那么 cmp 恒返回 true ，迭代器指针会不断右移导致程序越界，发⽣生段错误~

结构体数组排序

#include <iostream>
#include <algorithm>
using namespace std;

struct node{
  	int x, y;
}ssd[10];

bool cmp(node a, node b);
int main(void)
{
  	ssd[0].x = 2;
  	ssd[0].y = 2;
  	ssd[1].x = 1;
  	ssd[1].y = 3;
  	ssd[2].x = 3;
  	ssd[2].y = 1;
  	sort(ssd, ssd + 3, cmp);
  	for (int i = 0; i < 3; i++)
  	{
    	cout << ssd[i].x << " " << ssd[i].y << ",";	//  3 1,2 2,1 3
  	}
	}
// 按x值从大到小排序
bool cmp(node a,node b){
  	return a.x > b.x;
}

结构体二级排序实现

#include <iostream>
#include <algorithm>
using namespace std;

struct node{
    int x, y;
}ssd[10];

bool cmp(node a, node b);
int main(void)
{
    ssd[0].x = 2;
    ssd[0].y = 2;
    ssd[1].x = 1;
    ssd[1].y = 3;
    ssd[2].x = 2;
    ssd[2].y = 1;
    sort(ssd, ssd + 3, cmp);
    for (int i = 0; i < 3; i++)
    {
        cout << ssd[i].x << " " << ssd[i].y << ","; // 2 1,2 2,1 3
    }
}
// 先按x从大到小排序,当x相等情况下，按照y从小到大排序
bool cmp(node a,node b){
    if (a.x != b.x)
    {
        return a.x > b.x;
    }else
    {
        return a.y < b.y;
    }
}

C++11

auto

auto 是C++11里面的新特性，可以让编译器根据初始值类型直接推断变量的类型。比如这样

auto x = 3;			// x是int
auto y = 3.14;	// y是double

// 本来set的迭代器遍历要这样写:
for(set<int>::iterator it = s.begin(); it != s.end(); it++) {
		cout << *it << " ";
}
// 现在可以直接替换成这样的写法:
for(auto it = s.begin(); it != s.end(); it++) {
		cout << *it << " ";		
}

to_string()

to_string 的头文件是 #include <string> ， to_string 最常用的就是把一个 int 型变量或者一个数字转化为 string 类型的变量，当然也可以转 double 、 float 等类型的变量，以下是示例代码:

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s1 = to_string(123); 				// 将123这个数字转成字符串 cout << s1 << endl;
    string s2 = to_string(4.5); 				// 将4.5这个数字转成字符串 cout << s2 << endl;
    cout << s1 + s2 << endl; 						// 将s1和s2两个字符串拼接起来并输出
    printf("%s\n", (s1 + s2).c_str()); 	// 如果想⽤printf输出string，得加⼀个.c_str()
    return 0; 
}

stoi、stod

使⽤ stoi 、 stod 可以将字符串string转化为对应的 int 型、 double 型变量，这在字符串处理的很

多问题中很有帮助~以下是示例代码和⾮法输入的处理方法:

#include <iostream>
#include <string>
using namespace std;
int main() {
    string str = "123"; 
  	int a = stoi(str); cout << a;
    str = "123.44"; 
  	double b = stod(str); 
  	cout << b;
    return 0; 
}
/*
stoi如果遇到的是非法输入 (比如stoi("123.4")，123.4不是一个int型变量): 
1.会自动截取最前面的数字，直到遇到不是数字为止 (所以说如果是浮点型，会截取前面的整数部分)
2.如果最前面不是数字，会运行时发生错误

stod如果是非法输入:
1.会自动截取最前面的浮点数，直到遇到不满足浮点数为止 
2.如果最前⾯不是数字或者小数点，会运行时发生错误 
3.如果最前面是小数点，会自动转化后在前面补0
*/

相应的还有：

stof (string to float)
stold (string to long double)
stol (string to long)
stoll (string to long long)
stoul (string to unsigned long)
stoull (string to unsigned long long)

unordered_map、unordered_set

unordered_map 在头文件 #include <unordered_map> 中

unordered_set 在头文件#include<unordered_set>中

unordered_map 和 map (或者 unordered_set 和 set )的区别是， map 会按照键值对的键 key 进行排序( set ⾥面会按照集合中的元素⼤小进⾏排序，从小到大顺序)，而 unordered_map (或者 unordered_set )省去了这个排序的过程，如果偶尔刷题时候用 map 或者 set 超时了，可以考虑用 unordered_map (或者 unordered_set )缩短代码运行时间、提⾼代码效率~至于用法和map 、 set 是一样的

NULL和nullptr

C中的NULL

在C语言中，NULL通常被定义为：#define NULL ((void*)0)

所以说NULL实际上是一个空指针，如果在C语言中写入以下代码，编译是没有问题的，因为在C语言中把空指针赋给int和char指针的时候，发生了隐式类型转换，把void指针转换成了相应类型的指针。
```
int  *pi = NULL;
char *pc = NULL;
```
C++中的NULL

但是问题来了，以上代码如果使用C++编译器来编译则是会出错的，因为C++是强类型语言，void*是不能隐式转换成其他类型的指针的，所以实际上编译器提供的头文件做了相应的处理：
```
#ifdef __cplusplus
#define NULL 0
#else
#define NULL ((void *)0)
#endif
```
可见，在C++中，NULL实际上是0.因为C++中不能把void*类型的指针隐式转换成其他类型的指针，所以为了结果空指针的表示问题，C++引入了0来表示空指针，这样就有了上述代码中的NULL宏定义。
```
#include <iostream>
using namespace std;
 
void func(void* i)
{
	cout << "func1" << endl;
}
 
void func(int i)
{
	cout << "func2" << endl;
}
 
void main(int argc,char* argv[])
{
	func(NULL);				// func2
	func(nullptr);		// func1
	getchar();
}
```
我们对函数func进行可重载，参数分别是void*类型和int类型，但是运行结果却与我们使用NULL的初衷是相违背的，因为我们本来是想用NULL来代替空指针，但是在将NULL输入到函数中时，它却选择了int形参这个函数版本，所以是有问题的，这就是用NULL代替空指针在C++程序中的二义性。
C++中的nullptr

为解决NULL代指空指针存在的二义性问题，在C++11版本(2011年发布)中特意引入了nullptr这一新的关键字来代指空指针，从上面的例子中我们可以看到，使用nullptr作为实参，确实选择了正确的以void*作为形参的函数版本。

总结

NULL在C++中就是0，这是因为在C++中void* 类型是不允许隐式转换成其他类型的，所以之前C++中用0来代表空指针，但是在重载整形的情况下，会出现上述的问题。所以，C++11加入了nullptr，可以保证在任何情况下都代表空指针，而不会出现上述的情况，因此，建议以后还是都用nullptr替代NULL吧，而NULL就当做0使用。

C++内存分配

new/delete

new/delete是c++中的关键字
使用new操作符申请内存分配时无须指定内存块的大小，编译器会根据类型信息自行计算
new操作符内存分配成功时，返回的是对象类型的指针，类型严格与对象匹配，无须进行类型转换，故new是符合类型安全性的操作符
new内存分配失败时，会抛出bac_alloc异常

malloc/free

malloc/free是c中的系统函数，当然c++中也支持malloc/free,不过效率不及new/delete
malloc则需要显式地指出所需内存的尺寸
malloc内存分配成功则是返回void * ，需要通过强制类型转换将void*指针转换成我们需要的类型
malloc分配内存失败时返回NULL

C/C++基础整理（三）

结构体

定义

访问

初始化

标准模板库(STL)

string

vector

set

map

queue

stack

algorithm

max()、min()、abs()

sort()

结构体二级排序实现

C++11

auto

to_string()

stoi、stod

unordered_map、unordered_set

NULL和nullptr

C++内存分配

new/delete

malloc/free

感谢您的支持，我会继续努力的!