c/c++笔记

一、常规

1.1 c

头文件后缀名： .h

源文件后缀名： .c

1.2 c++

头文件后缀名： .h, .hpp, .hxx

源文件后缀名：.cpp, .cc, .cxx, .C .c++

.hpp: 声明和实现都有

.inl: 内联函数

1.3 内联函数

  使用inline修饰的具体函数实现，非声明。编译期间对于编译器承认的inline函数，将会直接把代码拷贝到函数调用位置。

1.4 重定义

   #include会将头文件复制，同一个东西头文件实现一次，源文件实现一次就会触发重定义。

1.5 main函数

二、编译

2.1 编译器

2.2 定义与声明

  源文件中的全局变量 int a; 形式，默认修饰符为extern。

2.3 模块化设计

  1. 模块即是一个.c文件和一个.h文件的结合，头文件(.h)中是对于该模块接口的声明，一般都用extern进行修饰；
  2. 供给其它模块调用的外部函数及全局变量需在.h中文件中冠以extern关键字声明；
  3. 模块内的函数和全局变量需在.c文件开头冠以static关键字声明；
  4. 永远不要在.h文件中定义全局变量！
  5. 头文件中可以定义的实体，得有头文件保护，否则会重定义。
    • 值在编译时就已知的const 变量的定义可以放到头文件中
    • 结构体，类的定义可以放到头文件中
    • inline 函数

三、关键字

3.1 new/delete

  编译器关键字，会调用构造器与析构器。malloc/free为库函数实现。

3.2 const

// 限定内容
const int*p;
int const *p;

// 限定指针
 int*const p;

// 都限定
const int*const p;

不可变的 := 可变的 ，反过来不行。

1. c

1. c++

3.3 override

  配合 virtual 关键字使用；修饰子类 override 函数。

3.4 volatile

3.5 static

3.6 extern "C"

  会指示编译器这部分代码按C语言的进行编译，而不是C++的;能够正确实现C++代码调用其他C语言代码。

3.7 extern

  使用include将另一个文件全部包含进去可以引用另一个文件中的变量，但是这样做的结果就是，被包含的文件中的所有的变量和方法都可以被这个文件使用，这样就变得不安全。如果只是希望一个文件使用另一个文件中的某个变量还是使用extern关键字更好。

3.8 friend

  可以让外部函数或者外部类，访问私有类的私有属性与函数。

3.8 储存类型符

3.9 cin

1. 简介

2. 用法

  1. cin >>

    • 连续从键盘读取想要的数据，以空格、tab 、换行为分隔符。

          char a;
    int b;
    float c;
    string 
    cin>>a>>b>>c;

    • 当 cin >> 从缓冲区中读取数据时，若缓冲区中第一个字符是空格、tab或换行这些分隔符时，cin>> 会将其忽略并清除，继续读取下一个字符; 若缓冲区为空，则继续等待。但是如果读取成功，字符后面的 空白符号 是残留在缓冲区的，cin>> 不做处理。

    • 不想略过空白字符，那就使用 noskipws 流控制。

    • cin >>的返回值为 cin ;当输入 EOF （windows:ctrl+z， Linux:ctrl+d）时， cin >> 会返回0。

      int a;
// 当输入 EOF 时，可以终止循环
while（cin >> a）{

}

  2. cin.get()

      缓冲区没有东西时，会堵塞等待。

    int get();
istream& get(char& var);
istream& get( char* s, streamsize n );
istream& get( char* s,  streamsize  n, char delim);

读取字符 :

```c++

#include <iostream>
using namespace std;

int main() {
    char a;
    char b;
    a=cin.get();
    cin.get(b);
    cout << a << b <<endl;
    return 0;
}

```

- <font color="#f44336">从输入缓冲区读取单个字符时不忽略分隔符，直接将其读取。</font>

读取行
c++ istream& get(char* s, streamsize n) istream& get(char* s, size_t n, char delim)
- s ，接收字符串用的数组
- n ，读取个数。实际读取个数为 n - 1 ，留了一个给 \0
- delim ，指定终止符
- 换行符(结束符)会被留在缓冲区， 但末尾其余空白符会被读取。

  1. cin.getline（） 读取行

    istream& getline(char* s, streamsize count); //默认以换行符结束
istream& getline(char* s, streamsize count, char delim);
    • 换行符(结束符)会被清理掉， 但末尾其余空白符会被读取。
    • getline(cin,string,"结束符") 功能更强。传入的是 cin ，不是 stdin

3. cin 清空输入缓冲区

  1. 方法一
istream &ignore(streamsize num=1, int delim=EOF);

