C++高频面试题精选 - 第二部分（题目11-20）

C++高频面试题精选 - 第二部分（题目11-20）

内存管理

题目11: C++的内存分区有哪些？

解答：

C++程序的内存主要分为以下几个区域：

1. 栈（Stack）：

1
2
3
4
5
6
7
8
9
10
11
void function() {
    int x = 10;              // 栈上分配
    char buffer[100];        // 栈上分配
    string s = "hello";      // string对象在栈，内容可能在堆
    
    // 特点：
    // - 自动分配和释放
    // - 速度快
    // - 大小有限（通常1-8MB）
    // - 后进先出（LIFO）
}  // 离开作用域，所有变量自动销毁

2. 堆（Heap）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void function() {
    int* p = new int(10);           // 堆上分配
    int* arr = new int[1000];       // 堆上分配数组
    string* ps = new string("hi");  // 堆上分配
    
    // 特点：
    // - 需要手动分配（new/malloc）和释放（delete/free）
    // - 速度较慢（需要查找合适的内存块）
    // - 大小较大，受系统内存限制
    // - 生命周期由程序员控制
    
    delete p;
    delete[] arr;
    delete ps;
}

3. 全局/静态存储区：

1
2
3
4
5
6
7
8
9
10
11
int global_var = 10;        // 全局变量（数据段）
static int static_var = 20; // 静态变量（数据段）

void function() {
    static int local_static = 30;  // 静态局部变量
}

// 特点：
// - 程序开始时分配，结束时释放
// - 整个程序运行期间都存在
// - 分为已初始化数据段（.data）和未初始化数据段（.bss）

4. 常量区（文字常量区）：

1
2
3
4
5
6
7
8
9
const char* str1 = "hello";  // "hello"存储在常量区
const char* str2 = "hello";  // 可能与str1指向同一位置（编译器优化）

const int ci = 100;  // const全局变量，通常在常量区

// 特点：
// - 存放字符串常量、const全局变量
// - 只读，不能修改
// - 程序结束时释放

5. 代码区（文本段）：

1
2
3
4
5
6
7
8
void function() {
    // 函数代码存储在代码区
}

// 特点：
// - 存放编译后的机器码
// - 只读，可共享（多个进程可以共享同一段代码）
// - 程序开始时加载

完整示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;

// 全局变量 - 全局/静态区
int global_initialized = 10;
int global_uninitialized;

// 常量 - 常量区
const char* const_string = "Hello, World!";

void demonstrateMemory() {
    // 局部变量 - 栈
    int stack_var = 20;
    char stack_array[100];
    
    // 静态局部变量 - 全局/静态区
    static int static_local = 30;
    
    // 动态分配 - 堆
    int* heap_var = new int(40);
    char* heap_array = new char[100];
    
    // 打印地址，观察内存分布
    cout << "代码区（函数地址）：     " << (void*)demonstrateMemory << endl;
    cout << "全局变量：               " << &global_initialized << endl;
    cout << "静态局部变量：           " << &static_local << endl;
    cout << "常量字符串：             " << (void*)const_string << endl;
    cout << "栈变量：                 " << &stack_var << endl;
    cout << "堆变量：                 " << heap_var << endl;
    
    // 释放堆内存
    delete heap_var;
    delete[] heap_array;
}

// 典型的内存地址分布（从低到高，64位Linux）：
// 0x00400000 - 代码区
// 0x00600000 - 数据区（全局/静态变量）
// 0x...      - 堆（向高地址增长）
// 0x7fff...  - 栈（向低地址增长）

内存增长方向：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void stackGrowth() {
    int a;
    int b;
    int c;
    
    cout << "&a: " << &a << endl;
    cout << "&b: " << &b << endl;
    cout << "&c: " << &c << endl;
    // 栈：向低地址增长（c < b < a）
}

void heapGrowth() {
    int* p1 = new int;
    int* p2 = new int;
    int* p3 = new int;
    
    cout << "p1: " << p1 << endl;
    cout << "p2: " << p2 << endl;
    cout << "p3: " << p3 << endl;
    // 堆：向高地址增长（p1 < p2 < p3）
    
    delete p1;
    delete p2;
    delete p3;
}

不同区域的比较：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Demo {
    int member;  // 对象在哪，成员就在哪
public:
    static int static_member;  // 静态成员在全局/静态区
    
    void testMemory() {
        int local;              // 栈
        static int s_local;     // 全局/静态区
        int* heap = new int;    // 指针在栈，指向的内存在堆
        
        cout << "this指针：       " << this << endl;
        cout << "成员变量：       " << &member << endl;
        cout << "静态成员：       " << &static_member << endl;
        cout << "局部变量：       " << &local << endl;
        cout << "静态局部变量：   " << &s_local << endl;
        cout << "heap指针本身：   " << &heap << endl;
        cout << "heap指向的内存： " << heap << endl;
        
        delete heap;
    }
};

int Demo::static_member = 0;

// 使用
Demo stack_obj;           // 对象在栈
Demo* heap_obj = new Demo;  // 对象在堆
static Demo static_obj;   // 对象在全局/静态区

内存大小限制：

1
2
3
4
5
6
7
8
9
10
void testLimits() {
    // 栈：有限（通常1-8MB）
    // int huge_array[10000000];  // 可能栈溢出！
    
    // 堆：较大，受系统内存限制
    int* huge_heap = new int[10000000];  // 通常可以
    delete[] huge_heap;
    
    // 可以通过ulimit -s查看栈大小限制（Linux）
}

口头解答：
“C++程序的内存主要分为五个区域。栈是用来存局部变量和函数调用信息的，它的特点是速度快、自动管理，但空间有限，通常只有几MB。堆用于动态分配，灵活但需要程序员手动管理，容易出现内存泄漏，空间较大。全局静态区存放全局变量和静态变量，整个程序运行期间都存在。常量区存放字符串字面量这些不可修改的数据。代码区存放编译后的机器码。理解这些分区对于写出高效、安全的程序很重要，比如大对象应该放堆上，频繁调用的小对象可以考虑栈分配。栈和堆的增长方向相反，栈向低地址增长，堆向高地址增长。”

题目12: 什么是内存泄漏？如何检测和避免？

解答：

定义： 分配的内存未被释放，导致可用内存逐渐减少，最终可能耗尽系统资源。

1. 常见的内存泄漏原因：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 原因1：忘记delete
void leak1() {
    int* p = new int(10);
    // 忘记delete p;
}  // p超出作用域，但内存未释放

// 原因2：异常导致delete未执行
void leak2() {
    int* p = new int(10);
    
    riskyOperation();  // 可能抛异常
    
    delete p;  // 如果上面抛异常，这行不会执行
}

// 原因3：数组new但用delete（非数组）释放
void leak3() {
    int* arr = new int[10];
    delete arr;  // 错误！应该是delete[]
    // 可能只释放第一个元素，其余泄漏
}

// 原因4：类中有指针成员但未正确管理
class LeakyClass {
    int* data;
public:
    LeakyClass() : data(new int[100]) {}
    // 缺少析构函数！
    // 缺少拷贝构造和赋值运算符（浅拷贝问题）
};

void leak4() {
    LeakyClass obj;
}  // obj析构，但data指向的内存泄漏

// 原因5：循环引用（智能指针）
class Node {
public:
    shared_ptr<Node> next;
};

void leak5() {
    auto node1 = make_shared<Node>();
    auto node2 = make_shared<Node>();
    node1->next = node2;
    node2->next = node1;  // 循环引用，都不会释放
}

2. 检测内存泄漏的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// 方法1：手动计数（简单但不实用）
class MemoryTracker {
    static int alloc_count;
    static int dealloc_count;
public:
    static void* allocate(size_t size) {
        alloc_count++;
        return malloc(size);
    }
    
    static void deallocate(void* ptr) {
        dealloc_count++;
        free(ptr);
    }
    
    static void report() {
        cout << "分配次数: " << alloc_count << endl;
        cout << "释放次数: " << dealloc_count << endl;
        cout << "泄漏: " << (alloc_count - dealloc_count) << endl;
    }
};

int MemoryTracker::alloc_count = 0;
int MemoryTracker::dealloc_count = 0;

// 方法2：重载new/delete（调试用）
void* operator new(size_t size) {
    void* ptr = malloc(size);
    cout << "分配 " << size << " 字节，地址: " << ptr << endl;
    return ptr;
}

void operator delete(void* ptr) noexcept {
    cout << "释放地址: " << ptr << endl;
    free(ptr);
}

// 方法3：使用工具
// Valgrind (Linux):
//   valgrind --leak-check=full ./program
//
// Visual Studio (Windows):
//   内置的CRT调试堆
//
// AddressSanitizer:
//   编译时加 -fsanitize=address

#ifdef _MSC_VER
#define _CRTDBG_MAP_ALLOC
#include <crtdbg.h>

void detectLeaksVS() {
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
    
    int* leak = new int[10];
    // 忘记delete
    
    // 程序结束时会报告泄漏
}
#endif

3. 避免内存泄漏的方法：

方法1：使用RAII和智能指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// ✗ 容易泄漏
void bad() {
    int* p = new int(10);
    riskyOperation();
    delete p;  // 可能不会执行
}

// ✓ RAII，异常安全
void good() {
    unique_ptr<int> p(new int(10));
    // 或：auto p = make_unique<int>(10);
    riskyOperation();
    // 自动释放，即使抛异常
}

// ✓ 智能指针管理动态数组
void goodArray() {
    unique_ptr<int[]> arr(new int[100]);
    // 或：auto arr = make_unique<int[]>(100);
    // 自动用delete[]释放
}

方法2：使用容器代替裸指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// ✗ 手动管理
void bad() {
    int* arr = new int[1000];
    // 使用arr
    delete[] arr;
}

// ✓ 使用vector
void good() {
    vector<int> arr(1000);
    // 自动管理，不会泄漏
}

// ✗ 指针的容器
void bad2() {
    vector<Widget*> widgets;
    widgets.push_back(new Widget);
    widgets.push_back(new Widget);
    // 忘记delete
}

// ✓ 智能指针的容器
void good2() {
    vector<unique_ptr<Widget>> widgets;
    widgets.push_back(make_unique<Widget>());
    widgets.push_back(make_unique<Widget>());
    // 自动释放
}

方法3：正确实现类的资源管理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class GoodClass {
    int* data;
    size_t size;
public:
    GoodClass(size_t s) : size(s), data(new int[s]) {}
    
    // 析构函数
    ~GoodClass() {
        delete[] data;
    }
    
    // 拷贝构造（深拷贝）
    GoodClass(const GoodClass& other) : size(other.size) {
        data = new int[size];
        memcpy(data, other.data, size * sizeof(int));
    }
    
    // 拷贝赋值
    GoodClass& operator=(const GoodClass& other) {
        if (this != &other) {
            int* new_data = new int[other.size];
            memcpy(new_data, other.data, other.size * sizeof(int));
            delete[] data;
            data = new_data;
            size = other.size;
        }
        return *this;
    }
    
    // 移动构造
    GoodClass(GoodClass&& other) noexcept 
        : data(other.data), size(other.size) {
        other.data = nullptr;
        other.size = 0;
    }
    
    // 移动赋值
    GoodClass& operator=(GoodClass&& other) noexcept {
        if (this != &other) {
            delete[] data;
            data = other.data;
            size = other.size;
            other.data = nullptr;
            other.size = 0;
        }
        return *this;
    }
};

