AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【C++篇】从零实现 C++ Vector：深度剖析 STL 的核心机制与优化2

2024-10-08 61
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【C++篇】从零实现 C++ Vector：深度剖析 STL 的核心机制与优化

【C++篇】从零实现 C++ Vector：深度剖析 STL 的核心机制与优化1:https://developer.aliyun.com/article/1617539


3.2 pop_back函数：删除末尾元素

3.2.1 需求分析
  • pop_back用于删除vector中的最后一个元素。需要确保：
  • 删除后更新_finish指针。
  • 元素已经从逻辑上被移除，但空间不回收。


实现思路
  1. 将_finish指针向前移动一位，即删除最后一个元素。
  2. 不释放空间。
实现代码：
namespace W {
    template<class T>
    class vector {
    public:
        void pop_back() {
            assert(_finish != _start);  // 确保vector非空
            --_finish;  // 逻辑删除最后一个元素
        }

    private:
        T* _start;
        T* _finish;
        T* _endOfStorage;
    };
}


测试用例：
void TestPopBackVector() {
    W::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.pop_back();

    assert(v.size() == 2);  // 验证删除后的大小
    assert(v[0] == 1 && v[1] == 2);  // 验证剩余元素是否正确

    std::cout << "TestPopBackVector passed" << std::endl;
}
输出：
TestPopBackVector passed

3.3 insert函数：在指定位置插入元素

3.3.1 需求分析
  • insert用于在vector的任意位置插入元素。需要确保：
  • 插入位置之后的元素向后移动。
  • 插入前检查容量是否足够，必要时扩容。
实现思路
  1. 检查容量是否足够，不足时扩容。
  2. 将插入位置及其后的元素整体向后移动。
  3. 将新元素插入指定位置。
  4. 更新_finish指针。
实现代码：
namespace W {
    template<class T>
    class vector {
    public:
        T* insert(T* pos, const T& value) {
            assert(pos >= _start && pos <= _finish);  // 确保pos是有效指针

            // 检查空间是否足够
            if (_finish == _endOfStorage) {
                size_t newCapacity = capacity() == 0 ? 1 : capacity() * 2;
                size_t offset = pos - _start;  // 记录插入位置
                reserve(newCapacity);  // 扩容
                pos = _start + offset;  // 更新插入位置
            }

            // 将插入位置之后的元素整体向后移动
            for (T* it = _finish; it > pos; --it) {
                *it = *(it - 1);
            }

            // 插入新元素
            *pos = value;
            ++_finish;
            return pos;
        }

    private:
        T* _start;
        T* _finish;
        T* _endOfStorage;
    };
}


测试用例：
void TestInsertVector() {
    W::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(4);

    v.insert(v.begin() + 2, 3);  // 在第2个位置插入3

    assert(v.size() == 4);  // 验证插入后的大小
    assert(v[0] == 1 && v[1] == 2 && v[2] == 3 && v[3] == 4);  // 验证插入的元素是否正确

    std::cout << "TestInsertVector passed" << std::endl;
}
输出：
TestInsertVector passed

3.4 erase函数：删除指定位置的元素

3.4.1 需求分析
  • erase用于删除vector中的某个位置的元素。需要确保：
  • 删除后，删除位置之后的元素向前移动。
  • 删除后更新_finish指针。
实现思路
  1. 将erase位置之后的元素向前移动一位。
  2. 更新_finish指针。
实现代码：
namespace W {
    template<class T>
    class vector {
    public:
        T* erase(T* pos) {
            assert(pos >= _start && pos < _finish);  // 确保pos是有效指针

            // 将pos之后的元素向前移动
            for (T* it = pos; it < _finish - 1; ++it) {
                *it = *(it + 1);
            }

            --_finish;  // 更新_finish指针
            return pos;
        }

    private:
        T* _start;
        T* _finish;
        T* _endOfStorage;
    };
}
测试用例：
void TestEraseVector() {
    W::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);

    v.erase(v.begin() + 2);  // 删除第2个元素

    assert(v.size() == 3);  // 验证删除后的大小
    assert(v[0] == 1 && v[1] == 2 && v[2] == 4);  // 验证删除后的元素顺序

    std::cout << "TestEraseVector passed" << std::endl;
}
输出：
TestEraseVector passed

4. front和back函数

4.1 front函数：获取第一个元素

4.1.1 需求分析
  • front函数返回vector的第一个元素。需要确保：
  • 当vector非空时，返回正确的第一个元素。
实现代码：
namespace W {
    template<class T>
    class vector {
    public:
        T& front() {
            assert(!empty());  // 确保vector非空
            return *_start;  // 返回第一个元素
        }

    private:
        T* _start;
        T* _finish;
        T* _endOfStorage;
    };
}


测试用例：
void TestFrontVector() {
    W::vector<int> v;
    v.push_back(10);
    assert(v.front() == 10);  // 验证front

    v.push_back(20);
    assert(v.front() == 10);  // 验证front不变

    std::cout << "TestFrontVector passed" << std::endl;


}


