金山办公二面复习 - Powered by MinDoc

C++无锁设计

#include <atomic>
#include <iostream>

template <typename T>
class LockFreeStack {
private:
    struct Node {
        T data;
        Node* next;
        Node(T value) : data(value), next(nullptr) {}
    };

    std::atomic<Node*> head;

public:
    LockFreeStack() : head(nullptr) {}

    void push(T value) {
        Node* newNode = new Node(value);
        newNode->next = head.load();
        // CAS操作：比较并交换
        //head先比较它的值是否等于newNode->next，如果是则将head改为newNode,否则一直等待
        while (!head.compare_exchange_weak(newNode->next, newNode)); 
    }

    bool pop(T& result) {
        Node* topNode = head.load();
        while (topNode && !head.compare_exchange_weak(topNode, topNode->next)); // CAS操作
        if (topNode) {
            result = topNode->data;
            delete topNode;
            return true;
        }
        return false;
    }
};

C++为什么比其他高级语言运行的快

C++编译器最终生成的是机器码，直接与底层硬件交互，而其他语言可能需要依赖如虚拟机（java）,无需而外面的解释或者翻译
手动内存管理，不依赖语言层面的垃圾回收机制，虽说有垃圾回收机制能简化开发，但回收机制不可能是虽说想回收就回收的，c++能更加细粒度的控制分配和释放。
更少的运行检查，其他语言可能会依赖于语言机制的检查，而C++全由程序员检查
编译器优化，比如GCC和Clang的-o2和-o3优化选项等。

编译器优化

编译器优化主要是最终生成的机器码的优化

常量传播：
指的是编译器中的常量值会被替换到所有它们用到的地方，减少内存访问和计算开销
内联展开：
将函数调用展开成为函数体代码，从而消除调用开销，这种优化非常适合短小、频繁调用的函数。
循环优化
循环展开：将循环体复制多分，减少循环控制变量的增减和跳转开销
循环合并：将两个变量相同的数组循环合并成一个，较少不必要的循环控制开销
循环分裂：复杂循环分成小循环，优化内存访问的局部性
死代码消除

内存可见性

内存可见性主要是说并发编程中，一个线程修改了变量后，其他线程在其寄存器或者缓存中保留了内存位置的副本，导致其他线程无法及时对修改可见。

产生此问题的原因主要是多处理器的cpu缓存导致、或者说是编译器优化（为了提高性能可能会重拍指令执行顺序，使变量的复制和读写顺序变化）、内存屏障
解决方案是用std::atomic原子操作、互斥锁

区分（）和{}不同初始化

结论：

圆括号不会检查变窄的转换，花括号不允许，无法通过编译

C++规定凡是能解析成声明的东西必须被解析为声明。因此：

Widget w2();  //本来是要调用默认构造的，但是被解析成函数声明
Widget w2{};  //此方式能够避免这个问题

3.存在的问题：

构造函数调用，只要不包含std::initializer_list形参，花括号和圆括号初始化结果一样
如果有std::initializer_list形参，使用花括号就会更倾向于此，甚至普通构造函数和移动构造函数也会被劫持，总之只有没办法转为参数列表，编译器才会选其他构造函数。如：

class Widget { 
public:  
    Widget(int i, bool b);      //同上
    Widget(int i, double d);    //同上
    Widget(std::initializer_list<long double> il);      //新添加的
}; 


Widget w1(10, true);    //使用圆括号初始化，同之前一样
                        //调用第一个构造函数

Widget w2{10, true};    //使用花括号初始化，但是现在
                        //调用带std::initializer_list的构造函数
                        //(10 和 true 转化为long double)

Widget w3(10, 5.0);     //使用圆括号初始化，同之前一样
                        //调用第二个构造函数 

Widget w4{10, 5.0};     //使用花括号初始化，但是现在
                        //调用带std::initializer_list的构造函数
                        //(10 和 5.0 转化为long double)

什么是静态多态

就是在编译期就能够进行类型绑定，核心思想是通过CRTP（奇异递归模版模式）来实现。
CRTP的思想：将派生类自身作为模版参数传递给基类，从而使积累的方法可以在编译器访问到派生类的实现。
代码示例：

template<typename Derived>
class Base{
public:
    void interface(){
        static_cast<Derived*>(this)->doSomething();
    }

    void doSomething()
    {
        cout<<"默认实现";    
    }
};

