面试十五容器

一、vector容器

template<typename T>
class Allocator{
public:
    T* allocator(size_t size){
    // 负责内存开辟
        return (T*)malloc(sizeof(T) * size);
    }
    void deallocate(void * p){
        free(p);
    }
    void construct(T*p,const T&val){
        // 定位new
        new (p) T(val);
    }
    void destroy(T*p){
       p->~T();
    }

};


template<typename T, typename Alloc = Allocator<T>>
class vector{
public:
    vector(int size=10){
        //  需要把内存开辟和对象构造分开处理
        //  _first = new T[size];
        _first= _allocator.allocator(size);
        _end = _first + size;
        _last =_first;
    }
    ~vector(){
        //  delete[] _first;
        //  析构容器有效的元素，然后释放_first指针指向的堆内存

        for (T* p = _first; p != _last; ++p){
            _allocator.destroy(p); // 把_first指针指向的数组的有效元素进行析构操作
            }
        _allocator.deallocate(_first); // 释放堆上的数组内存
        _first=_last=_end= nullptr;
    }


    vector(const Vector<T>& src){
        int size = src._last-src._first;
//        _first =new T[size];
        _first = _allocator.allocator(size);
        int len=src._last-src._first;
        for(int i=0;i<len;i++){
//            _first[i]=src._first[i];
            _allocator.construct(_first + i, src._first[i]);
        }
        _last = _first + len;
        _end = _first + size;
    }

    vector<T>& operator=(const vector<T>&src){
        if(this==&src){
            return *this;
        }
//        delete[] _first;
        for (T* p = _first; p != _last; ++p)
        {
            _allocator.destroy(p); // 把_first指针指向的数组的有效元素进行析构操作
        }
        _allocator.deallocate(_first);
        int size = src._end - src._first;
        int len = src._last - src._first;
//        _first = new T[size];
        _first=_allocator.allocate(size);
        for (int i=0; i<len; ++i) {
//            _first[i] = src._first[i];
            _allocator.construct(_first + i, src._first[i]);
        }
        _last = _first + len;
        _end = _first + size;
        return *this;
    }


    void push_back(const T &x) {
        if (full()) {
            resize();
        }
//        *_last ++ = x;
        _allocator.construct(_last, x);
        _last++;
    }
    void pop_back() {
        if (empty()) {
            return;
        }
        _allocator.destroy(_last);
        --_last;
    }

    T back() const {
        if (empty()) {

        }
        return *(_last-1);
    }

    bool full() {
        return _end == _last;
    }

    bool empty() {
        return _last == _first;
    }
    void resize() {
        int size=_end-_first;
//        T *tmp = new T[2*size];
        T* tmp = _allocator.allocator(2 * size);
        int len = _last-_first;
//        for(int i=0; i<len; ++i) {
//            tmp[i] = _first[i];
//        }
//        delete[] _first;
        for (int i = 0; i < size; ++i)
        {
            //ptmp[i] = _first[i];
            _allocator.construct(tmp + i, _first[i]);
        }
        //delete[]_first;
        for (T* p = _first; p != _last; ++p)
        {
            _allocator.destroy(p);
        }
        _allocator.deallocate(_first);
        _first = tmp;
        _end = _first + 2*size;
        _last = _first + len;
    }
    int size() const{
        return _last-_first;
    }
    T& operator[](int index){
        if(index<0 || index>=size()){
            throw "OutOfException";
        }
        return _first[index];
    }

    // 迭代器一般实现成容器的嵌套类型
    class iterator{
    public:
        iterator(T* ptr = nullptr):_ptr(ptr){}
        bool operator !=(const iterator &it) const{
            return _ptr !=it._ptr;
        }
        void operator++(){
            _ptr++;
        }
        T* operator*() {return *_ptr;}
        const T& operator*()const {return  *_ptr;}
    private:
        T* _ptr;
    };

    // 给容器提供begin() 和end()方法
    iterator begin(){return iterator(_first);}
    iterator end(){return iterator(_last);}

    // for each的底层也是iterator

     
private:
    T* _first;
    T* _last;
    T* _end;
    Alloc _allocator; // // 定义容器的空间配置器对象


};


int main() {
    Test t1;
    Test t2;
    vector<Test> vec;
    vec.push_back(t1);
    vec.push_back(t2);
    cout << "===========================" << endl;
    vec.pop_back();
    cout << "===========================" << endl;
    return 0;
}

二、迭代器失效

