C++ 进阶

2025-07-29

C++

字数统计: 19.4k | 阅读时长≈ 84 分钟

通过 C++基础的学习我们已经对基础语法、面向对象、简单模板和STL都已经掌握了，接下来就是 C++ 的进阶了。

1. 优先掌握现代 C++ (C++11/14/17/20)

现代 C++ 极大地改变了编写高效、安全、易读 C++ 代码的方式

移动语义

需要理解其为什么能极大提升性能（避免不必要的拷贝），熟练掌握 std::move 和 std::forward 的使用场景和区别（移动 vs 完美转发）

移动语义允许在对象之间转移资源的所有权，而不是进行深拷贝，从而减少内存分配和复制的开销

在实现移动语义前我们需要了解三个术语：左值引用 （ lvalue reference ）、右值引用 （ rvalue reference ）和 万能引用 （ universal reference ），通过 C++基础我们对这三个术语都有一定的了解，知道了：引用即别名，int a = 10; int& b = a; b 是 a 的引用，普通引用其就是左值引用

左值： 可以放在赋值操作的左侧，有名字、可寻址的对象（如变量 int a = 20; 中的 a ），可以被修改

右值： 可以放在赋值操作的右侧，无名字、不可寻址的临时对象（如 a + 20 的结果、函数返回的临时对象），在没有右值引用之前是不可以被修改的

右值引用 是我们需要重点学习：它是C++11里面最重要的新特性了，移动语义和完美转发都建立在它的基础之上，使用 && 来声明右值引用（int && r = 右值;），但是当我们在代码中遇到 && 却不一定就是右值引用，因为源代码当中出现的 && 有可能是 & 的意思，所以 && 可能是右值引用也可能是左值引用，听着很拗口吧

接下来我们需要引入一个新术语万能引用以便在交流的时候清楚的表明 && ：

右值引用只能绑定右值和即将被销毁的左值上，左值引用除了可以绑定到左值上，在满足一定条件后也可以绑定到右值上。这个条件就是常量（ const ）

1 2	int val = 100; int&& rref3 = std::move(val); // 右值引用绑定到即将被销毁的左值

const

从上图可以看出：常量左值引用绑定到右值，非常量左值引用必须为左值不可绑定到右值

universal reference： 从上面可以看出声明中带 && 的可以是左值引用（ const ）也可能是右值引用，这种引用我们可以给它取一个万能应用的名字，也叫通用引用和转发引用

如何区分万能应用（universal reference）

在区分 T&& 之前我们还需要在引入一个新的术语 auto

auto： 关键字在 C++11 中被引入，用于自动推导变量的类型。从那时起，它的功能在 C++14 和 C++17 中得到了增强。auto 让编译器根据变量的初始值自动推导其类型，从而避免显式地写出复杂冗长的类型名，简化代码书写并提高代码的灵活性

当 T&& 出现在函数模板参数中，并且 T 是通过模板参数推导（ auto ）出来的，那么这个 T&& 就是万能引用
如果 T&& 不涉及类型推导，或者 T 已经被指定，那么 T&& 就是右值引用

在类模板中，如果成员函数不是模板函数，那么即使形参是 T&&，它也不是万能引用

template <typename T>
class mytestc
{
  public:
      void testfunc(T&& x) {} // 这不是万能引用，是右值引用
};

成员函数是模板函数，并且 T 是通过模板参数推导出来的，那么 T&& 就是万能引用

template <typename T>
class mytestc
{
  public:
      template <typename T2>
      void testfunc2(T2&& x) {} // 这是万能引用
};

引用示例

#include <iostream>
#include <string>

using namespace std;

// 左值引用示例
void printLeftValueRef(const std::string& str) {
    cout << "Left value reference: " << str << endl;
}

// 右值引用示例
void printRightValueRef(std::string&& str) {
    cout << "Right value reference: " << str << endl;
}

// 万能引用示例
template<typename T>
void printUniversalRef(T&& str) {
    cout << "Universal reference: " << str << endl;
}

int main() {
    string str = "Hello, World!";

    // 左值引用
    printLeftValueRef(str); // 绑定到左值

    // 右值引用
    printRightValueRef(move(str)); // 绑定到右值

    // 万能引用
    printUniversalRef(str); // 绑定到左值
  
    printUniversalRef("Hello, World!"); // 绑定到右值

    return 0;
}

输出结果：

Left value reference: Hello, World!
Right value reference: Hello, World!
Universal reference: Hello, World!
Universal reference: Hello, World!

移动语义

在C++11之前，如果我们定义一个空类，编译器会自动为我们生4个特殊成员函数：成构造函数、析构函数、拷贝构造函数以及拷贝赋值运算符。但是在C++11之后，如果我们定义一个空类，除了之前的4个特殊成员函数，编译器还会为我们生成移动构造函数和移动赋值运算符，所以我们知道移动语义一般有两种方式：移动构造函数和移动赋值运算符。 std::move 是触发移动的关键函数

注意：

1. 如果我们在类中定义了拷贝构造函数或者拷贝赋值运算符，那么编译器就不会自动生成移动构造函数和移动赋值运算符，如果调用移动语义，因为编译器没有自动生成，所以会执行拷贝操作

#include <iostream>

class myTest {
  public: myTest(){}
    // 注意：这里定义了拷贝构造函数，会禁止编译器自动生成移动构造函数和移动赋值运算符
    myTest(const myTest& value){}
};

int main() {
  myTest tempValue {};
  myTest data { std::move(tempValue) }; // 其实调用拷贝构造函数来生成data
  
  return 0; 
}

2. 如果我们在类中定义了析构函数，那么编译器也不会自动生成移动构造函数和移动赋值运算符。如果调用移动语义，也是执行拷贝操作，因为基类都要有一个 virtual 析构函数，如果子类实现了析构函数，如果要运行移动语义就需要手动为该类定义移动构造函数以及移动赋值运算符，如果子类没有实现了析构函数，就不会影响移动构造函数以及移动赋值运算符的自动生成

#include <iostream>

class myTest {
  public:
  ~myTest(){}
};

int main() {
  myTest tempValue {};
  myTest data { std::move(tempValue) }; 
  
  return 0; // 执行的是拷贝构造函数来创建对象B
}

当然反过来也一样：如果我们在类中定义了移动构造函数就不会自动生成移动赋值运算符

下面我们进行一个假设性夸张数据的处理的对比：

// 模拟员工数据库

#include <iostream>
#include <vector>
#include <chrono>
#include <memory>
#include <string>
#include <cstddef>
#include <iomanip>
#include <algorithm>

// 内存测量工具
#ifdef _WIN32
#include <windows.h>
#include <psapi.h>
#else
#include <sys/resource.h>
#endif

size_t get_current_memory_usage() {
#ifdef _WIN32
    PROCESS_MEMORY_COUNTERS pmc;
    GetProcessMemoryInfo(GetCurrentProcess(), &pmc, sizeof(pmc));
    return pmc.WorkingSetSize;
#else
    struct rusage usage;
    getrusage(RUSAGE_SELF, &usage);
    return usage.ru_maxrss * 1024; // Linux返回的是KB
#endif
}

// 性能数据收集器
struct PerformanceStats {
    double duration = 0.0;
    size_t peak_memory = 0;
    size_t constructions = 0;
    size_t copies = 0;
    size_t moves = 0;
};

// 员工类 - 包含大量绩效数据
class Employee {
    std::string name;
    size_t dataSize;
    double* performanceData; // 原始指针用于精确控制内存
    
public:
    // 构造函数
    Employee(const std::string& n, size_t size) 
        : name(n), dataSize(size), performanceData(new double[size])
    {
        // 初始化绩效数据
        for (size_t i = 0; i < size; ++i) {
            performanceData[i] = static_cast<double>(i % 100);
        }
    }
    
    // 移动构造函数
    Employee(Employee&& other) noexcept
        : name(std::move(other.name)),
          dataSize(other.dataSize),
          performanceData(other.performanceData)
    {
        other.dataSize = 0;
        other.performanceData = nullptr;
    }
    
    // 拷贝构造函数（深拷贝）
    Employee(const Employee& other)
        : name(other.name), dataSize(other.dataSize),
          performanceData(new double[other.dataSize])
    {
        for (size_t i = 0; i < dataSize; ++i) {
            performanceData[i] = other.performanceData[i];
        }
    }
    
    // 析构函数
    ~Employee() {
        delete[] performanceData;
    }
    
    // 禁用拷贝赋值
    Employee& operator=(const Employee&) = delete;
};