// 或者更好：使用智能指针成员
class BetterClass {
    unique_ptr<int[]> data;
    size_t size;
public:
    BetterClass(size_t s) : size(s), data(make_unique<int[]>(s)) {}
    // 不需要手动写析构、拷贝、移动！（如果不需要拷贝）
    
    // 如果需要拷贝
    BetterClass(const BetterClass& other) : size(other.size) {
        data = make_unique<int[]>(size);
        memcpy(data.get(), other.data.get(), size * sizeof(int));
    }
};

方法4：使用作用域守卫

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 自定义资源的RAII包装
class FileHandle {
    FILE* fp;
public:
    FileHandle(const char* name, const char* mode) 
        : fp(fopen(name, mode)) {
        if (!fp) throw runtime_error("打开文件失败");
    }
    
    ~FileHandle() {
        if (fp) fclose(fp);
    }
    
    FILE* get() { return fp; }
    
    // 禁止拷贝
    FileHandle(const FileHandle&) = delete;
    FileHandle& operator=(const FileHandle&) = delete;
};

void processFile() {
    FileHandle file("data.txt", "r");
    // 使用file.get()
    // 异常安全，自动关闭
}

// 通用的ScopeGuard
template<typename Func>
class ScopeGuard {
    Func cleanup;
    bool dismissed;
public:
    ScopeGuard(Func f) : cleanup(std::move(f)), dismissed(false) {}
    
    ~ScopeGuard() {
        if (!dismissed) cleanup();
    }
    
    void dismiss() { dismissed = true; }
};

template<typename Func>
auto make_guard(Func f) {
    return ScopeGuard<Func>(std::move(f));
}

void transaction() {
    Resource* res = acquireResource();
    auto guard = make_guard([res]{ releaseResource(res); });
    
    // 使用res
    riskyOperation();
    
    // guard析构时自动释放资源
}

方法5：解决智能指针的循环引用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// ✗ 循环引用
class BadNode {
public:
    shared_ptr<BadNode> next;
};

// ✓ 用weak_ptr打破循环
class GoodNode {
public:
    shared_ptr<GoodNode> next;
    weak_ptr<GoodNode> prev;  // 不增加引用计数
};

// 或者明确所有权关系
class Parent {
public:
    vector<unique_ptr<Child>> children;  // 父拥有子
};

class Child {
public:
    Parent* parent;  // 子只引用父（裸指针安全）
};

4. 完整示例：内存泄漏检测和修复

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 有问题的代码
class LeakyDatabase {
    Connection* conn;
public:
    void connect(const string& str) {
        conn = new Connection(str);  // 可能泄漏
    }
    
    void query(const string& sql) {
        Result* result = conn->execute(sql);
        // 使用result
        // 忘记delete result - 泄漏！
    }
    
    ~LeakyDatabase() {
        delete conn;  // 如果connect多次调用，之前的会泄漏
    }
};

// 修复后的代码
class FixedDatabase {
    unique_ptr<Connection> conn;
public:
    void connect(const string& str) {
        conn = make_unique<Connection>(str);  // 自动释放旧连接
    }
    
    void query(const string& sql) {
        unique_ptr<Result> result(conn->execute(sql));
        // 使用result
        // 自动释放
    }
    
    // 不需要手动写析构函数
};

口头解答：
“内存泄漏是C++中很常见也很严重的问题，就是分配了内存但没释放，长时间运行的程序会越来越慢，最终崩溃。主要原因是忘记delete或者异常导致delete没执行。要避免内存泄漏，最好的办法是遵循RAII原则——资源获取即初始化，让对象的生命周期自动管理资源。具体做法就是用智能指针代替裸指针，用STL容器代替手动管理的数组。如果确实要用裸指针，要保证每个new都有对应的delete，而且要考虑异常情况。检测的话，Valgrind在Linux下很好用，能准确定位泄漏的位置。现代C++中，如果代码里出现很多new/delete，通常说明设计有问题，应该重构使用智能指针和容器。”

题目13: 解释RAII（Resource Acquisition Is Initialization）原则

解答：

核心思想： 将资源的获取和释放绑定到对象的生命周期，利用C++自动调用析构函数的特性来管理资源。

1. RAII的基本原理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class RAIIExample {
    Resource* resource;
public:
    // 构造时获取资源
    RAIIExample() {
        resource = acquireResource();
        cout << "资源已获取\n";
    }
    
    // 析构时释放资源
    ~RAIIExample() {
        releaseResource(resource);
        cout << "资源已释放\n";
    }
    
    // 禁止拷贝（通常）
    RAIIExample(const RAIIExample&) = delete;
    RAIIExample& operator=(const RAIIExample&) = delete;
};

void useResource() {
    RAIIExample obj;  // 构造时获取资源
    
    // 使用资源
    doSomething();
    
    if (error) {
        return;  // 提前返回也安全
    }
    
    riskyOperation();  // 抛异常也安全
    
}  // obj析构，自动释放资源

2. 标准库中的RAII应用：

智能指针：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void smartPointerExample() {
    // unique_ptr：独占所有权
    {
        unique_ptr<Widget> ptr(new Widget);
        // 或：auto ptr = make_unique<Widget>();
        
        ptr->doSomething();
        
        // 离开作用域，自动delete
    }
    
    // shared_ptr：共享所有权
    {
        shared_ptr<Widget> ptr1 = make_shared<Widget>();
        {
            shared_ptr<Widget> ptr2 = ptr1;  // 引用计数+1
            // 使用ptr2
        }  // ptr2析构，引用计数-1
        // 使用ptr1
    }  // ptr1析构，引用计数归0，释放资源
}

互斥锁：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <mutex>

mutex mtx;
int shared_data = 0;

void threadSafeIncrement() {
    lock_guard<mutex> lock(mtx);  // 构造时加锁
    
    shared_data++;
    
    if (shared_data > 100) {
        return;  // 提前返回，lock自动解锁
    }
    
    riskyOperation();  // 抛异常，lock也会自动解锁
    
}  // lock析构，自动解锁

// unique_lock：更灵活的锁
void flexibleLocking() {
    unique_lock<mutex> lock(mtx);
    
    // 可以手动解锁
    shared_data++;
    lock.unlock();
    
    // 做一些不需要锁的操作
    expensiveComputation();
    
    // 重新加锁
    lock.lock();
    shared_data--;
}  // 如果还持有锁，析构时自动解锁

文件管理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <fstream>

void fileExample() {
    // fstream使用RAII
    {
        ofstream file("data.txt");
        
        if (!file) {
            throw runtime_error("打开失败");
        }
        
        file << "Hello, RAII!\n";
        
        // 可能抛异常
        riskyOperation();
        
    }  // file析构，自动关闭文件
    
    // 即使上面抛异常，文件也会被正确关闭
}

// 自定义文件RAII包装
class File {
    FILE* fp;
public:
    File(const char* name, const char* mode) : fp(fopen(name, mode)) {
        if (!fp) {
            throw runtime_error("无法打开文件");
        }
    }
    
    ~File() {
        if (fp) {
            fclose(fp);
        }
    }
    
    // 禁止拷贝
    File(const File&) = delete;
    File& operator=(const File&) = delete;
    
    // 允许移动
    File(File&& other) noexcept : fp(other.fp) {
        other.fp = nullptr;
    }
    
    FILE* get() { return fp; }
};

void useFile() {
    File f("data.txt", "w");
    fprintf(f.get(), "Hello\n");
    // 自动关闭
}

3. 自定义RAII类示例：

数据库连接：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class DatabaseConnection {
    Connection* conn;
public:
    DatabaseConnection(const string& connStr) {
        conn = connectToDatabase(connStr);
        if (!conn) {
            throw runtime_error("连接失败");
        }
        cout << "数据库已连接\n";
    }
    
    ~DatabaseConnection() {
        if (conn) {
            conn->close();
            delete conn;
            cout << "数据库已断开\n";
        }
    }
    
    // 禁止拷贝
    DatabaseConnection(const DatabaseConnection&) = delete;
    DatabaseConnection& operator=(const DatabaseConnection&) = delete;
    
    void execute(const string& sql) {
        conn->executeSQL(sql);
    }
};

void databaseOperation() {
    DatabaseConnection db("server=localhost;db=test");
    
    db.execute("SELECT * FROM users");
    
    // 即使这里抛异常，连接也会正确关闭
    riskyOperation();
    
}  // db析构，自动断开连接

计时器：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Timer {
    chrono::time_point<chrono::high_resolution_clock> start;
    string name;
public:
    Timer(string n) : name(std::move(n)), 
                      start(chrono::high_resolution_clock::now()) {
        cout << name << " 开始\n";
    }
    
    ~Timer() {
        auto end = chrono::high_resolution_clock::now();
        auto duration = chrono::duration_cast<chrono::milliseconds>(end - start);
        cout << name << " 耗时: " << duration.count() << "ms\n";
    }
};

void expensiveFunction() {
    Timer t("expensiveFunction");
    
    // 复杂计算
    for (int i = 0; i < 1000000; ++i) {
        // ...
    }
    
}  // t析构，自动输出耗时

OpenGL上下文：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class GLContext {
    GLFWwindow* window;
public:
    GLContext(GLFWwindow* win) : window(win) {
        glfwMakeContextCurrent(window);
        cout << "OpenGL上下文已激活\n";
    }
    
    ~GLContext() {
        glfwMakeContextCurrent(nullptr);
        cout << "OpenGL上下文已释放\n";
    }
};

void renderFrame(GLFWwindow* window) {
    GLContext ctx(window);
    
    // OpenGL渲染代码
    glClear(GL_COLOR_BUFFER_BIT);
    // ...
    
}  // ctx析构，自动释放上下文

临时状态保存：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class StateGuard {
    int& state;
    int old_value;
public:
    StateGuard(int& s, int new_value) : state(s), old_value(s) {
        state = new_value;
    }
    
    ~StateGuard() {
        state = old_value;  // 恢复旧值
    }
};

int global_mode = 0;

void temporaryMode() {
    cout << "原始模式: " << global_mode << endl;
    
    {
        StateGuard guard(global_mode, 5);  // 临时改为5
        cout << "临时模式: " << global_mode << endl;
        
        doSomethingInMode5();
    }  // guard析构，恢复原值
    
    cout << "恢复后: " << global_mode << endl;
}

4. RAII vs 手动管理对比：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// ✗ 手动管理：容易出错
void manualManagement() {
    Resource* res = acquireResource();
    
    if (!checkCondition()) {
        releaseResource(res);  // 需要记得释放
        return;
    }
    
    processResource(res);  // 可能抛异常
    
    if (anotherCondition()) {
        releaseResource(res);  // 又要记得释放
        return;
    }
    
    releaseResource(res);  // 还要记得释放
}

// ✓ RAII：自动、安全
class ResourceGuard {
    Resource* res;
public:
    ResourceGuard() : res(acquireResource()) {}
    ~ResourceGuard() { releaseResource(res); }
    Resource* get() { return res; }
};

