C/C++ 面试经典题：从基础到高级

// 指针
int a = 10;
int* ptr = &a;      // 指针需要取地址
*ptr = 20;          // 解引用修改值
ptr = nullptr;      // 可以为空
ptr++;              // 可以进行指针运算

// 引用
int b = 10;
int& ref = b;       // 引用直接初始化
ref = 20;           // 直接修改值
// int& ref2;       // 错误：引用必须初始化
// int& ref3 = nullptr; // 错误：引用不能为空
// ref++;           // 错误：引用不能重新绑定

// 1. const 修饰变量
const int a = 10;
a = 20;  // 错误：const 变量不能修改

// 2. const 修饰指针
int b = 10;
const int* ptr1 = &b;      // 指向常量的指针（指向的内容不能改）
int const* ptr2 = &b;      // 同上
int* const ptr3 = &b;      // 常量指针（指针本身不能改）
const int* const ptr4 = &b; // 指向常量的常量指针

*ptr1 = 20;  // 错误：不能通过 ptr1 修改值
ptr1 = nullptr;  // 正确：ptr1 本身可以改

*ptr3 = 20;  // 正确：可以通过 ptr3 修改值
ptr3 = nullptr;  // 错误：ptr3 本身不能改

// 3. const 修饰函数参数
void func(const int x) {
    x = 10;  // 错误：参数不能修改
}

void func2(const std::string& str) {
    str = "new";  // 错误：引用的内容不能修改
    // 优点：避免拷贝，且保证不修改原数据
}

// 4. const 成员函数
class MyClass {
    int value;
public:
    int getValue() const {  // const 成员函数
        // value = 10;  // 错误：不能修改成员变量
        return value;
    }
    
    int& getValue() {  // 非 const 成员函数
        return value;  // 可以修改
    }
};

// 1. 静态局部变量
void counter() {
    static int count = 0;  // 只初始化一次，生命周期持续到程序结束
    count++;
    std::cout << count << std::endl;
}
// 调用 3 次输出：1, 2, 3

// 2. 静态全局变量/函数（内部链接）
static int globalVar = 10;  // 只在当前文件可见
static void internalFunc() {}  // 只在当前文件可见

// 3. 静态成员变量
class MyClass {
public:
    static int count;  // 所有对象共享
    MyClass() { count++; }
};
int MyClass::count = 0;  // 类外初始化

// 4. 静态成员函数
class MyClass {
public:
    static int count;
    static int getCount() {  // 没有 this 指针
        // value = 10;  // 错误：不能访问非静态成员
        return count;
    }
};

// malloc/free（C 风格）
int* p1 = (int*)malloc(sizeof(int));  // 分配内存
free(p1);                              // 释放内存

// new/delete（C++ 风格）
int* p2 = new int(10);  // 分配内存并初始化
delete p2;               // 释放内存

// 数组
int* p3 = new int[10];  // 分配数组
delete[] p3;             // 释放数组

// 对象
class MyClass {
public:
    MyClass() { std::cout << "构造\n"; }
    ~MyClass() { std::cout << "析构\n"; }
};

MyClass* obj = new MyClass();  // 调用构造函数
delete obj;                     // 调用析构函数

// 1. 使用智能指针（推荐）
#include <memory>

void safeCode() {
    std::unique_ptr<int> p1(new int(10));
    std::shared_ptr<int> p2 = std::make_shared<int>(20);
    // 自动释放，无需手动 delete
}

// 2. RAII 模式
class Resource {
    int* data;
public:
    Resource() : data(new int[100]) {}
    ~Resource() { delete[] data; }  // 析构时自动释放
    
    // 禁止拷贝（避免重复释放）
    Resource(const Resource&) = delete;
    Resource& operator=(const Resource&) = delete;
};

// 3. 使用工具检测
// - Valgrind（Linux）
// - AddressSanitizer（GCC/Clang）
// - Visual Studio 内存检测器

// 4. 编译时检查
// -Wall -Wextra -Werror
// -fsanitize=address

// 内存对齐规则
struct Example1 {
    char a;     // 1 byte
    int b;      // 4 bytes
    char c;     // 1 byte
};
// 大小：12 bytes（不是 6 bytes）

struct Example2 {
    int b;      // 4 bytes
    char a;     // 1 byte
    char c;     // 1 byte
};
// 大小：8 bytes

// 对齐规则：
// 1. 每个成员按其大小对齐
// 2. 结构体总大小是最大成员大小的倍数
// 3. 成员按声明顺序排列

// 手动指定对齐
#pragma pack(1)  // 1 字节对齐
struct Packed {
    char a;
    int b;
    char c;
};
// 大小：6 bytes

// C++11 方式
struct alignas(16) Aligned {
    int a;
    int b;
};

class Base {
public:
    virtual void show() {
        std::cout << "Base::show()" << std::endl;
    }
    
    virtual ~Base() {}  // 虚析构函数
};