class Derived:public Base<Derived>
{
public:
    void doSomething()
    {
        cout<<"继承类实现";    
    }
};

class Derived2 : public Base<Derived2> {
    // 使用基类的默认 implementation 实现
};

int main()
{
    Derived d;
    d.interface();    //调用的是集成类的实现

    Derived2 d2;
    d2.interface(); // 输出 "Base implementation"
    return 0;
}

C++的发展方向的看法

简化语法和提高易用性：auto、lambda、智能指针等
性能优化和零开销抽象（使用抽象时在编译、运行时不会带来任何额外性能损耗，及和低级别的等价代码没有性能显著差异）

对MVC的理解，工作中哪个用了MVC。

作中的技术突破，什么功能做了比较有成就感？（不是业务逻辑的）

从图片挂靠功能问有没有用碰撞检测。

从统计节点工具延申出树的遍历方式（深度和广度）。

有正整数，数字范围是0~，用struct或者class，设计一种数据结构，方便查找跟插入。

浏览器渲染过程是怎么样的

http://www.jb51.net/softjc/67746.html

知道碰撞检测吗？对AABB和OBB了解多少？

知道texture2D跟texture3D吗？

知道哪些寻路算法？

图集优化，drawcall的理解，一张图什么时候不能打入一张图集？

有一大堆重复int值，如何获知不同int的数量

内存消耗太大，怎么改进

用位图需要提前分配足量内存，假如这些值很稀疏，那就会浪费大量内存，怎么改进？（＊）

Qt 多线程

线程池怎么封装，一个线程给另一个线程抛消息怎么实现？

#include <vector>
#include <thread>
#include <queue>
#include <mutex>
#include <condition_variable>
#include <functional>
#include <future>
#include <iostream>

class ThreadPool {
public:
    ThreadPool(size_t numThreads);
    ~ThreadPool();

    // 提交任务到线程池
    // 返回值类型：std::future<typename std::result_of<F(Args...)>::type>
    // 表示根据执行F(Args...)结果推导出返回值的类型
    template <class F, class... Args>
    auto enqueue(F&& f, Args&&... args) -> std::future<typename std::result_of<F(Args...)>::type>;

private:
    std::vector<std::thread> workers;
    std::queue<std::function<void()>> tasks;

    std::mutex queueMutex;
    std::condition_variable condition;
    bool stop;
};

// 构造函数，创建指定数量的线程
ThreadPool::ThreadPool(size_t numThreads) : stop(false) {
    for (size_t i = 0; i < numThreads; ++i) {
        workers.emplace_back([this] {
            for (;;) {
                std::function<void()> task;
                {
                    std::unique_lock<std::mutex> lock(this->queueMutex);
                    this->condition.wait(lock, [this] { return this->stop || !this->tasks.empty(); });
                    if (this->stop && this->tasks.empty())
                        return;
                    task = std::move(this->tasks.front());
                    this->tasks.pop();
                }
                task();
            }
        });
    }
}

// 向线程池中提交任务
template <class F, class... Args>
auto ThreadPool::enqueue(F&& f, Args&&... args) -> std::future<typename std::result_of<F(Args...)>::type> {
    using return_type = typename std::result_of<F(Args...)>::type;

    auto task = std::make_shared<std::packaged_task<return_type()>>(std::bind(std::forward<F>(f), std::forward<Args>(args)...));

    std::future<return_type> res = task->get_future();
    {
        std::unique_lock<std::mutex> lock(queueMutex);
        if (stop)
            throw std::runtime_error("enqueue on stopped ThreadPool");
        tasks.emplace([task]() { (*task)(); });
    }
    condition.notify_one();
    return res;
}

// 析构函数，等待所有线程完成
ThreadPool::~ThreadPool() {
    {
        std::unique_lock<std::mutex> lock(queueMutex);
        stop = true;
    }
    condition.notify_all();
    for (std::thread& worker : workers)
        worker.join();
}

快排优化，时间复杂度、空间复杂度

模板里可以定义虚函数吗

全部静态变量，局部静态变量，类内静态成员变量的生命周期，作用域，以及构造和析构函数的调用时间

在头文件中声明一个静态变量，在多个cpp文件进行调用，会生成多少个实例

sort()函数的实现，会用到什么排序，为什么

说一下C++11的新特性有哪些

auto、range for循环、lambda函数式编程、nullptr解决了C99中NULL的二义性、智能指针

python RAII机制

python的内存管理机制