迭代器失效是指：迭代器的底层其实就是容器的原生指针，插入元素可能导致容器内部的数据结构重新分配，从而使得原先的迭代器指向的位置不再有效；删除元素可能导致迭代器指向的位置被移动或删除，从而使得原先的迭代器不再指向期望的位置。也就是说原来的指针指向的内容被改变了，而不是现在内存中存的。

怎么判断迭代器失效没有：

容器迭代器失效增加代码，它是一个结构体维护了一个链表。cur是指向某一个结构体的指针，又定义了一个指向下一个Iterator_Base节点的地址，还定义了一个头节点。记录了用户从中获取的哪一个元素的迭代器，记录在Iterator_Base链表中，哪一个迭代器增加或删除要让其失效并重新更新。

然后判断链表中的迭代器，看它是否在插入、删除点和_last之间，将会失效，失效的话将迭代器的容器对象赋值为nullptr，再进行 operator != 、 operator++ 、 insert、erase进行操作时候，先判断迭代器是否失效。

    void verify(T* first,T* last){
        Iterator_Base *pre = &this->_head;
        Iterator_Base *it =this->_head._next;
        while(it!= nullptr){
            if(it->_cur->_ptr >first && it->_cur->_ptr <=last){
                it->_cur->_pVec = nullptr;
                pre->_next =it->_next;
                delete it;
                it=pre->_next;
            }else{
                pre=it;
                it=it->_next;
            }
        }
    }

所有代码：

//
// Created by zhangchuang on 2024/4/22.
//

#include <iostream>
using namespace std;
//#include <vector>


template<typename T>
class Allocator{
public:
    T* allocator(size_t size){
        // 负责内存开辟
        return (T*)malloc(sizeof(T) * size);
    }
    void deallocate(void * p){
        free(p);
    }
    void construct(T*p,const T&val){
        // 定位new
        new (p) T(val);
    }
    void destroy(T*p){
        p->~T();
    }

};


template<typename T, typename Alloc = Allocator<T>>
class vector{
public:
    vector(int size=10){
        //  需要把内存开辟和对象构造分开处理
        //  _first = new T[size];
        _first= _allocator.allocator(size);
        _end = _first + size;
        _last =_first;
    }
    ~vector(){
        //  delete[] _first;
        //  析构容器有效的元素，然后释放_first指针指向的堆内存

        for (T* p = _first; p != _last; ++p){
            _allocator.destroy(p); // 把_first指针指向的数组的有效元素进行析构操作
        }
        _allocator.deallocate(_first); // 释放堆上的数组内存
        _first=_last=_end= nullptr;
    }


    vector(const vector<T>& src){
        int size = src._last-src._first;
//        _first =new T[size];
        _first = _allocator.allocator(size);
        int len=src._last-src._first;
        for(int i=0;i<len;i++){
//            _first[i]=src._first[i];
            _allocator.construct(_first + i, src._first[i]);
        }
        _last = _first + len;
        _end = _first + size;
    }

    vector<T>& operator=(const vector<T>&src){
        if(this==&src){
            return *this;
        }
//        delete[] _first;
        for (T* p = _first; p != _last; ++p)
        {
            _allocator.destroy(p); // 把_first指针指向的数组的有效元素进行析构操作
        }
        _allocator.deallocate(_first);
        int size = src._end - src._first;
        int len = src._last - src._first;
//        _first = new T[size];
        _first=_allocator.allocate(size);
        for (int i=0; i<len; ++i) {
//            _first[i] = src._first[i];
            _allocator.construct(_first + i, src._first[i]);
        }
        _last = _first + len;
        _end = _first + size;
        return *this;
    }


    void push_back(const T &x) {
        if (full()) {
            resize();
        }
//        *_last ++ = x;
        _allocator.construct(_last, x);
        _last++;
    }
    void pop_back() {
        if (empty()) {
            return;
        }
        // 验证迭代器是否失效

        verify(_last-1, _last);
        // 如果是erase   验证verify(it._ptr, _last);
        // insert  验证verify(it._ptr, _last);
        _allocator.destroy(_last);
        --_last;
    }

    T back() const {
        if (empty()) {

        }
        return *(_last-1);
    }

    bool full() {
        return _end == _last;
    }