// 无移动语义版本（强制拷贝）
void processEmployeesWithoutMove(PerformanceStats& stats) {
    auto start = std::chrono::high_resolution_clock::now();
    size_t start_memory = get_current_memory_usage();
    
    std::vector<Employee> department;
    department.reserve(1000); // 预分配空间
    
    for (int i = 0; i < 1000; ++i) {
        // 创建临时对象（会消耗内存）
        Employee emp("Employee_" + std::to_string(i), 100000);
        
        // 添加到vector（深拷贝）
        department.push_back(emp);
        
        // 更新内存峰值
        stats.peak_memory = std::max(stats.peak_memory, get_current_memory_usage());
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    stats.duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
}

// 使用移动语义版本
void processEmployeesWithMove(PerformanceStats& stats) {
    auto start = std::chrono::high_resolution_clock::now();
    size_t start_memory = get_current_memory_usage();
    
    std::vector<Employee> department;
    department.reserve(1000); // 预分配空间
    
    for (int i = 0; i < 1000; ++i) {
        // 创建临时对象（会消耗内存）
        Employee emp("Employee_" + std::to_string(i), 100000);
        
        // 添加到vector（移动操作）
        department.push_back(std::move(emp));
        
        // 更新内存峰值
        stats.peak_memory = std::max(stats.peak_memory, get_current_memory_usage());
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    stats.duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
}

// 打印性能对比
void printPerformanceComparison(const PerformanceStats& withoutMove, const PerformanceStats& withMove) {
    std::cout << "\n===================== 性能对比 =====================\n";
    std::cout << std::left << std::setw(30) << "指标" 
              << std::setw(20) << "无移动语义" 
              << std::setw(20) << "有移动语义" 
              << std::setw(15) << "提升" << "\n";
    
    std::cout << std::string(85, '-') << "\n";
    
    auto printRow = [](const std::string& name, auto without, auto with, const std::string& unit = "") {
        double improvement = 0.0;
        std::string improvementStr;
        
        if (without > 0 && with < without) {
            improvement = (static_cast<double>(without) - with) / without * 100;
            improvementStr = std::to_string(static_cast<int>(improvement)) + "%";
        } else if (with > without) {
            improvement = (static_cast<double>(with) - without) / without * 100;
            improvementStr = "+" + std::to_string(static_cast<int>(improvement)) + "%";
        } else {
            improvementStr = "N/A";
        }
        
        std::cout << std::left << std::setw(30) << name
                  << std::setw(20) << (std::to_string(without) + unit)
                  << std::setw(20) << (std::to_string(with) + unit)
                  << std::setw(15) << improvementStr << "\n";
    };
    
    printRow("执行时间 (ms)", withoutMove.duration, withMove.duration);
    printRow("峰值内存使用 (MB)", withoutMove.peak_memory / (1024.0*1024.0), 
             withMove.peak_memory / (1024.0*1024.0), " MB");
    
    std::cout << "\n内存差异解释：\n";
    std::cout << "1. 无移动语义：临时对象 + vector副本同时存在\n";
    std::cout << "2. 有移动语义：仅vector中的对象存在\n";
    std::cout << "3. 每个员工对象约占用800KB内存\n";
    std::cout << "==================================================\n";
}

int main() {
    try {
        PerformanceStats statsWithoutMove;
        PerformanceStats statsWithMove;
        
        std::cout << "运行无移动语义版本...\n";
        processEmployeesWithoutMove(statsWithoutMove);
        
        std::cout << "\n运行有移动语义版本...\n";
        processEmployeesWithMove(statsWithMove);
        
        printPerformanceComparison(statsWithoutMove, statsWithMove);
    } catch (const std::bad_alloc& e) {
        std::cerr << "\n内存分配失败: " << e.what() << "\n";
        std::cerr << "这证明了无移动语义版本需要过多内存！\n";
    } catch (const std::exception& e) {
        std::cerr << "错误: " << e.what() << "\n";
    }
}

运行结果：

截屏2025-07-25 17.49.24.png

通过以上的对比我们可以知道移动语义的优势和必要性

移动语义的实现要点：

1. 资源转移： 直接窃取源对象的资源（如动态内存、文件句柄），而非复制

2. 置空源对象： 避免资源双重释放，需要将源对象的资源指针设为 nullptr ，确保其析构时不会释放已被接管的资源，置空操作成本极低（单指针赋值），但避免深拷贝可提升10-100倍性能，尤其在容器扩容（如 std::vector ）时

class ResourceHolder {  
    int* data;  
public:  
    // 移动构造函数  
    ResourceHolder(ResourceHolder&& other) noexcept  
        : data(other.data)  {  // 接管资源  
        other.data  = nullptr; // 关键置空  
    }  
    // 移动赋值运算符  
    ResourceHolder& operator=(ResourceHolder&& other) noexcept {  
        if (this != &other) { // 自赋值检查  
            delete[] data;     // 释放自身旧资源  
            data = other.data;  // 接管新资源  
            other.data  = nullptr; // 置空源对象  
        }  
        return *this;  
    }  
};

3. 标记为noexcept： 若移动操作不抛出异常，需显式标记为 noexcept ，以便标准库容器优先使用移动语义优化性能

noexcept

在上面的例子中移动构造函数中我们用到了 noexcept （不会抛出异常的函数），声明为 noexcept 的函数可以帮助编译器进行更好的优化，避免不必要的内存分配和拷贝操作，为了提高性能，移动构造函数和移动赋值运算符通常也应该声明为 noexcept

2. 深入模板与泛型编程

C++ 中的模板与泛型编程是实现代码复用和灵活性的重要机制。通过模板，程序员可以编写独立于特定类型的代码，从而在编译时根据实际类型生成相应的代码。这种机制不仅提高了代码的可维护性，还减少了重复编写相同逻辑的需要

优势：

通过模板编写通用代码，独立于具体数据类型（如 vector<T> 适配任意类型）
避免为相似逻辑重复编写类型特定版本（如交换函数 swap 的通用实现）
编译期实例化生成类型专属代码，消除运行时抽象开销

模板

模板是C++泛型编程的核心工具，允许编写与类型无关的代码。模板分为函数模板和类模板，模板的定义以关键字 template 开始，后接一个模板参数列表

函数模板

函数模板是一种使函数能够处理不同数据类型的工具。通过使用模板，函数可以在编译时根据传入的参数类型自动生成对应的函数代码

#include <iostream>

template <typename T>
T max(T a, T b) {
    return (a > b) ? a : b;
}

int main() {
    std::cout << max(3, 5) << "\n";       // T = int
    std::cout << max(3.14, 2.71) << "\n"; // T = double
    std::cout << max('a', 'z') << "\n";   // T = char
    
  std::cout << max(3, 4.5) << "\n";   // 报错：没有与参数匹配的 函数模板 “max” 实例
  
  return 0;
}

类模板

类模板与函数模板类似，但用于定义类。类模板允许程序员根据不同的数据类型创建类的实例

#include <iostream>

template <typename T>
class Box {
    T content;
public:
    void set(T value) { content = value; }
    T get() const { return content; }
};

int main() {
    Box<int> intBox;
    intBox.set(42);
    
    Box<std::string> strBox;
    strBox.set("Hello Templates!");
}

模板参数详解

模板参数可以是类型参数或非类型参数。类型参数用于指定模板的类型，而非类型参数用于指定模板的非类型值

类型参数

通过 typename T 或 class T 定义类型占位符，实例化时由编译器推导具体类型

template <typename T1, typename T2>

class Pair {
    T1 first;
    T2 second;
public:
    Pair(T1 f, T2 s) : first(f), second(s) {}
    // ...
};

非类型参数

模板参数可以是常量值（如整数、指针），用于编译时优化

template <typename T, int Size>

class FixedArray {
    T data[Size];
public:
    T& operator[](int index) { return data[index]; }
    // ...
};

FixedArray<double, 10> measurements;

默认模板参数

默认模板参数允许在模板定义时为某些模板参数指定默认值。这样，在实例化模板时，如果没有提供这些参数的值，编译器将使用默认值

template <typename T = int, int Size = 100>
class Buffer {
    // ...
};

Buffer<> defaultBuffer; // 使用默认参数

模板特化与偏特化

全特化

为特定类型提供定制实现

template <>
class Box<const char*> {
    const char* content;
public:
    void set(const char* value) { content = value; }
    const char* get() const { return content; }
};

偏特化

针对部分模板参数进行特化

template <typename T>
class Box<T*> {
    T* content;
public:
    void set(T* value) { content = value; }
    T* get() const { return content; }
};

template <typename T1, typename T2>
class Pair<T1, T2*> {
    // 偏特化版本，当第二个参数是指针时
};

变参模板 (C++11)

变参模板的核心是参数包（ parameter pack ），它是一种特殊的模板参数，可以表示零个或多个参数。参数包分为两种类型

模板参数包： 表示零个或多个模板参数
函数参数包： 表示零个或多个函数参数

#include <iostream>

template <typename... Args>

void printAll(Args... args) {
    (std::cout << ... << args) << "\n"; // C++17折叠表达式
}

int main() {
    printAll(1, "apple", 3.14, '!');
}

模板元编程 (TMP)

模板元编程（ TMP ）是一种在编译时执行的基于模板的 C++ 程序。它利用模板机制在编译期间生成代码，从而将工作从运行时转移到编译时，提高程序的效率并实现早期错误检测，TMP 可以用于生成编译时的常量、类型计算和编译时的条件分支

编译期计算

计算阶乘：通过递归模板实例化实现阶乘计算

#include <iostream>

template <int N>
struct Factorial {
    static const int value = N * Factorial<N-1>::value;
};

template <>
struct Factorial<0> {
    static const int value = 1;
};

int main() {
    std::cout << Factorial<5>::value; // 输出120
}

类型萃取（Type Traits）

主要用于在编译时获取和操作类型信息。通过类型萃取，程序可以根据类型信息进行编译时决策，从而提高代码的性能和安全性。类型萃取的核心思想是将不同类型的数据抽象为具有相同属性的类别，使得函数能够对不同的参数表现一致

template <typename T>
struct is_pointer {
    static const bool value = false;
};

template <typename T>
struct is_pointer<T*> {
    static const bool value = true;
};

template <typename T>
void process(T value) {
    if constexpr (is_pointer<T>::value) {
        std::cout << "Pointer: " << *value << "\n";
    } else {
        std::cout << "Value: " << value << "\n";
    }
}

概念与约束 (C++20)

这是最重要的现代 TMP 特性！概念极大地简化了模板约束的写法，让错误信息更友好，代码可读性更强。优先学习使用标准概念 ( <concepts> 头文件 )，然后尝试定义自己的概念

template <typename T>
concept Numeric = std::integral<T> || std::floating_point<T>;

template <Numeric T>
T square(T x) {
    return x * x;
}

template <typename T>
requires Numeric<T>
T cube(T x) {
    return x * x * x;
}

模板高级技巧

CRTP (奇异递归模板模式)

CRTP 的核心思想是利用模板和继承的特性，在编译时进行多态操作，提高代码的性能和灵活，这种模式允许基类通过静态转换访问派生类的成员函数，从而实现静态多态

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

class Derived : public Base<Derived> {
public:
    void implementation() {
        std::cout << "Derived implementation\n";
    }
};

类型擦除

类型擦除是指在编程中消除或隐藏原有类型，以获得更好的扩展性、减少耦合和简化代码，在 C++ 中，有多种实现类型擦除的方法，每种方法都有其优缺点。以下是几种常见的类型擦除方法及其详细说明

多态擦除类型 ：通过将派生类型转换为基类型，实现多态调用

优点： 实现简单，易于理解

缺点： 仅是部分类型擦除，依赖于继承关系，导致对象间的耦合

struct BaseClass {
    virtual std::string getName() const = 0;
};

struct Bar : BaseClass {
    std::string getName() const override {
        return "Bar";
    }
};

struct Foo : BaseClass {
    std::string getName() const override {
        return "Foo";
    }
};

void printName(std::vector<const BaseClass*> vec) {
    for(auto v : vec) std::cout << v->getName() << "\n";
}

模板擦除类型 ：通过模板抽象不同类型的共同行为

优点： 降低耦合，提高代码的灵活性

缺点： 基本类型仍需指定，未完全消除类型信息

// 在这个例子中，printName 函数模板可以接受任何具有 getName 方法的对象

template<typename T>
void printName(const T& obj) {
    std::cout << obj.getName() << "\n";
}

容器擦除类型 ：将多种类型封装在一个容器中，如 boost::variant

优点： 实现类型擦除，支持多种类型

缺点： 容器类型需事先定义，不支持动态类型

using Shape = std::variant<Circle, Square, Triangle>;
struct GenericInvoker {
    template<typename T>
    void operator()(T& shape) const {
        shape.draw();
    }
};

void drawShapes(const std::vector<Shape>& shapes) {
    for (const auto& shape : shapes) {
        std::visit(GenericInvoker(), shape);
    }
}

通用类型擦除类型 ：类似 C# 和 Java 中的 object，通过 boost::any 实现

优点： 无需预先定义类型，灵活性高

缺点： 取值时仍依赖于具体类型

unordered_map<string, boost::any> m_creatorMap;

m_creatorMap.insert(make_pair(strKey, new T)); // T may be any type

boost::any obj = m_creatorMap[strKey];

T t = boost::any_cast<T>(obj);

闭包擦除类型 ：利用 C++11 的闭包（ lambda 表达式），实现函数式编程风格

优点： 抽象出公共行为，无需关心具体类型，解决前四种方式的局限性

缺点： 实现复杂

std::map<const char, std::function<double(double, double)>> dispTable{
    {'+', add},
    {'-', Sub()},
    {'*', std::bind(multThree, 1, _1, _2)},
    {'/', [](double a, double b){ return a / b; }}
};

泛型编程

泛型编程的核心思想是通过模板（ Templates ）来实现，使得函数和类能够适用于多种数据类型，编写独立于特定类型的算法和数据结构，原则：算法与数据结构分离、通过迭代器作为中介、类型安全下的代码复用

泛型编程的典范

容器

如动态数组、链表、树等数据结构的通用实现

#include <vector>
#include <list>
#include <map>

// 通用算法处理不同容器
template <typename Container>
void processContainer(Container& c) {
    for (auto& elem : c) {
        // 处理元素
    }
}

int main() {
    std::vector<int> vec = {1, 2, 3};
    std::list<std::string> lst = {"a", "b", "c"};
    std::map<int, std::string> map = {{1, "one"}, {2, "two"}};
    
    processContainer(vec);
    processContainer(lst);
    processContainer(map);
}

迭代器

C++ 标准库中的泛型算法（如 find, sort, copy 等）都是通过迭代器来操作容器的。这些算法不直接作用于容器，而是通过迭代器来访问和修改容器中的元素。这种设计使得算法可以独立于容器的类型，从而实现了真正的泛型编程

template <typename InputIt, typename T>
InputIt find(InputIt first, InputIt last, const T& value) {
    for (; first != last; ++first) {
        if (*first == value) {
            return first;
        }
    }
    return last;
}

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto it = find(vec.begin(), vec.end(), 3);
    if (it != vec.end()) {
        std::cout << "Found: " << *it << "\n";
    }
}

算法

排序、查找等算法适配任意可比较类型

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 5, 6};
    
    // 排序
    std::sort(numbers.begin(), numbers.end());
    
    // 反转
    std::reverse(numbers.begin(), numbers.end());
    
    // 查找
    auto pos = std::find(numbers.begin(), numbers.end(), 5);
    
    // 累加
    int sum = std::accumulate(numbers.begin(), numbers.end(), 0);
}