输出：
TestFrontVector passed

4.2 back函数：获取最后一个元素

4.2.1 需求分析
  • back函数返回vector的最后一个元素。需要确保：
  • 当vector非空时，返回正确的最后一个元素。
实现代码：
namespace W {
    template<class T>
    class vector {
    public:
        T& back() {
            assert(!empty());  // 确保vector非空
            return *(_finish - 1);  // 返回最后一个元素
        }

    private:
        T* _start;
        T* _finish;
        T* _endOfStorage;
    };
}
测试用例：
void TestBackVector() {
    W::vector<int> v;
    v.push_back(10);
    assert(v.back() == 10);  // 验证back

    v.push_back(20);
    assert(v.back() == 20);  // 验证back变化

    std::cout << "TestBackVector passed" << std::endl;
}
输出：
TestBackVector passed

5.1 begin 与 end 函数：迭代器的基本操作

5.1.1 需求分析
  • begin 函数返回指向 vector 起始位置的迭代器（即指向第一个元素）。
  • end 函数返回指向 vector 末尾的迭代器（即指向最后一个元素的下一个位置）。
  • 两者结合可以用于遍历 vector 中的元素。
实现代码：
namespace W {
    template<class T>
    class vector {
    public:
        typedef T* iterator;  // 使用原生指针作为迭代器

        iterator begin() {
            return _start;
        }

        iterator end() {
            return _finish;
        }

    private:
        T* _start;
        T* _finish;
        T* _endOfStorage;
    };
}
测试用例：
void TestIteratorVector() {
    W::vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    // 使用迭代器遍历 vector
    for (W::vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    std::cout << "TestIteratorVector passed" << std::endl;
}
输出：
10 20 30 
TestIteratorVector passed

5.2 swap 函数：交换两个 vector

5.2.1 需求分析
  • swap 函数用于交换两个 vector 的内容，包括它们的起始指针、结束指针和容量指针。
  • swap 函数是常用的优化操作，特别是在实现移动语义时能大大提高效率。
实现代码：
namespace W {
    template<class T>
    class vector {
    public:
        void swap(vector<T>& v) {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_endOfStorage, v._endOfStorage);
        }

    private:
        T* _start;
        T* _finish;
        T* _endOfStorage;
    };
}
测试用例：
void TestSwapVector() {
    W::vector<int> v1;
    W::vector<int> v2;

    v1.push_back(1);
    v1.push_back(2);
    v2.push_back(3);
    v2.push_back(4);
    
    v1.swap(v2);

    // 验证 v1 和 v2 交换后内容是否正确
    for (auto e : v1) {
        std::cout << e << " ";
    }
    std::cout << std::endl;

    for (auto e : v2) {
        std::cout << e << " ";
    }
    std::cout << std::endl;

    std::cout << "TestSwapVector passed" << std::endl;
}


输出：
3 4 
1 2 
TestSwapVector passed

5.3 赋值运算符重载：深拷贝 vector（现代写法）

5.3.1 需求分析
  • 拷贝构造函数的任务是创建一个全新的 vector，并确保与原 vector 独立，使用深拷贝拷贝元素。赋值运算符重载代码大致也是相同的，那有没有办法简化呢？
  • 为了使用现代 C++ 的最佳实践，我们可以采用 拷贝并交换（Copy and Swap） 技术，这种技术可以减少重复代码并提高异常安全性。
  • 使用 传值（pass-by-value）参数，配合 swap 函数，使代码简洁高效，且异常安全。
实现代码：
namespace W {
    template<class T>
    class vector {
    public:
        //这里可以服用reserve和push_back函数了
        vector(const vector<T>& v)
            : _start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
        {
            reserve(v.size());  // 分配所需空间
            for (const T& elem : v) {
                push_back(elem);  // 拷贝每个元素
            }
        }

        // 赋值操作符，使用拷贝并交换技术
        vector<T>& operator=(vector<T> v) {
            swap(v);  // 调用 swap 函数交换内容
            return *this;
        }

        // swap 函数
        void swap(vector<T>& v) {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_endOfStorage, v._endOfStorage);
        }

        // 其他成员函数同之前实现...

    private:
        T* _start;
        T* _finish;
        T* _endOfStorage;
    };
}
现代写法说明
  • 传值参数：通过传递 vector<T> 的值作为参数，创建一个临时对象 v。调用拷贝构造函数时自动执行拷贝，然后在赋值操作中与现有对象交换内容。传值是安全的，避免了手动内存管理问题。
  • swap：通过交换数据成员 _start、_finish 和 _endOfStorage，避免手动内存释放，简化代码逻辑。交换后的临时对象 v 离开作用域时自动销毁，保证资源释放。