void raii Management() {
    ResourceGuard guard;
    
    if (!checkCondition()) {
        return;  // guard自动释放
    }
    
    processResource(guard.get());  // 异常安全
    
    if (anotherCondition()) {
        return;  // guard自动释放
    }
    
    // guard自动释放
}

5. RAII的优势：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 1. 异常安全
void exceptionSafe() {
    lock_guard<mutex> lock(mtx);
    unique_ptr<Widget> ptr(new Widget);
    
    // 下面的操作可能抛异常
    riskyOperation();
    
    // 即使抛异常：
    // - lock会自动释放
    // - ptr会自动delete
}

// 2. 简化代码
void simplified() {
    // 不需要这样：
    // acquire(); try { use(); } finally { release(); }
    
    // 只需要：
    RAIIWrapper wrapper;
    use();
    // 自动释放
}

// 3. 防止遗忘
void noForget() {
    unique_ptr<int> p(new int(10));
    
    // 多个返回路径
    if (condition1) return;
    if (condition2) return;
    if (condition3) return;
    
    // 不需要在每个return前delete
    // unique_ptr自动处理
}

// 4. 代码更清晰
void clearer() {
    // 作用域即生命周期
    {
        FileGuard file("data.txt");
        // 文件在此作用域内有效
    }  // 离开作用域，文件自动关闭
}

6. RAII的最佳实践：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 1. 一个类管理一种资源
class GoodRAII {
    Resource* resource;  // 只管理一种资源
public:
    GoodRAII() : resource(acquire()) {}
    ~GoodRAII() { release(resource); }
};

// 2. 禁止拷贝或正确实现拷贝
class UniqueRAII {
    Resource* resource;
public:
    UniqueRAII() : resource(acquire()) {}
    ~UniqueRAII() { release(resource); }
    
    // 禁止拷贝
    UniqueRAII(const UniqueRAII&) = delete;
    UniqueRAII& operator=(const UniqueRAII&) = delete;
    
    // 允许移动
    UniqueRAII(UniqueRAII&& other) noexcept : resource(other.resource) {
        other.resource = nullptr;
    }
};

// 3. 提供访问接口但不暴露所有权
class RAIIWithAccess {
    unique_ptr<Resource> resource;
public:
    RAIIWithAccess() : resource(make_unique<Resource>()) {}
    
    Resource* get() const { return resource.get(); }  // 不转移所有权
    Resource& operator*() const { return *resource; }
    Resource* operator->() const { return resource.get(); }
};

口头解答：
“RAII是C++中最重要的编程思想之一，中文叫’资源获取即初始化’。它的核心就是把资源的生命周期和对象的生命周期绑定在一起——对象构造时获取资源，析构时释放资源。因为C++保证对象离开作用域时一定会调用析构函数，所以这种方式特别安全，即使中间抛异常也不会泄漏。标准库里到处都是RAII的应用：智能指针管理内存，lock_guard管理锁，fstream管理文件。我们自己写代码时也应该遵循这个原则，把资源封装到类里，构造时获取，析构时释放。这样就不需要记得手动清理，也不用担心异常时的泄漏。可以说，RAII是C++区别于C和其他语言的一个核心优势，也是现代C++推荐的资源管理方式。”

题目14: 什么时候会发生内存对齐？为什么需要内存对齐？

解答：

定义： 编译器为了满足硬件要求和提高访问效率，将数据存储在特定地址边界上的过程。

1. 内存对齐的规则：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct Example {
    char c;    // 1字节
    int i;     // 4字节
    char d;    // 1字节
};

// 不对齐的话（理论上）：总共1+4+1=6字节
// 实际对齐后：
// char c   : 1字节
// padding  : 3字节（填充）
// int i    : 4字节
// char d   : 1字节
// padding  : 3字节（结构体末尾填充）
// 总共：12字节

cout << sizeof(Example);  // 输出：12

2. 对齐规则详解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 规则1：成员按自身大小对齐
struct Aligned {
    char a;     // 偏移0，大小1
    // 填充3字节，使int对齐到4的倍数
    int b;      // 偏移4，大小4
    short c;    // 偏移8，大小2
    // 填充2字节，使结构体大小是最大成员(int=4)的倍数
};
// 总大小：12字节

// 规则2：结构体大小是最大成员大小的倍数
struct SizeRule {
    int a;      // 4字节
    char b;     // 1字节
    // 填充3字节
};
// 总大小：8字节（int的倍数）

// 规则3：数组元素对齐
struct ArrayAlign {
    char a;
    int b;
};
ArrayAlign arr[2];
// arr[0]和arr[1]都要满足对齐要求

3. 查看内存布局：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstddef>  // offsetof

struct Data {
    char a;
    int b;
    short c;
    double d;
};

void printLayout() {
    cout << "sizeof(Data): " << sizeof(Data) << endl;
    cout << "offsetof(a): " << offsetof(Data, a) << endl;
    cout << "offsetof(b): " << offsetof(Data, b) << endl;
    cout << "offsetof(c): " << offsetof(Data, c) << endl;
    cout << "offsetof(d): " << offsetof(Data, d) << endl;
}

// 输出（64位系统）：
// sizeof(Data): 24
// offsetof(a): 0   (char, 1字节)
// offsetof(b): 4   (int, 4字节, 从4开始)
// offsetof(c): 8   (short, 2字节, 从8开始)
// offsetof(d): 16  (double, 8字节, 从16开始)

4. 为什么需要内存对齐：

原因1：硬件要求

1
2
3
4
5
6
// 某些CPU架构（如早期ARM）要求：
// - 4字节数据必须从4的倍数地址读取
// - 8字节数据必须从8的倍数地址读取
// 否则会出错或触发异常

// x86/x64虽然支持非对齐访问，但性能会降低

原因2：性能优化

1
2
3
4
5
6
7
8
9
10
11
// 对齐的访问：CPU一次读取
int* aligned_ptr = (int*)0x1000;  // 地址是4的倍数
int value = *aligned_ptr;  // 一次内存读取

// 未对齐的访问：可能需要两次读取
int* unaligned_ptr = (int*)0x1002;  // 地址不是4的倍数
int value = *unaligned_ptr;  
// 1. 读取0x1000-0x1003
// 2. 读取0x1004-0x1007
// 3. 拼接得到0x1002-0x1005的数据
// 性能降低！

5. 优化结构体大小：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// ✗ 未优化：24字节
struct Bad {
    char a;     // 1字节
    double b;   // 8字节，前面填充7字节
    int c;      // 4字节
    char d;     // 1字节，后面填充3字节
};
// 布局：a(1) + padding(7) + b(8) + c(4) + d(1) + padding(3) = 24

// ✓ 优化后：16字节
struct Good {
    double b;   // 8字节
    int c;      // 4字节
    char a;     // 1字节
    char d;     // 1字节
    // 填充2字节
};
// 布局：b(8) + c(4) + a(1) + d(1) + padding(2) = 16

cout << sizeof(Bad);   // 24
cout << sizeof(Good);  // 16

6. 手动控制对齐：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// #pragma pack：改变对齐边界
#pragma pack(push, 1)  // 设置1字节对齐
struct Packed {
    char a;
    int b;
    char c;
};
#pragma pack(pop)  // 恢复默认对齐

cout << sizeof(Packed);  // 6字节（紧凑但可能性能差）

// C++11: alignas
struct alignas(16) Aligned16 {
    char a;
    int b;
};

cout << sizeof(Aligned16);  // 16字节（强制16字节对齐）

// alignas用于缓存行对齐
struct alignas(64) CacheAligned {  // 64字节 = 典型缓存行大小
    int data[10];
};
// 避免false sharing

7. 实际应用示例：

网络协议包结构：

1
2
3
4
5
6
7
8
9
10
11
12
// 通常需要紧凑存储
#pragma pack(push, 1)
struct NetworkPacket {
    uint8_t type;       // 1字节
    uint16_t length;    // 2字节
    uint32_t sequence;  // 4字节
    uint8_t data[100];  // 100字节
};
#pragma pack(pop)

// 确保包大小 = 1+2+4+100 = 107字节
// 不会有填充

缓存行对齐（避免false sharing）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 多线程中，不同线程访问的数据应该在不同缓存行
struct CounterWithFalseSharing {
    int counter1;  // 线程1访问
    int counter2;  // 线程2访问
};
// 问题：counter1和counter2在同一缓存行
// 修改counter1会使包含counter2的缓存行失效

// 解决方案：缓存行对齐
struct alignas(64) CounterNoFalseSharing {
    alignas(64) int counter1;
    alignas(64) int counter2;
};
// 现在counter1和counter2在不同缓存行

SIMD优化：

1
2
3
4
5
// SIMD指令要求数据对齐
alignas(16) float data[4];  // SSE要求16字节对齐
alignas(32) float data[8];  // AVX要求32字节对齐

// 未对齐的数据会导致性能下降或崩溃

8. 检查对齐：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <type_traits>

// 检查类型的对齐要求
cout << alignof(char) << endl;    // 1
cout << alignof(int) << endl;     // 4
cout << alignof(double) << endl;  // 8

struct MyStruct {
    char a;
    int b;
};
cout << alignof(MyStruct) << endl;  // 4（由int决定）

// C++11: is_aligned
template<typename T>
bool is_aligned(T* ptr) {
    return (reinterpret_cast<uintptr_t>(ptr) % alignof(T)) == 0;
}

int* p1 = new int;
cout << is_aligned(p1);  // true（new保证对齐）

char buffer[100];
int* p2 = reinterpret_cast<int*>(buffer + 1);
cout << is_aligned(p2);  // 可能false

9. 性能测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <chrono>

void testAlignment() {
    const int SIZE = 10000000;
    
    // 对齐的访问
    alignas(16) int aligned[SIZE];
    auto start = chrono::high_resolution_clock::now();
    for (int i = 0; i < SIZE; ++i) {
        aligned[i] = i;
    }
    auto end = chrono::high_resolution_clock::now();
    cout << "对齐: " 
         << chrono::duration_cast<chrono::milliseconds>(end - start).count() 
         << "ms\n";
    
    // 未对齐的访问（故意制造）
    char buffer[SIZE * sizeof(int) + 1];
    int* unaligned = reinterpret_cast<int*>(buffer + 1);
    start = chrono::high_resolution_clock::now();
    for (int i = 0; i < SIZE; ++i) {
        unaligned[i] = i;
    }
    end = chrono::high_resolution_clock::now();
    cout << "未对齐: " 
         << chrono::duration_cast<chrono::milliseconds>(end - start).count() 
         << "ms\n";
}

口头解答：
“内存对齐是编译器为了满足硬件要求和提高性能做的优化。简单说，就是让数据存储在特定的地址上，比如4字节的int最好从能被4整除的地址开始。这样做的原因，一是某些CPU架构强制要求对齐，不对齐会出错；二是对齐后CPU可以一次读取完整数据，未对齐可能要读两次再拼接，影响性能。所以编译器会在结构体成员之间插入填充字节。这也提醒我们，定义结构体时把小成员放一起，大成员放一起，可以减少填充，节省内存。在嵌入式或对内存敏感的场景，这个优化还是挺重要的。另外，多线程编程中要注意缓存行对齐，避免false sharing问题。”

题目15: 解释new和delete的实现原理

解答：

1. new的执行过程：

1
2
3
4
5
6
7
8
9
10
11
Widget* pw = new Widget(args);

