当前位置:首页 » 《关注互联网》 » 正文

【C++篇】深入剖析C++ Vector底层源码及实现机制

9 人参与  2024年12月08日 16:01  分类 : 《关注互联网》  评论

点击全文阅读


文章目录

须知

? 欢迎讨论:如果你在学习过程中有任何问题或想法,欢迎在评论区留言,我们一起交流学习。你的支持是我继续创作的动力!

? 点赞、收藏与分享:觉得这篇文章对你有帮助吗?别忘了点赞、收藏并分享给更多的小伙伴哦!你们的支持是我不断进步的动力!
? 分享给更多人:如果你觉得这篇文章对你有帮助,欢迎分享给更多对C++感兴趣的朋友,让我们一起进步!

 全面剖析vector底层及实现机制

接上篇:【C++篇】探索STL之美:vector容器讲解_c++vector容器-CSDN博客

前言

 Vector是C++标准模板库(STL)中提供的一种动态数组容器,能够高效管理元素的存储与操作。它具有自动扩容的特性,即在存储空间不足时会自动分配更大的内存,保证连续存储的同时提高了灵活性。Vector支持随机访问,拥有接近数组的访问速度,同时也提供了丰富的成员函数用于插入、删除、排序等操作,兼顾了灵活性与性能。

总之,Vector是C++开发中最常用的容器之一,因其高效、灵活、易用的特性,在处理动态数据时显得尤为重要。

1. 基本结构与初始化(具有不同种方式)

1.1 基本结构

Vector底层实现类似于动态数组,其内部通过一块连续的内存空间存储元素。主要成员包括:

指针数据(_start, _end, _end_of_storage):分别指向当前元素的起始地址、末尾地址和存储空间的尾地址,用于跟踪已存储的元素和剩余空间。动态扩容:当插入新元素超出当前容量时,Vector会申请更大的连续内存空间,并将现有元素复制到新空间中。扩容一般是以一定倍数增长(通常为2倍)。

1.2 带大小和默认值初始化构造函数

