一. 基础篇

基础问题

todo:

结构体和共用体的 size 是如何计算的
类的 size 是如何计算的

友元类和友元函数

能访问私有成员
破坏封装性
友元关系不可传递
友元关系的单向性
友元声明的形式及数量不受限制

C++ 中的友元

virtual 关键字

C++ 中的 virtual 关键字

简单介绍一下虚函数表与虚函数指针
单继承时的虚函数表和多继承时的虚函数表有什么区别
为什么虚函数表指针的类型为void *
为什么虚函数表前要加const
虚函数中的默认参数
静态函数可以被声明为虚函数吗
构造函数可以为虚函数吗
析构函数可以为虚函数吗
虚函数可以为私有函数吗
虚函数可以被内联吗
纯虚函数与抽象类的基本概念
为什么不要重写非虚函数

override 关键字

从C++11起，引入了新的关键字override，主要用于紧随成员函数声明或定义内成员函数的声明器之后使用。
在成员函数声明或定义中，override确保该函数为虚并覆写（overrride）来自基类的虚函数。override是在成员函数声明器后使用时才拥有特殊含义的标识符，其他情况下不是保留的关键字。

struct A
{
    virtual void foo();
    void bar();
};

struct B : A
{
    void foo() const override; // 错误： B::foo 不覆写 A::foo（签名不匹配）
    void foo() override; // OK ： B::foo 覆写 A::foo
    void bar() override; // 错误： A::bar 非虚
};

final 关键字

指定派生类不能覆写虚函数，或类不能被继承。
在虚函数声明或定义中使用时，final确保函数为虚且不可被派生类覆写，否则程序生成编译时错误。
在类定义中使用时，final指定此类不可出现于另一类的定义的 base-specifier-list 中（换言之，不能从它派生出其他类），否则程序生成编译时错误。
final是在用于成员函数声明或类头部时有特殊含义的标识符，其他语境中它非保留关键字，可用于命名对象或函数。

struct Base
{
    virtual void foo();
};

struct A : Base
{
    void foo() final; // A::foo 被覆写且是最终覆写
    void bar() final; // 错误：非虚函数不能被覆写或是 final
};

struct B final : A // struct B 为 final
{
    void foo() override; // 错误： foo 不能被覆写，因为它在 A 中是 final
};
struct C : B // 错误： B 为 final
{
};

explicit 关键字

当类的构造函数只有 一个参数 时, C++ 默认会对其调用执行隐式的类型转换. 这时候, 可以使用explicit关键字修饰构造函数, 防止函数参数的隐式转换. (多个参数不涉及隐式转换问题)
explicit关键字只能用于类内部的单参数构造函数的声明上, 而不能用于其他函数
Effective C++建议, 除非有一个好的理由允许构造函数被用于隐式类型转换, 否则应该将其声明为explicit.
还有一个例外情况, 就是如果构造函数除了第一个参数以外, 剩余参数都具有默认值, 那么此时, explicit也有效

extern 关键字

C++ 中的 extern 关键字

extern 关键字的主要作用是什么?
如何令 const 对象可以在多个文件中共享
一个源文件定义了char a[6], 在另一个文件使用extern char *a进行声明, 可以吗?
在 C++ 程序中调用被 C 编译器编译后的函数, 为什么要加 extern “C”
当函数提供方单方面修改函数原型时, 使用方却没有修改, 这时候编译会怎么样? 链接时会怎么样? 如何解决?
extern 和 static 可以同时修饰一个变量吗?

const 关键字

C++ 中的const关键字

修饰普通类型的变量: 变量会变成常量, 其值不能再被更改
修饰指针变量: 常量指针, 指向常量的指针, 指向常量的常量指针.
修饰函数参数: 值传递(无需const, 因为自带保护作用), 指针/引用传递(可防止数据被意外篡改)
修饰函数返回值: 内置类型(加不加const区别不大), 自定义类型, 指针/引用.
修饰类成员函数

static 关键字

C++ 中的static关键字

static 关键字的作用是什么
都有哪些存储持续性类型和链接性类型
全局变量的链接性是怎么样的? 全局常量呢?
函数存储持续性和是否受static关键字影响? static关键字修饰函数时, 其什么作用?
静态成员数据和静态成员函数有哪些特点?
可以用 const static 来修饰成员数据和成员函数吗?

静态局部变量保存在全局数据区, 而不是保存在栈中, 每次的值保持到下一次调用, 知道下次赋新值

类的静态成员在类实例化之前就存在了, 并分配了内存, 而函数的静态局部变量会在执行函数时才分配内存.

const全局常量的链接性为内部, 因此可以放在头文件中而不会重定义