// 等价于三个步骤：
// 1. 分配内存
void* memory = operator new(sizeof(Widget));

// 2. 类型转换
Widget* pw = static_cast<Widget*>(memory);

// 3. 调用构造函数
pw->Widget::Widget(args);  // 在已分配的内存上构造对象

2. delete的执行过程：

1
2
3
4
5
6
7
8
delete pw;

// 等价于两个步骤：
// 1. 调用析构函数
pw->~Widget();

// 2. 释放内存
operator delete(pw);

3. operator new的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 全局operator new的简化实现
void* operator new(size_t size) {
    if (size == 0) {
        size = 1;  // 保证返回非空指针
    }
    
    while (true) {
        void* ptr = malloc(size);
        
        if (ptr) {
            return ptr;  // 分配成功
        }
        
        // 分配失败，调用new_handler
        new_handler handler = set_new_handler(nullptr);
        set_new_handler(handler);
        
        if (handler) {
            (*handler)();  // 尝试释放内存
        } else {
            throw std::bad_alloc();  // 没有handler，抛异常
        }
    }
}

// 对应的operator delete
void operator delete(void* ptr) noexcept {
    free(ptr);
}

4. 数组的new和delete：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int* arr = new int[10];

// 等价于：
// 1. 分配内存（可能额外存储数组大小）
void* memory = operator new[](10 * sizeof(int) + extra);

// 2. 在extra空间存储数组大小（实现定义）
// 某些实现会在数组前存储元素数量

// 3. 初始化每个元素
for (size_t i = 0; i < 10; ++i) {
    new (memory + i * sizeof(int)) int;  // placement new
}

// 删除
delete[] arr;

// 等价于：
// 1. 析构每个元素（逆序）
for (size_t i = 10; i > 0; --i) {
    arr[i-1].~int();
}

// 2. 释放内存
operator delete[](arr);

5. placement new：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// placement new：在已分配的内存上构造对象
void* buffer = malloc(sizeof(Widget));

// 在buffer上构造Widget
Widget* pw = new (buffer) Widget(args);

// 使用完后：手动调用析构函数
pw->~Widget();

// 释放内存
free(buffer);

// 实际应用：内存池
class MemoryPool {
    char buffer[1000];
    size_t offset = 0;
public:
    void* allocate(size_t size) {
        void* ptr = buffer + offset;
        offset += size;
        return ptr;
    }
    
    template<typename T, typename... Args>
    T* construct(Args&&... args) {
        void* ptr = allocate(sizeof(T));
        return new (ptr) T(std::forward<Args>(args)...);
    }
};

6. 重载new和delete：

类专属版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class MyClass {
public:
    // 类专属operator new
    void* operator new(size_t size) {
        cout << "MyClass::operator new, size=" << size << endl;
        return ::operator new(size);  // 调用全局版本
    }
    
    void operator delete(void* ptr) noexcept {
        cout << "MyClass::operator delete\n";
        ::operator delete(ptr);
    }
    
    // 数组版本
    void* operator new[](size_t size) {
        cout << "MyClass::operator new[]\n";
        return ::operator new[](size);
    }
    
    void operator delete[](void* ptr) noexcept {
        cout << "MyClass::operator delete[]\n";
        ::operator delete[](ptr);
    }
};

MyClass* p1 = new MyClass;        // 调用MyClass::operator new
delete p1;                         // 调用MyClass::operator delete

MyClass* p2 = new MyClass[10];    // 调用MyClass::operator new[]
delete[] p2;                       // 调用MyClass::operator delete[]

全局版本（慎用）：

1
2
3
4
5
6
7
8
9
10
11
12
// 重载全局operator new
void* operator new(size_t size) {
    cout << "全局operator new: " << size << " bytes\n";
    void* ptr = malloc(size);
    if (!ptr) throw std::bad_alloc();
    return ptr;
}

void operator delete(void* ptr) noexcept {
    cout << "全局operator delete\n";
    free(ptr);
}

7. 带额外参数的new：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// nothrow版本
void* operator new(size_t size, const std::nothrow_t&) noexcept {
    try {
        return operator new(size);
    } catch (...) {
        return nullptr;  // 失败返回nullptr，不抛异常
    }
}

// 使用
Widget* pw = new (std::nothrow) Widget;
if (!pw) {
    // 分配失败
}

// 自定义分配器
void* operator new(size_t size, MemoryPool& pool) {
    return pool.allocate(size);
}

MemoryPool myPool;
Widget* pw = new (myPool) Widget;  // 从myPool分配

8. new_handler：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 设置内存分配失败时的处理函数
void outOfMemory() {
    cout << "内存不足！\n";
    // 尝试释放一些内存
    // 或者抛出异常
    throw std::bad_alloc();
}

void testNewHandler() {
    std::set_new_handler(outOfMemory);
    
    try {
        // 尝试分配大量内存
        while (true) {
            new int[100000000];
        }
    } catch (std::bad_alloc& e) {
        cout << "捕获异常: " << e.what() << endl;
    }
}

9. 内存对齐的new：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// C++17: aligned new
struct alignas(32) AlignedData {
    char data[32];
};

AlignedData* p = new AlignedData;  // 自动32字节对齐
delete p;

// 重载对齐版本的new
void* operator new(size_t size, std::align_val_t alignment) {
    void* ptr = aligned_alloc(static_cast<size_t>(alignment), size);
    if (!ptr) throw std::bad_alloc();
    return ptr;
}

void operator delete(void* ptr, std::align_val_t alignment) noexcept {
    free(ptr);
}

10. 调试和追踪：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 追踪内存分配
class MemoryTracker {
    static size_t allocCount;
    static size_t deallocCount;
    static size_t totalAllocated;
public:
    static void* allocate(size_t size) {
        void* ptr = malloc(size);
        if (ptr) {
            allocCount++;
            totalAllocated += size;
            cout << "分配 " << size << " 字节，地址：" << ptr << endl;
        }
        return ptr;
    }
    
    static void deallocate(void* ptr) {
        if (ptr) {
            deallocCount++;
            cout << "释放地址：" << ptr << endl;
            free(ptr);
        }
    }
    
    static void report() {
        cout << "=== 内存报告 ===\n";
        cout << "分配次数：" << allocCount << endl;
        cout << "释放次数：" << deallocCount << endl;
        cout << "总分配量：" << totalAllocated << " 字节\n";
        cout << "泄漏次数：" << (allocCount - deallocCount) << endl;
    }
};

size_t MemoryTracker::allocCount = 0;
size_t MemoryTracker::deallocCount = 0;
size_t MemoryTracker::totalAllocated = 0;

// 使用
void* operator new(size_t size) {
    return MemoryTracker::allocate(size);
}

void operator delete(void* ptr) noexcept {
    MemoryTracker::deallocate(ptr);
}

11. 常见陷阱：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 陷阱1：new/delete 与 new[]/delete[] 不匹配
int* p1 = new int[10];
delete p1;  // 错误！应该用delete[]

Widget* p2 = new Widget;
delete[] p2;  // 错误！应该用delete

// 陷阱2：delete void*
void* p = operator new(sizeof(Widget));
new (p) Widget;  // placement new
delete p;  // 危险！不会调用析构函数

// 正确做法
Widget* pw = static_cast<Widget*>(p);
pw->~Widget();
operator delete(p);

// 陷阱3：重复delete
int* p = new int;
delete p;
delete p;  // 未定义行为！

// 陷阱4：delete栈对象
int x = 10;
int* p = &x;
delete p;  // 崩溃！

12. 完整示例：自定义内存池：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
template<typename T>
class ObjectPool {
    union Slot {
        T element;
        Slot* next;
    };
    
    Slot* freeSlots = nullptr;
    static const size_t BLOCK_SIZE = 100;
    
public:
    T* allocate() {
        if (!freeSlots) {
            // 分配新块
            Slot* newBlock = static_cast<Slot*>(
                ::operator new(BLOCK_SIZE * sizeof(Slot))
            );
            
            // 链接空闲槽位
            for (size_t i = 0; i < BLOCK_SIZE - 1; ++i) {
                newBlock[i].next = &newBlock[i + 1];
            }
            newBlock[BLOCK_SIZE - 1].next = nullptr;
            freeSlots = newBlock;
        }
        
        // 从空闲列表取一个
        Slot* slot = freeSlots;
        freeSlots = slot->next;
        return &slot->element;
    }
    
    void deallocate(T* ptr) {
        if (!ptr) return;
        
        // 放回空闲列表
        Slot* slot = reinterpret_cast<Slot*>(ptr);
        slot->next = freeSlots;
        freeSlots = slot;
    }
};

// 使用
ObjectPool<Widget> pool;
Widget* w1 = pool.allocate();
new (w1) Widget;  // placement new
// 使用w1
w1->~Widget();
pool.deallocate(w1);

口头解答：
“new操作符的工作其实分为三步：首先调用operator new分配原始内存，这个函数类似malloc；然后对返回的指针做类型转换；最后在这块内存上调用构造函数初始化对象。delete正好相反，先调用析构函数清理对象，再调用operator delete释放内存。理解这个过程很重要，因为我们可以重载operator new和operator delete来实现自定义的内存管理，比如内存池、调试追踪等。还有placement new，可以在指定位置构造对象，这在内存池实现中很有用。需要注意的是，new[]和delete[]处理数组时会额外存储数组大小信息，所以new和delete、new[]和delete[]必须配对使用，否则会导致未定义行为。”

STL容器与算法

题目16: vector的实现原理和扩容机制是什么？

解答：

1. vector的基本实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// vector的简化实现
template<typename T>
class SimpleVector {
    T* data;          // 指向动态数组的指针
    size_t size_;     // 当前元素数量
    size_t capacity_; // 当前容量
    
public:
    SimpleVector() : data(nullptr), size_(0), capacity_(0) {}
    
    ~SimpleVector() {
        clear();
        operator delete(data);
    }
    
    size_t size() const { return size_; }
    size_t capacity() const { return capacity_; }
    bool empty() const { return size_ == 0; }
    
    T& operator[](size_t index) {
        return data[index];
    }
    
    const T& operator[](size_t index) const {
        return data[index];
    }
};

2. 扩容机制：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
template<typename T>
class SimpleVector {
    // ...前面的代码
    
    void reserve(size_t new_capacity) {
        if (new_capacity <= capacity_) {
            return;  // 不缩小容量
        }
        
        // 1. 分配新内存
        T* new_data = static_cast<T*>(
            operator new(new_capacity * sizeof(T))
        );
        
        // 2. 移动/拷贝元素到新内存
        for (size_t i = 0; i < size_; ++i) {
            new (&new_data[i]) T(std::move(data[i]));  // 移动构造
            data[i].~T();  // 销毁旧元素
        }
        
        // 3. 释放旧内存
        operator delete(data);
        
        // 4. 更新指针和容量
        data = new_data;
        capacity_ = new_capacity;
    }
    
    void push_back(const T& value) {
        if (size_ == capacity_) {
            // 触发扩容
            size_t new_capacity = capacity_ == 0 ? 1 : capacity_ * 2;  // 2倍扩容
            reserve(new_capacity);
        }
        
        // 在末尾构造新元素
        new (&data[size_]) T(value);
        ++size_;
    }
    
