C++ vector 动态数组容器详解与源码实现

拷贝构造函数

利用一个对象初始化另外一个对象传引用 new 出和传递的对象一样大小的空间，在 string 类中我们利用了 mencpy 进行拷贝，在 vector 中不采用 mencpy mencpy 拷贝只能进行内置类型的浅拷贝，不能进行自定义类型的深拷贝 在这里面进行依次赋值，或者 push_back 最后进行_finish 和_endofstorage 的初始化

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

赋值运算符重载

在 operator=的参数中是值传递，是实参的拷贝，这里面利用这个特性进数据的交换

返回 this 指针就是赋值的内容了

void swap(vector<T>& tmp) {
    std::swap(_start, tmp._start);
    std::swap(_finish, tmp._finish);
    std::swap(_endofstorage, tmp._endofstorage);
}
vector<T>& operator=(vector<T> v) {
    swap(v);
    return *this;
}

析构函数

判断_start 是否为空为空，避免再次析构

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

迭代器（iterator）

本质是指针

const_iterator cbegin() { return _finish; }
const_iterator cend() const { return _start; }
iterator begin() { return _start; }
iterator end() { return _finish; }
const_iterator begin()const { return _start; }
const_iterator end()const { return _finish; }

容量（capacity）

capacity

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

size

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

empty

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

resize

n<=capacity 直接进行移动_finish n>capacity 进行容量的检查和扩容，依次赋值 val

void resize(size_t n, T val = T()) {
    if (n <= size()) {
        _finish = _start + n;
    } else {
        reserve(n);
        while (_finish < _start + n) {
            *_finish = val;
            ++_finish;
        }
    }
}

reserve

开始判断需要扩容的大小是否大于 capacity，以避免重复扩容效率低下 在开始时候记录原始空间的大小，是为了避免迭代器失效 进行空间的扩容，会将原来的空间析构，原始的计算空间大小已经已释放，指向的_start_finish_endofstorage 已经失效 这里还是采用在这里面进行依次赋值，或者 push_back 更新_start _finish _endofstorage

void reserve(size_t n) {
    if (n > capacity()) {
        size_t oldSize = size();
        T* tmp = new T[n];
        if (_start) {
            //memcpy(tmp, _start, sizeof(T) * oldSize);
            for (size_t i = 0; i < oldSize; i++) {
                tmp[i] = _start[i];
            }
            delete[]_start;
        }
        _start = tmp;
        _finish = _start + oldSize;
        _endofstorage = _start + n;
    }
}

修改（modify）

push_back

**首先进行容量的检查

直接将_finsih位置解引用赋值，++_finsih**

void push_back(const T& x) {
    if (_finish == _endofstorage) {
        size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newcapacity);
    }
    *_finish = x;
    ++_finish;
}

pop_back

void pop_back() {
    assert(!empty());
    _finish--;
}

insert

进行断言，防止 pos 越界访问 判断空间的大小_finish == _endofstorage size_t len = pos - _start 用 step 记录，距离 _start 距离，扩容的时候将原空间释放，pos 将无法访问，扩容完成后进行 pos 的恢复 将 pos 位置的数据依次进行移动、 插入 pos 位置的值，修改_finish 为了避免迭代器失效，返回现在的位置 pos

iterator insert(iterator pos, const T& x) {
    assert(pos >= _start && pos <= _finish);
    if (_finish == _endofstorage) {
        size_t len = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        pos = _start + len;
    }
    iterator i = _finish - 1;
    while (i >= pos) {
        *(i + 1) = *i;
        --i;
    }
    *pos = x;
    ++_finish;
    return pos;
}

erase

进行断言，防止 pos 越界访问

将 pos 后面的元素向前面移动，进行覆盖

为了避免迭代器失效，返回现在的位置 pos

iterator erase(iterator pos) {
    assert(pos >= _start);
    assert(pos < _finish);
    iterator i = pos + 1;
    while (i < _finish) {
        *(i - 1) = *i;
        ++i;
    }
    _finish--;
    return pos;
}

swap

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

operator[]

实现 const 和 非 const 两种，只读和可读可改

充分利用字符串特性可以进行下标的访问

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

源码

#pragma once
#include<assert.h>
#include<iostream>
using namespace std;

namespace wu {
    template<class T> class vector {
    public:
        typedef T* iterator;
        typedef const T* const_iterator;
        iterator begin() { return _start; }
        iterator end() { return _finish; }
        const_iterator begin() const { return _start; }
        const_iterator end() const { return _finish; }
        vector() {}
        //类模版的成员函数，也可以是一个函数模版
        template<class InputIterator> vector(InputIterator first, InputIterator last) {
            while (first != last) {
                push_back(*first);
                ++first;
            }
        }
        vector(size_t n, const T& val = T()) {
            reserve(n);
            for (size_t i = 0; i < n; i++) {
                push_back(val);
            }
        }
        vector(int n, const T& val = T()) {
            reserve(n);
            for (int i = 0; i < n; i++) {
                push_back(val);
            }
        }
        vector(initializer_list<T> il) {
            reserve(il.size());
            for (auto& e : il) {
                push_back(e);
            }
        }
        vector(const vector<T>& v) {
            reserve(v.capacity());
            for (auto& e : v) {
                push_back(e);
            }
        }
        void swap(vector<T>& tmp) {
            std::swap(_start, tmp._start);
            std::swap(_finish, tmp._finish);
            std::swap(_endofstorage, tmp._endofstorage);
        }
        vector<T>& operator=(vector<T> v) {
            swap(v);
            return *this;
        }
        ~vector() {
            if (_start) {
                delete[]_start;
                _start = _finish = _endofstorage = nullptr;
            }
        }
        T& operator[](size_t i) {
            assert(i < size());
            return _start[i];
        }
        size_t size() const { return _finish - _start; }
        size_t capacity() const { return _endofstorage - _start; }
        void reserve(size_t n) {
            if (n > capacity()) {
                size_t oldSize = size();
                T* tmp = new T[n];
                if (_start) {
                    //memcpy(tmp, _start, sizeof(T) * size());
                    for (size_t i = 0; i < oldSize; i++) {
                        tmp[i] = _start[i];
                    }
                    delete[]_start;
                }
                _start = tmp;
                _finish = _start + oldSize;
                _endofstorage = _start + n;
            }
        }
        void resize(size_t n, T val = T()) {
            if (n <= size()) {
                _finish = _start + n;
            } else {
                reserve(n);
                while (_finish < _start + n) {
                    *_finish = val;
                    ++_finish;
                }
            }
        }
        void push_back(const T& x) {
            insert(_finish, x);
        }
        bool empty() { return _start == _finish; }
        void pop_back() {
            assert(!empty());
            _finish--;
        }
        iterator insert(iterator pos, const T& x) {
            assert(pos >= _start && pos <= _finish);
            if (_finish == _endofstorage) {
                size_t len = pos - _start;
                reserve(capacity() == 0 ? 4 : capacity() * 2);
                pos = _start + len;
            }
            iterator i = _finish - 1;
            while (i >= pos) {
                *(i + 1) = *i;
                --i;
            }
            *pos = x;
            ++_finish;
            return pos;
        }
        iterator erase(iterator pos) {
            assert(pos >= _start);
            assert(pos < _finish);
            iterator i = pos + 1;
            while (i < _finish) {
                *(i - 1) = *i;
                ++i;
            }
            _finish--;
            return pos;
        }
    private:
        iterator _start = nullptr;
        iterator _finish = nullptr;
        iterator _endofstorage = nullptr;
    };
}