sizeof 关键字

sizeof 对于指针和数组名的不同反应.

数组的内存空间要么在静态存储区中(全局数组), 要么在栈中. 而指针可以随时指向任意类型的内存块.
在使用sizeof运算符时, 数组返回的是整个数组所占的字节数, 指针返回的是指针变量本身的字节数(由处理器的位数决定). C++/C 语言没有办法知道指针所指的内存容量, 除非在申请内存时记住它, 注意当数组作为函数的参数进行传递时, 该数组名就会自动退化为同类型的指针, 也就是说此时再使用sizeof时, 返回的是指针变量的大小, 而不是数组大小

sizeof 对结构体和共用体的反应:

在计算结构体时, 要在总字节大小的基础之上, 4字节或者8字节上对齐.

在计算共用体时, 要在最大字节大小的基础之上, 4字节或者8字节上对齐.

引用

C++ 引用

什么是引用? 声明和使用引用时要注意哪些问题?
引用和指针的关系与区别?
将引用作为函数参数有哪些特点?
将引用作为函数返回值类型的优势和注意事项?
在什么时候需要使用常引用?
什么是右值引用?

this指针

this 指针

函数指针和函数对象(仿函数)

Cpp-函数指针和函数对象

构造函数

C++ 中的构造函数和析构函数

子类析构时要调用父类的析构函数吗?

内联函数

虚函数可以是内联函数吗
对于常见的主流编译器, 写不写 inline 有什么影响

内存分配和动态内存

C++ 中的内存分配和动态内存

描述 C++ 的内存分配方式以及它们之间的区别?
自由存储区和堆的区别
new 和 malloc 的区别
new 运算符, operator new, new 表达式
delete 和 delete []的区别
如何限制一个类对象只在栈(堆)上分配空间?

C++ 浮点数

控制输出的小数位数:

1	std::cout << std::fixed << std::setprecision(3) << 3.1415 << endl;

math

设计模式

都有哪些设计模式? 具体的实现方法是什么?

二. 字符串及模板篇

字符串

basic_string 模板类

stringstream 字符串流

更详细的总结可见:C++ string 完整笔记

模板

详细总结请见: C++ 标准模板库STL完整笔记

容器

顺序式容器:
array ,vector ,list ,deque
关联式容器:
map, unordered_map, multimap, unordered_multimap, set, unordered_set, multiset, unordered_multiset
容器适配器:
queue, priority_queue

标准库中各个容器的数据结构是什么?
vector 的容量增长机制是怎样的? 内存分配机制是怎样的?
为什么vector::push_back()的复杂度是分摊之后的 $O(1)$?
设计一道可以使用low_bound/upper_bound轻松解决的算法题
实现一下set_intersection()/set_union()/merge()
迭代器在什么情况下会失效?
标准库的线程安全性
list 的insert()/erase()与 vector 相比哪个快?

算法

排序

算法	功能	复杂度
sort	默认将区间升序排序	$O(nlogn)$
is_sorted	默认检查区间元素是否按照升序排列	$O(n)$
is_sorted_until	返回满足范围 [first, it) 已排序的最后的迭代器it.	$O(n)$
partial_sort	将区间内较小的k个元素排序, 对数复杂度	$O(klogk)$
partial_sort_copy	先将区间内的元素复制, 然后再进行部分排序, 部分排序的数量根据目标范围决定	$O(nlog(\min(n, n_{copy})))$
stable_sort	稳定排序, 将区间内的元素排序, 同时保持相等的元素之间的顺序不变	$O(nlogn^2)$, 若额外内存可用, 则为 $O(nlogn)$
nth_element	对给定的区间部分排序, 使得第n个元素位于排序后的正确位置上, 并且前半段的元素小于等于后半段元素	$O(n)$, 基于 Partition 算法实现

调用示例:

vector<int> vec = {2,5,8,5,3,2,3,6,8};
std::sort(vec.begin(), vec.end(),
        [](int a, int b){return a >= b;});
std::is_sort(vec.begin(), vec.end(),
        [](int a, int b){return a >= b;});
auto it = std::is_sort_until(vec.begin(), vec.begin()+3, vec.end(),
        [](int a, int b){return a >= b;});
if (it = vec.end()) std::cout << *it << std::endl;
std::partial_sort(vec.begin(), vec.begin()+3, vec.end(),
        [](int a, int b){return a >= b;});
std::partial_sort_copy(vec.begin(), vec.end(), copy.begin(), copy.end(),
        std::greater<int>()); // 注意这里的greater带有(), 说明是函数, 而不是类型
std::stable_sort(vec.begin(), vec.end(),
        [](int a, int b){return a >= b;});