#include <limits>
numeric_limits<std::streamsize>::max();
  1. 方法二
fflush(stdin);

3.10 ::

int x;  // Global x 
 
int main() 
{ 
  int x = 10; // Local x 
  cout << "Value of global x is " << ::x; 
  cout << "\nValue of local x is " << x;  
  return 0; 
} 

class Test 
{   
public: 
    static int x; 
};

int Test::x = 1;

void main(){
    Test::x;
}


#include<iostream> 
using namespace std; 
 
class outside 
{ 
public: 
      int x; 
      class inside 
      { 
      public: 
            int x; 
            static int y;  
            int foo(); 
 
      }; 
}; 
int outside::inside::y = 5;  
 
int main(){ 
    outside A; 
    outside::inside B; 
 
}

3.10 include

四、类

4.1 指针与引用

储存 初始化 二次赋值 形式
指针 有储存空间 NULL 可以 类名 *
引用 无空间，别名 已有的对象 不行 类名 &

   c语言没有引用机制，是靠c++扩展实现。

4.2 对象与类

描述 储存
类 模板，包括属性和行为 无
对象 类的实例化，主要是数据的集合 主要只储存了属性，储存位置看具体情况 ; 函数放代码段，所有对象通用

4.3 智能指针

  通过库函数，管理对象指针。

4.4 野指针

  野指针不是NULL指针，是未初始化或者未清零的指针，在程序中乱指。

4.5 指针与数组

二次修改 参与运算 sizeof
指针 可以 可以 指针的字节
数组 不行 可以 声明空间的字节

4.6 字符串

1. c风格

#include <string.h>

// 创建
char str[] = "RUNOOB";
char *str =  "fuck you";
char str[7] = {'R', 'U', 'N', 'O', 'O', 'B', '\0'};

// 拷贝字符串
strcpy(char *dest, const char *src); // 将src拷贝到dest，拷贝以 \0 作终止;
char *strncpy(char *dest, const char *src, size_t n); // n指定长度，更安全

// 拼接字符串
char *strcat(char *dest, const char *src); // 往dest上加字符串

// 字符串长度
strlen(str); // \0 终止

// 比较字符串
int strcmp(const char *s1, const char *s2); // 相同返回 0

// 查找
char *strchr(const char *str, int c); //返回第一个字符位置，没有返回NULL
char *strstr(const char *haystack, const char *needle); // 返回第一个字符串位置，没有返回NULL

2. c++字符串

#include <string>

// 创建
string str; // s1的值为NULL
string str = "c plus plus";
string str(c风格);

// 字符串长度
str.length();

// 转c风格
str.c_str();

// 访问字符
str[i];

// 数字转字符串
string to_string(int value);
string to_string(long value);
string to_string(double value);

// 字符转数字
atoi(const char*);
stoi(const string&);
strtoi(const char *);

// 插入
string& insert (size_t pos, const string& str);

// 删除
string& erase (size_t pos = 0, size_t len = npos);

// 获取子串
string substr (size_t pos = 0, size_t len = npos) const;

// 查找 返回第一个找到的位置，没找到返回一个无穷数
size_t find (const string& str, size_t pos = 0) const;
size_t find (const char* s, size_t pos = 0) const;
find_first_of(const string& str); // 子字符串和字符串共同具有的字符在字符串中首次出现的位置

五、面向对象

5.1 重载，重写，重定义

  函数名相同就会屏蔽父类同名函数

注 :
   用户能定义自己的C语言库函数，连接器在连接时自动使用这些新的功能函数。这个过程叫做重定向C语言库函数。

5.2 虚函数

  虚函数是动绑定，运行时确定。

5.3 继承

  当私有继承和保护继承时，父类指针(引用)无法指向子类。默认为私有继承。 防止多重继承，出现属性多次定义，继承时，还要使用 virtual 进行修饰。
   在子类中均存在但不可访问

5.4 重载/多态

5.5 构造/析构函数

5.6 静绑定与动绑定

  上面的函数也是能正常运行的，因为obj在编译时静绑定。

5.7 构造函数

六、内存

6.1 c++

6.3 内存泄露/栈溢出

6.4 字符存储编码

6.5 对象的内存分布

alt text

6.6 代码地址

七、进程线程

7.1 进程

1. 创建

  创建的是原进程的子进程，子进程会复制父进程的PCB(进程控制块)，二者之间代码共享，数据独有，拥有各自的进程虚拟地址空间。

#include <unistd.h>
pid_t fork(void);

2. 终止