    void push_back(T&& value) {
        if (size_ == capacity_) {
            size_t new_capacity = capacity_ == 0 ? 1 : capacity_ * 2;
            reserve(new_capacity);
        }
        
        new (&data[size_]) T(std::move(value));  // 移动构造
        ++size_;
    }
};

3. 不同编译器的扩容策略：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void demonstrateGrowth() {
    vector<int> v;
    
    for (int i = 0; i < 100; ++i) {
        if (v.size() == v.capacity()) {
            cout << "容量: " << v.capacity() << " -> ";
        }
        v.push_back(i);
        if (i > 0 && v.size() == v.capacity()) {
            cout << v.capacity() << endl;
        }
    }
}

// GCC/Clang: 通常2倍扩容
// 0 -> 1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 128

// MSVC: 通常1.5倍扩容
// 0 -> 1 -> 2 -> 3 -> 4 -> 6 -> 9 -> 13 -> 19 -> 28 -> 42 -> 63 -> 94 -> 141

4. emplace_back的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
template<typename T>
class SimpleVector {
    // ...
    
    template<typename... Args>
    void emplace_back(Args&&... args) {
        if (size_ == capacity_) {
            size_t new_capacity = capacity_ == 0 ? 1 : capacity_ * 2;
            reserve(new_capacity);
        }
        
        // 直接在位置上构造，不创建临时对象
        new (&data[size_]) T(std::forward<Args>(args)...);
        ++size_;
    }
};

// 使用对比
struct Widget {
    int x, y;
    Widget(int a, int b) : x(a), y(b) {
        cout << "构造\n";
    }
    Widget(const Widget& w) : x(w.x), y(w.y) {
        cout << "拷贝\n";
    }
    Widget(Widget&& w) noexcept : x(w.x), y(w.y) {
        cout << "移动\n";
    }
};

vector<Widget> v;

v.push_back(Widget(1, 2));  // 输出：构造 移动
v.emplace_back(1, 2);        // 输出：构造（直接构造，无拷贝/移动）

5. pop_back和clear：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
template<typename T>
class SimpleVector {
    // ...
    
    void pop_back() {
        if (size_ > 0) {
            --size_;
            data[size_].~T();  // 调用析构函数
            // 注意：不释放内存，capacity不变
        }
    }
    
    void clear() {
        for (size_t i = 0; i < size_; ++i) {
            data[i].~T();
        }
        size_ = 0;
        // capacity保持不变
    }
    
    void shrink_to_fit() {
        if (size_ < capacity_) {
            T* new_data = static_cast<T*>(
                operator new(size_ * sizeof(T))
            );
            
            for (size_t i = 0; i < size_; ++i) {
                new (&new_data[i]) T(std::move(data[i]));
                data[i].~T();
            }
            
            operator delete(data);
            data = new_data;
            capacity_ = size_;
        }
    }
};

6. 迭代器实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
template<typename T>
class SimpleVector {
public:
    using iterator = T*;
    using const_iterator = const T*;
    
    iterator begin() { return data; }
    iterator end() { return data + size_; }
    
    const_iterator begin() const { return data; }
    const_iterator end() const { return data + size_; }
    
    const_iterator cbegin() const { return data; }
    const_iterator cend() const { return data + size_; }
};

// 使用
SimpleVector<int> v;
for (auto it = v.begin(); it != v.end(); ++it) {
    cout << *it << " ";
}

// 范围for循环
for (const auto& val : v) {
    cout << val << " ";
}

7. insert和erase：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
template<typename T>
class SimpleVector {
    // ...
    
    iterator insert(iterator pos, const T& value) {
        size_t index = pos - begin();
        
        if (size_ == capacity_) {
            reserve(capacity_ == 0 ? 1 : capacity_ * 2);
        }
        
        // 移动元素为新元素腾出空间
        for (size_t i = size_; i > index; --i) {
            new (&data[i]) T(std::move(data[i-1]));
            data[i-1].~T();
        }
        
        // 在pos位置构造新元素
        new (&data[index]) T(value);
        ++size_;
        
        return begin() + index;
    }
    
    iterator erase(iterator pos) {
        size_t index = pos - begin();
        
        // 销毁元素
        data[index].~T();
        
        // 移动后面的元素
        for (size_t i = index; i < size_ - 1; ++i) {
            new (&data[i]) T(std::move(data[i+1]));
            data[i+1].~T();
        }
        
        --size_;
        return begin() + index;
    }
};

8. 时间复杂度分析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// vector的时间复杂度：
// 访问：O(1)
int val = v[100];  // 直接通过指针+偏移

// 尾部插入：摊销O(1)
v.push_back(10);  
// 大多数情况O(1)
// 偶尔需要扩容O(n)
// 但平均下来是O(1)

// 中间插入：O(n)
v.insert(v.begin() + 50, 10);  
// 需要移动插入点后的所有元素

// 删除：O(n)
v.erase(v.begin() + 50);  
// 需要移动删除点后的所有元素

// 查找：O(n)
auto it = find(v.begin(), v.end(), 10);  
// 需要线性搜索

9. 内存增长可视化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void visualizeGrowth() {
    vector<int> v;
    
    cout << "初始 - size: " << v.size() 
         << ", capacity: " << v.capacity() << endl;
    
    for (int i = 0; i < 20; ++i) {
        size_t old_cap = v.capacity();
        v.push_back(i);
        size_t new_cap = v.capacity();
        
        if (old_cap != new_cap) {
            cout << "扩容: " << old_cap << " -> " << new_cap 
                 << " (size: " << v.size() << ")" << endl;
        }
    }
    
    // 预留空间避免扩容
    cout << "\n使用reserve:\n";
    vector<int> v2;
    v2.reserve(20);  // 预分配20个元素的空间
    cout << "reserve后 - size: " << v2.size() 
         << ", capacity: " << v2.capacity() << endl;
    
    for (int i = 0; i < 20; ++i) {
        v2.push_back(i);  // 不会触发扩容
    }
    cout << "插入20个后 - size: " << v2.size() 
         << ", capacity: " << v2.capacity() << endl;
}

10. 性能优化建议：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// ✗ 低效：多次扩容
vector<int> v1;
for (int i = 0; i < 10000; ++i) {
    v1.push_back(i);  // 可能扩容多次
}

// ✓ 高效：预留空间
vector<int> v2;
v2.reserve(10000);  // 一次分配
for (int i = 0; i < 10000; ++i) {
    v2.push_back(i);  // 不扩容
}

// ✗ 低效：频繁中间插入
vector<int> v3;
for (int i = 0; i < 1000; ++i) {
    v3.insert(v3.begin(), i);  // O(n)，总共O(n²)
}

// ✓ 高效：尾部插入后反转
vector<int> v4;
for (int i = 0; i < 1000; ++i) {
    v4.push_back(i);  // O(1)摊销
}
reverse(v4.begin(), v4.end());  // O(n)
// 总共O(n)

// ✗ 低效：拷贝大对象
vector<BigObject> v5;
BigObject obj;
v5.push_back(obj);  // 拷贝

// ✓ 高效：移动或原地构造
vector<BigObject> v6;
v6.push_back(std::move(obj));     // 移动
v6.emplace_back(constructor_args); // 原地构造

口头解答：
“vector是最常用的STL容器，它本质是个动态数组，在连续内存上存储元素。它的关键特性是支持快速随机访问，时间复杂度是O(1)。内部实现维护三个指针：指向数据的起始、当前末尾和容量末尾。当元素数量超过容量时，vector会自动扩容——分配一块更大的内存（通常是原来的1.5或2倍），把所有元素移动过去，然后释放旧内存。这个过程比较耗时，所以如果我们预先知道大概需要多少元素，最好用reserve预留空间。vector的优势是随机访问快，内存连续对缓存友好；缺点是中间插入删除慢，扩容时会有性能抖动。在实践中，vector应该是我们的首选容器，除非有特殊需求。”

题目17: map和unordered_map的区别和应用场景

解答：

1. 基本区别对比：

特性 map unordered_map
底层实现 红黑树（平衡二叉搜索树） 哈希表
有序性 有序（按key排序） 无序
查找复杂度 O(log n) 平均O(1)，最坏O(n)
插入复杂度 O(log n) 平均O(1)，最坏O(n)
删除复杂度 O(log n) 平均O(1)，最坏O(n)
内存占用 较少（只存节点） 较多（哈希表+桶+节点）
key要求 可比较（<运算符） 可哈希+可判等
迭代器稳定性 稳定（插入删除不影响其他） 不稳定（rehash时失效）

2. map的使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <map>

// 基本操作
map<string, int> ages;

// 插入
ages["Alice"] = 25;
ages["Bob"] = 30;
ages.insert({"Charlie", 35});
ages.insert(make_pair("David", 40));

// 查找
if (ages.find("Alice") != ages.end()) {
    cout << "找到Alice，年龄: " << ages["Alice"] << endl;
}

// 删除
ages.erase("Bob");

// 遍历（有序）
for (const auto& [name, age] : ages) {
    cout << name << ": " << age << endl;
}
// 输出按key排序：Alice, Charlie, David

// 范围查询
auto it_begin = ages.lower_bound("Bob");   // 第一个 >= "Bob"
auto it_end = ages.upper_bound("David");   // 第一个 > "David"

for (auto it = it_begin; it != it_end; ++it) {
    cout << it->first << ": " << it->second << endl;
}

3. unordered_map的使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <unordered_map>

// 基本操作
unordered_map<string, int> word_count;

// 插入和更新
vector<string> words = {"apple", "banana", "apple", "cherry", "banana", "apple"};
for (const auto& word : words) {
    word_count[word]++;  // 快速查找和更新
}

// 查找
auto it = word_count.find("apple");
if (it != word_count.end()) {
    cout << "apple出现了 " << it->second << " 次\n";
}

// 遍历（无序）
for (const auto& [word, count] : word_count) {
    cout << word << ": " << count << endl;
}
// 输出顺序不确定

// 桶信息
cout << "桶数量: " << word_count.bucket_count() << endl;
cout << "负载因子: " << word_count.load_factor() << endl;
cout << "最大负载因子: " << word_count.max_load_factor() << endl;

4. 性能对比：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <chrono>

void performanceTest() {
    const int N = 100000;
    
    // map性能
    auto start = chrono::high_resolution_clock::now();
    map<int, int> m;
    for (int i = 0; i < N; ++i) {
        m[i] = i;
    }
    for (int i = 0; i < N; ++i) {
        int val = m[i];
    }
    auto end = chrono::high_resolution_clock::now();
    cout << "map: " 
         << chrono::duration_cast<chrono::milliseconds>(end - start).count() 
         << "ms\n";
    
    // unordered_map性能
    start = chrono::high_resolution_clock::now();
    unordered_map<int, int> um;
    for (int i = 0; i < N; ++i) {
        um[i] = i;
    }
    for (int i = 0; i < N; ++i) {
        int val = um[i];
    }
    end = chrono::high_resolution_clock::now();
    cout << "unordered_map: " 
         << chrono::duration_cast<chrono::milliseconds>(end - start).count() 
         << "ms\n";
}

// 典型结果：unordered_map明显更快（数据量大时）

5. 自定义类型作为key：

map：需要比较函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct Person {
    string name;
    int age;
    
    // 方法1：重载<运算符
    bool operator<(const Person& other) const {
        if (name != other.name) {
            return name < other.name;
        }
        return age < other.age;
    }
};