策略模式与泛型

策略模式： 是一种行为设计模式，它定义了一系列算法，并将每个算法封装起来，使它们可以互相替换。策略模式让算法独立于使用它的客户端而变化。在 C++ 中，策略模式通常通过继承和多态来实现，但也可以结合泛型编程来增强其灵活性和通用性

template <typename T, typename Compare = std::less<T>>
class PriorityQueue {
    std::vector<T> data;
    Compare comp;
    
public:
    void push(const T& value) {
        data.push_back(value);
        std::push_heap(data.begin(), data.end(), comp);
    }
    
    void pop() {
        std::pop_heap(data.begin(), data.end(), comp);
        data.pop_back();
    }
    
    const T& top() const { return data.front(); }
};

int main() {
    // 默认最小堆
    PriorityQueue<int> minHeap;
    
    // 最大堆
    PriorityQueue<int, std::greater<int>> maxHeap;
}

泛型编程高级技巧

标签分发（Tag Dispatching）

标签分发的核心思想是： 通过定义一些空类作为标签（ tags ），然后在函数模板中使用这些标签作为参数，从而实现基于类型属性的函数重载。编译器会根据传入的标签类型选择合适的函数版本

struct input_iterator_tag {};
struct random_access_iterator_tag {};

template <typename Iter>
void advance_impl(Iter& it, int n, input_iterator_tag) {
    while (n-- > 0) ++it;
}

template <typename Iter>
void advance_impl(Iter& it, int n, random_access_iterator_tag) {
    it += n;
}

template <typename Iter>
void advance(Iter& it, int n) {
    using category = typename std::iterator_traits<Iter>::iterator_category;
    advance_impl(it, n, category{});
}

SFINAE (替换失败不是错误)

SFINAE 的核心思想是： 当编译器尝试将模板参数替换为实际类型时，如果替换失败，编译器不会报错，而是忽略该特化，继续尝试其他可能的实例化。这种机制使得开发者可以控制模板的重载行为，从而实现更精细的类型约束和条件编译

template <typename T>
class has_size {
    using yes = char[1];
    using no = char[2];

    template <typename U> 
    static auto test(U* p) -> decltype(p->size(), yes{});
    
    template <typename> 
    static no& test(...);
    
public:
    static const bool value = sizeof(test<T>(nullptr)) == sizeof(yes);
};

template <typename T>
std::enable_if_t<has_size<T>::value, void> printSize(const T& obj) {
    std::cout << "Size: " << obj.size() << "\n";
}

template <typename T>
std::enable_if_t<!has_size<T>::value, void> printSize(const T&) {
    std::cout << "No size method\n";
}

现代C++泛型编程特性

auto 与 decltype

template <typename Container>
auto getFirst(Container& c) -> decltype(c.front()) {
    return c.front();
}

template <typename T1, typename T2>
auto add(T1 a, T2 b) -> decltype(a + b) {
    return a + b;
}

完美转发

template <typename... Args>
void logAndCreate(Args&&... args) {
    std::cout << "Creating object\n";
    // 完美转发参数
    T obj(std::forward<Args>(args)...);
    return obj;
}

泛型编程注意

1. 约束模板参数： 使用概念或 static_assert 确保类型满足要求

1
2
3

template <typename T>
requires std::copyable<T>
void safeCopy(T a, T b) { ... }

2. 避免不必要的泛化： 只在真正需要复用代码时使用模板

3. 提供清晰的错误信息： 使用 static_assert 和概念改进错误消息

template <typename T>
void process(T value) {
    static_assert(std::is_arithmetic_v<T>, 
                 "T must be an arithmetic type");
    // ...
}

4. 考虑性能影响： 模板实例化可能导致代码膨胀

5. 使用类型别名简化复杂类型

template <typename T>
using Matrix = std::vector<std::vector<T>>;

Matrix<double> rotation(3, std::vector<double>(3));

3. 吃透 STL

STL 是 C++ 标准库的一部分，提供了丰富的数据结构、算法和迭代器，用于简化和加速常见的编程任务。STL 的设计基于泛型编程，允许开发者在处理不同类型的数据时使用统一的接口，而不必重复编写不同的数据结构和算法。STL 的核心组件包括容器（ Containers ）、迭代器（ Iterators ）和算法（ Algorithms ）

容器

深刻理解每种容器的底层数据结构（ vector 是动态数组，list 是双向链表，map/set 通常是红黑树，unordered_map/set 是哈希表），这是选择合适容器的依据，理解迭代器失效规则至关重要

1. 顺序容器

vector

vector： 底层基于连续内存块实现，通过三个指针管理空间

template <typename T, typename Alloc = allocator<T>> 
class vector { 
private:
    T* start;       // 指向内存块的起始位置 
    T* finish;      // 指向已使用内存的末尾（size = finish - start）
    T* end_of_storage;  // 指向内存块的末尾（capacity = end_of_storage - start）
    Alloc alloc;    // 空间配置器（管理内存分配/释放）
};

当调用 push_back、emplace_back 等添加元素的操作时，会检查 if (size() == capacity()) ，即满载，向其添加元素会导致扩容

扩容详细过程

默认策略： 原容量的 2 倍（如 libstdc++ ）或 1.5 倍（部分实现，如 libc++ ），Visual Studio ( VS ) 通常会扩容现有容器容量的 50%，GCC 和 Clang 通常会扩容现有容器容量的 100%（即两倍）。特殊情况：若原容量为0（空容器），则新容量设为最小容量（如1或4，取决于实现）。例如：vector<int> v，初始 capacity=0，第一次 push_back 后 capacity=1；第二次 push_back 时 capacity 扩容为2；第三次扩容为4，依此类推

1. 分配新内存： 完全弃用现有的内存空间，重新申请更大的内存空间，通过alloc.allocate(new_capacity) 申请一块连续的新内存（大小为 new_capacity * sizeof(T) ）

