C++ 八股文（性能优化）

1. 如何优化 C++ 中的算法复杂度？

1. 选择合适的数据结构： 根据操作频率选择容器，频繁查找用unordered_map时间O(1)而不是map的O(log n)，频繁插入删除用list而不是vector，需要排序用set或priority_queue，空间换时间用哈希表缓存计算结果。

2. 算法优化技巧： 避免嵌套循环降低时间复杂度，使用双指针、滑动窗口减少遍历次数，二分查找将O(n)降到O(log n)，动态规划避免重复计算，分治算法降低复杂度如归并排序。

3. 提前终止和剪枝： 找到结果立即返回不继续遍历，使用短路求值&&和||，循环中使用break减少无效迭代，递归中剪枝避免无效分支，缓存中间结果避免重复计算。

4. 空间时间权衡： 使用额外空间换取时间如哈希表，预计算结果存储查找表，使用位运算优化空间和时间，lazy evaluation延迟计算，批量处理减少函数调用开销。

// 优化前：O(n²)
for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
        if(arr[i] + arr[j] == target) return true;

// 优化后：O(n)使用哈希表
std::unordered_set<int> seen;
for(int x : arr) {
    if(seen.count(target - x)) return true;
    seen.insert(x);
}

2. C++ 中如何优化循环和内存访问模式？

1. 缓存友好访问： 按行优先顺序访问二维数组利用空间局部性，连续内存访问提高缓存命中率，避免跨步访问stride access，数组优于链表因为内存连续，结构体成员按访问频率排列热数据放一起。

2. 循环优化技巧： 循环不变量外提减少重复计算，循环展开减少分支判断开销，循环融合合并多个循环减少遍历次数，循环交换改变嵌套顺序优化缓存，使用迭代器而不是索引访问。

3. 减少分支预测失败： 避免循环内的条件判断，使用位运算代替if-else，数据排序后处理减少分支，使用查找表代替复杂条件，编译器likely/unlikely提示优化分支。

4. 向量化和并行： 使用SIMD指令并行处理，编译器自动向量化需要满足条件，OpenMP并行化循环，使用std::transform等算法库，避免循环依赖使能并行。

// 缓存不友好：按列访问
for(int j = 0; j < cols; j++)
    for(int i = 0; i < rows; i++)
        sum += matrix[i][j];

// 缓存友好：按行访问
for(int i = 0; i < rows; i++)
    for(int j = 0; j < cols; j++)
        sum += matrix[i][j];

// 循环展开
for(int i = 0; i < n; i += 4) {
    sum += arr[i] + arr[i+1] + arr[i+2] + arr[i+3];
}

3. 如何使用缓存优化提高 C++ 程序性能？

1. 缓存层次理解： L1缓存最快但最小约32KB，L2缓存较大约256KB，L3缓存更大约8MB但较慢，主内存最慢，缓存行通常64字节，理解缓存工作原理才能有效优化。

2. 数据局部性优化： 时间局部性短时间内重复访问同一数据，空间局部性访问相邻地址的数据，数组优于链表因为连续存储，结构体数组SoA优于数组结构体AoS提高向量化，热数据集中存储冷数据分离。

3. 避免false sharing： 多线程访问不同变量但在同一缓存行导致缓存失效，使用alignas(64)对齐到缓存行，在结构体中添加padding分隔热数据，使用thread_local避免共享，每个线程独立的数据结构。

4. 预取和预分配： 使用__builtin_prefetch预取数据到缓存，容器使用reserve预分配避免重新分配，批量处理数据提高缓存利用率，循环分块tiling优化缓存使用，减少工作集大小适应缓存。

// 避免false sharing
struct alignas(64) ThreadData {  // 缓存行对齐
    int counter;
    char padding[60];  // 填充到64字节
};

// 循环分块优化缓存
const int BLOCK = 64;
for(int ii = 0; ii < n; ii += BLOCK)
    for(int jj = 0; jj < n; jj += BLOCK)
        for(int i = ii; i < ii+BLOCK; i++)
            for(int j = jj; j < jj+BLOCK; j++)
                C[i][j] += A[i][j] * B[i][j];

4. C++ 中如何避免不必要的内存拷贝？

1. 使用移动语义： 返回值使用std::move转移所有权，函数参数使用右值引用接收临时对象，容器插入使用emplace_back而不是push_back，std::move转移大对象避免拷贝，移动构造和移动赋值声明noexcept。

2. 引用传递： 函数参数使用const引用传递大对象，返回引用而不是值避免拷贝，使用std::ref包装引用传递给线程或bind，注意引用生命周期避免悬空引用，小对象按值传递大对象按引用。

3. 原地构造： 使用emplace系列函数原地构造对象，避免先构造再拷贝的两步操作，容器使用reserve预分配避免扩容拷贝，使用placement new在指定位置构造，std::optional和std::variant原地构造。

4. 返回值优化： 编译器RVO返回值优化自动消除拷贝，NRVO命名返回值优化，返回局部对象不要使用std::move阻止RVO，C++17保证拷贝消除，返回大对象时信任编译器优化。

// 避免拷贝：使用移动
std::vector<int> create() {
    std::vector<int> v(1000);
    return v;  // RVO或移动，不拷贝
}

// 避免拷贝：引用传递
void process(const std::string& str) {}  // 不拷贝

// 避免拷贝：原地构造
vec.emplace