3. 等待

  如果子进程先于父进程退出，而父进程并没有关心子进程的退出状况，从而无法回收子进程的资源，就会导致子进程变成僵尸进程。进程等待的作用就是父进程对子进程收尸！父进程通过进程等待的方式，回收子进程的资源，获取子进程的退出状态。

4. 进程退出信息status

7.2 进程状态

7.3 进程状态变化

八、STL

8.1 简介

  STL（Standard Template Library），即标准模板库，是一个具有工业强度的，高效的C++程序库。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。

  主要构成有六大组件:

8.2 容器（Container）

   set map multi set multimap 通过红黑实现，无序 unoder_map unorder_set 通过哈希表实现。

8.3 分配器

  容器类自动申请和释放内存，无需new和delete操作。

8.4 迭代器

    Container c;
    Container::iterator it;
    for(it=c.begin();it!=c.end();it++){
        // vector 获取值
        *it;
        // map 获取键值对
        it->first;
        it->second;
    }

8.5 算法

1. 头文件

  算法部分主要由头文件，和组成。

2. 常用算法

   STL常用算法

8.6 仿函数

   钩子函数，可以当参数传递，让具体算法进行调用。 系统定义好的仿函数: <functional>

    #include <stdio.h>
    #include <algorithm>
    #include <vector>

    class Compare{
        public:
        bool operator()(int a,int b){
            return a > b;
        } 
    };

    int main(int argn,const char* args[]){
        vector<int> vec(5,1);
        vec[0] = 2;
        vec[1] = 1;
        vec[2] = 9;
        vec[3] = 3;
        vec[4] = 1;

        // 排序算法
        sort(vec.begin(),vec.end(),Compare());

        // 实际的函数调用
        bool flag = Compare()(10,12); 
    }

注意：
   Compare()是定义了一个临时对象，作为参数传递给了 sort()；若sort()没有采用引用传递，则对象将是值传递。

8.7 容器适配器

  对基础容器进行功能扩展，标准库提供了三种顺序容器适配器:

容器 头文件 默认容器 可选容器 说明
queue <queue> deque list、deque 基础容器必须提供push_front()运算
priority_queue <queue> vector vector、deque 基础容器必须提供随机访问功能
stack <stack> deque vector、list、deque

8.8 栈 stack

#include <stack>
#include <vector>
stack<int> s;
stack< int, vector<int> > stk;  //覆盖基础容器类型，使用vector实现stk
s.empty();  //判断stack是否为空，为空返回true，否则返回false
s.size();   //返回stack中元素的个数

s.pop();    //删除栈顶元素，但不返回其值
s.top();    //返回栈顶元素的值，但不删除此元素

s.push(item);   //在栈顶压入新元素item

8.9 队列 queue

queue<int> q; //priority_queue<int> q;
q.empty();  //判断队列是否为空
q.size();   //返回队列长度

// 出队和入队
q.push(item);   //对于queue，在队尾压入一个新元素
q.pop();  //删除 queue 中的第一个元素

// 队列访问
q.front();  //返回队首元素的值，但不删除该元素
q.back();   //返回队尾元素的值，但不删除该元素

8.10 vector

#include <vector>

// 创建
vector<T> vec;
vector<T> vec(int nSize); // 指定容器初始大小
vector(int nSize,const T& initValue):// 指定容器初始值

// 增加
vec.push_back(const T& item); // 在屁股添加
iterator vec.insert(iterator it,const T& item); // 迭代器指定位置插入元素

// 删除
vec.pop_back(); // 删除屁股
iterator erase(iterator it); // 删除迭代器指定位置元素
vec.clear(); // 删除全部

// 查找
vec[i];
vec.at(i); // 会检查是否越界，提高稳定性

// 容器内储存元素个数
vec.size();

// 容器是否有东西
vec.empty();

// 迭代器位置
vector<int>::iterator it = vec.begin(); // 起始位置
vector<int>::iterator it = vec.end(); // 结束位置
int a = *it; //获取值
*it += 1; 

// 定义二维数组
 vector< vector<int> > obj(row); // row定义行数

排序：

8.11 map/multimap

//头文件
#include<map>
 
// 创建
map<int, string> map;

// 使用{}赋值是从c++11开始的，因此编译器版本过低时会报错，如visual studio 2012
map<int, string> map = {
                { 2015, "Jim" },
                { 2016, "Tom" },
                { 2017, "Bob" } };

map<int, string,Compare> map; // 指定排序规则

// 迭代器
map<int,string>::iterator it = map.begin(); 
map<int,string>::iterator it = map.end();
it->first; // key
it->second; // 值

