1.关联容器unordered_map

unordered_map是实现哈希表功能的容器，通常也被称为 “STL 哈希表” 或 “STL 哈希映射”。它通过哈希函数将键（Key）映射到存储位置，实现 O (1) 平均时间复杂度的插入、删除和查找操作，是高效存储 “键值对（Key-Value）” 的常用工具。

1.1核心特性

  无序元素：元素的存储顺序与插入顺序无关，不支持顺序访问（与map不同，map是有序地红黑树）。

  键唯一：每个键在容器中是唯一的，不能重复（若需要重复，使用unordered_multimap）.

  哈希函数依赖：通过键的哈希值确定存储位置，哈希函数影响性能。

1.2哈希表的工作机制

unordered_map 的底层是哈希表（Hash Table），核心逻辑如下

  哈希函数：将键（如 int、std::string）转换为一个整数（哈希值），用于确定该键值对在哈希表中的 “桶（Bucket）” 位置。

  桶数组：哈希表由多个 “桶” 组成，每个桶存储哈希值相同的键值对（解决 “哈希冲突”—— 不同键可能计算出相同哈希值）。

  冲突解决：当多个键映射到同一桶时，通常通过 “链表” 或 “红黑树” 将这些键值对串联起来（现代实现中，当桶中元素过多时会自动转为红黑树，提升查询效率）。

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    // 定义：键为 string 类型，值为 int 类型的 unordered_map
    std::unordered_map<std::string, int> hash_map;

    // 1. 插入键值对（三种方式）
    hash_map["apple"] = 5;          // 直接赋值
    hash_map.insert({"banana", 3}); // insert 函数
    hash_map.emplace("orange", 7);  // emplace 更高效（直接在容器中构造）

    // 2. 查找元素
    std::string key = "apple";
    auto it = hash_map.find(key);
    if (it != hash_map.end()) {
        std::cout << key << " 的值：" << it->second << std::endl; // 输出：apple 的值：5
    } else {
        std::cout << key << " 不存在" << std::endl;
    }

    // 3. 遍历所有键值对（无序）
    for (const auto& pair : hash_map) {
        std::cout << pair.first << ": " << pair.second << " "; 
        // 输出顺序不确定，可能是：apple:5 banana:3 orange:7 或其他组合
    }
    std::cout << std::endl;

    // 4. 删除元素
    hash_map.erase("banana"); // 删除键为 "banana" 的元素

    return 0;
}

2.function

function是定义于<functional>头文件的通用函数包装类，它可以存储、复制、调用任何可调用函数（如普通函数、Lambda表达式、函数指针、仿函数、成员函数等），实现了不同类型的可调用对象用统一的方式处理，是泛型编程和回调机制的重要工具。

2.1统一可调用对象的类型

C++中的可调用对象的类型千差万别（如lamnda表达式的类型是编译器生成的匿名类，函数指针是void（*）（int）等），function可以将这些不同类型的可调用对象包装起来，形成一个统一的类型，方便存储、传递or调用。function就像一个“函数容器”，无论放任何类型的可调用函数，都能用相同的方式（如operator（））调用它。

实例1：包装普通函数

#include <functional>
#include <iostream>

//普通函数
int add(int,int b){
  return a+b;
}

int main(){
  //用function包装add函数
  function<int(int,int)>func=add;
  cout<<func(3,5)<<endl;
  return 0;
}

实例2：包装lambda表达式

#include<functional>
#include<iostream>