测试用例：
void TestCopyAndAssignVector() {
    // 测试拷贝构造函数
    W::vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);

    W::vector<int> v2(v1);  // 使用拷贝构造函数
    for (size_t i = 0; i < v2.size(); ++i) {
        assert(v2[i] == v1[i]);  // 验证每个元素是否相同
    }

    // 测试赋值操作符
    W::vector<int> v3;
    v3 = v1;  // 使用赋值操作符
    for (size_t i = 0; i < v3.size(); ++i) {
        assert(v3[i] == v1[i]);  // 验证每个元素是否相同
    }

    std::cout << "TestCopyAndAssignVector passed" << std::endl;
}
输出：
TestCopyAndAssignVector passed

5.4 优点总结

  • 简化代码：通过传值和 swap，避免了重复的深拷贝代码。
  • 异常安全性：无论是在构造过程中出现异常，还是在赋值操作中，资源都可以安全地释放，避免内存泄漏。
  • 效率：现代 C++ 的传值优化会确保性能不会显著下降，并且在支持移动语义的场景下，效率非常高。

写在最后

至此，我们完成了 vector 的从零实现，并深入分析了其中的每个细节，包括动态内存管理、迭代器操作、容量管理、拷贝构造与赋值重载等。通过这次实现，我们可以更清晰地理解标准库中的 vector 是如何通过高效的内存分配、深拷贝与异常安全机制来确保性能和安全的。


在实际开发中，理解这些细节不仅能够帮助我们更好地使用 vector，也为日后设计自己的容器类打下了坚实的基础。希望通过这个过程，读者能够更深刻地感受到 C++ 的强大与精妙。


💬 欢迎讨论：本文对 vector 容器的实现进行了细致的分析与讲解，如果你在学习过程中遇到问题或有任何建议，欢迎在评论区与我交流。期待与你一起探讨更多相关知识！


👍 支持一下：如果你觉得这篇文章对你有帮助，请点赞、收藏并分享给更多朋友！你们的支持是我创作的最大动力！


以上就是关于【C++篇】从零实现 C++ Vector：深度剖析 STL 的核心机制与优化的内容啦，然后各位大佬有什么问题欢迎在评论区指正，或者私信我也是可以的啦，您的支持是我创作的最大动力！❤️

文章标签：
C++
测试技术
安全
容器
关键词：
C++机制
C++ vector
C++ stl
C++ vector机制
C++ vector stl
Hoshiᅟᅠ
目录
相关文章
ephemerals__
|
10天前
|
存储 安全 编译器
【c++】深入理解别名机制--引用
本文介绍了C++中的引用概念及其定义、特性、实用性和与指针的区别。引用是C++中的一种别名机制，通过引用可以实现类似于指针的功能，但更安全、简洁。文章详细解释了引用的定义方式、引用传参和返回值的应用场景，以及常引用的使用方法。最后，对比了引用和指针的异同，强调了引用在编程中的重要性和优势。
ephemerals__
26 1
Svan.
|
1月前
|
存储 程序员 C++
C++常用基础知识—STL库(2)
C++常用基础知识—STL库(2)
Svan.
68 5
白子寰
|
30天前
|
存储 C++ 索引
【C++打怪之路Lv9】-- vector
【C++打怪之路Lv9】-- vector
白子寰
20 1
Svan.
|
1月前
|
存储 自然语言处理 程序员
C++常用基础知识—STL库(1)
C++常用基础知识—STL库(1)
Svan.
52 1
努力学习的小廉
|
1月前
|
编译器 C++
【C++】—— vector模拟实现
【C++】—— vector模拟实现
努力学习的小廉
32 1
蓝易云
|
1月前
|
算法 数据处理 C++
c++ STL划分算法；partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具，能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景，将有助于编写更加高效和清晰的C++代码。
蓝易云
22 0
禁默
|
1月前
|
算法 C++ 容器
C++之打造my vector篇（下）
C++之打造my vector篇（下）
禁默
26 0
禁默
|
1月前
|
存储 编译器 C++
C++之打造my vector篇（上）
C++之打造my vector篇（上）
禁默
25 0
ephemerals__
|
6天前
|
存储 编译器 C++
【c++】类和对象（中）（构造函数、析构函数、拷贝构造、赋值重载）
本文深入探讨了C++类的默认成员函数，包括构造函数、析构函数、拷贝构造函数和赋值重载。构造函数用于对象的初始化，析构函数用于对象销毁时的资源清理，拷贝构造函数用于对象的拷贝，赋值重载用于已存在对象的赋值。文章详细介绍了每个函数的特点、使用方法及注意事项，并提供了代码示例。这些默认成员函数确保了资源的正确管理和对象状态的维护。
ephemerals__
29 4
ephemerals__
|
7天前
|
存储 编译器 Linux
【c++】类和对象（上）（类的定义格式、访问限定符、类域、类的实例化、对象的内存大小、this指针）
本文介绍了C++中的类和对象，包括类的概念、定义格式、访问限定符、类域、对象的创建及内存大小、以及this指针。通过示例代码详细解释了类的定义、成员函数和成员变量的作用，以及如何使用访问限定符控制成员的访问权限。此外，还讨论了对象的内存分配规则和this指针的使用场景，帮助读者深入理解面向对象编程的核心概念。
ephemerals__
25 4