用过哪些linux命令？比如网络方面的

查看cpu的命令呢

进程的状态有那几个

编程遇到过CLOSE_WAIT状态吗

文字排版引擎、表格计算引擎、演示动画引擎（WPS）

OCR 模型以及库文件大小不超过 9MB，可轻量化部署，该模型在文本检测、文本分类和文本识别上都表现出了较好的性能

TIME_WAIT对端口有什么影响

基本认识
是TCP主动断开后进入的一个短暂状态，目的是确保数据完整传输以及确保连接是可靠关闭的

对端口影响
会导致端口占用、同时有一定的系统占用、可能导致连接数限制

如何缓解

TCP端口重用（SO_REUSEADDR/SO_REUSEPORT）,服务端套接字开启后此状态下的端口依然可用
缩短持续时间（需要在系统上配置）
使用长连接，减少频繁的连接与关闭

注意事项
只有主动发起关闭请求的一方会进入此状态

遇到过程序崩溃的情况吗？怎么调试？gdb咋用的

g++ -g myprogram.cpp -o myprogram  # -g 生成调试信息

子窗口和父窗口的事件传递，叠加窗口的事件穿透

基本常识：

非gui事件由QCoreApplication负责将QEvent分发到QObject的子类
GUI则由QApplication负责
需要接受处理事件，重写QObject::event()函数
Qt中事件是一个QEvent对象，一个事件一个对象

event()函数并不直接处理事件，而是分发用，如果事件被识别并处理，需要返回true，Qt会认为事件已经处理完毕。

GUI事件处理流程：

接受鼠标事件
QApplication调用QObject::event，进行事件分配
调用Button的时间处理函数
调用button的click函数
触发信号

事件传递流程

事件传递给获得焦点窗口的部件
系统事件 -> QCoreApplication事件 -> （根据坐标、界面结构）从顶层窗口部件向下传递找到具体组件（childAt()函数）
如果该部件忽略该事件，则传递给父组件
沿父子对象的层次结构向上冒泡传递，直到找到一个能够处理事件的对象
处理事件
找打目标QCpreApplication的notify调用目标对象的event()

事件底层结构
每个线程都有一个事件队列，基于链表存储，每个事件都作为一个链表节点
QCoreApplication::postEvent将时间插入到时间队列中，QEventLoop不断去除事件处理。

linux基本命令

ip addr  ifconfig     #查看IP；
mv oldname newname    #给文件改名；
ls -al file           #查看文件权限
chmod 754  file       #修改权限
chmod +x file         #添加权限
lsb_release -a        #怎么查看当前系统的版本
df -h                 #怎么查看当前系统硬盘空间的总量与使用情况
free -h               #怎么查看系统内存多少
ldd /bin/ls           #怎么查看某个命令执行的时候需要链接哪些系统库；
ln -s file  linkname  #怎么给一个文件做一个软链接

说一下gdb

GUN中的调试器，用于调试C++程序

gdb ./my_program  # 启动gdb
run arg1          # 带参启动
break main        # 设置断点
break file.cpp:25 # 特定文件和行号设置断点
break file.cpp:25 if x==5 # 设置条件断点
continue          # 继续执行
next              # 单步执行
step              # 单步进入函数内部
print varname     # 打印变量
print *ptr        # 查看指针指向内容
backtrace         # 查看当前调用栈
set varname = newvalue # 修改变量值
info threads      # 查看线程列表
thread threadid   # 切换到特定线程
quit              # 退出调试器

怎么把一个test.cpp编译成一个test.so；

g++ -fPIC -shared -o test.so test.cpp -I/includePath -lotherlib

// -fPIC 生成动态库必须得配置，表示生成位置无关代码（PIC）,共享库可以在任何位置加载
// -fPIC 生成共享库
// -I 依赖头文件位置
// -l 依赖库

ls -l test.so

红黑树的原理

1. 基本规则

a. 根节点是黑色的
b. 所有为null的叶子结点都是黑色的
c. 如果一个节点是红色，则它的子节点都是黑色的
d. 一个节点到它的子孙节点的所有黑色节点的路径都是相同的。
e. 时间复杂度是O(lgn)

2. 插入和删除

左旋：交换当前节点和它的右子节点，将右子节点作为当前节点的父亲，根据当前节点是其原父亲的左右节点，以相同的方式挂载新的父亲节点，新服务的左子结点作为当前节点的右子节点（取代新父亲之前的位置）。

