C++学习笔记-优化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
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

#include <iostream>
#include <vector>

struct Vertex
{
    float x, y, z;
    
    Vertex(float x, float y, float z) : x(x), y(y), z(z) {}
    
    Vertex(const Vertex& other) : x(other.x), y(other.y), z(other.z)
    {
        std::cout << "Copied Vertex(" << x << ", " << y << ", " << z << ")" << std::endl;
    }
    
    Vertex(Vertex&& other) noexcept : x(other.x), y(other.y), z(other.z)
    {
        std::cout << "Moved Vertex(" << x << ", " << y << ", " << z << ")" << std::endl;
    }
};

std::ostream& operator<<(std::ostream& ostream, const Vertex& vertex)
{
    ostream << vertex.x << ", " << vertex.y << ", " << vertex.z;
    return ostream;
}

void DemonstrateReallocation()
{
    std::cout << "=== Without reserve ===" << std::endl;
    std::vector<Vertex> vertices;
    
    std::cout << "Initial capacity: " << vertices.capacity() << std::endl;
    
    vertices.push_back(Vertex(1, 2, 3));
    std::cout << "After 1st push_back, capacity: " << vertices.capacity() << std::endl;
    
    vertices.push_back(Vertex(4, 5, 6));
    std::cout << "After 2nd push_back, capacity: " << vertices.capacity() << std::endl;
    
    vertices.push_back(Vertex(7, 8, 9));
    std::cout << "After 3rd push_back, capacity: " << vertices.capacity() << std::endl;
    
    /*
    分析输出结果：
    1. Vector首先在当前栈上创建临时对象，然后移动到Vector内存中，会输出1次Moved
    2. 当Vector当前容量不足以存储新加入的元素时，会重新分配Vector内存，
       也就是在当前栈上重新创建一个Vector，然后将旧的Vector中的元素Copied到新的Vector中，
       然后再把新的Vector移动到实际的Vector内存中去，这就是为什么会输出3次Copied的原因
    */
}

int main()
{
    DemonstrateReallocation();
}

 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 OptimizedWithReserve()
{
    std::cout << "\n=== With reserve ===" << std::endl;
    std::vector<Vertex> vertices;
    vertices.reserve(3);  // 预分配容量，避免重新分配
    
    std::cout << "Initial capacity: " << vertices.capacity() << std::endl;
    
    vertices.push_back(Vertex(1, 2, 3));
    std::cout << "After 1st push_back, capacity: " << vertices.capacity() << std::endl;
    
    vertices.push_back(Vertex(4, 5, 6));
    std::cout << "After 2nd push_back, capacity: " << vertices.capacity() << std::endl;
    
    vertices.push_back(Vertex(7, 8, 9));
    std::cout << "After 3rd push_back, capacity: " << vertices.capacity() << std::endl;
    
    // 使用reserve后，不会发生重新分配，只会有移动操作，没有拷贝操作
}

int main()
{
    DemonstrateReallocation();
    OptimizedWithReserve();
}

 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

struct ComplexObject
{
    std::string name;
    int value;
    std::vector<int> data;
    
    ComplexObject(const std::string& n, int v, std::initializer_list<int> d)
        : name(n), value(v), data(d)
    {
        std::cout << "Construct ComplexObject: " << name << std::endl;
    }
    
    ComplexObject(const ComplexObject& other)
        : name(other.name), value(other.value), data(other.data)
    {
        std::cout << "Copy ComplexObject: " << name << std::endl;
    }
    
    ComplexObject(ComplexObject&& other) noexcept
        : name(std::move(other.name)), value(other.value), data(std::move(other.data))
    {
        std::cout << "Move ComplexObject: " << name << std::endl;
    }
    
    ~ComplexObject()
    {
        std::cout << "Destroy ComplexObject: " << name << std::endl;
    }
};

void ComparePushBackAndEmplaceBack()
{
    std::cout << "\n=== push_back vs emplace_back ===" << std::endl;
    
    std::vector<ComplexObject> vec1;
    vec1.reserve(2);
    
    std::cout << "--- Using push_back ---" << std::endl;
    vec1.push_back(ComplexObject("Object1", 42, {1, 2, 3}));  // 构造临时对象，然后移动
    
    std::cout << "\n--- Using emplace_back ---" << std::endl;
    std::vector<ComplexObject> vec2;
    vec2.reserve(2);
    vec2.emplace_back("Object2", 84, std::initializer_list<int>{4, 5, 6});  // 直接在vector内存中构造
    
    std::cout << "\n--- Comparison complete ---" << std::endl;
}

int main()
{
    ComparePushBackAndEmplaceBack();
}

 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