int main(){
  //lambda表达式(无捕获)
  auto multiply=[](int a,int b){return a*b;};
  function<int(int,int)>func=multyply;
  cout<<func(3,5)<<endl;

  //lambda表达式(you捕获)
  int base=10
  auto multiply2=[base](int a,int b){return base*b;};
  function<int(int,int)>func2=multyply2;
  cout<<func2(3,5)<<endl;

实例3：包装类成员函数（需绑定实例）

#include <functional>
#include <iostream>

class Calculator{
public:
  int divide(int a,int b)const{//成员函数
    return a*b;
  }
};

int mian(){
  Calculator calc;
  //包装成员函数：需用bing绑定实例（calc）
function<int(int,int)>func=bind(&Calculator::divide,&calc,placeholders::_1,placeholders::_2);

  cout<<func(10,2)<<endl;
  return 0;
}

实例4：包装仿函数（重载 operator() 的类）

#include <functional>
#include <iostream>

// 仿函数类
class Subtract {
public:
    int operator()(int a, int b) const {
        return a - b;
    }
};

int main() {
    std::function<int(int, int)> func = Subtract(); // 包装仿函数对象
    std::cout << func(10, 3) << std::endl; // 输出：7
    return 0;
}

3._atomic_flag/atomic

atomic_flag和atomic是<atomic>头文件提供的原子操作类型，用于多线程环境下无锁同步，确保对共享变量的操作具有原子性。 是最简单的原子类型，本质是一个 “原子布尔标志”，仅支持两种状态：set（设置为真）和 clear（清除为假），且操作是原子的。

3.1atomic_flag

atomic_flag 是 C++ 标准中唯一保证无锁的原子类型，必须用 ATOMIC_FLAG_INIT 初始化（初始化为 clear 状态）。

核心操作：

• test_and_set()：原子操作，先返回当前状态（true 表示 set，false 表示 clear），再将状态设为 set。
• clear()：原子操作，将状态设为 clear。

实例：

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

std::atomic_flag lock = ATOMIC_FLAG_INIT; // 初始化原子标志（clear 状态）

// 自旋锁：获取锁
void acquire_lock() {
    // 循环等待，直到 test_and_set 返回 false（表示成功获取锁）
    while (lock.test_and_set(std::memory_order_acquire)) {
        // 空循环（自旋），等待锁释放
    }
}

// 释放锁
void release_lock() {
    lock.clear(std::memory_order_release); // 清除标志，释放锁
}

int shared_data = 0; // 共享数据

void increment() {
    for (int i = 0; i < 1000; ++i) {
        acquire_lock();       // 获取锁
        shared_data++;        // 安全操作共享数据
        release_lock();       // 释放锁
    }
}

int main() {
    std::thread t1(increment);
    std::thread t2(increment);
    t1.join();
    t2.join();
    std::cout << shared_data << std::endl; // 输出 2000（无数据竞争）
    return 0;
}

3.2 atomic<T>：通用原子类型

atomic是模板类，可用于任意可复制类型（如int、long、指针等），提供对T类型变量的原子操作（如赋值、加减、比较交换等）。

核心特性：

• 泛化支持：支持 bool、整数类型（int、long long 等）、指针类型等，语法类似普通变量，但操作是原子的。

• 内存序控制：通过 std::memory_order 控制原子操作的内存可见性和顺序（如 memory_order_relaxed、memory_order_acquire 等），平衡性能和正确性。

• 核心操作：

  • 原子赋值：store()

  • 原子读取：load()

  • 原子交换：exchange()

  • 比较并交换（CAS）：compare_exchange_strong() / compare_exchange_weak()

  • 算术操作：fetch_add()、fetch_sub() 等（针对整数类型）。

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

std::atomic<int> atomic_num(0); // 原子整数，初始化为 0

void add() {
    for (int i = 0; i < 1000; ++i) {
        atomic_num.fetch_add(1, std::memory_order_relaxed); // 原子自增 1
    }
}

int main() {
    std::thread t1(add);
    std::thread t2(add);
    t1.join();
    t2.join();
    std::cout << atomic_num.load() << std::endl; // 输出 2000（无数据竞争）
    return 0;
}

3.3atomic_flag VS atomic<T>

特性	atomic_flag	atomic<T>
功能	仅支持 set/clear 的标志	支持任意类型的原子读写、算术等操作
无锁保证	强制无锁（标准规定）	可能有锁（取决于类型 T 和平台）
适用场景	实现自旋锁等简单同步机制	多线程共享变量的原子读写、计数等
灵活性	低（仅标志功能）	高（支持多种操作）

3.4核心价值：无锁同步

传统互斥量（mutex）在竞争时会导致线程阻塞（进入内核态等待），而原子类型通过无锁操作（硬件指令支持，如 x86 的 LOCK 前缀）实现同步，避免阻塞开销，适合轻量级、高频访问的共享资源场景（如计数器、状态标志）。

atomic_flag 是最简单的原子标志，强制无锁，适合实现自旋锁等基础同步工具。

atomic<T> 是通用原子类型，支持多种原子操作，适用于多线程环境下共享变量的安全访问。

4.条件变量（Condition Variable）

在 C++ 多线程编程中，条件变量（Condition Variable） 是一种同步机制（定义于 <condition_variable> 头文件），用于线程间的 “等待 - 通知” 通信：允许一个线程等待某个条件成立，而其他线程在条件成立时通知等待的线程，从而避免线程无意义的自旋等待，提高效率。

4.1为什么需要条件变量？

在多线程场景中，线程常常需要等待某个条件满足后再执行（例如：消费者线程等待队列中有数据，生产者线程生产数据后通知消费者）。如果没有条件变量，线程只能通过 “循环检查条件”（自旋）来等待，这会浪费大量 CPU 资源。

条件变量的出现就是为了解决这个问题：让等待的线程暂时阻塞并释放 CPU，直到被其他线程 “唤醒”，从而减少资源浪费。

4.2条件变量的工作原理

条件变量通常与互斥量（std::mutex） 和共享条件配合使用，核心流程如下：

1. 等待线程：

   • 锁定互斥量，检查共享条件是否满足；

   • 若条件不满足，调用条件变量的 wait() 函数：释放互斥量，并阻塞等待；

   • 若被唤醒（其他线程通知），重新锁定互斥量，再次检查条件（防止虚假唤醒），满足则执行后续操作。

2. 通知线程：

   • 完成操作后（如修改了共享条件），锁定互斥量，更新共享条件；

   • 调用条件变量的 notify_one() 或 notify_all() 函数，唤醒一个或所有等待的线程；

   • 释放互斥量。

4.3条件变量：condition_variable

C++ 标准库提供condition_variable 类实现条件变量，需配合unique_lock<std::mutex> 使用（确保锁的正确释放）。

经典示例：生产者 - 消费者模型

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <queue>

std::queue<int> q; // 共享队列（生产者放数据，消费者取数据）
std::mutex mtx; // 保护队列的互斥量
std::condition_variable cv; // 条件变量（通知队列状态变化）

// 生产者线程：往队列放数据
void producer() {
    for (int i = 0; i < 5; ++i) {
        std::unique_lock<std::mutex> lock(mtx); // 锁定互斥量
        q.push(i); // 生产数据
        std::cout << "生产者放入：" << i << std::endl;
        lock.unlock(); // 可选：提前解锁，减少消费者等待时间
        
        cv.notify_one(); // 通知一个等待的消费者
        std::this_thread::sleep_for(std::chrono::milliseconds(100)); // 模拟耗时
    }
}

// 消费者线程：从队列取数据
void consumer() {
    for (int i = 0; i < 5; ++i) {
        std::unique_lock<std::mutex> lock(mtx); // 锁定互斥量
        
        // 等待条件：队列不为空（防止虚假唤醒，必须用循环检查）
        cv.wait(lock, []{ return !q.empty(); });
        
        // 条件满足，取数据
        int val = q.front();
        q.pop();
        std::cout << "消费者取出：" << val << std::endl;
    }
}

int main() {
    std::thread t1(producer);
    std::thread t2(consumer);
    t1.join();
    t2.join();
    return 0;
}

生产者放入：0 消费者取出：0

生产者放入：1 消费者取出：1

生产者放入：2 消费者取出：2

生产者放入：3 消费者取出：3

生产者放入：4 消费者取出：4