map<Person, string> person_info;

// 方法2：自定义比较器
struct PersonCompare {
    bool operator()(const Person& a, const Person& b) const {
        return a.name < b.name;
    }
};

map<Person, string, PersonCompare> person_info2;

unordered_map：需要哈希函数和相等比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct Person {
    string name;
    int age;
    
    // 重载==运算符
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

// 自定义哈希函数
struct PersonHash {
    size_t operator()(const Person& p) const {
        // 组合name和age的哈希值
        return hash<string>()(p.name) ^ (hash<int>()(p.age) << 1);
    }
};

unordered_map<Person, string, PersonHash> person_info;

// 或使用std::hash特化
namespace std {
    template<>
    struct hash<Person> {
        size_t operator()(const Person& p) const {
            return hash<string>()(p.name) ^ (hash<int>()(p.age) << 1);
        }
    };
}

unordered_map<Person, string> person_info2;

6. 应用场景选择：

使用map的场景：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 场景1：需要有序遍历
map<int, string> id_to_name;
// 按ID顺序输出
for (const auto& [id, name] : id_to_name) {
    cout << id << ": " << name << endl;
}

// 场景2：需要范围查询
map<int, double> scores;
// 查找分数在80-90之间的学生
auto begin = scores.lower_bound(80);
auto end = scores.upper_bound(90);
for (auto it = begin; it != end; ++it) {
    cout << it->first << ": " << it->second << endl;
}

// 场景3：需要找最大/最小key
map<int, string> m;
if (!m.empty()) {
    cout << "最小key: " << m.begin()->first << endl;
    cout << "最大key: " << m.rbegin()->first << endl;
}

// 场景4：需要稳定的迭代器
map<string, int> stable_map;
auto it = stable_map.find("key");
// 插入新元素不会使it失效
stable_map["new_key"] = 100;
// it仍然有效

使用unordered_map的场景：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 场景1：纯键值查找，追求速度
unordered_map<string, int> cache;
string key = getUserInput();
if (cache.find(key) != cache.end()) {
    return cache[key];  // 快速查找
}

// 场景2：频繁插入删除
unordered_map<int, Data> active_connections;
// 快速添加/删除连接

// 场景3：计数、频率统计
unordered_map<string, int> word_frequency;
for (const auto& word : document) {
    word_frequency[word]++;
}

// 场景4：大数据量，不需要排序
unordered_map<uint64_t, User> user_database;  // 百万级用户
// O(1)查找远快于O(log n)

7. 内存和性能权衡：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// map：内存紧凑
// 每个节点：key + value + 2个子指针 + 父指针 + 颜色（约5个指针）

// unordered_map：内存开销大
// 哈希表 + 桶数组 + 链表节点
// 可能是map的1.5-2倍内存

void memoryComparison() {
    const int N = 10000;
    
    map<int, int> m;
    unordered_map<int, int> um;
    
    for (int i = 0; i < N; ++i) {
        m[i] = i;
        um[i] = i;
    }
    
    // map通常更紧凑
    // unordered_map占用更多内存（哈希表开销）
}

8. 哈希冲突和性能退化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// unordered_map的最坏情况
struct BadHash {
    size_t operator()(int x) const {
        return 0;  // 所有key的哈希值相同！
    }
};

unordered_map<int, int, BadHash> bad_map;
for (int i = 0; i < 1000; ++i) {
    bad_map[i] = i;  // O(n)！所有元素在同一个桶
}
// 查找退化为O(n)

// 好的哈希函数分布均匀
unordered_map<int, int> good_map;  // 使用默认哈希
for (int i = 0; i < 1000; ++i) {
    good_map[i] = i;  // O(1)平均
}

9. 实际应用示例：

LRU缓存（使用unordered_map）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class LRUCache {
    int capacity;
    list<pair<int, int>> items;  // {key, value}
    unordered_map<int, list<pair<int, int>>::iterator> cache;
    
public:
    LRUCache(int cap) : capacity(cap) {}
    
    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1;
        }
        
        // 移到最前面
        items.splice(items.begin(), items, cache[key]);
        return cache[key]->second;
    }
    
    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            // 更新并移到最前
            items.splice(items.begin(), items, cache[key]);
            cache[key]->second = value;
            return;
        }
        
        if (items.size() == capacity) {
            // 删除最久未使用
            int old_key = items.back().first;
            items.pop_back();
            cache.erase(old_key);
        }
        
        items.push_front({key, value});
        cache[key] = items.begin();
    }
};

有序统计（使用map）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class OrderedStats {
    map<int, int> score_count;  // 分数 -> 出现次数
    
public:
    void addScore(int score) {
        score_count[score]++;
    }
    
    int getRank(int score) {
        int rank = 0;
        for (const auto& [s, count] : score_count) {
            if (s >= score) break;
            rank += count;
        }
        return rank;
    }
    
    int getPercentile(double p) {
        int total = 0;
        for (const auto& [s, count] : score_count) {
            total += count;
        }
        
        int target = total * p;
        int累计 = 0;
        for (const auto& [score, count] : score_count) {
            累计 += count;
            if (累计 >= target) {
                return score;
            }
        }
        return 0;
    }
};

口头解答：
“map和unordered_map都是关联容器，主要区别在底层实现。map用红黑树，元素自动排序，查找是O(log n)；unordered_map用哈希表，无序但查找平均O(1)，更快。选择哪个要看需求：如果需要遍历时有序，或者要做范围查询，用map；如果只是单纯的键值查找，追求速度，用unordered_map。不过unordered_map也有缺点，哈希冲突时性能会退化，而且占用内存更多。还有个细节，map的key只需要能比较大小，而unordered_map的key必须能计算哈希值，所以自定义类型作key时，后者要额外提供hash函数。总的来说，数据量大、频繁查找的场景用unordered_map；需要有序或范围查询的场景用map。”

第二部分总结：

本部分涵盖了内存管理（题目11-15）和STL容器（题目16-17）的核心内容：

  • C++内存分区模型
  • 内存泄漏的检测和预防
  • RAII原则及应用
  • 内存对齐机制
  • new/delete实现原理
  • vector的动态扩容机制
  • map与unordered_map的对比

这些知识点对于理解C++的内存模型和高效使用STL至关重要。

题目18: 迭代器失效的情况有哪些？

解答：

迭代器失效是指迭代器不再指向有效的元素或容器状态改变导致迭代器行为未定义。

1. vector的迭代器失效：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> v = {1, 2, 3, 4, 5};
auto it = v.begin();

// 情况1：插入导致扩容 - 所有迭代器失效
v.push_back(6);  // 可能扩容
// it失效！不能再使用

// 情况2：中间插入 - 插入点及之后的迭代器失效
v = {1, 2, 3, 4, 5};
it = v.begin() + 2;  // 指向3
v.insert(it, 99);     // 在位置2插入99
// it失效！

// 情况3：删除 - 被删除位置及之后的迭代器失效
v = {1, 2, 3, 4, 5};
it = v.begin() + 2;
v.erase(it);  // 删除3
// it失效！

// 正确做法：使用erase的返回值
it = v.erase(it);  // it现在指向下一个有效元素

安全删除元素：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// ✗ 错误
vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0) {
        v.erase(it);  // it失效，++it会导致未定义行为
    }
}

// ✓ 正确
for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) {
        it = v.erase(it);  // 更新迭代器
    } else {
        ++it;
    }
}

// ✓ 更好：使用算法
v.erase(remove_if(v.begin(), v.end(), 
                  [](int x) { return x % 2 == 0; }), 
        v.end());

2. deque的迭代器失效：

1
2
3
4
5
6
7
8
9
10
11
12
deque<int> d = {1, 2, 3, 4, 5};

// 首尾插入/删除：只有首尾迭代器失效
d.push_back(6);   // end()失效，其他有效
d.push_front(0);  // begin()失效，其他有效
d.pop_back();     // end()失效
d.pop_front();    // begin()失效

// 中间插入/删除：所有迭代器失效
auto it = d.begin() + 2;
d.insert(it, 99);  // 所有迭代器失效
d.erase(it);       // 所有迭代器失效

3. list的迭代器失效：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
list<int> l = {1, 2, 3, 4, 5};

// list的迭代器非常稳定！
auto it1 = l.begin();
auto it2 = ++l.begin();

// 插入：不影响其他迭代器
l.insert(it1, 99);
// it1, it2都仍然有效

// 删除：只有被删除元素的迭代器失效
it1 = l.begin();
l.erase(it1);  // 只有it1失效，it2仍有效

// 安全删除
for (auto it = l.begin(); it != l.end(); ) {
    if (*it % 2 == 0) {
        it = l.erase(it);  // 返回下一个迭代器
    } else {
        ++it;
    }
}

4. map/set的迭代器失效：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
map<int, string> m = {{1, "one"}, {2, "two"}, {3, "three"}};

auto it1 = m.find(1);
auto it2 = m.find(2);

// 插入：不影响现有迭代器
m[4] = "four";  // it1, it2仍有效

// 删除：只有被删除元素的迭代器失效
m.erase(it1);  // 只有it1失效，it2仍有效

// 安全删除
for (auto it = m.begin(); it != m.end(); ) {
    if (it->second == "two") {
        it = m.erase(it);  // C++11返回下一个迭代器
    } else {
        ++it;
    }
}

// C++03需要先递增
for (auto it = m.begin(); it != m.end(); ) {
    if (it->second == "two") {
        m.erase(it++);  // 先拷贝it，递增，再删除拷贝
    } else {
        ++it;
    }
}

5. unordered_map/set的迭代器失效：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
unordered_map<int, string> um = {{1, "one"}, {2, "two"}};

// rehash时：所有迭代器失效
auto it = um.begin();
um.reserve(1000);  // 可能触发rehash
// it失效！

// 插入可能导致rehash
um[3] = "three";  // 如果触发rehash，所有迭代器失效

// 删除：只有被删除元素的迭代器失效
it = um.find(1);
um.erase(it);  // 只有it失效

// 避免rehash
um.reserve(expected_size);  // 预留空间
// 之后的插入不会rehash（除非超过reserved size）

6. 完整的迭代器失效总结表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
容器类型       插入操作                    删除操作
-----------------------------------------------------------
vector        插入点及之后失效             删除点及之后失效
              扩容时全部失效

deque         中间插入全部失效             中间删除全部失效
              首尾插入只有首尾失效         首尾删除只有首尾失效

list          不失效                       只有被删元素失效

set/map       不失效                       只有被删元素失效

unordered_*   rehash时全部失效            只有被删元素失效
              插入可能导致rehash
*/

7. 实际案例和陷阱：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 陷阱1：在循环中修改容器
vector<int> v = {1, 2, 3, 4, 5};

// ✗ 危险
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it == 3) {
        v.erase(it);  // it失效，++it未定义行为
    }
}

// ✓ 安全
for (auto it = v.begin(); it != v.end(); ) {
    if (*it == 3) {
        it = v.erase(it);
    } else {
        ++it;
    }
}

// 陷阱2：使用失效的迭代器
vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4);  // 可能扩容
cout << *it;      // 未定义行为！