初始化一个给定大小的vector,并使用默认值填充。测试构造后大小、容量是否符合要求。
namespace W {    template<class T>    class vector {    public:        typedef T* iterator;        vector(size_t n, const T& value = T()) {            _start = new T[n];            _finish = _start + n;            _endOfStorage = _finish;            for (size_t i = 0; i < n; ++i) {                _start[i] = value;  // 填充默认值            }        }        size_t size() const { return _finish - _start; }        size_t capacity() const { return _endOfStorage - _start; }        bool empty() const { return _start == _finish; }        T& operator[](size_t pos) { return _start[pos]; }        ~vector(){if (_start){delete[] _start;_start = _finish = _endOfStorage = nullptr;}}    private:        iterator _start;        iterator _finish;        iterator _endOfStorage;    };}

测试用例:

void TestInitVector() {    W::vector<int> v(5, 10);    assert(v.size() == 5);  // 验证大小    assert(v.capacity() == 5);  // 验证容量    assert(!v.empty());  // 验证非空    for (size_t i = 0; i < 5; ++i) {        assert(v[i] == 10);  // 验证默认值    }    std::cout << "TestInitVector passed" << std::endl;}

1.3 拷贝构造函数

实现vector的拷贝构造函数。测试拷贝后的vector是否完全复制原来的内容和容量。

实现代码:

namespace W {    template<class T>    class vector {    public:        typedef T* iterator;        vector(const vector<T>& v) {            size_t n = v.size();            _start = new T[n];            _finish = _start + n;            _endOfStorage = _finish;            for (size_t i = 0; i < n; ++i) {                _start[i] = v._start[i];  // 复制数据            }        }        size_t size() const { return _finish - _start; }        size_t capacity() const { return _endOfStorage - _start; }        bool empty() const { return _start == _finish; }        T& operator[](size_t pos) { return _start[pos]; }        ~vector(){if (_start){delete[] _start;_start = _finish = _endOfStorage = nullptr;}}    private:        iterator _start;        iterator _finish;        iterator _endOfStorage;    };}

测试用例:

void TestCopyVector() {    W::vector<int> v1(10, 20);    W::vector<int> v2(v1);    assert(v2.size() == 10);  // 验证大小    assert(v2.capacity() == 10);  // 验证容量    for (size_t i = 0; i < 10; ++i) {        assert(v2[i] == 20);  // 验证数据拷贝    }    std::cout << "TestCopyVector passed" << std::endl;}

1.4 赋值操作符重载

实现赋值操作符重载。测试两个vector赋值后,是否正确拷贝了内容和容量。
namespace W {    template<class T>    class vector {    public:        typedef T* iterator;        vector<T>& operator=(const vector<T>& v) {            if (this != &v) {                delete[] _start;  // 释放旧的空间                size_t n = v.size();                _start = new T[n];                _finish = _start + n;                _endOfStorage = _finish;                for (size_t i = 0; i < n; ++i) {                    _start[i] = v._start[i];  // 复制数据                }            }            return *this;        }        size_t size() const { return _finish - _start; }        size_t capacity() const { return _endOfStorage - _start; }        bool empty() const { return _start == _finish; }        T& operator[](size_t pos) { return _start[pos]; }       ~vector(){if (_start){delete[] _start;_start = _finish = _endOfStorage = nullptr;}}    private:        iterator _start;        iterator _finish;        iterator _endOfStorage;    };}

测试用例:

void TestAssignVector() {    W::vector<int> v1(15, 30);    W::vector<int> v2 = v1;  // 赋值操作    assert(v2.size() == 15);  // 验证大小    assert(v2.capacity() == 15);  // 验证容量    for (size_t i = 0; i < 15; ++i) {        assert(v2[i] == 30);  // 验证数据拷贝    }    std::cout << "TestAssignVector passed" << std::endl;}

2. 容器管理内存的实现与测试

2.1 reserve函数:动态扩容

实现代码:

namespace W {    template<class T>    class vector {    public:        void reserve(size_t n) {            if (n > capacity()) {                size_t oldSize = size();                T* tmp = new T[n];                for (size_t i = 0; i < oldSize; ++i) {                    tmp[i] = _start[i];                }                delete[] _start;                _start = tmp;                _finish = _start + oldSize;                _endOfStorage = _start + n;            }        }    };}

测试用例:

void TestReserveVector() {    W::vector<int> v(5, 10);    v.reserve(10);  // 预留容量    assert(v.capacity() == 10);  // 验证容量扩展    for (size_t i = 0; i < 5; ++i) {        assert(v[i] == 10);  // 验证数据保持不变    }    std::cout << "TestReserveVector passed" << std::endl;}

输出

TestReserveVector passed

 2.2 resize函数:改变大小

用途

1. 增加容器大小

当新的大小大于当前大小时,resize会在容器末尾添加新元素,新添加的元素会被默认值初始化(对于内置类型,默认值通常为0或空值)。

std::vector<int> vec = {1, 2, 3};
vec.resize(5); // vec变为 {1, 2, 3, 0, 0}

2. 减少容器大小
当新的大小小于当前大小时,resize会移除多余的元素,只保留从起始位置算起的新大小的元素。

std::vector<int> vec = {1, 2, 3, 4, 5};
vec.resize(3); // vec变为 {1, 2, 3} 

 3.指定新元素的初始值
在扩容时,可以通过第二个参数指定新添加元素的初始值,而不是使用默认值。

std::vector<int> vec = {1, 2, 3};
vec.resize(5, 10); // vec变为 {1, 2, 3, 10, 10}

特点

不会影响容量(capacity)resize只调整size(实际元素数量),不会改变容器的容量(底层分配的内存大小)。扩容时容量可能会增长,但缩小时容量不会减少。元素保留特性:缩小时多余的元素会被移除,但未移除的元素保持不变;扩容时已存在的元素同样不受影响。性能resize可能引起新元素的构造或旧元素的析构,因此需要注意其性能开销。
namespace W {    template<class T>    class vector {    public:        void resize(size_t n, const T& value = T()) {            if (n < size()) {                _finish = _start + n;  // 缩小大小            } else {                reserve(n);                for (iterator it = _finish; it != _start + n; ++it)    {                    *it = value;  // 填充新值                }                _finish = _start + n;            }        }    };}

测试用例:

void TestResizeVector() {    W::vector<int> v(5, 10);    v.resize(8, 20);  // 扩展大小并填充新值    assert(v.size() == 8);  // 验证扩展后大小    for (size_t i = 0; i < 5; ++i) {        assert(v[i] == 10);  // 验证原值不变    }    for (size_t i = 5; i < 8; ++i) {        assert(v[i] == 20);  // 验证新值    }    std::cout << "TestResizeVector passed" << std::endl;}

3. 增加与删除元素

3.1 push_back函数:向vector末尾插入元素

3.1.1 实现思路

检查容量是否足够,若不足则扩容(通常容量加倍)。将新元素插入到当前末尾。更新_finish指针,指向新的末尾。

示例代码:

namespace W {    template<class T>    class vector {    public:        void push_back(const T& x) {            // 如果空间不足,扩展容量为当前容量的两倍            if (_finish == _endOfStorage) {                size_t newCapacity = capacity() == 0 ? 1 : capacity() * 2;                reserve(newCapacity);            }            // 在末尾插入新元素            *_finish = x;            ++_finish;        }    private:        T* _start;        T* _finish;        T* _endOfStorage;    };}

 测试用例:

void TestPushBackVector() {    W::vector<int> v;    v.push_back(1);    v.push_back(2);    v.push_back(3);    assert(v.size() == 3);  // 验证插入后的大小    assert(v.capacity() >= 3);  // 验证容量是否自动扩容    assert(v[0] == 1 && v[1] == 2 && v[2] == 3);  // 验证插入的元素是否正确    std::cout << "TestPushBackVector passed" << std::endl;}

输出:

TestPushBackVector passed

 3.2 pop_back函数:删除末尾元素

 将_finish指针向后移动移动一位,即该指针指向的就是最后一个元素

示例代码:

namespace W {    template<class T>    class vector {    public:        void pop_back() {            assert(_finish != _start);  // 确保vector非空            --_finish;  // 逻辑删除最后一个元素        }    private:        T* _start;        T* _finish;        T* _endOfStorage;    };}

3.3 insert:在指定位置插入数据

实现思路

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;    };}

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

实现思路

1 循环将指定位置数据的后面每一位向前挪动

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;    };}

4. 查找元素

4.1 front函数:返回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函数:获取最后一个元素

实现代码:

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;}

 5. 迭代器的实现

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;}

输出:

10   20   30

 6. swap函数:交换两个vector

用途:

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;}

输出:

3 4 
1 2 

 7. 赋值运算符重载:深拷贝vector

 现代技术:拷贝并交换(Copy and 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;    };}

测试用例:

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;}

现代写法解释 :

传值参数:通过传递 vector<T> 的值作为参数,创建一个临时对象 v。调用拷贝构造函数时自动执行拷贝,然后在赋值操作中与现有对象交换内容。传值是安全的,避免了手动内存管理问题。
swap:通过交换数据成员 _start、_finish 和 _endOfStorage,避免手动内存释放,简化代码逻辑。交换后的临时对象 v 离开作用域时自动销毁,保证资源释放。


 8. vector容器特性总结

1. 动态大小

可以根据需要动态调整大小,而无需预定义固定容量,避免内存浪费。

自动处理底层内存分配和扩展。

2. 随机访问性能优秀

支持常数时间的随机访问,类似于数组,便于快速读取和修改元素。

3. 便捷的插入和删除操作

支持尾部插入/删除操作,时间复杂度为O(1)。

通过eraseinsert等方法,支持中间位置的元素操作,虽然复杂度为O(n),但提供了便利。

4. 内存管理

自动管理底层内存,不需要开发者手动分配或释放内存,减少内存泄漏的风险。

5. 支持迭代器

提供灵活的迭代器支持,可以轻松遍历、修改元素,并与其他STL算法结合使用。

6. 多功能性

可以存储不同类型的对象,包括用户定义类型。

提供了丰富的操作函数,例如排序、搜索等。

7. 与C++标准库兼容性高

与标准库中的其他容器(如mapset)和算法无缝集成,形成强大的工具组合。

8. 性能优化

在扩容时,底层内存分配采用指数增长策略(通常为两倍),减少了频繁的重新分配操作

这些特点使vector在需要灵活、动态数组的场景中非常实用,例如处理未知大小的输入数据或需要高效随机访问的场景。

 

相信通过这篇文章你对C++STL->vector的使用高级部分的有了初步的了解。如果此篇文章对你学习C++有帮助,期待你的三连,你的支持就是我创作的动力!!!

下一篇文章再会.


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/198178.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1