template<class T>
class vector
{
public:
        typedef T* iterator;

private:
        iterator _start;
        iterator _finish;
        iterator _endofstorage;
};

template<class T>
class vector
{
public:
    typedef T* iterator;              // 普通迭代器類(lèi)型
    typedef const T* const_iterator;  // const迭代器類(lèi)型
    
private:
    iterator _start;         // 指向數(shù)組首元素
    iterator _finish;        // 指向最后一個(gè)元素的下一個(gè)位置
    iterator _endofstorage;  // 指向存儲(chǔ)空間末尾的下一個(gè)位置
};

// 默認(rèn)構(gòu)造函數(shù)
vector()
    :_start(nullptr)
    ,_finish(nullptr)
    ,_endofstorage(nullptr)
{}

// 析構(gòu)函數(shù)
~vector()
{
    delete[] _start;  // 釋放動(dòng)態(tài)分配的內(nèi)存
    _start = _finish = _endofstorage = nullptr;  // 指針置空
}

// 普通正向迭代器
iterator begin() { return _start; }
iterator end() { return _finish; }

// 只讀正向迭代器
const_iterator begin() const { return _start; }
const_iterator end() const { return _finish; }

// 獲取元素?cái)?shù)量
size_t size() const { return _finish - _start; }

// 獲取當(dāng)前容量
size_t capacity() const { return _endofstorage - _start; }

// 擴(kuò)容方法
void reserve(size_t n)
{
    size_t sz = size();  // 提前計(jì)算當(dāng)前大小
    if (n > capacity())
    {
        T* tmp = new T[n];  // 分配新內(nèi)存
        if (_start)  // 防止第一次分配內(nèi)存時(shí) memcpy 出錯(cuò)
        {
            // 這里使用 memcpy 是有問(wèn)題的，只能對(duì)內(nèi)置類(lèi)型
            // 的vector進(jìn)行擴(kuò)容，具體問(wèn)題和解決方案在
            // 后續(xù)“memcpy：更深一層次的深淺拷貝問(wèn)題”
            memcpy(tmp, _start, sizeof(T) * sz);  // 拷貝數(shù)據(jù)
            delete[] _start;  // 釋放舊內(nèi)存
        }
        _start = tmp;
        _finish = tmp + sz;
        _endofstorage = tmp + n;
    }
}

// 下標(biāo)運(yùn)算符重載
T& operator[](size_t i)
{
    assert(i < size());  // 越界檢查
    return _start[i];
}

// const 版本下標(biāo)運(yùn)算符
const T& operator[](size_t i) const
{
    assert(i < size());  // 越界檢查
    return _start[i];
}

/* resize */
// val不能給0，因?yàn)椴恢繲的類(lèi)型，所以給一個(gè)T的缺省值
void resize(size_t n, const T& val = T())
{
        // 縮小size
        if (n < size())
                _finish = _start + n;
        else // 增大size
        {
                // 假如需要擴(kuò)容
                if (n > capacity())
                {
                        reserve(n);
                }

                while (_finish < _start + n)
                {
                        *_finish = val;
                        ++_finish;
                }
        }
}

// 尾插元素
void push_back(const T& x)
{
    // 空間不足時(shí)擴(kuò)容
    if (_finish == _endofstorage)
    {
        size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;
        reserve(newcapacity);
    }
    
    *_finish = x;  // 在末尾位置添加元素
    ++_finish;     // 更新末尾指針
}

// 也可以直接借助insert完成尾插
void push_back(const T& x) { insert(_finish, x); }

// pos位置插入
void insert(iterator pos, const T& x)
{
    assert(pos <= _finish);  // 檢查位置有效性
    
    // 空間不夠就增容
    if (_finish == _endofstorage)
    {
        // 記下pos相對(duì)于_start的位置
        size_t n = pos - _start;
        size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;
        reserve(newcapacity);
        // 空間增容導(dǎo)致原pos迭代器失效，更新迭代器位置
        pos = _start + n;
    }
    
    // 后移元素
    iterator end = _finish - 1;
    while (end >= pos)  // 依次把pos及pos后面的數(shù)據(jù)往后挪1位
    {
        *(end + 1) = *end;
        --end;
    }
    
    *pos = x;    // 插入新元素
    ++_finish;   // 更新末尾指針
}