// 陷阱3：删除后继续使用
map<int, string> m = {{1, "one"}, {2, "two"}};
auto it = m.find(1);
m.erase(it);
cout << it->second;  // 未定义行为！

// 陷阱4：范围for中修改容器
vector<int> v = {1, 2, 3, 4, 5};
for (int& x : v) {  // 内部使用迭代器
    if (x == 3) {
        v.erase(v.begin() + 2);  // 导致迭代器失效！
    }
}

8. 安全模式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 方法1：使用算法而非手动循环
vector<int> v = {1, 2, 3, 4, 5};
v.erase(remove_if(v.begin(), v.end(), 
                  [](int x) { return x % 2 == 0; }), 
        v.end());

// 方法2：收集要删除的元素
vector<int> to_remove;
for (size_t i = 0; i < v.size(); ++i) {
    if (should_delete(v[i])) {
        to_remove.push_back(i);
    }
}
// 从后向前删除（避免索引变化）
for (auto it = to_remove.rbegin(); it != to_remove.rend(); ++it) {
    v.erase(v.begin() + *it);
}

// 方法3：构建新容器
vector<int> new_v;
for (int x : v) {
    if (!should_delete(x)) {
        new_v.push_back(x);
    }
}
v = std::move(new_v);

// 方法4：使用索引而非迭代器（vector/deque）
for (size_t i = 0; i < v.size(); ) {
    if (should_delete(v[i])) {
        v.erase(v.begin() + i);
        // 不递增i，因为元素向前移动
    } else {
        ++i;
    }
}

口头解答：
“迭代器失效是STL使用中的常见陷阱。对于vector，插入删除都可能让迭代器失效，特别是插入时如果触发扩容，所有迭代器都失效。正确做法是使用erase的返回值更新迭代器。list就稳定多了，因为是链表，删除只影响被删除的节点，其他迭代器都有效。map和set基于红黑树，删除也只影响被删元素。最麻烦的是unordered容器，rehash时所有迭代器都失效。总的原则是：修改容器后不要假设迭代器还有效，要么用返回的新迭代器，要么重新获取。最安全的办法是使用STL算法，比如remove_if，而不是手动循环删除。”

题目19: STL中的sort函数是如何实现的？

解答：

1. 实现策略：混合排序算法（Introspective Sort，内省排序）

STL的sort采用三种算法的组合：

1
2
3
4
5
6
7
8
9
10
11
// 伪代码展示sort的实现策略
template<typename RandomIt>
void sort(RandomIt first, RandomIt last) {
    if (first == last) return;
    
    // 计算最大递归深度
    int depth_limit = 2 * log2(last - first);
    
    introsort_loop(first, last, depth_limit);
    final_insertion_sort(first, last);
}

2. 三种算法的组合：

快速排序（主体）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
template<typename RandomIt>
void introsort_loop(RandomIt first, RandomIt last, int depth_limit) {
    while (last - first > THRESHOLD) {  // THRESHOLD通常是16-32
        if (depth_limit == 0) {
            // 递归过深，切换到堆排序
            partial_sort(first, last, last);
            return;
        }
        
        --depth_limit;
        
        // 快速排序分区
        RandomIt pivot = partition(first, last);
        
        // 递归排序较小的那一半（尾递归优化）
        introsort_loop(pivot + 1, last, depth_limit);
        last = pivot;  // 继续处理左半部分
    }
}

// 分区函数（三路划分）
template<typename RandomIt>
RandomIt partition(RandomIt first, RandomIt last) {
    // 选择枢轴（通常用中位数）
    RandomIt mid = first + (last - first) / 2;
    
    // 三数取中
    if (*mid < *first) swap(*mid, *first);
    if (*(last-1) < *first) swap(*(last-1), *first);
    if (*(last-1) < *mid) swap(*(last-1), *mid);
    
    auto pivot = *mid;
    swap(*mid, *(last-1));
    
    // 分区
    auto i = first;
    for (auto j = first; j < last - 1; ++j) {
        if (*j < pivot) {
            swap(*i, *j);
            ++i;
        }
    }
    swap(*i, *(last-1));
    return i;
}

堆排序（防止最坏情况）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
template<typename RandomIt>
void partial_sort(RandomIt first, RandomIt middle, RandomIt last) {
    // 建堆
    make_heap(first, last);
    
    // 逐个取出最大元素
    for (auto i = last; i != middle; ) {
        --i;
        pop_heap(first, i + 1);
    }
    
    // 排序堆顶元素
    sort_heap(first, middle);
}

// 堆操作
template<typename RandomIt>
void make_heap(RandomIt first, RandomIt last) {
    auto len = last - first;
    if (len < 2) return;
    
    auto parent = (len - 2) / 2;
    while (true) {
        sift_down(first, parent, len);
        if (parent == 0) return;
        --parent;
    }
}

插入排序（小数组优化）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
template<typename RandomIt>
void final_insertion_sort(RandomIt first, RandomIt last) {
    if (last - first > THRESHOLD) {
        // 先对前THRESHOLD个元素排序
        insertion_sort(first, first + THRESHOLD);
        // 再插入排序其余元素
        unguarded_insertion_sort(first + THRESHOLD, last);
    } else {
        insertion_sort(first, last);
    }
}

template<typename RandomIt>
void insertion_sort(RandomIt first, RandomIt last) {
    if (first == last) return;
    
    for (auto i = first + 1; i != last; ++i) {
        auto value = *i;
        auto j = i;
        
        // 向前查找插入位置
        while (j != first && value < *(j - 1)) {
            *j = *(j - 1);
            --j;
        }
        *j = value;
    }
}

3. 为什么这样设计：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
算法选择原因：

1. 快速排序：
   - 平均O(n log n)，最快
   - 缓存友好（连续访问）
   - 问题：最坏O(n²)

2. 堆排序：
   - 保证O(n log n)
   - 防止快排退化
   - 递归深度超限时切换

3. 插入排序：
   - 小数组（<16元素）最快
   - 常数因子小
   - 几乎有序的数据很快

组合优势：
- 平均性能：O(n log n)
- 最坏性能：O(n log n)（有堆排序保证）
- 小数组优化
- 缓存友好
*/

4. 完整实现示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
template<typename RandomIt, typename Compare>
class IntroSort {
    static const int INSERTION_THRESHOLD = 16;
    
    static void sort(RandomIt first, RandomIt last, Compare comp) {
        if (first >= last) return;
        
        int depth_limit = 2 * log2(last - first);
        introsort_loop(first, last, depth_limit, comp);
        final_insertion_sort(first, last, comp);
    }
    
    static void introsort_loop(RandomIt first, RandomIt last, 
                               int depth_limit, Compare comp) {
        while (last - first > INSERTION_THRESHOLD) {
            if (depth_limit == 0) {
                // 切换到堆排序
                make_heap(first, last, comp);
                sort_heap(first, last, comp);
                return;
            }
            
            --depth_limit;
            
            // 快速排序分区
            RandomIt cut = median_partition(first, last, comp);
            
            // 递归较小部分，循环较大部分
            if (cut - first < last - cut) {
                introsort_loop(first, cut, depth_limit, comp);
                first = cut;
            } else {
                introsort_loop(cut, last, depth_limit, comp);
                last = cut;
            }
        }
    }
    
    static RandomIt median_partition(RandomIt first, RandomIt last, 
                                     Compare comp) {
        RandomIt mid = first + (last - first) / 2;
        RandomIt end = last - 1;
        
        // 三数取中
        if (comp(*mid, *first)) std::iter_swap(mid, first);
        if (comp(*end, *first)) std::iter_swap(end, first);
        if (comp(*end, *mid)) std::iter_swap(end, mid);
        
        // mid现在是中位数
        std::iter_swap(mid, end - 1);
        
        return partition_impl(first, end - 1, end - 1, comp);
    }
    
    static RandomIt partition_impl(RandomIt first, RandomIt last, 
                                   RandomIt pivot, Compare comp) {
        while (first < last) {
            while (comp(*first, *pivot)) ++first;
            while (!comp(*last, *pivot) && first < last) --last;
            if (first < last) {
                std::iter_swap(first, last);
                ++first;
                --last;
            }
        }
        return first;
    }
    
    static void final_insertion_sort(RandomIt first, RandomIt last, 
                                     Compare comp) {
        for (auto i = first + 1; i < last; ++i) {
            auto value = std::move(*i);
            auto j = i;
            while (j > first && comp(value, *(j - 1))) {
                *j = std::move(*(j - 1));
                --j;
            }
            *j = std::move(value);
        }
    }
};

5. 性能特点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <algorithm>
#include <chrono>
#include <random>

void performanceTest() {
    const int N = 1000000;
    vector<int> v(N);
    
    random_device rd;
    mt19937 gen(rd());
    
    // 测试1：随机数据
    uniform_int_distribution<> dis(1, N);
    for (int& x : v) x = dis(gen);
    
    auto start = chrono::high_resolution_clock::now();
    sort(v.begin(), v.end());
    auto end = chrono::high_resolution_clock::now();
    
    cout << "随机数据: " 
         << chrono::duration_cast<chrono::milliseconds>(end - start).count() 
         << "ms\n";
    
    // 测试2：已排序数据（最好情况）
    start = chrono::high_resolution_clock::now();
    sort(v.begin(), v.end());  // 已经有序
    end = chrono::high_resolution_clock::now();
    
    cout << "有序数据: " 
         << chrono::duration_cast<chrono::milliseconds>(end - start).count() 
         << "ms\n";
    
    // 测试3：逆序数据
    reverse(v.begin(), v.end());
    start = chrono::high_resolution_clock::now();
    sort(v.begin(), v.end());
    end = chrono::high_resolution_clock::now();
    
    cout << "逆序数据: " 
         << chrono::duration_cast<chrono::milliseconds>(end - start).count() 
         << "ms\n";
}

6. stable_sort的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// stable_sort通常使用归并排序
template<typename RandomIt>
void stable_sort(RandomIt first, RandomIt last) {
    auto len = last - first;
    if (len <= 1) return;
    
    // 需要额外的O(n)空间
    using value_type = typename iterator_traits<RandomIt>::value_type;
    vector<value_type> buffer(len);
    
    merge_sort_impl(first, last, buffer.begin());
}

template<typename RandomIt, typename BufIt>
void merge_sort_impl(RandomIt first, RandomIt last, BufIt buffer) {
    auto len = last - first;
    if (len <= THRESHOLD) {
        insertion_sort(first, last);  // 小数组用插入排序
        return;
    }
    
    auto mid = first + len / 2;
    
    // 递归排序两半
    merge_sort_impl(first, mid, buffer);
    merge_sort_impl(mid, last, buffer);
    
    // 合并
    merge(first, mid, mid, last, buffer);
    
    // 拷贝回原数组
    copy(buffer, buffer + len, first);
}

7. 自定义比较函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct Person {
    string name;
    int age;
};

// 方法1：lambda
vector<Person> people = /* ... */;
sort(people.begin(), people.end(), 
     [](const Person& a, const Person& b) {
         return a.age < b.age;
     });

// 方法2：函数对象
struct CompareByAge {
    bool operator()(const Person& a, const Person& b) const {
        return a.age < b.age;
    }
};
sort(people.begin(), people.end(), CompareByAge());

// 方法3：重载<运算符
bool operator<(const Person& a, const Person& b) {
    return a.age < b.age;
}
sort(people.begin(), people.end());