std::nth_element(vec.begin(), vec.begin() + vec.size() / 2, vec.end()
        std::greater<int>());

查找/搜索

算法	功能	复杂度	返回值
binary_search	检查等价于 value 的元素是在 [first, last) 中, 要求范围内元素必须有序	$O(logn)$	bool
equal_range	返回 [first, last) 中等价于 value 的元素范围, 要求范围内元素必须有序	$O(logn)$	由 lower_bound 和 upper_bound 组成的 pair 对
lower_bound	返回 [first, last) 中首个不小于(大于等于) value 的元素迭代器, 要求范围内元素必须有序	$O(logn)$	对应元素的迭代器, 或者 last(没找到)
upper_bound	返回 [first, last) 中首个大于 value 的元素迭代器, 要求范围内元素必须有序	$O(logn)$	对应元素的迭代器, 或者 last(没找到)
search	搜索指定序列, 或者搜索 Searcher 构造函数中指定的模式	$O(N_1\times N_2)$	返回找到的首个子序列的起始迭代器, 或者 last(没找到)
search_n	在 [first, last) 中搜索 count 个值为 value 的序列	$O(n)$	返回找到的序列的起始迭代器, 或者 last(没找到)
find	返回 [first, last) 中满足特定判别标准的首个元素	$O(n)$	返回首个满足条件的迭代器, 或者 last(没找到)
find_if	同上	-
find_if_not	同上	-	-
find_end	在范围 [first, last) 中搜索序列 [s_first, s_last] 的最后一次出现	$O(n_s\times (n - n_s +1))$	返回找到序列的开始迭代器, 或者 last(没找到)
find_first_of
adjacent_find
count
count_if
all_of
any_of
none_of
mismatch
for_each
for_each_n

最值

算法	功能	复杂度	返回值

max
max_element
min
min_element
minmax
minmax_element
clamp: 在一堆边界值间夹住一个值

划分

算法	功能	复杂度	返回值
partition
is_partitioned
partition_copy
stable_partition
partition_point

排列

算法	功能	复杂度	返回值
is_permutation
next_permutation
prev_permutation

比较

算法	功能	复杂度	返回值
equal
lexicographical_compare
compare_3way

lexicographical_compare_3way | | | |

集合

以下算法均要求范围内的元素已经有序
| 算法 | 功能 | 复杂度 | 返回值 |
| :—: | :—: | :—: | :—: |
| merge | | | |
| inplace_merge | | | |
| includes | | | |
| set_difference | | | |
| set_intersection | | | |
| set_symmetric_difference | | | |
| set_union | | | |

堆

算法	功能	复杂度	返回值
is_heap
is_heap_until
make_heap
push_heap
pop_heap
sort_heap

其他


// generate: 根据函数结果将其值赋给范围内的每个元素
std::srand(0);
std::generate(vec.begin(), vec.end(),
        [](){return std::rand() % 100;});
// generate_n: 根据函数结果将其值赋给范围起始的前n个元素

三. 高级篇

lambda 表达式

C++中的lambda表达式

C++中的协变与逆变

https://www.jianshu.com/p/db76a8b08694

智能指针

C++ 中的智能指针

unique_ptr: 当进行赋值时, 会将旧指针的所有权转让, 使得 对于特定的对象, 只能有一个智能指针可以拥有它. unique_ptr 相比于 auto_ptr 会执行更加严格的所有权转让策略
shared_ptr: 通过引用计数(reference counting), 跟踪引用特定特定对象的智能指针数. 当发生赋值操作时, 计数增1, 当指针过期时, 计数减1. 仅当最后一个指针过期时, 才调用 delete.
weak_ptr: 不控制对象声明周期的智能指针, 它指向一个 shared_ptr 管理的对象, 而进行内存管理的只有 shared_ptr. weak_ptr 主要用来帮助解决循环引用问题, 它的构造和析构不会引起引用计数的增加或者减少. weak_ptr 一般都是配合 shared_ptr 使用, 通常不会单独使用.

C++ 的智能指针会带来循环引用问题, 引发内存泄露.

两个类, 类里面各有两个 shared_ptr, 然后一个对象互相指向, 造成循环引用.
sp1 指向 sp2, sp2 指向 sp1, 这样二者的引用计数都是 2, 到到期时, 二者的引用数目都不能达到 0, 因此不会自动释放内存.

解决方法, 用 weak_ptr

栈内存与文字常量区

C++ 11 新特性

右值引用, 泛化常量表达式
初始化列表, 类型推导(auto), 范围for循环, lambda表达式, final关键字
override
空指针 nullptr
default, delete
长整数(long, long)
智能指针, 哈希表(unordered_map)