【十三】【C++】vector简单实现

代码实现

/*vector类简单实现*/
#if 1
#define _CRT_SECURE_NO_WARNINGS
 #include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <crtdbg.h>
#include <assert.h>
#include <string.h>

namespace MyVector {
    template<class T>
    class vector {
    public:
        typedef T* itertor;
        
     public:
        vector()
        : _start(nullptr)
        , _finish(nullptr)
        , _endofstorage(nullptr)
        {}
        
         vector(int n, const T& val = T())
        : _start(new T[n]) {
            //memset(_start, val, sizeof(T)*n);
            for (int i = 0; i < n; ++i) {
                _start[i] = val;
            }
            
             _finish = _start + n;
            _endofstorage = _finish;
        }
        
         template<class Iterator>
        vector(Iterator first, Iterator last) {
            // size_t n = last - first;  //注意：一定不能减
            Iterator it = first;
            size_t n = 0;
            while (it != last) {
                n++;
                ++it;
            }
            
             _start = new T[n];
            _finish = _start;
            while (first != last) {
                *_finish++ = *first++;
                // _finish++;
                // first++;
            }
            _endofstorage = _finish;
        }
        
         vector(const vector<T>& v)
        : _start(new T[v.size()]) {
            size_t n = v.size();
            for (size_t i = 0; i < n; ++i) {
                _start[i] = v[i];
            }
            
             _finish = _start + n;
            _endofstorage = _finish;
        }
        
         vector<T>& operator=(vector<T> v) {
            swap(v);
            return *this;
        }
        
         ~vector() {
            if (_start) {
                delete[] _start;
                _start = _finish = _endofstorage = nullptr;
            }
        }
        
         /
        // 迭代器
        itertor begin() {
            return _start;
        }
        
         itertor end() {
            return _finish;
        }
        
         itertor rbegin() {
            return end();
        }
        
         itertor rend() {
            return begin();
        }
        
         
        // 容量
        size_t size()const {
            return _finish - _start;
        }
        
         size_t capacity()const {
            return _endofstorage - _start;
        }
        
         bool empty()const {
            return _start == _finish;
        }
        
         void resize(size_t newsize, const T& val = T()) {
            size_t oldsize = size();
            if (newsize > oldsize) {
                size_t oldcap = capacity();
                if (newsize > oldcap)
                    reserve(newsize);
                
                 for (size_t i = oldsize; i < newsize; ++i) {
                    _start[i] = val;
                }
            }
            
             _finish = _start + newsize;
        }
        
         void reserve(size_t newcap) {
            size_t oldcap = capacity();
            size_t count = size();
            if (newcap > oldcap) {
                // 1. 申请新空间
                T* temp = new T[newcap];
                
                 if (_start) {
                    // 2. 拷贝元素
                    // 浅拷贝
                    // memcpy(temp, _start, sizeof(T)*count);
                    
                     for (size_t i = 0; i < count; ++i) {
                        temp[i] = _start[i];
                    }
                    
                     // 3. 释放旧空间
                    delete[] _start;
                }
                
                 _start = temp;
                _finish = _start + count;
                _endofstorage = _start + newcap;
            }
        }
        
         
        // 元素访问
        T& front() {
            // return *begin();
            return _start[0];
        }
        
         const T& front()const {
            return _start[0];
        }
        
         T& back() {
            return *(_finish - 1);
        }
        
         const T& back()const {
            return *(_finish - 1);
        }
        
         T& operator[](size_t index) {
            assert(index < size());
            return _start[index];
        }
        
         const T& operator[](size_t index)const {
            assert(index < size());
            return _start[index];
        }
        
         //
        // 修改
        void push_back(const T& value) {
            if (_finish == _endofstorage) {
                reserve(size() * 2 + 3);
            }
            
             *_finish = value;
            ++_finish;
        }
        
         void pop_back() {
            if (empty())
                return;
            
             --_finish;
        }
        
         itertor insert(itertor pos, const T& value) {
            if (pos < _start || pos > _finish)
                return end();
            
             if (_finish == _endofstorage)
                reserve(2 * size());
            
             // 将pos及其后续所有的元素整体往后搬移
            itertor it = _finish;
            while (it != pos) {
                *it = *(it - 1);
                --it;
            }
            
             *pos = value;
            ++_finish;
            return pos;
        }
        
