c/c++问题集三

1、结构体与联合

结构体：将不同类型的数据组合成一个整体，是自定义类型;  共同体：不同类型的几个变量共同占用一段内存

1）结构体中的每个成员都有自己独立的地址，它们是同时存在的； 共同体中的所有成员占用同一段内存，它们不能同时存在；

2）sizeof(struct)是内存对齐后所有成员长度的总和，sizeof(union)是内存对齐后最长数据成员的长度

2、push_back和emplace_back

• push_back()：向容器中加入一个右值元素(临时对象)时，首先会调用构造函数构造这个临时对象，然后需要调用拷贝构造函数（或转移构造函数）将这个临时对象放入容器中。原来的临时变量释放。这样造成的问题就是临时变量申请资源的浪费。
• emplace_back()：在插入元素的时候直接构造（原地构造），只调用一次构造函数，不需要触发拷贝构造和转移构造。而且调用形式更加简洁，直接根据参数初始化临时对象的成员。
• 内存优化方面和运行效率方面更优。

elections.emplace_back("Nelson Mandela", "South Africa", 1994); // 传入的是 创建这个对象 需要的 构造参数

elections.push_back(President("Franklin Delano Roosevelt", "the USA", 1936));  // 传入的是一个对象

elections.emplace_back(President("Franklin Delano Roosevelt", "the USA", 1936));  // 同上一样

3、解决hash冲突的方法

1）开放定址法（再散列）：当发生地址冲突时，按照某种探测方法继续探测哈希表中的其他存储单元，直到找到空位置为止。

（1）线性探测：按递增顺序，在原来哈希值的基础上往后加一个单位，直至不发生哈希冲突。　 　　

（2）再平方探测：在原来哈希值的基础上先加1的平方个单位，若仍然存在则减1的平方个单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。 　　

（3）伪随机探测：通过随机函数随机生成一个数，在原来哈希值的基础上加上随机数，直至不发生哈希冲突。

2）再哈希法：对于冲突的哈希值再次用一个不同哈希函数进行哈希处理，直至没有哈希冲突。不易产生聚集，但是增加计算时间，同时需要准备许多哈希函数。

3）链地址法（拉链法）：对于相同的哈希值，使用链表进行连接，再将链表的头指针存放在哈希表的对应单元中。拉链法处理冲突简单，且无堆积现象，不要求表长大于关键字数量，关键字多的情况节省空间，适用于经常进行插入和删除的情况。

4）公共溢出区：将哈希表分为公共表和溢出表两部分，凡是发生冲突的元素，一律填入溢出表。

哈希函数（散列函数）

• 直接寻址法
• 数字分析法
• 平方取中法
• 折叠法
• 随机数法
• 除留余数法

查询性能：

• 散列函数是否均匀
• 处理冲突的方法
• 散列表的装填因子 ：α= 填入表中的元素个数 / 散列表的长度

4、宏的作用

（1）定义用来将一个标识符定义为一个字符串或常量，注意与const的区别

（2）定义预处理器变量

（3）定义条件编译

（4）定义宏函数，

宏函数在**预处理**时，同函数定义的代码来替换函数名，将函数代码段嵌入到当前程序，不会产生函数调用，所以会省去普通函数保留现场恢复现场的时间，但因为要将定义的函数体嵌入到当前程序，所以不可避免的会占用额外的存储空间

与inline函数的区别：

**内联函数**的作用主要就是使用在一些短小而使用非常频繁的函数中，在调用内联函数的地方将内联函数内的语句Copy到调用函数的地方，从而提高了效率，减少函数调用的开销。比如内联函数inline int func(int x){return x\*x;} 在调用的时候cout<<func(x)<<endl，在编译时将被展开为：cout<<(x\*x)<<endl;

• 宏是在预处理时进行的机械替换，内联是在编译时进行的
• 内联函数有参数匹配检查、语法判断等功能，但宏没有，
• 内联函数是真正的函数，满足函数的性质，比如有返回值、参数列表这些；
• 宏不能访问对象的私有成员，但是定义在类内的内联函数可以访问。
• 内联函数可以进行调试，宏不可以；

5、软链接和硬链接

• 软链接则是系统新建一个链接文件，内容是指向另一个文件的位置，系统看到软链接后自动跳到对应的文件位置处进行处理，类似于Windows操作系统中的快捷方式；
• 硬链接可认为是一个文件拥有两个文件名，为文件开设一个新的目录项，以文件副本的形式存在。但不占用实际空间。
• 此外，软链接可对文件和文件夹，而硬链接仅针对文件。软连接可跨文件系统，硬链接不行；软链接可以对一个不存在的文件名进行链接
• 删除一个文件之后，指向其的软链接失效，硬链接依然有效

6、智能指针

防止申请的动态内存没有被正确释放，导致内存泄漏。