LEFT-ROTATE(T, x)  
01  y ← right[x]            // 前提：这里假设x的右孩子为y。下面开始正式操作
02  right[x] ← left[y]      // 将 “y的左孩子” 设为 “x的右孩子”，即 将β设为x的右孩子
03  p[left[y]] ← x          // 将 “x” 设为 “y的左孩子的父亲”，即 将β的父亲设为x
04  p[y] ← p[x]             // 将 “x的父亲” 设为 “y的父亲”
05  if p[x] = nil[T]       
06  then root[T] ← y                 // 情况1：如果 “x的父亲” 是空节点，则将y设为根节点
07  else if x = left[p[x]]  
08            then left[p[x]] ← y    // 情况2：如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
09            else right[p[x]] ← y   // 情况3：(x是它父节点的右孩子) 将y设为“x的父节点的右孩子”
10  left[y] ← x             // 将 “x” 设为 “y的左孩子”
11  p[x] ← y                // 将 “x的父节点” 设为 “y”

右旋：将当前节点旋转成左子节点的右子节点，取代左子节点上的右子节点后，将这个右子节点当做自己的左子节点。

RIGHT-ROTATE(T, y)  
01  x ← left[y]             // 前提：这里假设y的左孩子为x。下面开始正式操作
02  left[y] ← right[x]      // 将 “x的右孩子” 设为 “y的左孩子”，即 将β设为y的左孩子
03  p[right[x]] ← y         // 将 “y” 设为 “x的右孩子的父亲”，即 将β的父亲设为y
04  p[x] ← p[y]             // 将 “y的父亲” 设为 “x的父亲”
05  if p[y] = nil[T]       
06  then root[T] ← x                 // 情况1：如果 “y的父亲” 是空节点，则将x设为根节点
07  else if y = right[p[y]]  
08            then right[p[y]] ← x   // 情况2：如果 y是它父节点的右孩子，则将x设为“y的父节点的左孩子”
09            else left[p[y]] ← x    // 情况3：(y是它父节点的左孩子) 将x设为“y的父节点的左孩子”
10  right[x] ← y            // 将 “y” 设为 “x的右孩子”
11  p[y] ← x                // 将 “y的父节点” 设为 “x”

map怎么插入数据，有几种方式

void test(){
    std::map<int,int> maps;
    maps.insert({1,100});
    maps.insert({1,200}); //如果存在相同的key则不会插入成功，返回当前已经存在的迭代器
    maps.emplace(2,333);  //更高效，直接构造键值对，避免额外拷贝
    maps[3] = 444;        //直接使用operator []
    maps.insert_or_assign(3,555) //C++17之后，如果存在则更新
}

进程怎么同步，线程怎么同步

1. 定位

同步是指在对共享资源访问时，尽可能避免数据不一致问题

2. 进程同步

信号量

#include <iostream>
#include <thread>
#include <semaphore>  // C++20

std::counting_semaphore<1> semaphore(1);  // 1 表示信号量初始值

void task(int id) {
    semaphore.acquire();  // 请求信号量
    std::cout << "Task " << id << " is working." << std::endl;
    std::this_thread::sleep_for(std::chrono::seconds(1));  // 模拟工作
    std::cout << "Task " << id << " is done." << std::endl;
    semaphore.release();  // 释放信号量
}

int main() {
    std::thread t1(task, 1);
    std::thread t2(task, 2);

    t1.join();
    t2.join();

    return 0;
}

共享内存

#include <iostream>
#include <sys/mman.h>
#include <fcntl.h>
#include <unistd.h>
#include <cstring>

int main() {
    const char* name = "/my_shared_memory";
    const size_t SIZE = 4096;

    // 创建共享内存
    int shm_fd = shm_open(name, O_CREAT | O_RDWR, 0666);
    ftruncate(shm_fd, SIZE);

    // 映射到进程的虚拟内存空间
    void* ptr = mmap(0, SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, shm_fd, 0);

    // 写入数据
    const char* message = "Hello from shared memory!";
    std::memcpy(ptr, message, std::strlen(message) + 1);

    std::cout << "Message written to shared memory: " << (char*)ptr << std::endl;

    // 清理
    munmap(ptr, SIZE);
    close(shm_fd);
    shm_unlink(name);

    return 0;
}

管道

#include <iostream>
#include <unistd.h>
#include <cstring>