// 刪除指定位置元素
iterator erase(iterator pos)
{
    assert(pos < _finish);  // 檢查位置有效性
    
    iterator it = pos;
    while (it < _finish)  // 將后續(xù)元素前移
    {
        *it = *(it + 1);
        ++it;
    }
    
    --_finish;  // 更新末尾指針
    return pos;  // 返回刪除后該位置的迭代器
}

// 尾刪
void pop_back() { erase(_finish - 1); }

/* 拷貝構(gòu)造函數(shù) */
vector(const vector<T>& v)
{
        _start = new T[v.capacity()];
        _finish = _start;
        _endofstorage = _start + v.capacity();
        // 拷貝數(shù)據(jù)
        for (size_t i = 0; i < v.size(); ++i)
        {
                *_finish = v[i];
                ++_finish;
        }
}

/* 拷貝構(gòu)造函數(shù)（更簡(jiǎn)潔的寫(xiě)法） */
vector(const vector<T>& v)
        :_start(nullptr)
        ,_finish(nullptr)
        ,_endofstorage(nullptr)
{
        reserve(v.capacity());        // 直接把空間開(kāi)好，避免增容
        for (const auto& e : v)        // 把 v 的數(shù)據(jù)直接一個(gè)個(gè)push_back進(jìn)去
                push_back(e);
}

/* 賦值重載 */
vector<T>& operator=(const vector<T>& v)
{
        if (this != &v)        // 防止自己賦值給自己
        {
                delete[] _start;
                _start = new T[v.capacity()];
                memcpy(_start, v._start, sizeof(T) * v.size());
                _finish = _start + v.size();
                _endofstorage = _start + v.capacity();
        }
        return *this;
}

/* 賦值重載更簡(jiǎn)潔的寫(xiě)法(現(xiàn)代寫(xiě)法) */
vector<T>& operator=(vector<T> v)
{
        swap(v);
        return *this;
}

/* 深淺拷貝問(wèn)題 */
void test_vector4()
{
        vector<int> v1;
        v1.push_back(1);
        v1.push_back(2);
        v1.push_back(3);
        v1.push_back(4);

        // 如果我們自己沒(méi)有實(shí)現(xiàn)深拷貝的拷貝構(gòu)造，就會(huì)發(fā)生和string類(lèi)一樣的淺拷貝問(wèn)題
        // 兩個(gè)vector對(duì)象的指針指向同一塊空間，最后析構(gòu)時(shí)同一塊空間被重復(fù)釋放，發(fā)生了錯(cuò)誤
        // 所以我們需要自己實(shí)現(xiàn)深拷貝
        vector<int> v2(v1);
        for (size_t i = 0; i < v1.size(); ++i)
        {
                cout << v2[i] << " ";
        }
        cout << endl;

        // 賦值同理
        vector<int> v3;
        v3.push_back(10);
        v3.push_back(20);
        v3.push_back(30);
        v3.push_back(40);

        v1 = v3;
        print_vector(v1);
        for (auto e : v1)
        {
                cout << e << " ";
        }
        cout << endl;
}

void test_vector1()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);

    // 使用迭代器遍歷和修改
    vector<int>::iterator it = v.begin();
    while (it != v.end())
    {
        *it += 1;
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    // 范圍for循環(huán)
    for (auto& e : v)
    {
        e -= 1;
        cout << e << " ";
    }
    cout << endl;

    // 下標(biāo)訪問(wèn)
    for (size_t i = 0; i < v.size(); ++i)
    {
        cout << v[i] << " ";
    }
    cout << endl;
}

void test_vector2()
{
    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);

    v.insert(v.begin(), 0);  // 在開(kāi)頭插入0

    // 刪除所有偶數(shù)
    vector<int>::iterator it = v.begin();
    while (it != v.end())
    {
        if (*it % 2 == 0)
        {
            it = v.erase(it);  // 刪除元素并更新迭代器
        }
        else
        {
            ++it;
        }
    }
}