智能指针可以自动释放new分配的内存，不需要手动delete这些new分配的内存

智能指针的实质是一个对象，行为却表现的像一个指针

auto_ptr:c++98版本，在c++11中已不再使用，管理权转移的思想，若通过拷贝构造和赋值操作符赋值它们，原指针会变成null ，而 复制所得的指针将取得资源的唯一控制权。

unique_ptr：c++11版本，独占对所指对象的独有权，不允许其他的智能指针共享其内部的指针，禁止进行拷贝构造和拷贝赋值的操作，但是unique_ptr允许通过函数返回给其他的unique_ptr，还可以通过std::move来把所有权转让到其他的unique_ptr，注意，这时它本身就不再拥有原来指针的所有权了。将一个 unique_ptr 赋值给另一个时，如果源 unique_ptr 是个临时右值，编译器允许这么做

//所有权的变化  
int *p_i = u_i2.release();	//释放所有权，而不会释放内存的
unique_ptr<string> u_s(new string("abc"));  
unique_ptr<string> u_s2 = std::move(u_s); //所有权转移(通过移动语义)，u_s所有权转移后，变成“空指针” 
u_s2.reset(u_s.release());	//所有权转移
u_s2=nullptr;//显式销毁所指对象，同时智能指针变为空指针。与u_s2.reset()等价

shared_ptr：允许多个指针指向同一个对象，通过引用计数的方式来实现多个shared_ptr对象之间的资源共享。

注意：

shared_ptr内部维护了一个引用计数变量，该变量是指针类型int*，只有指针类型才能保证拷贝自同一对象的不同对象享有相同的引用计数变量。

当对象被销毁时，会将对象的引用计数减一

当引用计数为0时，释放所申请的资源；不为0就不释放

循环引用的问题

class AA{
    public:
    shared_ptr<BB> bptr;
    ~A(){cout<<"~A()"<<endl;}
}
 
class BB
{
    public:
    shared_ptr<AA> aptr;
    ~B( ){cout<<"~BB()"<<endl;}
}
int main() {
    shared_ptr<AA> aa(new AA());
    shared_ptr<BB> bb(new BB());
    aa->bptr = bb;
    bb->aptr = aa;
    return 0;
}

即A内部有指向B，B内部有指向A，这样对于A，B必定是在A析构后B才析构，对于B，A必定是B析构后才析构A，这就是循环引用的问题，违反常规，导致内存泄露。

解决方法：weak_ptr的辅助类，配合shared_ptr而引入，是一种弱引用，指向shared_ptr所管理的对象，在weak_ptr类中不提供引用计数机制，仅起指针的作用，观测资源的使用情况。

class AA
{
public:
    weak_ptr<BB> bptr;
    ~AA( ){cout<<"~AA()"<<endl; }
};
class BB
{
public:
    weak_ptr<AA> aptr;
    ~BB(){cout<<"~BB()"<<endl; }
};
 
int main( ) {
shared_ptr<AA> aa(new AA());
shared_ptr<BB> bb(new BB());
aa->bptr = bb;
bb->aptr = aa;
cout<<aa.use_count()<<endl;
cout<<bb.use_count()<<endl;
return 0;
}

7、vector的内存分配

就是一个动态数组，里面有一个指针指向一片连续的内存空间。

特点：内存空间只会增长不会减少

• vector有两个函数，一个是capacity()，返回对象缓冲区（vector维护的内存空间）实际申请的空间大小，另一个size()，返回当前对象缓冲区存储数据的个数。对于vector来说，capacity是永远大于等于size的，档capacity和size相等时，vector就会扩容，capacity变大。
• 调用push_back当空间不够装下数据时会自动申请另一片更大的空间（一般是原来的两倍），然后把原有数据拷贝过去，之后在拷贝push_back的元素，最后要析构原有的vector并释放原有的内存空间
• 当调用erase或clear释放或者说是删除里面的数据时，其内存空间并不会释放，仅仅只是清空了里面的元素。
• 如果需要空间动态缩小，vector<Point>().swap(pointVec); //或者pointVec.swap(vector<Point> ())，vector的默认构造函数建立临时vector对象
• 如果vector中存放的是指针，那么当vector销毁时，这些指针指向的对象不会被销毁，内存也不会被释放，需要手动delete。

8、红黑树

作为C++ STL关系式容器（如set,multiset,map, multimap）的底层实现。

• 每个节点或是红色的,或是黑色的.
• 根节点是黑色的.
• 每个叶节点（NULL）是黑色的.
• 如果一个节点是红色的，则它的两个孩子节点都是黑色的.
• 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点.

红黑树可以在O(log n)时间内做查找，插入和删除

• 基本操作：左旋，右旋，重新着色
• 目的：红黑树在插入（新插入节点都为红节点），删除过程中可能会破坏原本的平衡条件导致不满足红黑树的性质，这时候一般情况下要通过左旋、右旋和重新着色这个三个操作来使红黑树重新满足平衡化条件