class Derived : public Base {
public:
    void show() override {  // 重写虚函数
        std::cout << "Derived::show()" << std::endl;
    }
};

// 多态使用
Base* ptr = new Derived();
ptr->show();  // 输出：Derived::show()
delete ptr;

// 虚函数表（vtable）原理
// 1. 每个有虚函数的类有一个虚函数表
// 2. 每个对象有一个虚函数指针（vptr）指向 vtable
// 3. 调用虚函数时，通过 vptr 找到 vtable，再找到函数地址

// 纯虚函数和抽象类
class Abstract {
public:
    virtual void func() = 0;  // 纯虚函数
    virtual ~Abstract() {}
};

// Abstract obj;  // 错误：不能实例化抽象类
class Concrete : public Abstract {
public:
    void func() override {
        std::cout << "实现纯虚函数" << std::endl;
    }
};

class Base {
public:
    Base() { std::cout << "Base 构造\n"; }
    ~Base() { std::cout << "Base 析构\n"; }
};

class Derived : public Base {
    Base member;  // 成员对象
public:
    Derived() { std::cout << "Derived 构造\n"; }
    ~Derived() { std::cout << "Derived 析构\n"; }
};

// 创建对象
Derived obj;
// 输出顺序：
// 1. Base 构造（基类）
// 2. Base 构造（成员对象）
// 3. Derived 构造（派生类）

// 销毁对象（相反顺序）：
// 1. Derived 析构
// 2. Base 析构（成员对象）
// 3. Base 析构（基类）

// 拷贝构造函数
class MyClass {
    int* data;
public:
    MyClass(int val) : data(new int(val)) {}
    
    // 深拷贝
    MyClass(const MyClass& other) 
        : data(new int(*other.data)) {}
    
    // 移动构造函数（C++11）
    MyClass(MyClass&& other) noexcept
        : data(other.data) {
        other.data = nullptr;
    }
    
    ~MyClass() { delete data; }
};

// 菱形继承问题
class A {
public:
    int value;
    A() : value(10) {}
};

class B : public A {};  // B 继承 A
class C : public A {};  // C 继承 A

class D : public B, public C {
    // D 有两份 A 的副本，产生二义性
};

D d;
// d.value = 10;  // 错误：二义性
d.B::value = 10;  // 正确：指定使用 B 的
d.C::value = 20;  // 正确：指定使用 C 的

// 解决方案：虚继承
class B : virtual public A {};  // 虚继承
class C : virtual public A {};  // 虚继承

class D : public B, public C {
    // D 只有一份 A 的副本
};

D d;
d.value = 10;  // 正确：没有二义性

#include <vector>

// vector 内部结构
template<typename T>
class vector {
private:
    T* data;        // 指向数组的指针
    size_t size;    // 当前元素数量
    size_t capacity; // 容量（已分配空间）
    
public:
    // 扩容策略
    void push_back(const T& value) {
        if (size == capacity) {
            // 容量不足，重新分配
            size_t newCapacity = capacity == 0 ? 1 : capacity * 2;
            T* newData = new T[newCapacity];
            
            // 拷贝旧数据
            for (size_t i = 0; i < size; i++) {
                newData[i] = data[i];
            }
            
            // 释放旧内存
            delete[] data;
            data = newData;
            capacity = newCapacity;
        }
        
        data[size++] = value;
    }
};

// 使用示例
std::vector<int> vec;
vec.reserve(100);  // 预分配空间，避免多次扩容

// 性能特点
// - 随机访问：O(1)
// - 尾部插入：O(1) 均摊
// - 中间插入：O(n)
// - 尾部删除：O(1)
// - 中间删除：O(n)

#include <map>
#include <unordered_map>

// map（红黑树）
std::map<std::string, int> map1;
map1["apple"] = 1;
map1["banana"] = 2;
// 有序：按 key 排序
// 查找：O(log n)
// 插入：O(log n)
// 删除：O(log n)

// unordered_map（哈希表）
std::unordered_map<std::string, int> map2;
map2["apple"] = 1;
map2["banana"] = 2;
// 无序：哈希分布
// 查找：O(1) 平均
// 插入：O(1) 平均
// 删除：O(1) 平均

// 如何选择
// 1. 需要有序 → map
// 2. 需要快速查找 → unordered_map
// 3. key 没有哈希函数 → map
// 4. 内存敏感 → map（红黑树更紧凑）

#include <thread>
#include <mutex>
#include <condition_variable>
#include <atomic>

// 1. 互斥锁（mutex）
std::mutex mtx;
int sharedData = 0;

void increment() {
    std::lock_guard<std::mutex> lock(mtx);  // RAII 风格
    sharedData++;
    // 离开作用域自动解锁
}

// 2. 原子变量
std::atomic<int> atomicData(0);

void atomicIncrement() {
    atomicData++;  // 原子操作，无需锁
}