2. 拷贝旧数据： 将旧内存空间中的数据按原有顺序移动到新的内存空间中。对于 POD 类型（如 int、char ）：直接用 memcpy 拷贝旧内存到新内存（高效）。对于自定义类型：调用拷贝构造函数（ T(const T&) ）或移动构造函数（ T(T&&)，C++11+ ）拷贝元素。若元素是大型对象（如包含动态内存的类），拷贝成本极高。例如：vector<BigObject> v，扩容时需逐个拷贝 BigObject 对象，若 BigObject 的拷贝构造函数复杂（如深拷贝），则性能急剧下降

3. 释放旧内存： 最后将旧的内存空间释放，通过 alloc.deallocate(start, old_capacity) 释放旧内存，并将 start 指向新内存，finish 指向新内存的原元素末尾，end_of_storage 指向新内存的末尾

4. 插入新元素： 将新元素插入到 finish 位置，finish 自增1

底层实现细节： vector 的内存分配完全由 allocator 管理（如 std::allocator ）。allocator 负责：allocate(n)：申请n个元素的连续内存（未构造对象）；construct(p, val)：在p指向的内存构造对象（调用构造函数）；deallocate(p, n)：释放p指向的n个元素内存；destroy(p)：销毁 p 指向的对象（调用析构函数）

性能影响与优化

性能瓶颈：

拷贝成本： 当存储大型对象或自定义类型时，频繁扩容会导致大量拷贝操作，性能下降明显（如 vector<vector<int>>，扩容时需拷贝所有子 vector ）
迭代器失效： 扩容操作会导致与之相关的指针、引用和迭代器失效，（如 auto it = v.begin(); v.push_back(1); // it失效），因为旧的内存空间被释放，新的内存空间被分配。因此，在进行连续插入或删除操作时，需要更新迭代器，否则第一次插入或删除后，迭代器就会失效

优化策略：

1. 提前预留容量： 使用 reserve(n) 函数提前分配 n 个元素的容量，避免频繁扩容。例如：vector<int> v; v.reserve(1000); ，此时 capacity() 变为 1000，后续 push_back 不会触发扩容（直到 size() 达到1000 ）

2. 使用 emplace_back 替代 push_back ： emplace_back 直接在容器内存中构造对象（调用构造函数），避免临时对象的拷贝（如 v.emplace_back(1, "hello") ，直接构造MyClass(1, "hello") ，而 push_back(MyClass(1, "hello")) 需要先构造临时对象，再拷贝）

3. 避免存储大型对象： 若需存储大型对象，建议存储指针（如 vector<BigObject*> ）或智能指针（如 vector<std::unique_ptr<BigObject>> ），这样扩容时只需拷贝指针（成本极低）

list