    bool empty() {
        return _last == _first;
    }
    void resize() {
        int size=_end-_first;
//        T *tmp = new T[2*size];
        T* tmp = _allocator.allocator(2 * size);
        int len = _last-_first;
//        for(int i=0; i<len; ++i) {
//            tmp[i] = _first[i];
//        }
//        delete[] _first;
        for (int i = 0; i < size; ++i)
        {
            //ptmp[i] = _first[i];
            _allocator.construct(tmp + i, _first[i]);
        }
        //delete[]_first;
        for (T* p = _first; p != _last; ++p)
        {
            _allocator.destroy(p);
        }
        _allocator.deallocate(_first);
        _first = tmp;
        _end = _first + 2*size;
        _last = _first + len;
    }
    int size() const{
        return _last-_first;
    }
    T& operator[](int index){
        if(index<0 || index>=size()){
            throw "OutOfException";
        }
        return _first[index];
    }

    // 迭代器一般实现成容器的嵌套类型
    class iterator{
    public:

        iterator(vector<T,Alloc>*pvec= nullptr,T* ptr = nullptr):_ptr(ptr),_pVec(pvec){
            Iterator_Base* itb = new Iterator_Base(this,_pVec->_head._next);
            _pVec->_head._next=itb;
        }

        bool operator !=(const iterator &it) const{
            // 检查迭代器的有效性
            if(_pVec == nullptr || _pVec!=it._pVec){
                throw "iterator incompatable!";
                return false;
            }
            return _ptr !=it._ptr;
        }
        void operator++(){
            // 检查迭代器的有效性,迭代器失效为空
            if(_pVec== nullptr){
                throw "iterator invalid";
            }
            _ptr++;
        }
        T* operator*() {return *_ptr;}
        const T& operator*()const {return  *_ptr;}
    private:
        T* _ptr;
        vector<T,Alloc> *_pVec;
    };

    // 给容器提供begin() 和end()方法
    iterator begin(){return iterator(_first);}
    iterator end(){return iterator(_last);}




    // 容器迭代器失效增加代码
    struct Iterator_Base{
        Iterator_Base(iterator *c = nullptr , Iterator_Base *n = nullptr):_cur(c),_next(n){}
        iterator *_cur;
        Iterator_Base *_next;
    };
    Iterator_Base _head;


    void verify(T* first,T* last){
        Iterator_Base *pre = &this->_head;
        Iterator_Base *it =this->_head._next;
        while(it!= nullptr){
            if(it->_cur->_ptr >first && it->_cur->_ptr <=last){
                it->_cur->_pVec = nullptr;
                pre->_next =it->_next;
                delete it;
                it=pre->_next;
            }else{
                pre=it;
                it=it->_next;
            }
        }
    }

    iterator insert(iterator it ,const T &val){
        // 1. 不考虑扩容
        // 2. 不考虑it._ptr的指针合法性
        verify(it._ptr -1 ,_last);
        T* p = _last;
        while(p>it._ptr){
            _allocator.construct(p,*(p-1));
            _allocator.destroy(p-1);
            p--;
        }
        _allocator.construct(p,val);
        _last++;
        return iterator(this,p);
    }

    iterator erase(iterator it ){
        // 1. 不考虑扩容
        // 2. 不考虑it._ptr的指针合法性
        verify(it._ptr -1 ,_last);
        T* p = _last;
        while(p<_last-1){
            _allocator.destroy(p);
            _allocator.construct(p,*(p+1));
            p++;
        }
        _allocator.destroy(p);
        _last--;
        return iterator(this,it._ptr);
    }



    // for each的底层也是iterator



private:
    T* _first;
    T* _last;
    T* _end;
    Alloc _allocator; // // 定义容器的空间配置器对象


};
/*
 vector怎么
 */

#if 0
int main(){
//    std::vector<int>vec{1,2,3,4,5,6,8};

    /*
     迭代器失效问题
     1. 删除元素
    for(auto it =vec.begin();it!=vec.end();it++){
        if(*it%2==0){
            vec.erase(it);
        }
    }
    // 2.增加元素

    for(auto it =vec.begin();it!=vec.end();it++){
        if(*it%2==0){
            vec.insert(it,*it-1);
        }
    }
     */


    // 2。 解决办法 -- 更新迭代器
    // 删除
    auto it =vec.begin();
    while(it!=vec.end()){
        if(*it%2==0){
            it=vec.erase(it);
        }else{
            ++it;
        }
    }

    // 增加
    for(auto it =vec.begin();it!=vec.end();it++){
        if(*it%2==0){
            vec.insert(it,*it-1);
            ++it;
        }
    }



}
#endif