class ExpensiveObject
{
private:
    std::vector<int> m_Data;
    std::string m_Name;
    
public:
    ExpensiveObject(const std::string& name, size_t size) : m_Name(name)
    {
        m_Data.resize(size, 42);
        std::cout << "Create ExpensiveObject: " << m_Name << " (size: " << size << ")" << std::endl;
    }
    
    ExpensiveObject(const ExpensiveObject& other) : m_Data(other.m_Data), m_Name(other.m_Name)
    {
        std::cout << "EXPENSIVE COPY of " << m_Name << " (size: " << m_Data.size() << ")" << std::endl;
    }
    
    ExpensiveObject(ExpensiveObject&& other) noexcept 
        : m_Data(std::move(other.m_Data)), m_Name(std::move(other.m_Name))
    {
        std::cout << "Move ExpensiveObject: " << m_Name << std::endl;
    }
    
    const std::string& GetName() const { return m_Name; }
    size_t GetSize() const { return m_Data.size(); }
};

void BadPractice()
{
    std::cout << "\n=== Bad Practice (causes copies) ===" << std::endl;
    std::vector<ExpensiveObject> vec;
    
    // 不好的做法：没有预分配容量
    vec.push_back(ExpensiveObject("Bad1", 1000));
    vec.push_back(ExpensiveObject("Bad2", 1000));  // 可能触发重新分配和拷贝
    vec.push_back(ExpensiveObject("Bad3", 1000));  // 可能再次触发重新分配和拷贝
}

void GoodPractice()
{
    std::cout << "\n=== Good Practice (avoids copies) ===" << std::endl;
    std::vector<ExpensiveObject> vec;
    vec.reserve(3);  // 预分配容量
    
    // 好的做法：使用emplace_back直接构造
    vec.emplace_back("Good1", 1000);
    vec.emplace_back("Good2", 1000);
    vec.emplace_back("Good3", 1000);
}

int main()
{
    BadPractice();
    GoodPractice();
}

 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

class MoveOptimizedClass
{
private:
    std::unique_ptr<int[]> m_Data;
    size_t m_Size;
    std::string m_Name;
    
public:
    MoveOptimizedClass(const std::string& name, size_t size) 
        : m_Name(name), m_Size(size)
    {
        m_Data = std::make_unique<int[]>(size);
        std::fill(m_Data.get(), m_Data.get() + size, 42);
        std::cout << "Create " << m_Name << " (size: " << m_Size << ")" << std::endl;
    }
    
    // 拷贝构造函数（昂贵）
    MoveOptimizedClass(const MoveOptimizedClass& other) 
        : m_Name(other.m_Name), m_Size(other.m_Size)
    {
        m_Data = std::make_unique<int[]>(m_Size);
        std::copy(other.m_Data.get(), other.m_Data.get() + m_Size, m_Data.get());
        std::cout << "EXPENSIVE COPY of " << m_Name << std::endl;
    }
    
    // 移动构造函数（高效）
    MoveOptimizedClass(MoveOptimizedClass&& other) noexcept
        : m_Data(std::move(other.m_Data)), m_Size(other.m_Size), m_Name(std::move(other.m_Name))
    {
        other.m_Size = 0;
        std::cout << "Move " << m_Name << std::endl;
    }
    
    const std::string& GetName() const { return m_Name; }
};

std::vector<MoveOptimizedClass> CreateObjects()
{
    std::vector<MoveOptimizedClass> result;
    result.reserve(3);
    
    result.emplace_back("Factory1", 1000);
    result.emplace_back("Factory2", 1000);
    result.emplace_back("Factory3", 1000);
    
    return result;  // 返回时使用移动语义
}

int main()
{
    std::cout << "\n=== Move Optimization ===" << std::endl;
    auto objects = CreateObjects();
    
    std::cout << "\nObjects in vector:" << std::endl;
    for (const auto& obj : objects)
    {
        std::cout << "- " << obj.GetName() << std::endl;
    }
}

 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

void CapacityManagement()
{
    std::cout << "\n=== Capacity Management ===" << std::endl;
    
    std::vector<int> vec;
    
    std::cout << "Initial - Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;
    
    // 观察容量增长模式
    for (int i = 0; i < 10; ++i)
    {
        vec.push_back(i);
        std::cout << "After push " << i << " - Size: " << vec.size() 
                  << ", Capacity: " << vec.capacity() << std::endl;
    }
    
    // 手动管理容量
    std::cout << "\n--- Manual capacity management ---" << std::endl;
    std::vector<int> vec2;
    vec2.reserve(20);  // 预分配
    std::cout << "After reserve(20) - Size: " << vec2.size() 
              << ", Capacity: " << vec2.capacity() << std::endl;
    
    for (int i = 0; i < 15; ++i)
    {
        vec2.push_back(i);
    }
    std::cout << "After 15 pushes - Size: " << vec2.size() 
              << ", Capacity: " << vec2.capacity() << std::endl;
    
    // 收缩容量
    vec2.shrink_to_fit();
    std::cout << "After shrink_to_fit() - Size: " << vec2.size() 
              << ", Capacity: " << vec2.capacity() << std::endl;
}