list： 底层实现为带头节点的双向循环链表。每个节点包含数据和两个指针，分别指向其前一个节点和后一个节点。这种结构使得 list 在任意位置进行插入和删除操作的时间复杂度为 O(1)，但不支持随机访问，访问某个元素的时间复杂度为 O(n），内存非连续，节点在堆中动态分配，无连续内存要求，因此不存在类似 vector 的 “扩容” 概念

struct ListNode {
    T data;                // 存储数据 
    ListNode* prev;        // 指向前驱节点
    ListNode* next;        // 指向后继节点
};

头节点（ Dummy Node ）：不存储有效数据，其 prev 指向尾节点，next 指向首节点，形成循环结构

节点创建与内存管理

当插入新元素时：

1. 动态分配节点内存： 当需要在某个位置插入一个新元素时，首先创建一个新的节点

1 2	ListNode* new_node = allocator.allocate(1); // 调用分配器申请单个节点内存 allocator.construct(&new_node->data, val); // 在节点上构造对象

2. 调整指针链接： 插入位置定位，通过迭代器找到插入点 pos，调整相邻节点指针

// 调整相邻节点指针
void insert(iterator pos, const T& val) {
    Node* pNewNode = new Node(val);
    Node* pCur = pos._node;
    pNewNode->_prev = pCur->_prev;// 新节点前驱 = 原位置前驱
    pNewNode->_next = pCur; // 新节点后继 = 原位置节点 
    pNewNode->_prev->_next = pNewNode;// 原前驱的后继指向新节点 
    pCur->_prev = pNewNode;// 原位置前驱指向新节点 
}

3. 无预分配与搬移： 每次插入仅新增一个节点，无需整体内存迁移，时间复杂度恒为 O(1)

当删除操作时：

当需要删除某个位置的元素时，只需调整相邻节点的指针，并释放该节点的空间

void erase(iterator pos) {
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;
    prev->_next = next;
    next->_prev = prev;
    delete cur;
}

性能优化策略：

list 是基于双向链表实现的容器，适合频繁的插入和删除操作
每次插入或删除一个元素时，只需配置或释放一个节点的空间，因此不需要像 std::vector 那样进行扩容操作
由于节点不是连续存储的，因此不支持随机访问，访问某个元素的时间复杂度为 O(n)

deque

deque（双端队列）： 以空间碎片化换取高效的双端操作，避免 vector 扩容时的整体拷贝，双端队列： 通过分段连续空间实现逻辑上的连续线性空间，迭代器需动态检测缓冲区边界，遍历效率低于 vector（推荐 vector 排序后转存 deque ），实现了高效地在序列两端添加或删除元素的能力。其扩容机制主要涉及 map 数组的扩展和 node 的分配，确保了在需要时能够动态地增加存储空间

核心组件

中控器（map）： 本质是动态数组（如T** ），存储指向各缓冲区的指针（称为节点），初始 map 大小由实现决定（如 GCC 默认为8 ），每个节点指向固定大小的缓冲区（如512字节）
缓冲区（Buffer）： 实际存储元素的连续空间，默认大小与元素类型相关（ sizeof(T)*512 ）
迭代器结构包含四个指针： cur（当前元素）、first/last（缓冲区首尾）、node（指向map中的节点），通过重载 operator++/– 处理跨缓冲区移动，维护 “逻辑连续” 的假象

deque 的迭代器设计复杂，因为它需要处理多个不连续的内存块

_Self& operator++() _GLIBCXX_NOEXCEPT {
    ++_M_cur;
    if (_M_cur == _M_last) { // 进入下一个 node
        _M_set_node(_M_node + 1);
        _M_cur = _M_first;
    }
    return *this;
}

_Self& operator--() _GLIBCXX_NOEXCEPT {
    if (_M_cur == _M_first) { // 进入上一个 node
        _M_set_node(_M_node - 1);
        _M_cur = _M_last;
    }
    --_M_cur;
    return *this;
}

扩容机制

deque 的扩容主要涉及 map 数组的扩展和 node 的分配。当 map 数组已满时，需要申请更大的连续空间供 map 数组使用，并将原有数据拷贝到新的 map 数组中，然后释放旧的空间

// deque扩容核心伪代码
void push_back(const T& value) {
    if (尾缓冲区有空间) {
        在尾缓冲区插入value;
    } else {
        分配新缓冲区;
        if (map空间不足) {
            新map_size = 旧map_size * 2;
            创建新map，拷贝原指针并预留头部空位;
            释放旧map;
        }
        将新缓冲区指针加入map尾部;
        在新缓冲区头部插入value;
    }
}

扩容时机: 当 map 数组已满时
扩容方式: 申请一块更大的连续空间供 map 数组使用，将原有数据（很多指针）拷贝到新的 map 数组中，然后释放旧 map 数组的空间（不释放 map 数组中的指针指向的空间）

void _M_reserve_map_at_back(size_t __nodes_to_add = 1) {
    if (__nodes_to_add + 1 > this->_M_impl._M_map_size - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
        _M_reallocate_map(__nodes_to_add, false);
}

void _M_reallocate_map(size_t __nodes_to_add, bool __add_at_front) {
    const size_t __old_num_nodes = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
    const size_t __new_num_nodes = __old_num_nodes + __nodes_to_add;

    _Map_pointer __new_nstart;
    if (this->_M_impl._M_map_size > 2 * __new_num_nodes) {
        __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size - __new_num_nodes) / 2 + (__add_at_front ? __nodes_to_add : 0);
        if (__new_nstart < this->_M_impl._M_start._M_node)
            std::copy(this->_M_impl._M_start._M_node, this->_M_impl._M_finish._M_node + 1, __new_nstart);
        else
            std::copy_backward(this->_M_impl._M_start._M_node, this->_M_impl._M_finish._M_node + 1, __new_nstart + __old_num_nodes);
    } else {
        size_t __new_map_size = this->_M_impl._M_map_size + std::max(this->_M_impl._M_map_size, __nodes_to_add) + 2;
        _Map_pointer __new_map = _M_allocate_map(__new_map_size);
        __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 + (__add_at_front ? __nodes_to_add : 0);
        std::copy(this->_M_impl._M_start._M_node, this->_M_impl._M_finish._M_node + 1, __new_nstart);
        _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
        this->_M_impl._M_map = __new_map;
        this->_M_impl._M_map_size = __new_map_size;
    }

    this->_M_impl._M_start._M_set_node(__new_nstart);
    this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
}

array

固定大小的数组，提供常数时间访问，其底层实现基于连续内存的线性排列，并且不维护任何多余的数据，由于 array 的大小在编译时确定且固定，因此它不支持扩容，使用 std::tuple ，重载了相关函数，支持 [] 操作符以及 begin(), end(), front() 等标准接口

forward_list

forward_list 是 C++11 引入的一种单向链表容器。其底层数据结构是一个单链表，每个节点只包含一个指向下一个节点的指针和存储数据的成员变量，按需为每个节点分配内存，无需预先分配连续空间，仅需调整指针，无需移动元素，单链表节点比双向链表更节省内存，仅支持前向迭代，无法反向遍历

template <typename T>
struct ForwardListNode { 
    T data;               // 数据域
    ForwardListNode* next; // 指向 next 节点的指针 
    // 构造函数（用于 emplace 操作）
    template <typename... Args>
    ForwardListNode(Args&&... args) : data(std::forward<Args>(args)...), next(nullptr) {} 
};

forward_list 的 “插入” 与 “内存分配” 过程：

分配节点内存：使用分配器（ Allocator ）为新节点分配内存（默认使用 std::allocator ）
构造元素：
- 若使用 push_front(const T& value) ：拷贝 value 到节点的数据域
- 若使用 emplace_front(Args&&... args) ：直接在节点内存中原地构造元素（避免拷贝/移动，更高效）
链接节点：将新节点的 next 指针指向原链表的头节点，再将链表的头指针（ head ）指向新节点

template <typename T, typename Allocator>
void forward_list<T, Allocator>::emplace_front(Args&&... args) { 
    // 1. 分配节点内存（通过分配器） 
    Node* new_node = allocator_traits::allocate(alloc_, 1); 
    try { 
        // 2. 原地构造元素（避免拷贝）
        allocator_traits::construct(alloc_, new_node, std::forward<Args>(args)...); 
    } catch (...) { 
        // 构造失败，释放内存 
        allocator_traits::deallocate(alloc_, new_node, 1); 
        throw;
    } 
    // 3. 链接新节点到链表头部 
    new_node->next = head_; 
    head_ = new_node;
}

2. 关联容器

set

set： 唯一元素集合，支持快速搜索，set 的底层实现是基于红黑树（ Red-Black Tree ）的数据结构。红黑树是一种自平衡的二叉查找树（ Balanced BST ），它确保了在最坏情况下的操作时间复杂度为 O(log n)，红黑树的平衡性直接决定了 set 的扩容效率，无需像动态数组一样重新分配内存空间

扩容过程：红黑树的动态调整

set 的扩容并非传统意义上的内存扩展，而是通过红黑树的插入/删除操作动态调整结构实现

1. 插入新元素： 通过二叉搜索找到合适位置，插入新节点（默认为红色），若插入节点的父节点为红色，则可能违反红黑树规则，需通过旋转（左旋/右旋）和重新着色恢复平衡，set 的 insert() 返回 pair<iterator, bool>（成功状态）

#include <iostream>
#include <set>

int main() {
    std::set<int> s;
    s.insert(10); // 插入元素 10
    s.insert(5);  // 插入元素 5
    s.insert(15); // 插入元素 15

    for (const auto& elem : s) {
        std::cout << elem << " "; // 输出: 5 10 15
    }
    std::cout << std::endl;

    return 0;
}

2. 删除元素： 找到目标节点，若节点有两个子节点，需找到其前驱或后继替代，删除可能导致黑高度变化，需通过旋转和重新着色修复平衡

#include <set>
#include <iostream>
using namespace std;

int main() { 
    set<int> s = {1, 2, 3, 4, 5}; 
    size_t count = s.erase(3);  // 删除键值3
    cout << "删除数量：" << count << endl; // 输出：1 
    for (int x : s) cout << x << " "; // 输出：1 2 4 5 
    return 0;
}

3. 平衡调整的核心操作：

左旋（Left Rotation）： 将右子节点提升为父节点，原父节点成为左子节点

右旋（Right Rotation）： 将左子节点提升为父节点，原父节点成为右子节点

重新着色： 通过改变节点颜色解决连续红色节点问题

总结：

set 的扩容本质是红黑树的动态平衡调整，通过旋转和重新着色维护高效性，无需内存拷贝。这一特性使其在有序集合操作（如交并集）和高频插入/删除场景中表现优异，但牺牲了内存连续性带来的缓存优势。理解红黑树的平衡机制是掌握 set 性能调优的关键

multiset

multiset： 有序可重复元素集合，允许重复值，也支持快速搜索，底层实现也是基于红黑树

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms;

    // 插入元素
    ms.insert(5);
    ms.insert(3);
    ms.insert(7);
    ms.insert(3); // 允许重复元素

    // 遍历元素
    std::cout << "Multiset elements: ";
    for (auto it = ms.begin(); it != ms.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 删除元素
    ms.erase(3); // 删除所有值为3的元素

    // 再次遍历元素
    std::cout << "Multiset elements after erase: ";
    for (auto it = ms.begin(); it != ms.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

set 的 insert() 返回 pair<iterator, bool>（成功状态），multiset 始终返回新元素迭代器
set 拒绝重复插入；multiset 允许重复，通过 count() 或 equal_range() 统计/访问相同元素
multiset 适合统计频率（如词频分析），但可能被 unordered_multiset（哈希表，O(1) 均摊）替代，后者无序但更快
迭代器失效：直接修改元素值会破坏红黑树结构（需先删除旧值再插入新值）
自定义排序：必须定义严格弱序（ operator< ），否则未定义行为
哈希表容器 unordered_set 在无需排序时更高效（ O(1)查找），但失去有序性

map

map：键值对映射，支持基于键的快速搜索，也是基于红黑树实现，每个节点包含四个字段：left、right、parent 和 rb（红黑标记）。left 和 right 分别指向节点的左子节点和右子节点，parent 指向父节点，rb 用于存储红黑树的红黑属性

Mastering the C++17 STL

插入/删除效率更高： 红黑树是 “近似平衡”（树高 ≤2log(n+1) ），插入/删除时旋转次数最多2次；AVL树是 “严格平衡”（平衡因子≤1 ），插入/删除时旋转次数最多 O(logn)次（如插入链状结构）。

更适合频繁修改： map 的核心功能是 “动态维护键值对”（插入/删除频繁），红黑树的低旋转次数大幅提升了修改效率

对比哈希表（ unordered_map ），map 的优势是有序性（支持范围查询，如 lower_bound()、upper_bound() ），且无哈希冲突风险（ unordered_map 在冲突严重时性能退化）

总结

若需有序、频繁修改的键值对存储（如用户权限管理、交易记录索引），优先选 map；若需无序、快速查询（如缓存），选 unordered_map；若需连续存储（如数组），选 vector

3. 容器适配器

stack

stack： 是一个容器适配器，它本身并不是一个容器，而是基于其他容器（如 deque、vector 或 list ）实现的。默认情况下，std::stack 使用 deque 作为其底层容器。这是因为 deque 提供了高效的随机访问、插入和删除操作，特别适合用作栈的底层容器。其核心逻辑是限制底层容器的接口，仅暴露栈操作（后进先出，LIFO ）

template<class T, class Container = std::deque<T>>
class stack {
protected:
    Container c; // 底层容器
public:
    // 成员函数
    bool empty() const { return c.empty(); }
    size_t size() const { return c.size(); }
    T& top() { return c.back(); }
    const T& top() const { return c.back(); }
    void push(const T& x) { c.push_back(x); }
    void pop() { c.pop_back(); }
    void swap(stack& other) { std::swap(c, other.c); }
};

一些关键成员函数及其底层实现：

empty()： 检查栈是否为空，通过调用底层容器的 empty() 函数实现
size()： 返回栈中元素的数量，通过调用底层容器的 size() 函数实现
top()： 返回栈顶元素的引用，通过调用底层容器的 back() 函数实现
push(const T& val)： 将元素压入栈顶，通过调用底层容器的 push_back() 函数实现
pop()： 弹出栈顶元素，通过调用底层容器的 pop_back() 函数实现
emplace(arg…)： 在栈顶直接构造一个对象，通过调用底层容器的 emplace_back() 函数实现
swap(stack & other_stack)： 交换两个栈的内容，通过调用底层容器的 swap() 函数实现

#include <iostream>
#include <stack>
#include <vector>

int main() {
    // 创建一个默认使用 deque 作为底层容器的 stack
    std::stack<int> stk;

    // 使用 vector 作为底层容器的 stack
    std::stack<int, std::vector<int>> stk_vector;

    // 压入元素
    stk.push(1);
    stk.push(2);
    stk.push(3);

    // 输出栈顶元素
    std::cout << "Top element: " << stk.top() << std::endl;

    // 弹出元素
    stk.pop();

    // 输出栈的大小
    std::cout << "Stack size: " << stk.size() << std::endl;

    // 检查栈是否为空
    std::cout << "Is stack empty? " << (stk.empty() ? "Yes" : "No") << std::endl;

    return 0;
}

queue

queue 是 C++ 标准模板库 ( STL ) 中的一种容器适配器，专门用于实现先进先出 ( FIFO ) 的数据结构。它通过封装一个底层容器来提供一组特定的成员函数来访问其元素。默认情况下，queue 使用 deque 作为其底层容器，但也可以指定 list 作为底层容器

template<typename T, typename Container = deque<T>>  
class queue {  
  protected:  
    Container c;  // 底层容器（默认 deque）  
  public:  
    void push(const T& value) { c.push_back(value);  }  
    void pop() { c.pop_front();  }  
    T& front() { return c.front();  }  
};

queue 提供了以下主要成员函数：

empty()： 检查队列是否为空
size()： 返回队列中元素的数量
front()： 返回队列的第一个元素的引用
back()： 返回队列的最后一个元素的引用
push(const T& x)： 在队列的末尾添加一个元素
pop()： 移除队列的第一个元素

#include <iostream>
#include <queue>

int main() {
    std::queue<int> iqueue;

    // 向队列中添加元素
    iqueue.push(1);
    iqueue.push(2);
    iqueue.push(3);

    // 输出队列中的元素
    while (!iqueue.empty()) {
        int i = iqueue.front();
        std::cout << i << " ";
        iqueue.pop();
    }
    std::cout << std::endl;

    return 0;
}

deque 以分块内存实现 O(1) 头尾操作，但内存开销较 vector 高 10-15%
避免用 vector 作底层容器，pop_front() 会触发 O(n) 搬移
超大型元素（ >128B ）用 list；固定大小队列用 circular_buffer

priority_queue

priority_queue 是 C++ 标准模板库 ( STL ) 中的一种容器适配器，用于实现优先队列。优先队列是一种特殊的队列，其中每个元素都有一个优先级，出队顺序取决于其优先级，而非插入顺序。默认情况下，priority_queue 是一个最大堆，即优先级最高的元素（通常是最大的元素）会被优先处理，priority_queue 的底层实现依赖于堆数据结构。堆是一种特殊的完全二叉树，其中每个节点的值都大于或等于其子节点的值（最大堆），或者每个节点的值都小于或等于其子节点的值（最小堆）。在 C++ STL 中，priority_queue 默认使用最大堆

// 默认构造函数，使用 vector 和 std::less<T>
priority_queue<int> q1;

// 使用自定义的比较函数
priority_queue<int, vector<int>, greater<int>> q2;

在 priority_queue 的构造过程中，首先根据传入的迭代器区间初始化底层容器 c，然后调用 make_heap() 使用底层容器建堆。每次插入新元素时，调用 push_heap() 调整堆结构；每次移除元素时，调用 pop_heap() 调整堆结构

template <class InputIterator>
priority_queue(Input_iterator first, Input_iterator last, const compare& x)
    : c(first, last), comp(x) {
    make_heap(c.begin(), c.end(), comp);
}

priority_queue 提供了以下核心操作：

push(const value_type& x)： 向优先队列中插入元素。插入后会自动调整堆结构以保持最大堆或最小堆的性质

pop()： 移除优先队列中优先级最高的元素。移除后会自动调整堆结构以保持最大堆或最小堆的性质

top()： 返回优先队列中优先级最高的元素，但不移除它

empty()： 检查优先队列是否为空

size()： 返回优先队列中元素的数量

#include <iostream>
#include <queue>

int main() {
    // 创建一个最大堆
    std::priority_queue<int> maxHeap;

    // 插入元素
    maxHeap.push(10);
    maxHeap.push(20);
    maxHeap.push(15);

    // 输出元素
    while (!maxHeap.empty()) {
        std::cout << maxHeap.top() << " "; // 输出最大值
        maxHeap.pop(); // 删除最大值
    }
    std::cout << std::endl;

    // 创建一个最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    // 插入元素
    minHeap.push(10);
    minHeap.push(20);
    minHeap.push(15);

    // 输出元素
    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " "; // 输出最小值
        minHeap.pop(); // 删除最小值
    }
    std::cout << std::endl;

    return 0;
}

总结：

priority_queue 是通过封装底层容器（默认为 vector ）并利用 STL 堆算法来实现的优先队列。它提供了高效的插入和删除操作，并且可以通过自定义比较函数来改变优先级规则

算法： 熟悉常用算法 ( find, sort, transform, accumulate 等 )，理解它们的复杂度。学会用 Lambda 和函数对象定制算法行为。了解 C++17 的并行算法。

sort

STL的sort采用内省排序（ Introsort ），结合了快速排序（ Quick Sort ）、堆排序（ Heap Sort ）和插入排序（ Insertion Sort ），优化了快速排序的递归深度问题

选择枢轴（ Pivot ）（通常取中间元素）
分割（ Partition ）：将序列分为两部分，左半部分≤枢轴，右半部分≥枢轴
递归排序左右子序列

当递归深度超过2log₂n（ n 为序列长度）时，切换为堆排序（避免快速排序的最坏情况O(n²) ）。
当子序列长度小于16时，切换为插入排序（小数据量下插入排序效率更高）

时间复杂度：平均 O(n log n)，最坏 O(n log n)（因堆排序优化）

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional> // 用于greater<> 
 
int main() { 
    std::vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6}; 
    
    // 1. 默认升序排序（使用less<>）
    std::sort(nums.begin(),  nums.end());  
    std::cout << "升序: "; 
    for (int num : nums) std::cout << num << " "; // 输出: 1 1 2 3 4 5 6 9
    
    // 2. 降序排序（使用greater<>）
    std::sort(nums.begin(),  nums.end(),  std::greater<int>()); 
    std::cout << "\n降序: "; 
    for (int num : nums) std::cout << num << " "; // 输出: 9 6 5 4 3 2 1 1
    
    // 3. 自定义排序（lambda表达式，按绝对值排序）
    std::vector<int> nums2 = {-3, 1, -4, 1, 5, -9, 2, 6}; 
    std::sort(nums2.begin(),  nums2.end(),  [](int a, int b) { 
        return std::abs(a) < std::abs(b); 
    }); 
    std::cout << "\n按绝对值升序: "; 
    for (int num : nums2) std::cout << num << " "; // 输出: 1 1 2 -3 -4 5 6 -9
    
    return 0;
}

find

find 是 C++ 标准模板库（ STL ）中非变易算法（ Non-mutating Algorithm ）的典型代表，用于在指定区间内查找第一个等于目标值的元素。它定义在 <algorithm> 头文件中，依赖迭代器遍历容器，不修改原始数据，find 的底层实现遵循线性遍历逻辑，核心是相等性比较（ == 运算符）

template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value) {
    while (first != last && *first != value) ++first;
    return first;
}