int main() {
    int pipe_fd[2];
    char buffer[128];

    if (pipe(pipe_fd) == -1) {
        std::cerr << "Pipe failed!" << std::endl;
        return 1;
    }

    // 写入数据
    const char* message = "Hello from pipe!";
    write(pipe_fd[1], message, std::strlen(message) + 1);

    // 读取数据
    read(pipe_fd[0], buffer, sizeof(buffer));
    std::cout << "Received message: " << buffer << std::endl;

    close(pipe_fd[0]);
    close(pipe_fd[1]);

    return 0;
}

消息队列

#include <iostream>
#include <mqueue.h>
#include <cstring>

int main() {
    mqd_t mq;
    const char* queue_name = "/my_message_queue";

    // 创建消息队列
    mq = mq_open(queue_name, O_CREAT | O_RDWR, 0644, NULL);
    if (mq == -1) {
        std::cerr << "Message Queue failed!" << std::endl;
        return 1;
    }

    const char* message = "Hello from message queue!";
    mq_send(mq, message, std::strlen(message) + 1, 0);  // 发送消息

    char buffer[128];
    mq_receive(mq, buffer, sizeof(buffer), NULL);  // 接收消息
    std::cout << "Received message: " << buffer << std::endl;

    mq_close(mq);
    mq_unlink(queue_name);  // 删除消息队列

    return 0;
}

互斥锁

#include <iostream>
#include <thread>
#include <mutex>

std::mutex mtx;  // 互斥锁

void task(int id) {
    std::lock_guard<std::mutex> lock(mtx);  // 自动加锁和解锁
    std::cout << "Thread " << id << " is working." << std::endl;
    std::this_thread::sleep_for(std::chrono::seconds(1));  // 模拟工作
    std::cout << "Thread " << id << " is done." << std::endl;
}

int main() {
    std::thread t1(task, 1);
    std::thread t2(task, 2);

    t1.join();
    t2.join();

    return 0;
}

3. 线程同步

互斥锁
读写锁
条件变量
原子操作
自旋锁

tcp与udp的区别，udp怎么实现多对多通信，问的很细，包括tcp的各种机制。

1. 区别

前：TCP 后：UDP

TCP是面向连接的，先建立连接再通信；udp是非连接的
tcp可靠，udp不可靠
tcp支持流量控制，udp不支持
tcp流传输协议、数据包传输
检验和重传机制、无重传

2. TCP机制

连接断开：三次握手、四次挥手
可靠性保证：数据包确认、当接受方收到数据包时会返回ack包确认，超时未收到，重传
流量控制：滑动窗口

3. udp实现多对多通信

广播，通过广播地址客户端可以向局域网的所有其他设备发送数据包，属于一对多
组播类似，属于多对多，设备需要加入特定组播组
通过心跳包机制保证长连接

tcp粘包问题

1. 定义,tcp是面向字节流协议并不保证数据包的边界，在发送过程中可能会导致多个小包合并成一个包的现象，导致数据边界丢失

2. 解决

固定包长度
数据包头部指定长度，支持可变长度消息
使用分隔符，适用于文本协议如html,smtp
TCP_NODELAY项目，关闭Nagle算法（小包合并大包算法）

QT的信号槽是什么原理

基本的认识：
Qt的信号声明实际上是一个空函数，目的只是为了通知消息
底层用的是生产者消费者模式
信号与槽是基于qt的元对象系统，支持不同线程的正确传递

1. Q_OBJECT宏声明

依赖于元对象系统，启用信号槽功能，通过moc生成额外代码，包括：

元信息：（类信号、槽、属性信息）
信号槽链接、断开代码实现（connect、disconnect）
qt_metacall函数，管理信号槽调用参数传递

2. connect连接会将信号、槽信息存储到元数据中：

通过qmetaobject查找信号、槽索引值
每个object存有connectList，存储链接信息（接受对象、调用方式）
如果是队列方式，qt会调用事件系统，封装信号发送到接受线程队列中

3. 信号发射实现

通过内部的connectList找到对应的槽函数，调用槽函数

4. 信号槽自动断开

object析构会调用connectList，删除相关连接信息

5. 信号槽性能优化

快速路径：同一个线程用直连，不进人事件系统
稀疏数组：qmetaobject信号槽索引用的是稀疏数组，加快查找速度
无锁设计：同一个线程中不涉及锁，减少多线程锁开销

作者：admin 创建时间：2024-11-11 17:44
最后编辑：admin 更新时间：2024-11-14 09:20