         itertor erase(itertor pos) {
            if (pos < _start || pos >= _finish)
                return end();
            
             itertor it = pos + 1;
            while (it != _finish) {
                *(it - 1) = *it;
                ++it;
            }
            
             --_finish;
            return pos;
        }
        
         void clear() {
            _finish = _start;
        }
        
         void swap(vector<T>& v) {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_endofstorage, v._endofstorage);
        }
        //vector成员变量
    private:
        itertor _start;
        itertor _finish;
        itertor _endofstorage;
    };
 }


void TestVector1() {
    MyVector::vector<int> v1;
    
     // int  int
    MyVector::vector<int> v2(10, 5);
    for (size_t i = 0; i < v2.size(); ++i)
        cout << v2[i] << " ";
    cout << endl;
    
     int array[] = { 1, 2, 3, 4, 5 };
    MyVector::vector<int> v3(array, array + 3);
    for (auto e : v3)
        cout << e << " ";
    cout << endl;
    
     MyVector::vector<int> v4(v3);
    auto it = v4.begin();
    while (it != v4.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
 }


void TestVector4() {
    MyVector::vector<int> v(10, 5);
    for (auto e : v)
        cout << e << " ";
    cout << endl;
    cout << "size=" << v.size() << endl;
    cout << "capacity=" << v.capacity() << endl;
    
     v.resize(20, 8);
    for (auto e : v)
        cout << e << " ";
    cout << endl;
    cout << "size=" << v.size() << endl;
    cout << "capacity=" << v.capacity() << endl;
    
     v.resize(30, 6);
    for (auto e : v)
        cout << e << " ";
    cout << endl;
    cout << "size=" << v.size() << endl;
    cout << "capacity=" << v.capacity() << endl;
    
     v.resize(10);
    for (auto e : v)
        cout << e << " ";
    cout << endl;
    cout << "size=" << v.size() << endl;
    cout << "capacity=" << v.capacity() << endl;
    
     v.resize(15, 0);
    for (auto e : v)
        cout << e << " ";
    cout << endl;
    cout << "size=" << v.size() << endl;
    cout << "capacity=" << v.capacity() << endl;
 }

void TestVector2() {
    MyVector::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    
     cout << v.size() << endl;
    cout << v.capacity() << endl;
    
     for (auto e : v)
        cout << e << " ";
    cout << endl;
    
     v.push_back(4);
    cout << v.size() << endl;
    cout << v.capacity() << endl;
    
     for (auto e : v)
        cout << e << " ";
    cout << endl;
    
     cout << v.front() << endl;
    cout << v.back() << endl;
    
     v.pop_back();
    cout << v.front() << endl;
    cout << v.back() << endl;
 }

void TestVector3() {
    MyVector::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(6);
    
     for (auto e : v)
        cout << e << " ";
    cout << endl;
    
     v.insert(v.begin(), 0);
    for (auto e : v)
        cout << e << " ";
    cout << endl;
    
     v.insert(v.begin() + 2, 22);
    
     for (auto e : v)
        cout << e << " ";
    cout << endl;
    
     auto it = v.begin();
    while (it != v.end()) {
        it = v.erase(it);
        ++it;
    }
 }

#include <list>

class String {
public:
    String(const char* str = "") {
        if (nullptr == str)
            str = "";
        
         _str = new char[strlen(str) + 1];
        strcpy(_str, str);
    }
    
     String(const String& s)
    : _str(new char[strlen(s._str) + 1]) {
        strcpy(_str, s._str);
    }
    
     String& operator=(const String& s) {
        if (this != &s) {
            char* temp = new char[strlen(s._str) + 1];
            strcpy(temp, s._str);
            delete[] _str;
            _str = temp;
        }
        
         return *this;
    }
    
     ~String() {
        if (_str) {
            delete[] _str;
            _str = nullptr;
        }
    }
private:
    char* _str;
 };


void Teststdvector() {
    vector<String> v;
    v.push_back("1111");
    v.push_back("1111");
    v.push_back("2222");
    v.push_back("3333");
 }

void TestMyvector() {
    MyVector::vector<String> v;
    v.push_back("1111");
    v.push_back("2222");
    v.push_back("3333");
    v.push_back("4444");
 }

int main() {
    //int array[10];
    //memset(array, 5, sizeof(array));
    
     /*int array[] = { 1, 2, 3, 4 };
    vector<int> v1(array, array + sizeof(array) / sizeof(array[0]));
    
     list<int> L{ 1, 2, 3 };
    vector<int> v2(L.begin(), L.end());*/
    
     // TestVector1();
    // TestVector2();
    // TestVector3();
    // TestVector4();
    // Teststdvector();
    Testvector();
    _CrtDumpMemoryLeaks();
    return 0;
 }
#endif

这段代码是一个简化版的 vector 类的实现，模拟了 C++ 标准库中 std::vector 的核心功能。vector 是一个模板类，用于存储元素的动态数组，可以根据需要动态地增加或减少其大小。下面是对代码中每个部分的简要解释：

类模板声明

template<class T>
class vector {

这里定义了一个模板类 vector，T 是元素类型的占位符，允许 vector 存储任意类型的元素。

成员变量

typedef T* itertor;
itertor _start; // 指向数组首元素的指针
itertor _finish; // 指向数组最后一个元素的下一个位置的指针
itertor _endofstorage; // 指向数组分配的存储空间尾部的下一个位置的指针

vector内的迭代器底层是T类型的指针类型。

_start相当于string类的字符指针。

_finish相当于string类的size。

_endofstorage相当于string类的capacity。

构造函数

默认构造函数、带参数的构造函数、范围构造函数、拷贝构造函数和析构函数用于初始化 vector 实例和清理资源。

范围构造函数特别注意不直接使用迭代器相减来确定元素数量，以支持不支持随机访问的迭代器。

默认构造函数

vector()
: _start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}

所有的指针都指向空。

带参数的构造函数

 vector(int n, const T& val = T())
: _start(new T[n]) {
    for (int i = 0; i < n; ++i) {
        _start[i] = val;
    }
    
     _finish = _start + n;
    _endofstorage = _finish;
}

使用默认的构造器给_start开辟空间，再依次赋值为val，接着修正_finish和_endofstorage。

可以理解为，_start相当于string类的字符指针。

_finish相当于string类的size。

_endofstorage相当于string类的capacity。

范围构造函数

 template<class Iterator>
vector(Iterator first, Iterator last) {
    // size_t n = last - first;  //注意：一定不能减
    Iterator it = first;
    size_t n = 0;
    while (it != last) {
        n++;
        ++it;
    }
    
     _start = new T[n];
    _finish = _start;
    while (first != last) {
        *_finish++ = *first++;
        // _finish++;
        // first++;
    }
    _endofstorage = _finish;
}

注意，对于 vector 的构造函数，使用了模板来允许接受任意类型的迭代器 Iterator 作为参数。这里不支持迭代器相减计算距离，原因是并不是所有的迭代器类型都支持相减计算距离。

随机访问迭代器（Random Access Iterator）：支持直接相减操作，因为它们可以在常数时间内访问序列中的任何元素。vector 和 deque 容器提供的迭代器就是随机访问迭代器。

双向迭代器（Bidirectional Iterator）、前向迭代器（Forward Iterator）、输入迭代器（Input Iterator） 和 输出迭代器（Output Iterator）：不支持相减操作，因为它们只能单向移动（或者在双向迭代器的情况下，前后移动），无法直接计算两个迭代器之间的距离。

根据迭代器范围来构造对象，首先计算迭代器范围内有多少个元素，计算的方法是迭代器依次++。计算好元素个数之后先开辟对应的空间大小。接着通过迭代器依次赋值。修正_finish和_endofstorage。

拷贝构造函数

 vector(const vector<T>& v)
: _start(new T[v.size()]) {
    size_t n = v.size();
    for (size_t i = 0; i < n; ++i) {
        _start[i] = v[i];
    }
    
     _finish = _start + n;
    _endofstorage = _finish;
}

std::vector<int> vec6(vec4)括号里面传入的是vector类型，属于拷贝构造函数。如上述代码所示，利用vec4构造vec6对象。此时vec6对象元素的数据类型是int类型，这个int类型就是上面代码的T类型，当然，和vec4里面的数据类型是相同的。

析构函数

 ~vector() {
    if (_start) {
        delete[] _start;
        _start = _finish = _endofstorage = nullptr;
    }
}

赋值操作符

vector<T>& operator=(vector<T> v) {
    swap(v);
    return *this;
}

通过拷贝-交换技巧实现赋值操作符，确保异常安全和自赋值安全。swap函数是vector类内部定义的函数。

迭代器相关方法

提供 begin() 和 end() 方法返回指向首元素和尾后位置的迭代器。

rbegin() 和 rend() 方法在此实现中不是反向迭代器的正确实现，它们只是简单地返回了 end() 和 begin()。

// 迭代器
itertor begin() {
    return _start;
}

 itertor end() {
    return _finish;
}

 itertor rbegin() {
    return end();
}

 itertor rend() {
    return begin();
}

end()函数返回的是_finish迭代器，_finish迭代器指向最后一个元素的下一个位置。

容量相关方法

size(), capacity(), empty(), resize(), reserve() 方法用于查询和修改 vector 的大小和容量。

// 容量
size_t size()const {
    return _finish - _start;
}

 size_t capacity()const {
    return _endofstorage - _start;
}

 bool empty()const {
    return _start == _finish;
}

随机访问迭代器（Random Access Iterator）：支持直接相减操作，因为它们可以在常数时间内访问序列中的任何元素。vector 和 deque 容器提供的迭代器就是随机访问迭代器。

因此在vector内部可以直接对指针进行相减操作，计算出来的就是指针之间的元素个数。

 void resize(size_t newsize, const T& val = T()) {
    size_t oldsize = size();
    if (newsize > oldsize) {
        size_t oldcap = capacity();
        if (newsize > oldcap)
            reserve(newsize);
        
         for (size_t i = oldsize; i < newsize; ++i) {
            _start[i] = val;
        }
    }
    
     _finish = _start + newsize;
}

计算当前大小：首先通过 size() 方法获取当前容器中元素的数量。

比较新旧大小：

如果 newsize 大于 oldsize（当前容器的大小），则需要扩展容器。

如果 newsize 小于或等于 oldsize，代码当前版本中没有显式处理这种情况，实际上通过设置 _finish = _start + newsize; 来减少容器的大小，多余的元素虽在逻辑上被“丢弃”，但它们并没有被销毁。

扩展容器（如果需要）：

首先检查是否需要扩展底层存储空间，即 newsize 是否大于当前容器的容量（oldcap）。如果是，调用 reserve(newsize) 来分配更大的存储空间。

然后，使用循环从 oldsize 开始，直到 newsize 结束，为新添加的位置赋予 val 值。这确保了扩展部分的元素被初始化。

更新 _finish：最后，无论容器是被扩展还是缩小，都通过设置 _finish = _start + newsize; 来更新指向容器中最后一个有效元素之后位置的指针。这样，容器的大小被改变为 newsize。


 void reserve(size_t newcap) {
    size_t oldcap = capacity();
    size_t count = size();
    if (newcap > oldcap) {
        // 1. 申请新空间
        T* temp = new T[newcap];
        
         if (_start) {
            // 2. 拷贝元素
            // 浅拷贝
            // memcpy(temp, _start, sizeof(T)*count);
            
             for (size_t i = 0; i < count; ++i) {
                temp[i] = _start[i];
            }
            
             // 3. 释放旧空间
            delete[] _start;
        }
        
         _start = temp;
        _finish = _start + count;
        _endofstorage = _start + newcap;
    }
}

这段代码是 vector 类中 reserve 方法的实现，它的主要目的是确保 vector 拥有至少 newcap 个元素的容量。如果当前容量小于请求的新容量，则会分配更大的存储空间并移动现有元素到新空间。

获取当前容量和元素数量：

oldcap 存储当前容量，通过 capacity() 方法获取。

count 存储当前元素的数量，通过 size() 方法获取。

检查是否需要扩容：

如果 newcap 大于 oldcap，则需要进行扩容。如果不是，什么都不做，即函数直接返回，保持现状。

申请新空间：

使用 new T[newcap] 申请一个新的元素数组，大小为请求的新容量 newcap。

拷贝现有元素到新空间：

如果 _start 不是 nullptr（即当前容器非空），则需要将现有元素从旧空间复制到新空间。

使用循环遍历当前所有元素，对每个元素使用拷贝赋值操作进行复制。这里的复制保证了如果类型 T 有特殊的拷贝语义（例如深拷贝需要的操作），那么这些语义会被正确处理。

注释中提到的“浅拷贝”和 memcpy 是不正确的选择。对于类类型 T，应使用循环拷贝来确保正确的语义。

释放旧空间：

使用 delete[] _start 释放原有的存储空间。

更新内部指针以反映新状态：

_start 更新为指向新分配的存储空间的开始。

_finish 更新为新空间中最后一个元素之后的位置，即 _start + count。

_endofstorage 更新为新空间的末尾，即 _start + newcap。

元素访问方法

front(), back(), operator[] 提供对 vector 元素的访问。

// 元素访问
T& front() {
    // return *begin();
    return _start[0];
}

 const T& front()const {
    return _start[0];
}

 T& back() {
    return *(_finish - 1);
}

 const T& back()const {
    return *(_finish - 1);
}

 T& operator[](size_t index) {
    assert(index < size());
    return _start[index];
}

 const T& operator[](size_t index)const {
    assert(index < size());
    return _start[index];
}

修改方法

包括 push_back(), pop_back(), insert(), erase(), clear() 等方法，用于修改 vector 的内容。

swap() 方法用于交换两个 vector 实例的内容。

// 修改
void push_back(const T& value) {
    if (_finish == _endofstorage) {
        reserve(size() * 2 + 3);
    }
    
     *_finish = value;
    ++_finish;
}

 void pop_back() {
    if (empty())
        return;
    
     --_finish;
}

 itertor insert(itertor pos, const T& value) {
    if (pos < _start || pos > _finish)
        return end();
    
     if (_finish == _endofstorage)
        reserve(2 * size());
    
     // 将pos及其后续所有的元素整体往后搬移
    itertor it = _finish;
    while (it != pos) {
        *it = *(it - 1);
        --it;
    }
    
     *pos = value;
    ++_finish;
    return pos;
}

 itertor erase(itertor pos) {
    if (pos < _start || pos >= _finish)
        return end();
    
     itertor it = pos + 1;
    while (it != _finish) {
        *(it - 1) = *it;
        ++it;
    }
    
     --_finish;
    return pos;
}

 void clear() {
    _finish = _start;
}

 void swap(vector<T>& v) {
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_endofstorage, v._endofstorage);
}