// 添加key value 
pair<iterator,bool> state;// 能判断是否插入成功;插入key存在时，返回false
state = map.insert(pair<int, string>(1, "student_one")); 
state = map.insert(map<int, string>::value_type (1, "student_one")); 

map[key] = value; // key存在就覆盖，key没有就创建

// 查找
// 关键字查询，找到则返回指向该关键字的迭代器，否则返回指向end的迭代器
// 根据map的类型，返回的迭代器为 iterator 或者 const_iterator
iterator find (const key_type& k);
const_iterator find (const key_type& k) const;

// 删除
// 删除迭代器指向位置的键值对，并返回一个指向下一元素的迭代器
iterator erase( iterator pos );

 // 根据Key来进行删除， 返回删除的元素数量，在map里结果非0即1
size_t erase( const key_type& key );

// 删除一定范围内的元素，并返回一个指向下一元素的迭代器
iterator erase( const_iterator first, const_iterator last );
 
// 清空map，清空后的size为0
void clear();

// 查询map是否为空
bool empty();
 
// 查询map中键值对的数量
size_t size();

// 查询关键字为key的元素的个数，在map里结果非0即1 ，可用于检测key是否包含
size_t count( const Key& key ) const;

排序：

class Compare{
public:
    bool operator()(const string & a,const string & b) const {
        return a.c_str()[0] < b.c_str()[0];
    } 
};
map<string,int,Compare> names;

8.12 set/multiset

#include <set>

// 创建
set<string> names;
set<string,Compare> names; // 指定排序规则 

// 添加
pair<set<int>::iterator, bool> ret = names.insert(name);

// 删除
names.erease(name);
names.clear();

// 查找，找不到返回 end()
set<string>::iterator it = names.find(name);

// 迭代器
set<string>::iterator it = names.begin();
set<string>::iterator it = names.end();
*it;

// 计数
names.count(name);

names.size();
names.empty();

排序：

class Compare{
public:
    bool operator()(const string & a,const string & b) const {
        return a.c_str()[0] < b.c_str()[0];
    } 
};
set<string,Compare> names;

8.13 deque

    #include <deque>

    // 创建
    deque<string> que;
    
    // 首尾操作 
    que.push_back(item);
    que.pop_back();
    que.push_front();
    que.pop_back();
    que.front();
    que.back();

    // 删除
    que.erase(it);
    que.clear();

    // 查找 没有查找 用 #include<algorithm> 库中的 find

九、工具

9.1 math

#include<math.h>

// 绝对值
int abs(int);
double fabs(double);

// 四舍五入
double round(double);

// 取整
double ceil(double num); // 向上取整
double floor(double num);// 向下取整

// 余数
double fmod(double num，double base);
%; 只能用于int;

9.2 regex

#include <regex>

// 定义表达式
regex reg("[a-z0-9]+");

// 是否匹配
bool regex_match(string,regex);//全匹配
bool regex_search(string,regex);//子串匹配，只匹配第一次找到的

// 捕获
bool reg_search(string，smatch，regex);
smatch.size(); //匹配到的个数: 表达式匹配 + 捕获匹配
smatch.str(0); // 整个正则匹配到的部分
smatch.str(i); // 0之后的，都是捕获部分
smatch.prefix().str(); // 未匹配的前部分
smatch.prefix().str();// 未匹配的后部分

9.2 动态规划

动态规划问题的一般形式就是求最值。

1. 解题框架

  1. 明确 base case: 初始条件
  2. 明确「状态」: 推进子问题向大问题演变的变量。
  3. 明确「选择」: 也就是导致「状态」产生变化的行为。「状态」能取哪些值
  4. 定义 dp 数组/函数: dp值 = f（当前状态）
    • dp函数: 参数就是上面说到的「状态」。函数的返回值就是题目要求我们计算的量。
    • dp 数组：当状态为「状态」，问题结果为dp[状态]
# 初始化
dp[] = init

# 边界条件
dp[0][0][...] = base

# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

2. 流程方向

3. 重复子问题的确定

    dp[i][j] = min{
        dp[i-1][j] + 1,
        dp[i][i-1] + 1,
        dp[i-1][j-1] + 1
    }

  当从dp[i-1][j-1]过度到dp[i][j]的求解有多种路径时，就存在解重叠的情况。采用备忘录和dp数组解决。

4. 状态遍历顺序

dynamic

  1. 确定二维表dp[][]初始值
  2. 确定递推式dp[i][j]的依赖情况（上图左边）
  3. 根据依赖关系填充二维表，满足横向填充或者纵向填充
    // i = 0, j = 0 的情况是边界条件，已经初始化好了。 
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n;j++){
            dp[i][j] = f(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]);
        }
    }