// 3. 条件变量
std::condition_variable cv;
std::mutex cv_mtx;
bool ready = false;

void producer() {
    std::lock_guard<std::mutex> lock(cv_mtx);
    ready = true;
    cv.notify_one();  // 通知消费者
}

void consumer() {
    std::unique_lock<std::mutex> lock(cv_mtx);
    cv.wait(lock, [] { return ready; });  // 等待条件满足
    // 处理数据
}

// 4. 读写锁（C++14）
std::shared_mutex rw_mtx;

void readData() {
    std::shared_lock<std::shared_mutex> lock(rw_mtx);  // 共享锁
    // 多个线程可以同时读
}

void writeData() {
    std::unique_lock<std::shared_mutex> lock(rw_mtx);  // 独占锁
    // 只有一个线程可以写
}

// 死锁示例
std::mutex mtx1, mtx2;

void thread1() {
    std::lock_guard<std::mutex> lock1(mtx1);
    std::this_thread::sleep_for(std::chrono::milliseconds(10));
    std::lock_guard<std::mutex> lock2(mtx2);  // 等待 mtx2
}

void thread2() {
    std::lock_guard<std::mutex> lock2(mtx2);
    std::this_thread::sleep_for(std::chrono::milliseconds(10));
    std::lock_guard<std::mutex> lock1(mtx1);  // 等待 mtx1
}

// 避免死锁的方法

// 方法1：固定加锁顺序
void safe_thread1() {
    std::lock_guard<std::mutex> lock1(mtx1);  // 先锁 mtx1
    std::lock_guard<std::mutex> lock2(mtx2);  // 再锁 mtx2
}

void safe_thread2() {
    std::lock_guard<std::mutex> lock1(mtx1);  // 同样先锁 mtx1
    std::lock_guard<std::mutex> lock2(mtx2);  // 再锁 mtx2
}

// 方法2：使用 std::lock 同时加锁
void safe_thread3() {
    std::lock(mtx1, mtx2);  // 同时锁定两个互斥量
    std::lock_guard<std::mutex> lock1(mtx1, std::adopt_lock);
    std::lock_guard<std::mutex> lock2(mtx2, std::adopt_lock);
}

// 方法3：使用超时
void safe_thread4() {
    std::unique_lock<std::mutex> lock1(mtx1, std::defer_lock);
    std::unique_lock<std::mutex> lock2(mtx2, std::defer_lock);
    
    if (lock1.try_lock_for(std::chrono::milliseconds(100))) {
        if (lock2.try_lock_for(std::chrono::milliseconds(100))) {
            // 成功锁定
        }
    }
}

#include <vector>
#include <algorithm>

// 快速排序
void quickSort(std::vector<int>& arr, int left, int right) {
    if (left >= right) return;
    
    // 选择基准元素
    int pivot = arr[left];
    int i = left, j = right;
    
    while (i < j) {
        // 从右向左找小于基准的元素
        while (i < j && arr[j] >= pivot) j--;
        // 从左向右找大于基准的元素
        while (i < j && arr[i] <= pivot) i++;
        
        if (i < j) {
            std::swap(arr[i], arr[j]);
        }
    }
    
    // 基准元素归位
    std::swap(arr[left], arr[i]);
    
    // 递归排序
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

// 使用示例
int main() {
    std::vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};
    quickSort(arr, 0, arr.size() - 1);
    // 结果：1, 1, 2, 3, 4, 5, 6, 9
}

#include <mutex>

// 方式1：静态局部变量（推荐，C++11 线程安全）
class Singleton {
private:
    Singleton() = default;
    
public:
    Singleton(const Singleton&) = delete;
    Singleton& operator=(const Singleton&) = delete;
    
    static Singleton& getInstance() {
        static Singleton instance;  // C++11 保证线程安全
        return instance;
    }
};

// 方式2：双重检查锁定
class Singleton2 {
private:
    static Singleton2* instance;
    static std::mutex mtx;
    
    Singleton2() = default;
    
public:
    Singleton2(const Singleton2&) = delete;
    Singleton2& operator=(const Singleton2&) = delete;
    
    static Singleton2* getInstance() {
        if (instance == nullptr) {  // 第一次检查
            std::lock_guard<std::mutex> lock(mtx);
            if (instance == nullptr) {  // 第二次检查
                instance = new Singleton2();
            }
        }
        return instance;
    }
};

Singleton2* Singleton2::instance = nullptr;
std::mutex Singleton2::mtx;

// 方式3：std::call_once
class Singleton3 {
private:
    Singleton3() = default;
    static std::once_flag flag;
    
public:
    Singleton3(const Singleton3&) = delete;
    Singleton3& operator=(const Singleton3&) = delete;
    
    static Singleton3& getInstance() {
        static Singleton3* instance;
        std::call_once(flag, []() {
            instance = new Singleton3();
        });
        return *instance;
    }
};

std::once_flag Singleton3::flag;