push_back：

向 vector 的末尾添加一个新元素。如果当前没有足够的存储空间（即 _finish == _endofstorage），则通过调用 reserve 来扩展容量，保证有足够的空间存储新元素。新元素被复制到 _finish 指向的位置，然后 _finish 自增以指向新的末尾。

pop_back：

从 vector 的末尾移除一个元素。这是通过简单地将 _finish 指针递减实现的。如果 vector 为空（即 _start == _finish），则不执行任何操作。

insert：

在指定位置 pos 前面插入一个新元素。首先检查 pos 是否在合法范围内。如果容量不足以插入新元素，则通过调用 reserve 扩展容量。然后，从 vector 的末尾开始，将元素向后移动一位，直到达到插入位置，最后在 pos 位置放入新元素并更新 _finish。

erase：

从 vector 中移除位于 pos 的元素。该操作通过将从 pos + 1 开始的所有元素向前移动一位来实现，并递减 _finish 指针。如果 pos 不在合法范围内，函数返回 end()，即 _finish。

clear：

清空 vector 中的所有元素，实现上通过将 _finish 设置为 _start 实现，逻辑上移除所有元素。这不会释放已分配的内存。

swap：

交换当前 vector 与另一个 vector 的内容。这是通过对 _start、_finish 和 _endofstorage 使用 std::swap 函数实现的。这个操作是非常高效的，因为它只涉及指针的交换，而不需要元素的逐个复制或移动。

反向迭代器探究

/*vector反向迭代器探究*/
#if 1
#define _CRT_SECURE_NO_WARNINGS
 #include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <crtdbg.h>

void TestVector14() {
    vector<int> v={1,2,3,4,5};
    auto it=v.rbegin();
    while(it!=v.rend()){
        cout<<*it<<endl;
        it++;
    }
    
     
}
int main() {
    TestVector14();
    return 0;
 }

#endif

反向迭代器中rbegin指向的是最后一个元素后一个位置，但是解引用的时候，它能够输出最后一个元素的位置，我认为这是编译器做出的自动优化，在反向迭代器中，解引用相当于调用迭代器++后的解引用。

针对于自定义类型的解引用

class Date{
private:
    int _year;
    int _month;
    int _day;
public:
    Date()
    :_year(2024)
    ,_month(1)
    ,_day(1)
    {}
    void Show(){
        cout<<_year<<"-"<<_month<<"-"<<_day<<endl;
    }
 };
int main() {
    MyVector::vector<Date>v;
    v.push_back(Date());
    v.push_back(Date());
    v.push_back(Date());
    v.push_back(Date());
    
     auto it=v.begin();
    while(it!=v.end()){
        it->Show();
        it++;
    }
    return 0;
 }
#endif