9、STL相关

（1）序列式容器

顺序访问元素的容器，vector、list（双向链表）、deque(双端队列）

vector：底层数据结构：数组

• 随机访问：O(1)
• 随机插入与删除：O(n)，中间插入会引起后面数据的拷贝，尾部可快速增删

（2）关联式容器

无序关联容器

按键值排好序，底层数据结构均为红黑树

set,multiset,map, multimap，元素是否唯一的区别

无序关联容器

从C++11开始提供的容器，无序的容器，unordered_map、unordered_multimap、unordered_set、unordered_mutiset

• 特性：查找、删除、插入：理论上为O(1)，但是实际上要考虑碰撞的问题

底层数据结构为哈希表，解决冲突的策略使用的是拉链法，通过在不同桶中新建节点的方式来避免冲突

（3）容器适配器

在上述容器的接口上进行封装和改写实现

Stack

底层容器：deque

Queue

底层容器：deque

priority_queue

底层容器：vector实现的Heap

STL提供了六大组件，彼此之间可以组合套用，这六大组件分别是:容器、算法、迭代器、仿函数、适配器、空间配置器。

• 容器：各种数据结构，如vector、list、deque、set、map等,用来存放数据，从实现角度来看，STL容器是一种class template。
• 算法：各种常用的算法，如sort、find、copy、for_each。从实现的角度来看，STL算法是一种function template.
• 迭代器：扮演了容器与算法之间的胶合剂，迭代器提供了一种方法，使得它能够按照顺序访问某个容器所含的各个元素，但无需暴露该容器的内部结构，它将容器和算法分开，让二者独立设计。共有五种类型，从实现角度来看，迭代器是一种将operator* , operator-> , operator++,operator–等指针相关操作予以重载的class template. 所有STL容器都附带有自己专属的迭代器，只有容器的设计者才知道如何遍历自己的元素。
• 仿函数：行为类似函数，可作为算法的某种策略。从实现角度来看，仿函数是一种重载了operator()的class 或者class template
• 适配器：一种用来修饰容器或者仿函数或迭代器接口的东西。
• 空间配置器：负责空间的配置与管理。从实现角度看，配置器是一个实现了动态空间配置、空间管理、空间释放的class tempalte.

10、map为何使用红黑树，而不用其他二叉树

对于STL中的set和map来说，需要进行频繁的插入和删除

AVL是一种严格平衡二叉树，因此在增加或者删除节点的时候，旋转的次数比红黑树要多，影响性能，只适合查找较多但插入、删除不多的操作。当然，由于AVL高度平衡，因此AVL的Search效率更高啦。

红黑树也是一种平衡二叉树，但不追求"完全平衡"，它只要求部分达到平衡

在增删节点时候旋转次数会降低，任何不平衡都会在三次旋转之内解决，因此，更适合插入、删除操作较多的结构。

红黑树，读取略逊于AVL，维护强于AVL，综合来看更适合STL场景。

11、DDoS攻击

DDos全名Distributed Denial of Service，翻译成中文就是分布式拒绝服务。指的是处于不同位置的多个攻击者同时向一个或数个目标发动攻击，是一种分布的、协同的大规模攻击方式。单一的DoS攻击一般是采用一对一方式的，它利用网络协议和操作系统的一些缺陷，采用欺骗和伪装的策略来进行网络攻击，它在短时间内发起大量请求，使网站服务器充斥大量要求回复的信息，消耗网络带宽或系统资源，导致网络或系统不胜负荷以至于瘫痪而停止提供正常的网络服务

# SYN Flood进行DDoS攻击的实现原理 SYN Flood是一种利用TCP协议缺陷，发送大量伪造的TCP连接请求，从而使得被攻击方资源耗尽（CPU满负荷或内存不足）的攻击方式。

一次正常的建立TCP连接，需要三次握手：客户端发送SYN报文，服务端收到请求并返回报文表示接受，客户端也返回确认，完成连接。

SYN Flood 就是用户向服务器发送报文后突然死机或掉线，那么服务器在发出应答报文后就无法收到客户端的确认报文（第三次握手无法完成），这时服务器端一般会重试并等待一段时间后再丢弃这个未完成的连接。

一个用户出现异常导致服务器的一个线程等待一会儿并不是大问题，但恶意攻击者大量模拟这种情况，服务器端为了维护数以万计的半连接而消耗非常多的资源，结果往往是无暇理睬客户的正常请求，甚至崩溃。从正常客户的角度看来，网站失去了响应，无法访问。

如何防范？

1、防火墙

2、充足的网络带宽保证

3、CDN

CDN 指的是网站的静态内容分发到多个服务器，用户就近访问，提高速度。因此，CDN 也是带宽扩容的一种方法，可以用来防御 DDOS 攻击。