以上这段代码的核心逻辑是一个 while 循环，它会不断递增迭代器 first，直到 first 指向的元素等于目标值 value 或者 first 达到范围的末尾 last。如果找到了目标值，函数返回指向该值的迭代器；否则，返回 last 迭代器，表示未找到目标值

关键特性

相等性比较： std::find 使用 == 运算符判断元素是否相等，因此自定义类型必须重载 operator==，否则无法编译

线性时间复杂度： 最坏情况下需遍历整个区间（如目标值不存在），时间复杂度为 O(n)（ n为区间元素个数）

第一个匹配项： 仅返回第一个满足条件的元素，若需查找所有匹配项，需循环调用 std::find

#include <iostream>
#include <vector>
#include <algorithm>
 
int main() { 
    std::vector<int> numbers = {1, 2, 3, 4, 5}; 
    int target = 3;
 
    auto it = std::find(numbers.begin(),  numbers.end(),  target); 
 
    if (it != numbers.end())  { 
        numbers.erase(it);   // 删除找到的元素 
        std::cout << "删除元素 " << target << " 后，容器内容："; 
        for (int num : numbers) { 
            std::cout << num << " "; 
        } 
        std::cout << std::endl;
    } else { 
        std::cout << "未找到元素 " << target << std::endl;
    } 
 
    return 0;
}

其他库组件： string_view ( 零拷贝字符串“视图” )、filesystem ( 跨平台文件操作 )、chrono ( 精确时间处理 )、regex ( 正则表达式 ) 等都是非常实用的现代库

4. 征服并发与内存模型

C++11 引入了正式的内存模型，用于定义程序中不同线程间内存操作如何互相影响。内存模型的主要目标是提供一种机制，使得程序员可以理解和预测多线程程序的行为，特别是在涉及共享数据时

1. 内存模型基础

内存模型主要关注两个方面：基本结构（与对象和内存位置的布局有关）和并发（与多线程环境下的操作顺序和可见性有关）。在 C++ 中，所有数据都是由对象构成，而这些对象存储在内存位置中。每个内存位置可以是一个标量类型（如 unsigned short 或 my_class* ）的对象，或者是一系列相邻的位字段

每个变量占独立内存位置（位域除外），相邻位域共享同一位置
所有线程对同一对象的写操作必须形成全局一致序列
位域处理易引发数据竞争，需显式同步（如互斥锁）避免未定义行为

2. 原子操作与类型

C++ 标准库提供了多种原子类型，如 std::atomic<int>、std::atomic<bool>、std::atomic<T*> 等。这些原子类型支持一系列的操作，包括但不限于 load、store、exchange、compare_exchange_weak、compare_exchange_strong、fetch_add、fetch_sub、fetch_or、fetch_and、fetch_xor 等。这些操作确保了对共享数据的访问是原子的( 不可分割的操作，确保读写一次完成 )，从而避免了数据竞争

多数原子类型通过 CPU 指令（如 x86 的 LOCK 前缀）直接实现，性能比互斥量高60-70%
复杂类型（如 atomic<struct> ）可能用内部锁，需 is_lock_free ( ) 检测
用户自定义原子类型需满足可平凡复制（ Trivially Copyable ），否则限制应用场景

#include <atomic>
#include <thread>
#include <iostream>

std::atomic<int> x(0);
std::atomic<int> y(0);
std::atomic<int> z(0);

void increment(std::atomic<int>* var, int* values) {
    for (int i = 0; i < 10; ++i) {
        values[i] = var->fetch_add(1);
    }
}

void read_vals(int* values) {
    for (int i = 0; i < 10; ++i) {
        values[i] = x.load();
        values[i + 10] = y.load();
        values[i + 20] = z.load();
    }
}

int main() {
    int values1[10], values2[10], values3[10], values4[30], values5[30];
    std::thread t1(increment, &x, values1);
    std::thread t2(increment, &y, values2);
    std::thread t3(increment, &z, values3);
    std::thread t4(read_vals, values4);
    std::thread t5(read_vals, values5);

    t1.join();
    t2.join();
    t3.join();
    t4.join();
    t5.join();

    // 打印结果
    for (int i = 0; i < 10; ++i) {
        std::cout << "values1[" << i << "] = " << values1[i] << std::endl;
        std::cout << "values2[" << i << "] = " << values2[i] << std::endl;
        std::cout << "values3[" << i << "] = " << values3[i] << std::endl;
        std::cout << "values4[" << i << "] = " << values4[i] << std::endl;
        std::cout << "values5[" << i << "] = " << values5[i] << std::endl;
    }

    return 0;
}

3. 内存顺序（Memory Ordering）

内存顺序的本质是约束编译器和CPU的优化行为，确保多线程间的操作顺序和数据可见性符合程序员的预期，具体解决以下问题：

编译器乱序优化： 编译器可能调整代码顺序以提高性能，但会破坏多线程间的依赖关系
CPU乱序执行： CPU 可能并行执行指令或重排顺序，导致线程间看到的操作顺序不一致
缓存一致性： 多核 CPU 的缓存可能导致不同线程看到同一变量的不同值，内存顺序确保缓存同步

C++11 提供了六种内存序模式：

memory_order_relaxed： 开销低，最弱的内存顺序，仅保证原子性（操作不可分割），不保证操作顺序，编译器和 CPU 可以重排该原子操作与其他操作的顺序，除非明确知道不需要顺序一致性，否则不要使用 relaxed，如计数器、状态标志，不涉及线程间同步
memory_order_consume： 用于读操作，保证后续依赖该值的操作不会重排到该读之前，该语义目前不鼓励使用（规范修订中），建议用 acquire 代替
memory_order_acquire： 保证当前线程中所有后续操作在读取操作之后执行
memory_order_release： 保证当前线程中所有前续操作在写入操作之前执行