int main()
{
    CapacityManagement();
}

 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

#include <chrono>

void PerformanceBenchmark()
{
    const size_t SIZE = 100000;
    const int ITERATIONS = 100;
    
    // 测试1：不使用reserve的push_back
    auto start = std::chrono::high_resolution_clock::now();
    for (int iter = 0; iter < ITERATIONS; ++iter)
    {
        std::vector<Vertex> vec;
        for (size_t i = 0; i < SIZE; ++i)
        {
            vec.push_back(Vertex(i, i+1, i+2));
        }
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto duration1 = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    // 测试2：使用reserve的push_back
    start = std::chrono::high_resolution_clock::now();
    for (int iter = 0; iter < ITERATIONS; ++iter)
    {
        std::vector<Vertex> vec;
        vec.reserve(SIZE);
        for (size_t i = 0; i < SIZE; ++i)
        {
            vec.push_back(Vertex(i, i+1, i+2));
        }
    }
    end = std::chrono::high_resolution_clock::now();
    auto duration2 = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    // 测试3：使用reserve的emplace_back
    start = std::chrono::high_resolution_clock::now();
    for (int iter = 0; iter < ITERATIONS; ++iter)
    {
        std::vector<Vertex> vec;
        vec.reserve(SIZE);
        for (size_t i = 0; i < SIZE; ++i)
        {
            vec.emplace_back(i, i+1, i+2);
        }
    }
    end = std::chrono::high_resolution_clock::now();
    auto duration3 = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    
    std::cout << "\n=== Performance Benchmark ===\n";
    std::cout << "push_back without reserve: " << duration1.count() << " ms\n";
    std::cout << "push_back with reserve: " << duration2.count() << " ms\n";
    std::cout << "emplace_back with reserve: " << duration3.count() << " ms\n";
    std::cout << "Reserve improvement: " << (double)duration1.count() / duration2.count() << "x\n";
    std::cout << "Emplace improvement: " << (double)duration2.count() / duration3.count() << "x\n";
}

int main()
{
    PerformanceBenchmark();
}

 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

class VectorBestPractices
{
public:
    // 1. 预分配容量
    static std::vector<int> CreateWithKnownSize(size_t expectedSize)
    {
        std::vector<int> vec;
        vec.reserve(expectedSize);  // 避免重新分配
        
        for (size_t i = 0; i < expectedSize; ++i)
        {
            vec.emplace_back(i);  // 使用emplace_back
        }
        
        return vec;  // 依赖RVO/移动语义
    }
    
    // 2. 避免不必要的拷贝
    static void ProcessVector(const std::vector<int>& vec)  // 传递const引用
    {
        for (const auto& element : vec)  // 使用const auto&
        {
            std::cout << element << " ";
        }
        std::cout << std::endl;
    }
    
    // 3. 合理使用移动语义
    static std::vector<std::string> CreateStringVector()
    {
        std::vector<std::string> result;
        result.reserve(3);
        
        std::string temp1 = "Hello";
        std::string temp2 = "World";
        std::string temp3 = "!";
        
        result.push_back(std::move(temp1));  // 移动而不是拷贝
        result.push_back(std::move(temp2));
        result.push_back(std::move(temp3));
        
        return result;
    }
    
    // 4. 使用emplace系列函数
    static void EmplaceExample()
    {
        std::vector<std::pair<int, std::string>> vec;
        vec.reserve(3);
        
        // 好的做法：直接构造
        vec.emplace_back(1, "One");
        vec.emplace_back(2, "Two");
        
        // 不好的做法：创建临时对象
        // vec.push_back(std::make_pair(3, "Three"));
        
        // 插入时也使用emplace
        vec.emplace(vec.begin(), 0, "Zero");
    }
};

int main()
{
    auto vec = VectorBestPractices::CreateWithKnownSize(5);
    VectorBestPractices::ProcessVector(vec);
    
    auto stringVec = VectorBestPractices::CreateStringVector();
    for (const auto& str : stringVec)
    {
        std::cout << str << " ";
    }
    std::cout << std::endl;
    
    VectorBestPractices::EmplaceExample();
}