// 降序排序
sort(people.begin(), people.end(), greater<Person>());

8. sort vs stable_sort vs partial_sort：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

// sort：不稳定，O(n log n)
sort(v.begin(), v.end());

// stable_sort：稳定（保持相等元素的相对顺序），O(n log n)
stable_sort(v.begin(), v.end());

// partial_sort：只排序前k个，O(n log k)
partial_sort(v.begin(), v.begin() + 3, v.end());
// 前3个是最小的且有序，后面的无序

// nth_element：第n个元素在正确位置，O(n)
nth_element(v.begin(), v.begin() + 3, v.end());
// v[3]是第4小的元素，前面都<=它，后面都>=它

// 性能比较：
// sort:           O(n log n)  不稳定  全排序
// stable_sort:    O(n log n)  稳定    全排序  需要额外空间
// partial_sort:   O(n log k)  不稳定  部分排序
// nth_element:    O(n)        不稳定  找第k个

口头解答：
“STL的sort非常巧妙，它不是单一算法，而是综合了三种排序的优点。主体是快速排序，因为平均性能最好，而且缓存友好。但快排有个问题，遇到特殊数据可能退化到O(n²)，所以当递归太深时会切换到堆排序保证最坏情况性能。另外，数据量很小时（通常少于16个元素），插入排序反而更快，因为没有递归开销。这种设计叫内省排序，既快又稳定，保证了平均和最坏情况都是O(n log n)。需要注意的是，sort是不稳定的，如果要保持相等元素的相对顺序，要用stable_sort，它通常用归并排序实现。还有就是sort要求随机访问迭代器，所以list不能用sort，要用list自己的sort成员函数。”

题目20: emplace_back和push_back的区别

解答：

1. 基本区别：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Widget {
    int x, y;
public:
    Widget(int a, int b) : x(a), y(b) {
        cout << "构造(" << a << ", " << b << ")\n";
    }
    
    Widget(const Widget& w) : x(w.x), y(w.y) {
        cout << "拷贝构造\n";
    }
    
    Widget(Widget&& w) noexcept : x(w.x), y(w.y) {
        cout << "移动构造\n";
    }
};

vector<Widget> v;

// push_back：先构造对象，再移动/拷贝到容器
v.push_back(Widget(1, 2));
// 输出：构造(1, 2)
//       移动构造

// emplace_back：直接在容器内存上构造
v.emplace_back(3, 4);
// 输出：构造(3, 4)
// 只构造一次，无拷贝/移动！

2. 详细的执行过程：

1
2
3
4
5
6
7
8
// push_back的过程
Widget temp(1, 2);           // 1. 创建临时对象
v.push_back(std::move(temp)); // 2. 移动到容器
                              // 3. 销毁临时对象

// emplace_back的过程
// 直接在vector的内存位置调用构造函数
new (v.data() + v.size()) Widget(1, 2);  // placement new

3. 实现原理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 简化的实现
template<typename T>
class SimpleVector {
    T* data;
    size_t size_;
    size_t capacity_;
    
public:
    // push_back（拷贝版本）
    void push_back(const T& value) {
        if (size_ == capacity_) {
            reserve(capacity_ * 2);
        }
        new (&data[size_]) T(value);  // 拷贝构造
        ++size_;
    }
    
    // push_back（移动版本）
    void push_back(T&& value) {
        if (size_ == capacity_) {
            reserve(capacity_ * 2);
        }
        new (&data[size_]) T(std::move(value));  // 移动构造
        ++size_;
    }
    
    // emplace_back（可变参数模板）
    template<typename... Args>
    void emplace_back(Args&&... args) {
        if (size_ == capacity_) {
            reserve(capacity_ * 2);
        }
        // 完美转发，直接构造
        new (&data[size_]) T(std::forward<Args>(args)...);
        ++size_;
    }
};

4. 性能对比：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <chrono>

struct LargeObject {
    int data[1000];
    
    LargeObject(int val) {
        for (int& x : data) x = val;
    }
    
    LargeObject(const LargeObject& other) {
        memcpy(data, other.data, sizeof(data));
    }
    
    LargeObject(LargeObject&& other) noexcept {
        memcpy(data, other.data, sizeof(data));
    }
};

void performanceTest() {
    const int N = 100000;
    
    // push_back测试
    vector<LargeObject> v1;
    v1.reserve(N);
    auto start = chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) {
        v1.push_back(LargeObject(i));  // 构造临时对象 + 移动
    }
    auto end = chrono::high_resolution_clock::now();
    cout << "push_back: " 
         << chrono::duration_cast<chrono::milliseconds>(end - start).count() 
         << "ms\n";
    
    // emplace_back测试
    vector<LargeObject> v2;
    v2.reserve(N);
    start = chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) {
        v2.emplace_back(i);  // 直接构造，无移动
    }
    end = chrono::high_resolution_clock::now();
    cout << "emplace_back: " 
         << chrono::duration_cast<chrono::milliseconds>(end - start).count() 
         << "ms\n";
}

// emplace_back通常更快，特别是对于大对象

5. 使用场景对比：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
vector<Widget> v;

// 场景1：已有对象 - push_back更清晰
Widget w(1, 2);
v.push_back(w);              // 拷贝
v.push_back(std::move(w));   // 移动
v.emplace_back(w);           // 也可以，但不如push_back清晰

// 场景2：构造新对象 - emplace_back更高效
v.push_back(Widget(3, 4));   // 构造临时对象 + 移动
v.emplace_back(3, 4);        // 直接构造，更高效

// 场景3：复杂构造参数
struct Complex {
    string name;
    vector<int> data;
    int value;
    
    Complex(const string& n, vector<int> d, int v)
        : name(n), data(std::move(d)), value(v) {}
};

vector<Complex> cv;

// push_back：需要显式构造
cv.push_back(Complex("test", vector<int>{1,2,3}, 42));

// emplace_back：更简洁
cv.emplace_back("test", vector<int>{1,2,3}, 42);

6. 隐式转换：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<string> v;

// push_back：会进行隐式转换
v.push_back("hello");  // const char* 隐式转换为 string

// emplace_back：也支持隐式转换
v.emplace_back("world");

// 但emplace_back可以避免某些不必要的转换
vector<vector<int>> vv;

vv.push_back({1, 2, 3});     // 创建临时vector + 移动
vv.emplace_back({1, 2, 3});  // 直接构造（C++11）

// 初始化列表的情况
vv.emplace_back(initializer_list<int>{4, 5, 6});  // 显式
vv.push_back({4, 5, 6});     // 更简洁

7. 潜在陷阱：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 陷阱1：explicit构造函数
struct ExplicitWidget {
    explicit ExplicitWidget(int x) {}
};

vector<ExplicitWidget> v;

// v.push_back(10);    // 错误！explicit阻止隐式转换
v.push_back(ExplicitWidget(10));  // 正确
v.emplace_back(10);               // 正确！直接调用构造函数

// 陷阱2：异常安全
class Resource {
    int* ptr;
public:
    Resource(int val) : ptr(new int(val)) {}
    ~Resource() { delete ptr; }
};

vector<Resource> vr;

// push_back：异常发生在移动时，原对象还在
try {
    Resource r(10);
    vr.push_back(std::move(r));
} catch (...) {
    // r仍然有效（虽然是moved-from状态）
}

// emplace_back：异常发生在构造时
try {
    vr.emplace_back(10);  // 直接在vector中构造
} catch (...) {
    // 如果构造失败，没有外部对象
}

// 陷阱3：多步构造
vector<pair<int, string>> vp;

vp.push_back({1, "one"});      // 简洁
vp.emplace_back(1, "one");     // 也可以
vp.emplace_back(make_pair(2, "two"));  // 不必要的复杂

// 最清晰的写法
vp.push_back(make_pair(3, "three"));

8. 其他容器的emplace系列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// map/unordered_map：emplace
map<string, int> m;

// insert：需要构造pair
m.insert(make_pair("key", 42));
m.insert({"key", 42});

// emplace：直接构造pair
m.emplace("key", 42);  // 更高效

// emplace_hint：提供插入位置提示
auto hint = m.lower_bound("key");
m.emplace_hint(hint, "key", 42);

// list：emplace_front, emplace_back, emplace
list<Widget> l;
l.emplace_front(1, 2);
l.emplace_back(3, 4);
l.emplace(l.begin(), 5, 6);

// deque：emplace_front, emplace_back
deque<Widget> d;
d.emplace_front(1, 2);
d.emplace_back(3, 4);

// set：emplace
set<Widget> s;
s.emplace(1, 2);

9. 选择建议：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 使用push_back的情况：
// 1. 已有对象要插入
Widget w(1, 2);
v.push_back(w);

// 2. 移动已有对象
v.push_back(std::move(w));

// 3. 代码更清晰的情况
v.push_back({1, 2});  // initializer_list

// 使用emplace_back的情况：
// 1. 构造新对象
v.emplace_back(1, 2);  // 直接传构造参数

// 2. 避免临时对象
v.emplace_back(arg1, arg2, arg3);  // 多个参数

// 3. explicit构造函数
v.emplace_back(single_arg);

// 总原则：
// - 有对象：push_back
// - 构造对象：emplace_back
// - 不确定：emplace_back更安全（总能工作）

10. C++17的改进：

1
2
3
4
5
6
7
8
9
10
11
12
// C++17：保证拷贝省略
vector<Widget> v;

Widget createWidget() {
    return Widget(1, 2);
}

v.push_back(createWidget());  
// C++17保证零拷贝，性能与emplace_back相当

// 但仍然推荐emplace_back当直接构造时
v.emplace_back(1, 2);  // 更清晰地表达意图

口头解答：
“emplace_back是C++11引入的，它的优势在于原地构造。push_back要先创建一个对象，然后拷贝或移动到容器里；而emplace_back直接把构造函数的参数转发到容器的内存位置，在那里构造对象，省去了中间的拷贝或移动。对于构造成本高的对象，这个优化还是很明显的。不过对于简单类型或者已经有现成对象要插入的情况，两者差别不大。实践中，如果是传参数构造对象，用emplace_back；如果已经有对象，用push_back就行。不过现在很多人倾向于统一用emplace_back，因为它更通用也更高效。另外emplace_back还有个好处，能绕过explicit构造函数的限制。”

第二部分完整总结：

本部分涵盖了C++内存管理（题目11-15）和STL容器算法（题目16-20）的核心内容：

内存管理：

  • C++内存分区（栈、堆、全局/静态区、常量区、代码区）
  • 内存泄漏的原因、检测和避免方法
  • RAII原则及其在标准库中的广泛应用
  • 内存对齐的原理和优化技巧
  • new/delete的底层实现和重载机制

STL容器与算法：

  • vector的动态数组实现和扩容策略
  • map（红黑树）vs unordered_map（哈希表）的选择
  • 迭代器失效的各种情况和安全使用模式
  • sort的内省排序算法（快排+堆排序+插入排序）
  • emplace系列函数的原地构造优势

这些知识点对于编写高性能、内存安全的C++代码至关重要。

下一部分预告：
第三部分（题目21-30）将深入智能指针和多线程编程，包括unique_ptr、shared_ptr、weak_ptr的使用，以及std::thread、mutex、条件变量等并发编程核心内容。