data = prepare_data(); // 准备数据（前面的操作）
flag.store(true,  memory_order_release); // 发布数据，前面的操作不会重排到后面 

// 消费者线程 
while (!flag.load(memory_order_acquire))  ; // 获取数据，后面的操作不会重排到前面 
process_data(data); // 处理数据（后面的操作）

memory_order_acq_rel： 结合了 acquire 和 release 的特性，同时具备 acquire（读语义）和 release（写语义），用于 读-修改-写（RMW） 操作（如 fetch_add 、compare_exchange_weak ）
memory_order_seq_cst： 最强的内存序，默认值（若未指定内存顺序，原子操作默认使用seq_cst ），所有线程看到的操作顺序全局一致，相当于所有原子操作在一个全局队列中执行，性能最低，因为需要同步所有线程的操作顺序。除非必要，否则应避免使用（可优化为更弱的内存顺序）
正确，再优化： 优先使用 seq_cst 保证正确性，再根据场景尝试更弱的内存顺序（如 acquire/release、relaxed ）
注释内存顺序： 在代码中注释每个原子操作的内存顺序选择理由（如: 使用 relaxed，因为计数器无需同步），便于后续维护
避免memory_order_consume： 该语义目前不鼓励使用（规范修订中），建议用 acquire 代替

#include <atomic>
#include <thread>
#include <iostream>

std::atomic<bool> x(false);
std::atomic<bool> y(false);
std::atomic<int> z(0);

void write_x_then_y() {
    x.store(true, std::memory_order_relaxed); // 1
    y.store(true, std::memory_order_release); // 2
}

void read_y_then_x() {
    while (!y.load(std::memory_order_acquire)); // 3
    if (x.load(std::memory_order_relaxed)) ++z; // 4
}

int main() {
    x = false;
    y = false;
    z = 0;

    std::thread a(write_x_then_y);
    std::thread b(read_y_then_x);

    a.join();
    b.join();

    std::cout << "z = " << z.load() << std::endl;

    return 0;
}

4. 内存屏障（Memory Barrier）

内存屏障用于限制内存访问的重新排序和优化，确保特定的操作顺序。C++ 提供了 std::atomic_thread_fence 函数来创建内存屏障

#include <atomic>
#include <thread>
#include <iostream>

std::atomic<bool> x(false);
std::atomic<bool> y(false);
std::atomic<int> z(0);

void write_x_then_y() {
    x.store(true, std::memory_order_relaxed); // 1
    std::atomic_thread_fence(std::memory_order_release); // 2
    y.store(true, std::memory_order_relaxed); // 3
}

void read_y_then_x() {
    while (!y.load(std::memory_order_acquire)); // 4
    if (x.load(std::memory_order_relaxed)) ++z; // 5
}

int main() {
    x = false;
    y = false;
    z = 0;

    std::thread a(write_x_then_y);
    std::thread b(read_y_then_x);

    a.join();
    b.join();

    std::cout << "z = " << z.load() << std::endl;

    return 0;
}

5. 高级特性与惯用法

function

std::function 是 C++ 标准库中的一个通用多态函数封装器，可以存储、复制和调用任何可调用的目标——函数、lambda 表达式、绑定表达式或其他函数对象

#include <iostream>
#include <functional>
#include <map>

class Test {
public:
    void hello(std::string msg) {
        std::cout << "Hello, " << msg << "!" << std::endl;
    }
};

int main() {
    // 使用 lambda 表达式实例化 function
    std::function<int(int, int)> func4 = [](int a, int b) -> int {
        return a + b;
    };
    std::cout << func4(100, 200) << std::endl;

    // 使用成员函数指针实例化 function
    std::function<void(Test*, std::string)> func5 = &Test::hello;
    func5(&Test(), "call Test::hello!");

    // 使用 function 替代 switch-case 操作
    int choice = 0;
    std::map<int, std::function<void()>> actionMap;
    actionMap.insert({1, []() { std::cout << "查看所有书籍信息" << std::endl; }});
    actionMap.insert({2, []() { std::cout << "借书" << std::endl; }});
    actionMap.insert({3, []() { std::cout << "还书" << std::endl; }});
    actionMap.insert({4, []() { std::cout << "查询书籍" << std::endl; }});
    actionMap.insert({5, []() { std::cout << "注销" << std::endl; }});

    for (;;) {
        std::cout << "-----------------" << std::endl;
        std::cout << "1.查看所有书籍信息" << std::endl;
        std::cout << "2.借书" << std::endl;
        std::cout << "3.还书" << std::endl;
        std::cout << "4.查询书籍" << std::endl;
        std::cout << "5.注销" << std::endl;
        std::cout << "-----------------" << std::endl;
        std::cout << "请选择:";
        std::cin >> choice;

        auto it = actionMap.find(choice);
        if (it == actionMap.end()) {
            std::cout << "输入数字无效，重新选择!" << std::endl;
        } else {
            it->second();
        }
    }

    return 0;
}

实现原理

std::function 的实现原理主要依赖于类型擦除（ type erasure ）技术。它通过存储一个通用的函数对象来封装各种可调用对象。具体来说，std::function 内部维护一个指向具体函数对象的指针，并使用虚函数表（ vtable ）来管理这些对象的调用和销毁操作。当调用 std::function 对象时，实际调用的是存储在内部的函数对象的 operator() 方法

template<typename R, typename... Args>
class function<R(Args...)> {
private:
    struct FunctionBase {
        virtual R operator()(Args... args) = 0;
        virtual FunctionBase* clone() const = 0;
        virtual \~FunctionBase() {}
    };

    template<typename F>
    struct FunctionImpl : public FunctionBase {
        F f;
        FunctionImpl(F f) : f(f) {}
        R operator()(Args... args) override { return f(args...); }
        FunctionBase* clone() const override { return new FunctionImpl(*this); }
    };

    FunctionBase* impl;

public:
    template<typename F>
    function(F f) : impl(new FunctionImpl<F>(f)) {}

    function(const function& other) : impl(other.impl->clone()) {}

    \~function() { delete impl; }

    R operator()(Args... args) { return (*impl)(args...); }
};

C++ 面向对象机制

C++ 面向对象机制的底层实现主要包括类、对象、虚函数、单一继承、多重继承、虚基类、构造函数和析构函数等在底层的实现方法和工作原理

虚函数与多态

虚表（vtable）： 每个含虚函数的类生成虚表，存储函数入口地址
虚指针（vptr）： 对象首地址存储vptr，指向虚表（占用4/8字节）
调用过程： obj.action() → 底层：push this; call [vptr+offset]

继承内存布局

单一继承： 派生类对象包含基类数据 + 自身数据 + 虚表指针
多重继承： 派生类按顺序包含所有基类数据（可能冗余），各自维护虚表指针
虚基类： 通过额外指针间接访问共享基类数据，避免冗余

构造/析构函数

非函数调用： 构造函数代码直接嵌入对象创建处（无函数调用开销）
析构顺序： 反向析构成员，自动调用基类析构

编译期断言

利用模板特化实现编译时检查

1
2
3

template<bool> struct StaticAssert;      // 原始模板
template<> struct StaticAssert<true> {}; // 仅true特化有效
#define STATIC_ASSERT(x) sizeof(StaticAssert<bool(x)>)

6. 异常处理

异常机制与异常安全： C++ 异常处理通过栈展开、异常对象管理和类型匹配实现错误传递。核心是在保证资源安全（ RAII ）的前提下，将控制权转移至匹配的 catch 块。正确使用可提升程序健壮性，但需注意性能影响和资源管理细节

1. 异常对象创建与抛出

当使用 throw 抛出异常时，异常对象会被创建，其生命周期由运行时系统管理。若对象在栈上，直接复制；若在堆上，需手动管理（但通常由编译器自动处理）

异常对象存储在线程信息块（ TIB ）或栈外的特殊内存空间，确保所有 catch 块均可访问，确保其在栈展开过程中持续存在

1	throw std::runtime_error("An error occurred"); // 创建异常对象并抛出

2. 栈展开（Stack Unwinding）

从抛出异常的位置开始，程序沿着函数调用栈逆序查找匹配的 catch 块。在此过程中，会依次调用当前栈帧中局部对象的析构函数（即 RAII 机制中的资源释放）

栈展开依赖编译器生成的元数据（如调用栈信息），通过寄存器（如ebp、esp ）跟踪栈帧位置

若未找到匹配的 catch，程序调用 terminate() 终止

1
2
3

func3() → func2() → func1() → main()

// 若在 func3() 抛出异常，则依次退出 func3、func2、func1，最终在 main() 的 catch 块处理

3. 异常捕获机制

编译器为每个函数生成异常处理链（链表结构），记录 try 块的范围和对应的 catch 块信息

catch 块按声明顺序匹配异常类型。类型必须严格匹配（允许派生类到基类的隐式转换），且支持多态捕获（如catch(const std::exception&) ）

运行时系统通过 nStep（当前执行步骤 ID ）匹配 try 块：

若当前函数的 nStep 值在某个 try 块范围内，检查其 catch 块是否匹配异常类型
若匹配，复制异常对象到 catch 块并执行；否则沿链表向上查找（ prev 指针）直至找到匹配或终止程序

4. 未处理异常

若遍历整个调用栈仍无匹配的 catch 块，调用 terminate() 终止程序
若异常在栈展开过程中再次抛出，同样触发 terminate()

5. 资源管理与RAII

栈展开过程中，局部对象的析构函数自动调用，确保资源（如文件句柄、内存）正确释放。这是 RAII（资源获取即初始化）的核心机制

class FileHandler {
  public:
      FileHandler(const char* name) { 
          file = fopen(name, "r"); 
          if (!file) throw std::runtime_error("Open failed"); 
      }
      ~FileHandler() { if (file) fclose(file); }
  private:
      FILE* file;
};

7. 设计模式

设计模式核心思想： 解决软件设计常见问题的可重用方案

核心目标：

解耦与复用： 分离变化与不变部分，提升代码复用性
扩展性： 通过组合而非继承，支持功能动态扩展（如装饰者模式）
封装变化： 隔离不稳定因素（如策略模式封装算法）
简化复杂性： 通过模式规范复杂对象的创建与交互（如建造者模式）
遵循设计原则： 如单一职责、开闭原则、依赖倒置等

1. 创建型模式

将对象创建与使用分离，隐藏创建细节，提高灵活性

1. 单例模式（Singleton）

确保类只有一个实例，并提供全局访问点，私有化构造函数、拷贝构造和赋值运算符，静态方法返回静态局部变量实例（ C++11起线程安全），如：日志管理器、线程池管理

class Singleton {
  public:
      static Singleton& getInstance() {
          static Singleton instance;  // C++11线程安全 
          return instance;
      }
      void printTest() { std::cout << "Singleton works\n"; }
  private:
      Singleton() {}  // 阻止外部构造 
      Singleton(const Singleton&) = delete;  // 阻止拷贝 
      Singleton& operator=(const Singleton&) = delete; // 阻止赋值 
};
// 使用：Singleton::getInstance().printTest();

2. 工厂模式（Factory）

简单工厂模式

通过工厂类创建不同产品，避免直接调用具体类

class Product {
public:
    virtual void show() = 0;
};
class ProductA : public Product { void show() override { /*...*/ } };
class Factory {
public:
    Product* createProduct(ProductType type) {
        switch(type) {
            case TypeA: return new ProductA();
            // 其他类型分支
        }
    }
};

抽象工厂模式

创建产品家族（多个相关产品），解耦产品创建与使用，支持扩展

class AbstractFactory {
public:
    virtual Product* createProduct() = 0;
};
class ConcreteFactory1 : public AbstractFactory {
    Product* createProduct() override { return new ProductA(); }
};

3. 建造者模式（Builder）

分步构建复杂对象，将复杂对象的构建过程与表示分离，使相同构建过程可创建不同表示，它通过分步骤构建对象，将对象的创建细节封装在独立的建造者类中，由指挥者统一调度构建流程，提高灵活性和可维护性

// 1. 定义产品类 
class Car {
public:
    void setEngine(const string& engine) { engine_ = engine; }
    void setTires(const string& tires) { tires_ = tires; }
    void showSpecs() { cout << "Engine: " << engine_ << ", Tires: " << tires_ << endl; }
private:
    string engine_;
    string tires_;
};
 
// 2. 定义抽象建造者
class CarBuilder {
public:
    virtual void buildEngine() = 0;
    virtual void buildTires() = 0;
    virtual Car* getResult() = 0;
};
 
// 3. 实现具体建造者（跑车）
class SportsCarBuilder : public CarBuilder {
public:
    void buildEngine() override { car_->setEngine("V8 Turbo"); }
    void buildTires() override { car_->setTires("Racing Tires"); }
    Car* getResult() override { return car_; }
private:
    Car* car_ = new Car();
};
 
// 4. 实现指挥者 
class Director {
public:
    void construct(CarBuilder* builder) {
        builder->buildEngine();
        builder->buildTires();  // 固定构建顺序 
    }
};
 
// 客户端使用 
int main() {
    Director director;
    SportsCarBuilder sportsBuilder;
    director.construct(&sportsBuilder); 
    Car* sportsCar = sportsBuilder.getResult(); 
    sportsCar->showSpecs();  // 输出：Engine: V8 Turbo, Tires: Racing Tires 
    delete sportsCar;
    return 0;
}

2. 结构型模式

通过组合类或对象，形成更复杂的结构，解决接口兼容、功能扩展等问题

1. 装饰模式（Decorator）

动态扩展对象功能，避免子类爆炸，通过组合替代继承，动态扩展对象功能（如游戏装备系统）

class Phone {
public:
    virtual void show() { /* 基础功能 */ }
};
class Decorator : public Phone {
protected:
    Phone* phone;
public:
    Decorator(Phone* p) : phone(p) {}
    void show() override { phone->show(); }
};
class ScreenProtector : public Decorator {
    void show() override {
        Decorator::show();
        addProtector();  // 新增功能 
    }
};
// 使用：Phone* iphone = new ScreenProtector(new BasicPhone());

2. 适配器模式（Adapter）

将旧接口转换为新接口，整合不兼容接口（如旧系统改造），使不兼容的类可以协同工作（如将 legacy 系统适配到新框架）

class Target {  // 目标接口
public:
    virtual void request() = 0;
};
class Adaptee {  // 被适配者
public:
    void specificRequest() { /* 原有接口 */ }
};
class Adapter : public Target {
    Adaptee* adaptee;
public:
    void request() override { adaptee->specificRequest(); }
};

3. 行为型模式

定义对象间的通信方式，分配职责，降低耦合

1. 观察者模式（Observer）

一对多依赖关系，主题状态变化时自动通知观察者，发布-订阅机制，事件处理系统、MVC 模型更新，定义对象间的依赖关系（主题-观察者），当主题状态变化时，自动通知所有观察者（如天气站通知用户、GUI 组件交互）

class Observer {
public:
    virtual void update(const string& msg) = 0;
};
class Subject {
private:
    vector<Observer*> observers;
public:
    void attach(Observer* obs) { observers.push_back(obs);  }
    void notify(const string& msg) {
        for (auto obs : observers) obs->update(msg);
    }
};
class User : public Observer {
    void update(const string& msg) override { /* 处理消息 */ }
};
// 使用：subject.attach(&user);  subject.notify(" 新文章发布");

2. 策略模式（Strategy）

封装可互换算法、封装算法族，使算法可动态替换（如排序算法、支付方式）

class DataParser {
public:
    virtual void read() = 0;     // 子类实现
    virtual void process() = 0;
    void parse() {               // 固定流程
        read();
        process();
        write();
    }
};
class CSVParser : public DataParser {
    void read() override { cout << "Reading CSV..."; }
    void process() override { /*...*/ }
};

8. 性能优化与调试

C++ 性能优化的核心思想是在保证正确性的前提下，通过减少计算开销、优化内存访问、利用硬件特性和编译器能力，最大化程序执行效率。其实现过程通常遵循“测量->分析->修改->验证”的迭代流程

减少计算开销

优化算法复杂度（如用哈希表替代线性查找），避免重复计算
将运行时计算转移至编译时（如常量表达式、模板元编程）
利用CPU特性：优先使用整型加减/位操作等低开销指令，避免高开销操作（如除法、取余）
函数调用涉及压栈/出栈操作，频繁调用会显著影响性能
核心策略： 内联小函数、减少参数传递开销、合并功能相近的函数

内联函数： 消除压栈/出栈指令，直接嵌入函数体

// 内联避免百万次调用的开销
inline void smallFunction() { 
    std::cout << "Small function\n"; 
}

减少参数传递开销： 用引用替代值传递，尤其对大型对象

1
2
3

// 用结构体封装多个参数
struct Point { int x, y; };
void drawPoint(const Point& p); // 引用传递避免复制

强度削减（Strength Reduction）：

// 用乘法替代除法（编译器常自动优化）
// 原始：取余操作慢
for (int i=0; i<10000; i++) {
    if (i % 10 == 0) ... 
}
// 优化：位操作或乘法
for (int i=0; i<10000; i+=10) ...

编译时计算： 消除运行时函数调用

1
2
3

// 将atan2计算移至编译时
constexpr double kTanPI3 = std::tan(M_PI/3);
if (a < b * kTanPI3) ... // 运行时仅需乘法

批量处理与缓存： 重复计算相同输入的函数

// 缓存昂贵计算结果
std::map<int, ExpensiveResult> cache;
if (!cache.count(key)) {
    cache[key] = computeExpensiveResult(); // 仅计算一次
}
return cache[key];

循环优化： 降低循环控制指令占比

// 循环展开减少分支判断
for (int i=0; i<1000; i+=4) {
    arr[i] = i;
    arr[i+1] = i+1;
    arr[i+2] = i+2;
    arr[i+3] = i+3;
}

优化内存访问

减少写操作：

// 用位域合并多次写操作 传统写法需三次独立写操作
struct Bitfield {
    int a:4, b:2, c:2; // 4+2+2位
};
Bitfield x;
x.a = A; x.b = B; x.c = C; // 单次内存写入

预分配内存： 避免动态扩容时的复制开销

1
2
3

// vector预分配避免多次扩容
std::vector<int> vec;
vec.reserve(1000); // 一次性分配内存

利用硬件并行

并行计算： 任务需无数据依赖，避免锁竞争

// 多线程并行独立任务
std::thread t1(task1);
std::thread t2(task2);
t1.join(); 
t2.join();

图像并行处理（数据并行）： 将图像按行分块，多线程并行处理，避免全局锁，各线程独立处理数据块

#include <thread>
#include <vector>

void processPixels(int startY, int endY) {
  for (int y = startY; y < endY; ++y) {
    for (int x = 0; x < IMAGE_WIDTH; ++x) {
      // 处理像素（如滤波、变换）
    }
  }
}

int main() {
  const int THREAD_COUNT = 4;  // 4线程
  std::vector<std::thread> threads;
  int rowsPerThread = IMAGE_HEIGHT / THREAD_COUNT;

  for (int i = 0; i < THREAD_COUNT; ++i) {
    int startY = i * rowsPerThread;
    int endY = (i == THREAD_COUNT-1) ? IMAGE_HEIGHT : startY + rowsPerThread;
    threads.emplace_back(processPixels, startY, endY);
  }

  for (auto& t : threads) t.join();  // 等待所有线程
}

多核并行计算（任务并行）： 绑定线程到特定CPU核心，减少上下文切换，适用于计算密集型任务（如科学计算）

#include <pthread.h>

void* parallel_op(void* core_id) {
  int id = *(int*)core_id;
  for (int i = 0; i < 1000; ++i) {
    // 执行并行计算（如矩阵乘法）
  }
  return nullptr;
}

int main() {
  pthread_t threads[8];
  int core_ids[8] = {0,1,2,3,4,5,6,7};
  for (int i = 0; i < 8; ++i) {
    pthread_create(&threads[i], NULL, parallel_op, &core_ids[i]);
  }
  for (int i = 0; i < 8; ++i) pthread_join(threads[i], NULL);
}

打赏

版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！